Details

    • Type: New Feature New Feature
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.1
    • Component/s: None
    • Labels:
      None

      Description

      We need matrices for Mahout.

      An initial set of basic requirements includes:

      a) sparse and dense support are required

      b) row and column labels are important

      c) serialization for hadoop use is required

      d) reasonable floating point performance is required, but awesome FP is not

      e) the API should be simple enough to understand

      f) it should be easy to carve out sub-matrices for sending to different reducers

      g) a reasonable set of matrix operations should be supported, these should eventually include:
      simple matrix-matrix and matrix-vector and matrix-scalar linear algebra operations, A B, A + B, A v, A + x, v + x, u + v, dot(u, v)
      row and column sums
      generalized level 2 and 3 BLAS primitives, alpha A B + beta C and A u + beta v

      h) easy and efficient iteration constructs, especially for sparse matrices

      i) easy to extend with new implementations

      1. MAHOUT-6l.patch
        192 kB
        Grant Ingersoll
      2. MAHOUT-6k.diff
        182 kB
        Jeff Eastman
      3. MAHOUT-6j.diff
        184 kB
        Jeff Eastman
      4. MAHOUT-6i.diff
        149 kB
        Jeff Eastman
      5. MAHOUT-6h.patch
        51 kB
        Grant Ingersoll
      6. MAHOUT-6g.diff
        45 kB
        Jeff Eastman
      7. MAHOUT-6f.diff
        69 kB
        Jeff Eastman
      8. MAHOUT-6e.diff
        54 kB
        Jeff Eastman
      9. MAHOUT-6d.diff
        50 kB
        Jeff Eastman
      10. MAHOUT-6c.diff
        41 kB
        Jeff Eastman
      11. MAHOUT-6b.diff
        32 kB
        Jeff Eastman
      12. MAHOUT-6a.diff
        18 kB
        Jeff Eastman

        Issue Links

          Activity

          Hide
          Ted Dunning added a comment -

          My own, non-portable, non-releasable matrix package uses a class structure something like Colt, but with a simpler extension structure:

          interface Matrix1D – the basic interface including numerous convenience functions

          abstract class AbstractMatrix1D implements Matrix1D – implementations of generic capabilities like sum of elements and dot products

          class DenseMatrix1D extends AbstractMatrix1D – implements vector as an array of doubles with an offset and stride. used for vectors and views of sub-vectors and row or column views of dense matrices.

          class SparseBinaryVector extends AbstractMatrix1D – implements vector that only "stores" 0 or 1, but only stores the 1's, but doesn't store them because it knows what their value is. This is really a bit-vector implemented as a closed hash table that only holds integers.

          class SparseDoubleVector extends AbstractMatrix1D – implements vector that only stores non-zero doubles

          interface Matrix2D – the basic interface including convenience functions

          abstract class AbstractMatrix2D implements Matrix1D – a few universal implementations of convenience functions mostly in terms of BLAS ops

          abstract class AbstractSparseMatrix2D extends AbstractMatrix2D – efficient implementations of BLAS ops for generic sparse matrices

          abstract class AbstractDenseMatrix2D extends AbstractMatrix2D – reasonably efficient implementations of BLAS ops for dense matrices

          class DenseMatrix2D extends ADM2D – matrix of doubles implemented using a single 1D array with generic stride and offset. Also used to hold transposed views and some kinds of sub-matrix views.

          class DoublyIndexedSparseBinary2D – sparse matrix whose non-zero elements are all 1. Fast row and column views are available through redundant storage.

          class SparseRowDouble2D – sparse matrix with general element values whose rows are accessible quickly. Implemented as an array of SparseDouble1D vectors.

          class SparseColumnDouble2D – sparse matrix with general elements values whose columns are accessible quickly.

          Functions — Matrices support updates using functional objects so that generic in-place updates can be done very efficiently. I stole this idea from Colt. In fact, my matrix package uses the Colt Functions object for my own matrix implementations which is one reason I can't distribute my own matrices very easily.

          Any comments on this general structure? For machine learning, I have had very little call for complex numbers. Some might take issue with my assumption that float's pretty much just don't exist, but for large problems, I find it imperative to retain precision more than save memory.

          Show
          Ted Dunning added a comment - My own, non-portable, non-releasable matrix package uses a class structure something like Colt, but with a simpler extension structure: interface Matrix1D – the basic interface including numerous convenience functions abstract class AbstractMatrix1D implements Matrix1D – implementations of generic capabilities like sum of elements and dot products class DenseMatrix1D extends AbstractMatrix1D – implements vector as an array of doubles with an offset and stride. used for vectors and views of sub-vectors and row or column views of dense matrices. class SparseBinaryVector extends AbstractMatrix1D – implements vector that only "stores" 0 or 1, but only stores the 1's, but doesn't store them because it knows what their value is. This is really a bit-vector implemented as a closed hash table that only holds integers. class SparseDoubleVector extends AbstractMatrix1D – implements vector that only stores non-zero doubles interface Matrix2D – the basic interface including convenience functions abstract class AbstractMatrix2D implements Matrix1D – a few universal implementations of convenience functions mostly in terms of BLAS ops abstract class AbstractSparseMatrix2D extends AbstractMatrix2D – efficient implementations of BLAS ops for generic sparse matrices abstract class AbstractDenseMatrix2D extends AbstractMatrix2D – reasonably efficient implementations of BLAS ops for dense matrices class DenseMatrix2D extends ADM2D – matrix of doubles implemented using a single 1D array with generic stride and offset. Also used to hold transposed views and some kinds of sub-matrix views. class DoublyIndexedSparseBinary2D – sparse matrix whose non-zero elements are all 1. Fast row and column views are available through redundant storage. class SparseRowDouble2D – sparse matrix with general element values whose rows are accessible quickly. Implemented as an array of SparseDouble1D vectors. class SparseColumnDouble2D – sparse matrix with general elements values whose columns are accessible quickly. Functions — Matrices support updates using functional objects so that generic in-place updates can be done very efficiently. I stole this idea from Colt. In fact, my matrix package uses the Colt Functions object for my own matrix implementations which is one reason I can't distribute my own matrices very easily. Any comments on this general structure? For machine learning, I have had very little call for complex numbers. Some might take issue with my assumption that float's pretty much just don't exist, but for large problems, I find it imperative to retain precision more than save memory.
          Hide
          Jeff Eastman added a comment -

          +1, assuming you can come up with stories for all the leaves<grin>, the overall structure looks quite reasonable. I could probably start filling out a couple of the Matrix1D operations for clustering. Do you have any operations in mind for the interfaces?

          Show
          Jeff Eastman added a comment - +1, assuming you can come up with stories for all the leaves<grin>, the overall structure looks quite reasonable. I could probably start filling out a couple of the Matrix1D operations for clustering. Do you have any operations in mind for the interfaces?
          Hide
          Ted Dunning added a comment -

          Here is my set of methods for Matrix1D. These are nearly identical to the functions used by Colt with the addition of some convenience methods.

          double get(int index);
          void set(int index, double value);
          Matrix1D plus(double x);
          Matrix1D plus(Matrix1D x);
          Matrix1D minus(Matrix1D x);
          Matrix1D times(double x);
          // should this be element-wise or dot ... I think element-wise
          Matrix1D times(Matrix1D x);
          double dot(Matrix1D x);
          double zSum();

          Matrix1D viewPart(int offset, int length);
          Matrix1D copy();

          double getQuick(int index);
          void setQuick(int index, double value);

          void getNonZeros(IntArrayList jx, DoubleArrayList values);
          void foreachNonZero(IntDoubleFunction f);

          int size();
          int cardinality();

          double aggregate(DoubleDoubleFunction aggregator, DoubleFunction map);
          double aggregate(Matrix1D other, DoubleDoubleFunction aggregator, DoubleDoubleFunction map);

          Matrix1D assign(double[] values);
          Matrix1D assign(double value);
          Matrix1D assign(DoubleFunction function);
          Matrix1D assign(Matrix1D other);
          Matrix1D assign(Matrix1D y, DoubleDoubleFunction function);
          NewMatrix1D assign(Matrix1D y, DoubleDoubleFunction function, IntArrayList nonZeroIndexes);

          boolean haveSharedCells(Matrix1D other);

          Matrix1D like();
          Matrix1D like(int n);

          double[] toArray();

          Show
          Ted Dunning added a comment - Here is my set of methods for Matrix1D. These are nearly identical to the functions used by Colt with the addition of some convenience methods. double get(int index); void set(int index, double value); Matrix1D plus(double x); Matrix1D plus(Matrix1D x); Matrix1D minus(Matrix1D x); Matrix1D times(double x); // should this be element-wise or dot ... I think element-wise Matrix1D times(Matrix1D x); double dot(Matrix1D x); double zSum(); Matrix1D viewPart(int offset, int length); Matrix1D copy(); double getQuick(int index); void setQuick(int index, double value); void getNonZeros(IntArrayList jx, DoubleArrayList values); void foreachNonZero(IntDoubleFunction f); int size(); int cardinality(); double aggregate(DoubleDoubleFunction aggregator, DoubleFunction map); double aggregate(Matrix1D other, DoubleDoubleFunction aggregator, DoubleDoubleFunction map); Matrix1D assign(double[] values); Matrix1D assign(double value); Matrix1D assign(DoubleFunction function); Matrix1D assign(Matrix1D other); Matrix1D assign(Matrix1D y, DoubleDoubleFunction function); NewMatrix1D assign(Matrix1D y, DoubleDoubleFunction function, IntArrayList nonZeroIndexes); boolean haveSharedCells(Matrix1D other); Matrix1D like(); Matrix1D like(int n); double[] toArray();
          Hide
          Ted Dunning added a comment -

          The different matrix API's have differed on this.

          The goal to have easy extensibility implies that either these operations happen in one of the abstract classes or that they live in a different place.

          Many of these algorithms take the form of a matrix implementation. For instance, all of the factorizations like eigenvector or singular vector or QR or LU decomposition are nominally a matrix that has internal parts which are useful sometimes in their own right (eigenvalues) or which facilitate some common operation (back-sub in LU, least squares for QR). For all of them, however, you can do multiplications and additions and such (just not destructive mult and add).

          As such, the approach of having special matrix types that are actually decompositions is pretty attractive. The destructive ops can throw unimplemented operation exceptions (which is the default at the highest abstract matrix level anyway) and they can add some additional API elements for their special capabilities. Whether constructors or factor methods are better is an open question in my mind.

          On 2/22/08 6:38 AM, "Grant Ingersoll" <gsingers@apache.org> wrote:

          > Any thoughts about where support belongs for things like calculating
          > eigenvalues/vectors and/or *Rank algorithms that rely on an iterative
          > operations on a matrix/graph, etc.? Seems like they can be
          > generalized, but not sure if they are first class citizens on a Matrix
          > implementation or not.

          Show
          Ted Dunning added a comment - The different matrix API's have differed on this. The goal to have easy extensibility implies that either these operations happen in one of the abstract classes or that they live in a different place. Many of these algorithms take the form of a matrix implementation. For instance, all of the factorizations like eigenvector or singular vector or QR or LU decomposition are nominally a matrix that has internal parts which are useful sometimes in their own right (eigenvalues) or which facilitate some common operation (back-sub in LU, least squares for QR). For all of them, however, you can do multiplications and additions and such (just not destructive mult and add). As such, the approach of having special matrix types that are actually decompositions is pretty attractive. The destructive ops can throw unimplemented operation exceptions (which is the default at the highest abstract matrix level anyway) and they can add some additional API elements for their special capabilities. Whether constructors or factor methods are better is an open question in my mind. On 2/22/08 6:38 AM, "Grant Ingersoll" <gsingers@apache.org> wrote: > Any thoughts about where support belongs for things like calculating > eigenvalues/vectors and/or *Rank algorithms that rely on an iterative > operations on a matrix/graph, etc.? Seems like they can be > generalized, but not sure if they are first class citizens on a Matrix > implementation or not.
          Hide
          Jeff Eastman added a comment -

          Here's a minimal implementation of Matrix1D methods and tests that will be adequate to replace Point and Float[] in the clustering code. I did not implement all of Ted's suggestions as I did not understand them and/or there were missing classes. There are a couple of issues it raises:

          • I made all the methods side-effect free, returning new instances from all operations. This will exercise the garbage collector but eliminate difficult debugging problems. It also seems consistent with the functional programming roots of map/reduce.
          • I implemented no checking of cardinality sameness or division by zero so these are needed. The question in my mind is whether to use checked exceptions or runtime exceptions. There really is no valid use case I can think of for the former but I await comments before acting.
          • I added divide(), normalize(), asFormatString() and a decodeFormat static which are needed by clustering

          I will wait until MAHOOT-5 gets committed before beginning the refactoring since it will be a major change from the latest working patch and it really needs this stuff in trunk too before beginning.

          Show
          Jeff Eastman added a comment - Here's a minimal implementation of Matrix1D methods and tests that will be adequate to replace Point and Float[] in the clustering code. I did not implement all of Ted's suggestions as I did not understand them and/or there were missing classes. There are a couple of issues it raises: I made all the methods side-effect free, returning new instances from all operations. This will exercise the garbage collector but eliminate difficult debugging problems. It also seems consistent with the functional programming roots of map/reduce. I implemented no checking of cardinality sameness or division by zero so these are needed. The question in my mind is whether to use checked exceptions or runtime exceptions. There really is no valid use case I can think of for the former but I await comments before acting. I added divide(), normalize(), asFormatString() and a decodeFormat static which are needed by clustering I will wait until MAHOOT-5 gets committed before beginning the refactoring since it will be a major change from the latest working patch and it really needs this stuff in trunk too before beginning.
          Hide
          Paul Elschot added a comment -

          I had a quick look at the latest patch, the 6b.diff.
          It looks good, but I see one possible issue in there: the use of java interfaces.
          The problem with interfaces is that once they are implemented somewhere outside of a code base, there is no way to change them inside that code base without breaking something outside. In other words, public interfaces are forever, and it may be a bit too soon for that.
          So the question is whether it would be better to use public abstract classes instead of public interfaces.

          Also I'd like to have a sparse 2D matrix implementation on top of a Lucene index with term vectors, but that appears to be no problem, and it's better handled as another issue.
          It's related to labeling rows and columns though. Lucene docs could be labeled by a primary key value, and lucene features could be labeled by their term values, possibly combined with the term field. (Roughly, in Lucene, a document consists of several fields, each field having indexed terms. A term vector in Lucene consists of all the term values and frequencies for a field of a document.)

          Show
          Paul Elschot added a comment - I had a quick look at the latest patch, the 6b.diff. It looks good, but I see one possible issue in there: the use of java interfaces. The problem with interfaces is that once they are implemented somewhere outside of a code base, there is no way to change them inside that code base without breaking something outside. In other words, public interfaces are forever, and it may be a bit too soon for that. So the question is whether it would be better to use public abstract classes instead of public interfaces. Also I'd like to have a sparse 2D matrix implementation on top of a Lucene index with term vectors, but that appears to be no problem, and it's better handled as another issue. It's related to labeling rows and columns though. Lucene docs could be labeled by a primary key value, and lucene features could be labeled by their term values, possibly combined with the term field. (Roughly, in Lucene, a document consists of several fields, each field having indexed terms. A term vector in Lucene consists of all the term values and frequencies for a field of a document.)
          Hide
          Ted Dunning added a comment -

          Paul,

          Can you amplify a bit on how you see the difference between interfaces and abstract classes?

          It is absolutely true that interfaces can only be changed delicately, but at this stage I think that everybody understands that. But why is a public abstract class any different?

          I should also say that the interface is definitely incomplete as it says nothing about labeling of rows and columns, nor does it have any way to find out if a matrix is sparse, nor whether a sparse matrix has fast column or row viewing. All are pretty important, but all are additions to this API, rather than changes.

          Finally, I have a little problem in viewing a lucene index itself as a single matrix. I would propose an interface in which a lucene index is a factory which constructs matrices that are linear combinations of fields of the lucene matrix. There should also be some way to view the native retrieval operation of the lucene index as matrix multiplication.

          Show
          Ted Dunning added a comment - Paul, Can you amplify a bit on how you see the difference between interfaces and abstract classes? It is absolutely true that interfaces can only be changed delicately, but at this stage I think that everybody understands that. But why is a public abstract class any different? I should also say that the interface is definitely incomplete as it says nothing about labeling of rows and columns, nor does it have any way to find out if a matrix is sparse, nor whether a sparse matrix has fast column or row viewing. All are pretty important, but all are additions to this API, rather than changes. Finally, I have a little problem in viewing a lucene index itself as a single matrix. I would propose an interface in which a lucene index is a factory which constructs matrices that are linear combinations of fields of the lucene matrix. There should also be some way to view the native retrieval operation of the lucene index as matrix multiplication.
          Show
          Ted Dunning added a comment - See https://issues.apache.org/jira/browse/MAHOUT-7
          Hide
          Paul Elschot added a comment -

          Ted,

          An abstract class differs from an interface in that one can easily:

          • add a public method with a default implementation, and
          • deprecate a method.

          See also (but not only):
          http://faq.javaranch.com/java/InterfaceVsAbstractClass
          This mentions a.o.:

          • use an interface if you're sure the API is stable for the long run

          And thanks for opening MAHOUT-7.

          Show
          Paul Elschot added a comment - Ted, An abstract class differs from an interface in that one can easily: add a public method with a default implementation, and deprecate a method. See also (but not only): http://faq.javaranch.com/java/InterfaceVsAbstractClass This mentions a.o.: use an interface if you're sure the API is stable for the long run And thanks for opening MAHOUT-7 .
          Hide
          Ted Dunning added a comment -

          Regarding the 6b diff, the intent of the view functions is to return a reference to the same underlying storage so that in place updates of parts of a matrix or vector can be done. This is actually pretty important for performance in some cases and it pretty massively simplifies the API.

          This means that it is much simpler for the Dense1D implementation to have a reference to a double[], an offset and a stride. That means that views are easy. Likewise, the Dense2D implementation should have a reference to a double[], an offset and a column and row stride. This allows many views such as transpose, diagonals, rows and columns to allow be really simple. It also allows column or row major memory layout (if we ever get to the point we care that much). You can even handle banded matrices pretty well with this layout, although you need a teensy bit of logic to make sure that out-of-band references return zeros.

          The purpose, btw, of the get/set Quick methods is that if there is some sort of size checking (as there really has to be since array bounds checking won't necessary catch out of range references in views), then the quick alternatives can be used to avoid the checks. This allows the range checks to be factored out of some inner loops with obvious benefit in any case where the compiler is less than genius level.

          Show
          Ted Dunning added a comment - Regarding the 6b diff, the intent of the view functions is to return a reference to the same underlying storage so that in place updates of parts of a matrix or vector can be done. This is actually pretty important for performance in some cases and it pretty massively simplifies the API. This means that it is much simpler for the Dense1D implementation to have a reference to a double[], an offset and a stride. That means that views are easy. Likewise, the Dense2D implementation should have a reference to a double[], an offset and a column and row stride. This allows many views such as transpose, diagonals, rows and columns to allow be really simple. It also allows column or row major memory layout (if we ever get to the point we care that much). You can even handle banded matrices pretty well with this layout, although you need a teensy bit of logic to make sure that out-of-band references return zeros. The purpose, btw, of the get/set Quick methods is that if there is some sort of size checking (as there really has to be since array bounds checking won't necessary catch out of range references in views), then the quick alternatives can be used to avoid the checks. This allows the range checks to be factored out of some inner loops with obvious benefit in any case where the compiler is less than genius level.
          Hide
          Ted Dunning added a comment -

          Regarding Paul's comments about interfaces versus abstract classes, I prefer to use interfaces here, but provide abstract classes that most people will inherit from.

          In that case, updates to the interface come (mostly) in two flavors:

          a) convenience updates that can easily be implemented in the abstract classes. Very few implementors will be hurt here because they won't even notice that their classes suddenly have new functionality.

          b) substantial and important functionality that was overlooked at first. Changing the interface has the desired effect of forcing implementors to support this functionality. If the functionality isn't required of all implementations, then it can be declared in the abstract with gives the desired effect.

          Show
          Ted Dunning added a comment - Regarding Paul's comments about interfaces versus abstract classes, I prefer to use interfaces here, but provide abstract classes that most people will inherit from. In that case, updates to the interface come (mostly) in two flavors: a) convenience updates that can easily be implemented in the abstract classes. Very few implementors will be hurt here because they won't even notice that their classes suddenly have new functionality. b) substantial and important functionality that was overlooked at first. Changing the interface has the desired effect of forcing implementors to support this functionality. If the functionality isn't required of all implementations, then it can be declared in the abstract with gives the desired effect.
          Hide
          Jeff Eastman added a comment -

          On the point about interfaces, the current diff has both interfaces and abstract classes. I understand the brittleness that interfaces can introduce and have seen recent comments about challenges introduced by their evolution on the Hadoop list. I suggest we retain both artifacts for now while we are in a pre-release phase and continue this discussion. It would be a little work to remove the interfaces later but I do not see a reason to remove them now.

          On the view functions, I can see their value but not yet their explicit need in any submitted algorithms. Following agile practices, I would suggest tabling their implementation until such an explicit need does materialize. I do think the question of side-effects I raised earlier will be affected by any sharing of underlying data structures and invite further discussion thereof.

          On the fast methods that avoid the range checking that is currently missing, do we want to introduce checked exceptions or use runtime exceptions? I do not see any reasonable use case where recovery from such a condition would be a common practice. OTOH, introducing checked exceptions on the current methods and not having them on the fast methods would certainly make the difference between the methods more apparent.

          Show
          Jeff Eastman added a comment - On the point about interfaces, the current diff has both interfaces and abstract classes. I understand the brittleness that interfaces can introduce and have seen recent comments about challenges introduced by their evolution on the Hadoop list. I suggest we retain both artifacts for now while we are in a pre-release phase and continue this discussion. It would be a little work to remove the interfaces later but I do not see a reason to remove them now. On the view functions, I can see their value but not yet their explicit need in any submitted algorithms. Following agile practices, I would suggest tabling their implementation until such an explicit need does materialize. I do think the question of side-effects I raised earlier will be affected by any sharing of underlying data structures and invite further discussion thereof. On the fast methods that avoid the range checking that is currently missing, do we want to introduce checked exceptions or use runtime exceptions? I do not see any reasonable use case where recovery from such a condition would be a common practice. OTOH, introducing checked exceptions on the current methods and not having them on the fast methods would certainly make the difference between the methods more apparent.
          Hide
          Jeff Eastman added a comment -

          Well, here's a story that suggests using checked exceptions would be valuable:

          User is processing large volumes of vector data that contain some encoding errors causing some input vectors to be too small. User wishes to detect these conditions in order to be able to omit the records without aborting the computation.

          Show
          Jeff Eastman added a comment - Well, here's a story that suggests using checked exceptions would be valuable: User is processing large volumes of vector data that contain some encoding errors causing some input vectors to be too small. User wishes to detect these conditions in order to be able to omit the records without aborting the computation.
          Hide
          Jeff Eastman added a comment -

          Based upon my above story I decided to add checked exceptions to the Matrix1D interface. Needing some more efficient operations to avoid the bounds checking in the inner loops, I implemented the Quick operations too, as well as zSum(). Comments on my name choices (and Ted's too) are always fair game.

          I'm still being lazy about the view operations while we discuss side-effects.

          All unit tests run.

          Show
          Jeff Eastman added a comment - Based upon my above story I decided to add checked exceptions to the Matrix1D interface. Needing some more efficient operations to avoid the bounds checking in the inner loops, I implemented the Quick operations too, as well as zSum(). Comments on my name choices (and Ted's too) are always fair game. I'm still being lazy about the view operations while we discuss side-effects. All unit tests run.
          Hide
          Ted Dunning added a comment -

          Btw, the easiest Mahout user story for views is parallel multiplication (= coocurrence counting).

          To multiply A' * B, one way is to reduce on columns of A modulo some number that is about 2-5x the number of reducers which should about the number of cores to be used. The map would emit copies of B, one for each reduce key. Then it should emit columns of A keyed by the column number modulo the reduce key count.

          It is highly desirable to:

          a) not write a special serializer for columns of a matrix ... the serializer for vectors should do.

          b) not copy columns of A before serializer.

          Column views give us what we need. By symmetry, we should have row views, of course. Also, if you have the machinery for row and column views, sub-matrix views are trivial additions.

          Views can be done many ways. One way is with a view wrapper, and this can be used at the abstract matrix level to get views for free for new implementations. For many kinds of matrix, it is desirable to have a special purpose view to avoid the wrapper overhead. Dense matrices based on strided access to an array of values, for instance, can support views with no additional mechanism and without any appreciable overhead other than memory locality issues. Most sparse representations can provide either row or column views very cheaply as well.

          Show
          Ted Dunning added a comment - Btw, the easiest Mahout user story for views is parallel multiplication (= coocurrence counting). To multiply A' * B, one way is to reduce on columns of A modulo some number that is about 2-5x the number of reducers which should about the number of cores to be used. The map would emit copies of B, one for each reduce key. Then it should emit columns of A keyed by the column number modulo the reduce key count. It is highly desirable to: a) not write a special serializer for columns of a matrix ... the serializer for vectors should do. b) not copy columns of A before serializer. Column views give us what we need. By symmetry, we should have row views, of course. Also, if you have the machinery for row and column views, sub-matrix views are trivial additions. Views can be done many ways. One way is with a view wrapper, and this can be used at the abstract matrix level to get views for free for new implementations. For many kinds of matrix, it is desirable to have a special purpose view to avoid the wrapper overhead. Dense matrices based on strided access to an array of values, for instance, can support views with no additional mechanism and without any appreciable overhead other than memory locality issues. Most sparse representations can provide either row or column views very cheaply as well.
          Hide
          Jeff Eastman added a comment -

          This patch adds a Matrix1DView wrapper and tests thereof. In order to avoid side effects, calling the setQuick method throws an UnsupportedOperationException and copy materializes a new DenseMatrix1D, not another view. This is consistent with the read-onliness of most view abstractions and allows all of the abstract matrix operations to work. Views can be made of any MatrixID, and this includes views of views, which share the same underlying Matrix1D.

          Am I too hung-up on no side-effects?

          Show
          Jeff Eastman added a comment - This patch adds a Matrix1DView wrapper and tests thereof. In order to avoid side effects, calling the setQuick method throws an UnsupportedOperationException and copy materializes a new DenseMatrix1D, not another view. This is consistent with the read-onliness of most view abstractions and allows all of the abstract matrix operations to work. Views can be made of any MatrixID, and this includes views of views, which share the same underlying Matrix1D. Am I too hung-up on no side-effects?
          Hide
          Ted Dunning added a comment -

          Yes, you are too hung up on no side-effects!

          Ability to do destructive operations via views is critical to almost any decomposition algorithm (QR, LU, Lanczos).

          The author of Colt made a persuasive case that mutation by views was critical for performance without a HUGE api. Take for instance, the common operation of zero-ing out a column. With a Colt style (mutable view) API, this is done as:

          A.viewColumn.assign(0)

          Zeroing out a row is done this way:

          A.viewRow.assign(0)

          But what about adding a vector to a particular row?

          A.viewRow.assign(v, Function.plus)

          Or zeroing out a sub-matrix:

          A.viewBlock(tl, br, width, height).assign(0).

          IF you don't have these mutable views one of two things happens.

          Either:

          • the programmer calls set a LOT resulting in really, really slow code that the optimizer can't handle,

          Or

          • the API becomes (literally) exponentially larger because every common mutation such as setting to zero, incrementing by a constant, adding a vector and so on gets multiplied by the number of kinds of pieces that you want to work on. In fact, it is a good idea to factor out the kind of mutation as well, just as Colt does.

          On 2/25/08 5:47 PM, "Jeff Eastman (JIRA)" <jira@apache.org> wrote:

          > Am I too hung-up on no side-effects?

          Show
          Ted Dunning added a comment - Yes, you are too hung up on no side-effects! Ability to do destructive operations via views is critical to almost any decomposition algorithm (QR, LU, Lanczos). The author of Colt made a persuasive case that mutation by views was critical for performance without a HUGE api. Take for instance, the common operation of zero-ing out a column. With a Colt style (mutable view) API, this is done as: A.viewColumn .assign(0) Zeroing out a row is done this way: A.viewRow .assign(0) But what about adding a vector to a particular row? A.viewRow .assign(v, Function.plus) Or zeroing out a sub-matrix: A.viewBlock(tl, br, width, height).assign(0). IF you don't have these mutable views one of two things happens. Either: the programmer calls set a LOT resulting in really, really slow code that the optimizer can't handle, Or the API becomes (literally) exponentially larger because every common mutation such as setting to zero, incrementing by a constant, adding a vector and so on gets multiplied by the number of kinds of pieces that you want to work on. In fact, it is a good idea to factor out the kind of mutation as well, just as Colt does. On 2/25/08 5:47 PM, "Jeff Eastman (JIRA)" <jira@apache.org> wrote: > Am I too hung-up on no side-effects?
          Hide
          Jeff Eastman added a comment -

          Ok, I get the case for side-effects. It is a line to be crossed with eyes open and this diff does just that. In addition to semantic changes in copy, setQuick and viewPart I've implemented the assign operations (and unit tests too).

          Show
          Jeff Eastman added a comment - Ok, I get the case for side-effects. It is a line to be crossed with eyes open and this diff does just that. In addition to semantic changes in copy, setQuick and viewPart I've implemented the assign operations (and unit tests too).
          Hide
          Jeff Eastman added a comment -

          Here's another patch with like() and haveSharedCells() implemented and tested. I also implemented an initial SparseDoubleVector using a Map<Integer, Double> and tests for it. It uses a HashMap, is that ok with you?

          Could you provide some more insight into the remaining functions? The SparseBinaryVector seems pretty special purpose and I imagine you have a proposal for its implementation. Could you please discribe that?

          Both of these vector classes beg the question of why DenseMatrix1D is not called DenseVector instead. Comments?

          Show
          Jeff Eastman added a comment - Here's another patch with like() and haveSharedCells() implemented and tested. I also implemented an initial SparseDoubleVector using a Map<Integer, Double> and tests for it. It uses a HashMap, is that ok with you? Could you provide some more insight into the remaining functions? The SparseBinaryVector seems pretty special purpose and I imagine you have a proposal for its implementation. Could you please discribe that? Both of these vector classes beg the question of why DenseMatrix1D is not called DenseVector instead. Comments?
          Hide
          Ted Dunning added a comment -

          A hash map is a great first implementation for a sparse vector. Ultimately,
          it will need to be replaced, but delaying that day is a good thing. Also, a
          really efficient structure is a pain in the ass to get exactly right. The
          hash map you have will work right off the bat.

          The primary use of SparseBinaryVector is as a row or column of a
          SparseBinaryMatrix. A binary matrix is useful in cases where reduction to
          binary values makes sense (many behavioral analysis cases are good for that,
          as are many text analysis cases). It only makes sense, however, when there
          is beginning to be serious memory pressure since its virtue is that you save
          8 bytes per value. That can be 2/3 of the storage of some matrices. For
          some of my key programs, I need fast row and column access to very lare
          binary matrices and getting 3x larger matrices to fit in memory (and buying
          more memory) really helped.

          I used Matrix1D out of inertia from Colt. The only virtue to the notation
          is that it makes sense to go eventually to Matrix3D and Matrix4D, but the
          vector terminology is so well known that I wouldn't think it a problem.
          Nobody is ever going to be confused. Some purists might object that a
          vector is an object from linear algebra whereas what we have is a
          single-indexed array with a few linear algebra operations tacked on. I am
          not a purist.

          Show
          Ted Dunning added a comment - A hash map is a great first implementation for a sparse vector. Ultimately, it will need to be replaced, but delaying that day is a good thing. Also, a really efficient structure is a pain in the ass to get exactly right. The hash map you have will work right off the bat. The primary use of SparseBinaryVector is as a row or column of a SparseBinaryMatrix. A binary matrix is useful in cases where reduction to binary values makes sense (many behavioral analysis cases are good for that, as are many text analysis cases). It only makes sense, however, when there is beginning to be serious memory pressure since its virtue is that you save 8 bytes per value. That can be 2/3 of the storage of some matrices. For some of my key programs, I need fast row and column access to very lare binary matrices and getting 3x larger matrices to fit in memory (and buying more memory) really helped. I used Matrix1D out of inertia from Colt. The only virtue to the notation is that it makes sense to go eventually to Matrix3D and Matrix4D, but the vector terminology is so well known that I wouldn't think it a problem. Nobody is ever going to be confused. Some purists might object that a vector is an object from linear algebra whereas what we have is a single-indexed array with a few linear algebra operations tacked on. I am not a purist.
          Hide
          Jeff Eastman added a comment -
          • Renamed Matrix1D to Vector and Matrix2D to Matrix, in all interfaces and classes where they occurred
          • Removed Double (typename) from all artifacts
          • Moved all Vector artifacts into a new utils.vector package.
          • Implemented UnaryFunction and BinaryFunction interfaces
          • Implemented Negate and Plus functions for unit tests
          • Moved all function artifacts into a new utils.function package
          • Moved the two exceptions to utils
          • Implemented assign operations on functions and unit tests for all concrete classes
          • Removed the DenseBinaryVector for now until we converge on generics or not

          All unit tests run.

          It looks pretty clean now, for Vector at least. Time to start thinking about Matrix.

          Show
          Jeff Eastman added a comment - Renamed Matrix1D to Vector and Matrix2D to Matrix, in all interfaces and classes where they occurred Removed Double (typename) from all artifacts Moved all Vector artifacts into a new utils.vector package. Implemented UnaryFunction and BinaryFunction interfaces Implemented Negate and Plus functions for unit tests Moved all function artifacts into a new utils.function package Moved the two exceptions to utils Implemented assign operations on functions and unit tests for all concrete classes Removed the DenseBinaryVector for now until we converge on generics or not All unit tests run. It looks pretty clean now, for Vector at least. Time to start thinking about Matrix.
          Hide
          Grant Ingersoll added a comment -

          minor updates to Vector, mostly javadocs. Also added in a start to a Vector test for sanity purposes.

          Show
          Grant Ingersoll added a comment - minor updates to Vector, mostly javadocs. Also added in a start to a Vector test for sanity purposes.
          Hide
          Jeff Eastman added a comment -

          Initial implementation of Matrices and unit tests based upon the spirit of Vector. This needs to be merged with Grant's tweaks to Vector.

          Show
          Jeff Eastman added a comment - Initial implementation of Matrices and unit tests based upon the spirit of Vector. This needs to be merged with Grant's tweaks to Vector.
          Hide
          Jeff Eastman added a comment -

          Sorted out the two patches and added back my Vector unit tests that fell out due to an oversight. Couldn't resist adding a cross() operation on vectors but I'm going to do something else for a while to let people review this and let the dust settle. Once we get vectors into trunk I will update the clustering code to use them.

          Show
          Jeff Eastman added a comment - Sorted out the two patches and added back my Vector unit tests that fell out due to an oversight. Couldn't resist adding a cross() operation on vectors but I'm going to do something else for a while to let people review this and let the dust settle. Once we get vectors into trunk I will update the clustering code to use them.
          Hide
          Jason Rennie added a comment -

          Hmm... a HashMap SparseVector implementation is certainly flexible, but also quite inefficient both in terms of space and in terms of the basic vector/matrix operations (e.g. dot-product). What about a (second?) representation as an int[] of indices and a double[] of value, where the indices are stored in sorted order? This makes dot-products efficient and greatly reduces storage space. 'course, this makes get/set (very) slow, but I think the tradeoff is valuable. At least, when I tested a HashMap implementation (might have been the colt one), it was completely impractical for my work (waaaaay too slow, IIRC). The int[], double[] representation is what I use now and it serves me well.

          Btw, since there likely to be multiple implementations of a SparseVector, can we rename SparseVector to SparseVectorHashMap or some such?

          Show
          Jason Rennie added a comment - Hmm... a HashMap SparseVector implementation is certainly flexible, but also quite inefficient both in terms of space and in terms of the basic vector/matrix operations (e.g. dot-product). What about a (second?) representation as an int[] of indices and a double[] of value, where the indices are stored in sorted order? This makes dot-products efficient and greatly reduces storage space. 'course, this makes get/set (very) slow, but I think the tradeoff is valuable. At least, when I tested a HashMap implementation (might have been the colt one), it was completely impractical for my work (waaaaay too slow, IIRC). The int[], double[] representation is what I use now and it serves me well. Btw, since there likely to be multiple implementations of a SparseVector, can we rename SparseVector to SparseVectorHashMap or some such?
          Hide
          Jeff Eastman added a comment - - edited

          Boy, I am sure not wedded to the HashMap implementation. From my Smalltalk experience, one hash lookup like that is equivalent to about 40 iterations down a fixed array. Unless the vector cardinality is very large and mostly not sparse (size ~ cardinality), your implementation will likely outperform mine. I was coding stream-of-consciousness and picked only the most obvious and simplest to code approach for everything. Please feel free to propose a patch with your alternative. If you could include a unit test that measures the tradeoff point between iterating and hashing in the current jdk, it would be quite informative and even more compelling.

          I'm ok with either introducing another sparse implementation, or changing the current one. I do think we ought to make these sorts of changes based upon empirical data and agreed upon user stories.

          I do think we ought to get something into trunk soon so that the patch merging hassle is behind us.

          Show
          Jeff Eastman added a comment - - edited Boy, I am sure not wedded to the HashMap implementation. From my Smalltalk experience, one hash lookup like that is equivalent to about 40 iterations down a fixed array. Unless the vector cardinality is very large and mostly not sparse (size ~ cardinality), your implementation will likely outperform mine. I was coding stream-of-consciousness and picked only the most obvious and simplest to code approach for everything. Please feel free to propose a patch with your alternative. If you could include a unit test that measures the tradeoff point between iterating and hashing in the current jdk, it would be quite informative and even more compelling. I'm ok with either introducing another sparse implementation, or changing the current one. I do think we ought to make these sorts of changes based upon empirical data and agreed upon user stories. I do think we ought to get something into trunk soon so that the patch merging hassle is behind us.
          Hide
          Ted Dunning added a comment -

          Hashmaps in Java are surprisingly fast (very nearly 1 array access).

          Their real cost is memory size and locality of reference. Rennies sorted
          index suggest is very tight on memory and is good for sequential accesses.
          Random access isn't all that bad since binary search is available. My
          experience is similar to his... sequential scanning is vastly more important
          than random access.

          One point I would suggest, however, is to allow the vector to be unsorted
          until it needs to be in order. That allows fast filling of the vector
          followed by a single sort the first time sequential scanning or random
          access is done.

          Show
          Ted Dunning added a comment - Hashmaps in Java are surprisingly fast (very nearly 1 array access). Their real cost is memory size and locality of reference. Rennies sorted index suggest is very tight on memory and is good for sequential accesses. Random access isn't all that bad since binary search is available. My experience is similar to his... sequential scanning is vastly more important than random access. One point I would suggest, however, is to allow the vector to be unsorted until it needs to be in order. That allows fast filling of the vector followed by a single sort the first time sequential scanning or random access is done.
          Hide
          Jason Rennie added a comment -

          Re: Jeff

          Sounds good. It think I might actually have some time to do this. One thing I didn't see when looking through the last patch was basic matrix/vector operations. I'll go ahead and include a dot-product method to exhibit how it'd work and do some speed comparisons vs. a HashMap impl.

          Yeah, would definitely be good to get this stuff in trunk, if only to make it easier to read/access!

          Re: Ted

          Didn't realize HashMaps were so fast. Will be good to revisit the testing I did earlier. Agreed on the CRS benefits.

          One way I get around the sorted constraint while constructing a sparse vector is a SparseVectorBuilder class. It basically has two methods: void add(int _idx, double _val), and SparseVector build(). Avoids having to keep state within the SparseVector.

          Show
          Jason Rennie added a comment - Re: Jeff Sounds good. It think I might actually have some time to do this. One thing I didn't see when looking through the last patch was basic matrix/vector operations. I'll go ahead and include a dot-product method to exhibit how it'd work and do some speed comparisons vs. a HashMap impl. Yeah, would definitely be good to get this stuff in trunk, if only to make it easier to read/access! Re: Ted Didn't realize HashMaps were so fast. Will be good to revisit the testing I did earlier. Agreed on the CRS benefits. One way I get around the sorted constraint while constructing a sparse vector is a SparseVectorBuilder class. It basically has two methods: void add(int _idx, double _val), and SparseVector build(). Avoids having to keep state within the SparseVector.
          Hide
          Jason Rennie added a comment -

          Btw, noticed the matrix stuff is currently under utils.matrix and utils.vector. The matrix package is so important that I'd think we'd want it to have it's own package (org.apache.mahout.matrix). Also, we should not separate vector/matrix classes into separate packages b/c matrix-vector products will likely need to access protected members of both classes for efficient operation. Ted, Jeff, do you agree, or am I missing something here?

          Show
          Jason Rennie added a comment - Btw, noticed the matrix stuff is currently under utils.matrix and utils.vector. The matrix package is so important that I'd think we'd want it to have it's own package (org.apache.mahout.matrix). Also, we should not separate vector/matrix classes into separate packages b/c matrix-vector products will likely need to access protected members of both classes for efficient operation. Ted, Jeff, do you agree, or am I missing something here?
          Hide
          Jason Rennie added a comment -

          Hmm... actually, the HashMap implementation doubles nicely as the builder for the CRS implementation.

          Show
          Jason Rennie added a comment - Hmm... actually, the HashMap implementation doubles nicely as the builder for the CRS implementation.
          Hide
          Ted Dunning added a comment -

          I agree that they should be together.

          I don't know whether that is the correct rationale, but I am sure one will
          come up.

          Show
          Ted Dunning added a comment - I agree that they should be together. I don't know whether that is the correct rationale, but I am sure one will come up.
          Hide
          Jeff Eastman added a comment -

          Moved all Vector and Matrix artifacts into a new org.apache.mahout.matrix package so they are back together again.
          Renamed asFormatString() to asWritableComparable() and adjusted initial implementation to return Text.
          Updated unit tests to changes.
          All tests still run.

          Let's continue the discussion on HashMap and/or array optimizations with some tests to generate empirical data.

          Show
          Jeff Eastman added a comment - Moved all Vector and Matrix artifacts into a new org.apache.mahout.matrix package so they are back together again. Renamed asFormatString() to asWritableComparable() and adjusted initial implementation to return Text. Updated unit tests to changes. All tests still run. Let's continue the discussion on HashMap and/or array optimizations with some tests to generate empirical data.
          Hide
          Grant Ingersoll added a comment -

          Adds ASL headers, fixes testWritableComparable test to pass. Will commit in tomorrow so that we can start seeing how this works in real life.

          Show
          Grant Ingersoll added a comment - Adds ASL headers, fixes testWritableComparable test to pass. Will commit in tomorrow so that we can start seeing how this works in real life.
          Hide
          Jason Rennie added a comment -

          Ted, I am a bit surprised how speedy the HashMap impl. is! 2-3x slower than the CRS impl, but much better than I thought. Would be good to test a primitive HashMap (int, double). Might be as fast as the CRS version and much more flexible. I'm gonna just drop the code in here. Besides the two vector classes and test class, you'll also find StopWatch, the code I used to do the timing. One thing I didn't do was to check much time was wasted by the StopWatch code...

          import java.util.Random;

          import junit.framework.TestCase;

          import org.apache.log4j.Logger;

          public class SparseVectorPerformanceTests extends TestCase {

          private static final Logger log = Logger.getLogger(SparseVectorPerformanceTests.class);

          Random rand = new Random();

          /**

          • <ul>
          • <li> Finished HashMap dot product in 4.161 seconds.
          • <li> Finished CRS dot product in 2.340 seconds.
          • <li> numTrials=1000000 vectorSize=1000 nnz1=50 nnz2=200
          • </ul>
          • <ul>
          • <li> Finished HashMap dot product in 6.482 seconds.
          • <li> Finished CRS dot product in 2.663 seconds.
          • <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100
          • </ul>
            */
            public void testSparseVectorPerformance() throws Exception {
            StopWatch hmvSW = new StopWatch("HashMap dot product", log, false);
            StopWatch crsSW = new StopWatch("CRS dot product", log, false);
            final int numTrials = 1000000;
            final int vectorSize = 1000;
            final int nnz1 = 100;
            final int nnz2 = 100;
            for (int i = 0; i < numTrials; ++i)
            Unknown macro: { SparseVectorHashMap hmv1 = new SparseVectorHashMap(); SparseVectorHashMap hmv2 = new SparseVectorHashMap(); for (int j = 0; j < nnz1; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); }
            for (int j = 0; j < nnz2; ++j) { hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); }
            SparseVectorCRS crsv1 = hmv1.buildSparseVector();
            SparseVectorCRS crsv2 = hmv2.buildSparseVector();
            hmvSW.start();
            hmv1.dot(hmv2);
            hmvSW.stop();
            crsSW.start();
            crsv1.dot(crsv2);
            crsSW.stop();
            }
            hmvSW.logEndMessage();
            crsSW.logEndMessage();
            log.debug("numTrials=" + numTrials + " vectorSize=" + vectorSize + " nnz1=" + nnz1 + " nnz2=" + nnz2);
            }

            public void testSparseVectorCorrectness() throws Exception {
            final int vectorSize = 100;
            final int nnz = 10;
            SparseVectorHashMap hmv1 = new SparseVectorHashMap();
            SparseVectorHashMap hmv2 = new SparseVectorHashMap();
            for (int j = 0; j < nnz; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); }
            SparseVectorCRS crsv1 = hmv1.buildSparseVector();
            SparseVectorCRS crsv2 = hmv2.buildSparseVector();
            double hmvDot = hmv1.dot(hmv2);
            double vDot = crsv1.dot(crsv2);
            assertTrue(hmvDot == vDot);
            log.debug(hmvDot);
            log.debug(vDot);
            }

            }

            import java.util.ArrayList;
            import java.util.Collections;
            import java.util.HashMap;
            import java.util.List;
            import java.util.Map;

            public class SparseVectorHashMap {

            Map<Integer, Double> data;

            public SparseVectorHashMap() { this.data = new HashMap<Integer, Double>(); }

            public SparseVectorCRS buildSparseVector() {
            int size = this.data.size();
            int[] index = new int[size];
            double[] value = new double[size];
            List<Integer> keyList = new ArrayList<Integer>(this.data.keySet());
            Collections.sort(keyList);
            for (int i = 0; i < size; ++i) { Integer indexInteger = keyList.get(i); index[i] = indexInteger.intValue(); value[i] = this.data.get(indexInteger).doubleValue(); }
            return new SparseVectorCRS(index, value);
            }

            public void set(Integer _index, Double _value) { this.data.put(_index, _value); }

            /**
            * Assumption: _smaller.size() < _larger.size()
            *
            * @param _smaller
            * data entry of SparseVectorHashMap
            * @param _larger
            * data entry of SparseVectorHashMap
            * @return dot-product of corresponding vectors
            */
            static private double dot(Map<Integer, Double> _smaller, Map<Integer, Double> _larger) {
            double retval = 0.0;
            for (Map.Entry<Integer, Double> smallEntry : _smaller.entrySet()) {
            Double largeValue = _larger.get(smallEntry.getKey());
            if (largeValue != null) { retval += largeValue.doubleValue() * smallEntry.getValue().doubleValue(); }
            }
            return retval;
            }

            /**
            * @param _v
            * @return dot-product of this vector with _v
            */
            public double dot(SparseVectorHashMap _v) {
            if (this.data.size() < _v.data.size()) { return dot(this.data, _v.data); }
            return dot(_v.data, this.data);
            }
            }

            import java.util.Random;

            import junit.framework.TestCase;

            import org.apache.log4j.Logger;

            public class SparseVectorPerformanceTests extends TestCase {

            private static final Logger log = Logger.getLogger(SparseVectorPerformanceTests.class);

            Random rand = new Random();

            /**
            * <ul>
            * <li> Finished HashMap dot product in 4.161 seconds.
            * <li> Finished CRS dot product in 2.340 seconds.
            * <li> numTrials=1000000 vectorSize=1000 nnz1=50 nnz2=200
            * </ul>
            * <ul>
            * <li> Finished HashMap dot product in 6.482 seconds.
            * <li> Finished CRS dot product in 2.663 seconds.
            * <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100
            * </ul>
            */
            public void testSparseVectorPerformance() throws Exception {
            StopWatch hmvSW = new StopWatch("HashMap dot product", log, false);
            StopWatch crsSW = new StopWatch("CRS dot product", log, false);
            final int numTrials = 1000000;
            final int vectorSize = 1000;
            final int nnz1 = 100;
            final int nnz2 = 100;
            for (int i = 0; i < numTrials; ++i) {
            SparseVectorHashMap hmv1 = new SparseVectorHashMap();
            SparseVectorHashMap hmv2 = new SparseVectorHashMap();
            for (int j = 0; j < nnz1; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } for (int j = 0; j < nnz2; ++j) { hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } SparseVectorCRS crsv1 = hmv1.buildSparseVector(); SparseVectorCRS crsv2 = hmv2.buildSparseVector(); hmvSW.start(); hmv1.dot(hmv2); hmvSW.stop(); crsSW.start(); crsv1.dot(crsv2); crsSW.stop(); }

            hmvSW.logEndMessage();
            crsSW.logEndMessage();
            log.debug("numTrials=" + numTrials + " vectorSize=" + vectorSize + " nnz1=" + nnz1 + " nnz2=" + nnz2);
            }

          public void testSparseVectorCorrectness() throws Exception {
          final int vectorSize = 100;
          final int nnz = 10;
          SparseVectorHashMap hmv1 = new SparseVectorHashMap();
          SparseVectorHashMap hmv2 = new SparseVectorHashMap();
          for (int j = 0; j < nnz; ++j)

          { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); }

          SparseVectorCRS crsv1 = hmv1.buildSparseVector();
          SparseVectorCRS crsv2 = hmv2.buildSparseVector();
          double hmvDot = hmv1.dot(hmv2);
          double vDot = crsv1.dot(crsv2);
          assertTrue(hmvDot == vDot);
          log.debug(hmvDot);
          log.debug(vDot);
          }

          }

          import org.apache.log4j.Logger;

          public class StopWatch {

          enum StopWatchState

          { RUNNING, STOPPED }

          static final double meg = 1024.0 * 1024.0;

          long t0;

          String action;

          Logger log;

          StopWatchState state;

          double elapsedSeconds = 0.0;

          /**

          • Initializes and starts the clock.
          • @param _action
          • @param _log
            */
            public StopWatch(final String _action, final Logger _log) { this(_action, _log, true); }

          public StopWatch(final String _action, final Logger _log, final boolean _startRunning) {
          this.action = _action;
          this.log = _log;
          this.log.info(startMessage());
          if (_startRunning)

          { this.state = StopWatchState.RUNNING; this.t0 = System.currentTimeMillis(); }

          else
          this.state = StopWatchState.STOPPED;
          }

          String startMessage()

          { Runtime r = Runtime.getRuntime(); double totMemMeg = r.totalMemory() / meg; double freeMemMeg = r.freeMemory() / meg; return String.format("mem=%.2fm Started %s...", Double.valueOf(totMemMeg - freeMemMeg), this.action); }

          public void start() {
          if (this.state.equals(StopWatchState.RUNNING))

          { this.log.warn("start(): StopWatch is already running. Not doing anything."); return; }

          this.state = StopWatchState.RUNNING;
          this.t0 = System.currentTimeMillis();
          }

          public void stop() {
          double curElapsedSeconds = ((System.currentTimeMillis() - this.t0) / 1000.0);
          if (this.state.equals(StopWatchState.STOPPED))

          { this.log.warn("stop(): StopWatch is already stopped. Not doing anything."); return; }

          this.elapsedSeconds += curElapsedSeconds;
          this.state = StopWatchState.STOPPED;
          }

          public void logEndMessage()

          { this.log.info(endMessage()); }

          public void logEndMessage(final String _s)

          { this.log.info(endMessage() + " " + _s); }

          String endMessage() {
          double totalElapsedSeconds = this.elapsedSeconds;
          if (this.state.equals(StopWatchState.RUNNING))

          { totalElapsedSeconds += ((System.currentTimeMillis() - this.t0) / 1000.0); }

          Runtime r = Runtime.getRuntime();
          double totMemMeg = r.totalMemory() / meg;
          double freeMemMeg = r.freeMemory() / meg;
          return String.format("mem=%.2fm Finished %s in %.3f seconds.", Double.valueOf(totMemMeg - freeMemMeg), this.action, Double.valueOf(totalElapsedSeconds));
          }

          }

          Show
          Jason Rennie added a comment - Ted, I am a bit surprised how speedy the HashMap impl. is! 2-3x slower than the CRS impl, but much better than I thought. Would be good to test a primitive HashMap (int, double). Might be as fast as the CRS version and much more flexible. I'm gonna just drop the code in here. Besides the two vector classes and test class, you'll also find StopWatch, the code I used to do the timing. One thing I didn't do was to check much time was wasted by the StopWatch code... import java.util.Random; import junit.framework.TestCase; import org.apache.log4j.Logger; public class SparseVectorPerformanceTests extends TestCase { private static final Logger log = Logger.getLogger(SparseVectorPerformanceTests.class); Random rand = new Random(); /** <ul> <li> Finished HashMap dot product in 4.161 seconds. <li> Finished CRS dot product in 2.340 seconds. <li> numTrials=1000000 vectorSize=1000 nnz1=50 nnz2=200 </ul> <ul> <li> Finished HashMap dot product in 6.482 seconds. <li> Finished CRS dot product in 2.663 seconds. <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100 </ul> */ public void testSparseVectorPerformance() throws Exception { StopWatch hmvSW = new StopWatch("HashMap dot product", log, false); StopWatch crsSW = new StopWatch("CRS dot product", log, false); final int numTrials = 1000000; final int vectorSize = 1000; final int nnz1 = 100; final int nnz2 = 100; for (int i = 0; i < numTrials; ++i) Unknown macro: { SparseVectorHashMap hmv1 = new SparseVectorHashMap(); SparseVectorHashMap hmv2 = new SparseVectorHashMap(); for (int j = 0; j < nnz1; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } for (int j = 0; j < nnz2; ++j) { hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } SparseVectorCRS crsv1 = hmv1.buildSparseVector(); SparseVectorCRS crsv2 = hmv2.buildSparseVector(); hmvSW.start(); hmv1.dot(hmv2); hmvSW.stop(); crsSW.start(); crsv1.dot(crsv2); crsSW.stop(); } hmvSW.logEndMessage(); crsSW.logEndMessage(); log.debug("numTrials=" + numTrials + " vectorSize=" + vectorSize + " nnz1=" + nnz1 + " nnz2=" + nnz2); } public void testSparseVectorCorrectness() throws Exception { final int vectorSize = 100; final int nnz = 10; SparseVectorHashMap hmv1 = new SparseVectorHashMap(); SparseVectorHashMap hmv2 = new SparseVectorHashMap(); for (int j = 0; j < nnz; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } SparseVectorCRS crsv1 = hmv1.buildSparseVector(); SparseVectorCRS crsv2 = hmv2.buildSparseVector(); double hmvDot = hmv1.dot(hmv2); double vDot = crsv1.dot(crsv2); assertTrue(hmvDot == vDot); log.debug(hmvDot); log.debug(vDot); } } import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class SparseVectorHashMap { Map<Integer, Double> data; public SparseVectorHashMap() { this.data = new HashMap<Integer, Double>(); } public SparseVectorCRS buildSparseVector() { int size = this.data.size(); int[] index = new int [size] ; double[] value = new double [size] ; List<Integer> keyList = new ArrayList<Integer>(this.data.keySet()); Collections.sort(keyList); for (int i = 0; i < size; ++i) { Integer indexInteger = keyList.get(i); index[i] = indexInteger.intValue(); value[i] = this.data.get(indexInteger).doubleValue(); } return new SparseVectorCRS(index, value); } public void set(Integer _index, Double _value) { this.data.put(_index, _value); } /** * Assumption: _smaller.size() < _larger.size() * * @param _smaller * data entry of SparseVectorHashMap * @param _larger * data entry of SparseVectorHashMap * @return dot-product of corresponding vectors */ static private double dot(Map<Integer, Double> _smaller, Map<Integer, Double> _larger) { double retval = 0.0; for (Map.Entry<Integer, Double> smallEntry : _smaller.entrySet()) { Double largeValue = _larger.get(smallEntry.getKey()); if (largeValue != null) { retval += largeValue.doubleValue() * smallEntry.getValue().doubleValue(); } } return retval; } /** * @param _v * @return dot-product of this vector with _v */ public double dot(SparseVectorHashMap _v) { if (this.data.size() < _v.data.size()) { return dot(this.data, _v.data); } return dot(_v.data, this.data); } } import java.util.Random; import junit.framework.TestCase; import org.apache.log4j.Logger; public class SparseVectorPerformanceTests extends TestCase { private static final Logger log = Logger.getLogger(SparseVectorPerformanceTests.class); Random rand = new Random(); /** * <ul> * <li> Finished HashMap dot product in 4.161 seconds. * <li> Finished CRS dot product in 2.340 seconds. * <li> numTrials=1000000 vectorSize=1000 nnz1=50 nnz2=200 * </ul> * <ul> * <li> Finished HashMap dot product in 6.482 seconds. * <li> Finished CRS dot product in 2.663 seconds. * <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100 * </ul> */ public void testSparseVectorPerformance() throws Exception { StopWatch hmvSW = new StopWatch("HashMap dot product", log, false); StopWatch crsSW = new StopWatch("CRS dot product", log, false); final int numTrials = 1000000; final int vectorSize = 1000; final int nnz1 = 100; final int nnz2 = 100; for (int i = 0; i < numTrials; ++i) { SparseVectorHashMap hmv1 = new SparseVectorHashMap(); SparseVectorHashMap hmv2 = new SparseVectorHashMap(); for (int j = 0; j < nnz1; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } for (int j = 0; j < nnz2; ++j) { hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } SparseVectorCRS crsv1 = hmv1.buildSparseVector(); SparseVectorCRS crsv2 = hmv2.buildSparseVector(); hmvSW.start(); hmv1.dot(hmv2); hmvSW.stop(); crsSW.start(); crsv1.dot(crsv2); crsSW.stop(); } hmvSW.logEndMessage(); crsSW.logEndMessage(); log.debug("numTrials=" + numTrials + " vectorSize=" + vectorSize + " nnz1=" + nnz1 + " nnz2=" + nnz2); } public void testSparseVectorCorrectness() throws Exception { final int vectorSize = 100; final int nnz = 10; SparseVectorHashMap hmv1 = new SparseVectorHashMap(); SparseVectorHashMap hmv2 = new SparseVectorHashMap(); for (int j = 0; j < nnz; ++j) { hmv1.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); hmv2.set(this.rand.nextInt(vectorSize) + 1, this.rand.nextDouble()); } SparseVectorCRS crsv1 = hmv1.buildSparseVector(); SparseVectorCRS crsv2 = hmv2.buildSparseVector(); double hmvDot = hmv1.dot(hmv2); double vDot = crsv1.dot(crsv2); assertTrue(hmvDot == vDot); log.debug(hmvDot); log.debug(vDot); } } import org.apache.log4j.Logger; public class StopWatch { enum StopWatchState { RUNNING, STOPPED } static final double meg = 1024.0 * 1024.0; long t0; String action; Logger log; StopWatchState state; double elapsedSeconds = 0.0; /** Initializes and starts the clock. @param _action @param _log */ public StopWatch(final String _action, final Logger _log) { this(_action, _log, true); } public StopWatch(final String _action, final Logger _log, final boolean _startRunning) { this.action = _action; this.log = _log; this.log.info(startMessage()); if (_startRunning) { this.state = StopWatchState.RUNNING; this.t0 = System.currentTimeMillis(); } else this.state = StopWatchState.STOPPED; } String startMessage() { Runtime r = Runtime.getRuntime(); double totMemMeg = r.totalMemory() / meg; double freeMemMeg = r.freeMemory() / meg; return String.format("mem=%.2fm Started %s...", Double.valueOf(totMemMeg - freeMemMeg), this.action); } public void start() { if (this.state.equals(StopWatchState.RUNNING)) { this.log.warn("start(): StopWatch is already running. Not doing anything."); return; } this.state = StopWatchState.RUNNING; this.t0 = System.currentTimeMillis(); } public void stop() { double curElapsedSeconds = ((System.currentTimeMillis() - this.t0) / 1000.0); if (this.state.equals(StopWatchState.STOPPED)) { this.log.warn("stop(): StopWatch is already stopped. Not doing anything."); return; } this.elapsedSeconds += curElapsedSeconds; this.state = StopWatchState.STOPPED; } public void logEndMessage() { this.log.info(endMessage()); } public void logEndMessage(final String _s) { this.log.info(endMessage() + " " + _s); } String endMessage() { double totalElapsedSeconds = this.elapsedSeconds; if (this.state.equals(StopWatchState.RUNNING)) { totalElapsedSeconds += ((System.currentTimeMillis() - this.t0) / 1000.0); } Runtime r = Runtime.getRuntime(); double totMemMeg = r.totalMemory() / meg; double freeMemMeg = r.freeMemory() / meg; return String.format("mem=%.2fm Finished %s in %.3f seconds.", Double.valueOf(totMemMeg - freeMemMeg), this.action, Double.valueOf(totalElapsedSeconds)); } }
          Hide
          Dawid Weiss added a comment -

          A quickie:

          1. Make many, many rounds through the same code and throw away initial observations. JVMs tend to optimize code after some time (and compile it to native code of course). A single run is definitely not enough.

          2. There is no HashMap on primitive types in the JDK. It's done on boxed types – while these yield to low-level optimizations, I doubt you'll get much improvement.

          Show
          Dawid Weiss added a comment - A quickie: 1. Make many, many rounds through the same code and throw away initial observations. JVMs tend to optimize code after some time (and compile it to native code of course). A single run is definitely not enough. 2. There is no HashMap on primitive types in the JDK. It's done on boxed types – while these yield to low-level optimizations, I doubt you'll get much improvement.
          Hide
          Ted Dunning added a comment -

          I believe that Jason was referring to a purpose built primitive HashMap for
          primitives (of which there are many implementations, including a reasonably
          good one in Colt).

          Show
          Ted Dunning added a comment - I believe that Jason was referring to a purpose built primitive HashMap for primitives (of which there are many implementations, including a reasonably good one in Colt).
          Hide
          Jason Rennie added a comment -

          Re David:

          1. Good point. Was doing the test as more of a gut-check than a formal test, but yeah, we should change the test so that the first 10% or so iterations are ignored.

          Re Ted:

          Exactly. I'd be surprised if we don't see at least a 25% speed improvement with a special purpose int/double HashMap. Also, provides us with memory savings. Can/should we just grab Colt's impl?

          Show
          Jason Rennie added a comment - Re David: 1. Good point. Was doing the test as more of a gut-check than a formal test, but yeah, we should change the test so that the first 10% or so iterations are ignored. Re Ted: Exactly. I'd be surprised if we don't see at least a 25% speed improvement with a special purpose int/double HashMap. Also, provides us with memory savings. Can/should we just grab Colt's impl?
          Hide
          Grant Ingersoll added a comment -

          Not without looking at the license, etc. I see some LGPL in there: http://dsd.lbl.gov/~hoschek/colt/license.html
          We can implement our own, or maybe there is a version somewhere
          under ASL?

          Show
          Grant Ingersoll added a comment - Not without looking at the license, etc. I see some LGPL in there: http://dsd.lbl.gov/~hoschek/colt/license.html We can implement our own, or maybe there is a version somewhere under ASL?
          Hide
          Dawid Weiss added a comment -

          If you're looking at collection implementations based on primitives then there are a couple – commons collections used to have one, we used pcj (primitive collections for java) in Carrot2.

          That said, on modern JVMs the speed improvement is still not that impressive (read: minimal). I bet JVMs have good optimizations for boxed types (since they are immutable). Feel free to check pcj, it's quite all right and the license is permissive.

          Show
          Dawid Weiss added a comment - If you're looking at collection implementations based on primitives then there are a couple – commons collections used to have one, we used pcj (primitive collections for java) in Carrot2. That said, on modern JVMs the speed improvement is still not that impressive (read: minimal). I bet JVMs have good optimizations for boxed types (since they are immutable). Feel free to check pcj, it's quite all right and the license is permissive.
          Hide
          Jason Rennie added a comment -

          David's right, I'm wrong---a primitive implementation didn't help (wrt speed). I tested the pcj IntKeyDoubleOpenHashMap vs. java.util.HashMap<Integer,Double>. Tried two load factors (I set initial capacity to 1/loadFactor): 25% and 50%. The two maps were about comparable for 25%. java.util.HashMap was faster for 50%. The CRS impl. was 2.3-3.6x faster than java.util.HashMap (after subtracting the SW "base" times).

          The details:

          /**

          • <ul>
          • <li> Finished HashMap dot product in 6.501 seconds
          • <li> Finished PrimitiveMap dot product in 6.589 seconds
          • <li> Finished CRS dot product in 2.632 seconds
          • <li> Finished SW base time in 1.162 seconds
          • <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100 loadFactor=25%
          • </ul>
          • <ul>
          • <li> Finished HashMap dot product in 4.573 seconds
          • <li> Finished PrimitiveMap dot product in 4.033 seconds
          • <li> Finished CRS dot product in 2.290 seconds
          • <li> Finished SW base time in 1.103 seconds
          • <li> numTrials=1000000 vectorSize=1000 nnz1=200 nnz2=50 loadFactor=25%
          • </ul>
          • <ul>
          • <li> Finished HashMap dot product in 6.244 seconds
          • <li> Finished PrimitiveMap dot product in 7.417 seconds
          • <li> Finished CRS dot product in 2.575 seconds
          • <li> Finished SW base time in 1.054 seconds
          • <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100 loadFactor=50%
          • </ul>
          • <ul>
          • <li> Finished HashMap dot product in 3.745 seconds
          • <li> Finished PrimitiveMap dot product in 4.249 seconds
          • <li> Finished CRS dot product in 2.270 seconds
          • <li> Finished SW base time in 1.164 seconds
          • <li> numTrials=1000000 vectorSize=1000 nnz1=200 nnz2=50 loadFactor=50%
          • </ul>
            */
            public void testSparseVectorPerformance() throws Exception {
            StopWatch hmvSW = new StopWatch("HashMap dot product", log, false);
            StopWatch pmvSW = new StopWatch("PrimitiveMap dot product", log, false);
            StopWatch crsSW = new StopWatch("CRS dot product", log, false);
            StopWatch baseSW = new StopWatch("SW base time", log, false);
            final int numTrials = 1000000;
            final int vectorSize = 1000;
            final int nnz1 = 100;
            final int nnz2 = 100;
            final int sizeMultiple = 2;
            for (int i = 0; i < numTrials; ++i)
            Unknown macro: { // ignore first 10% of iterations if (i == numTrials / 10) { hmvSW.reset(); pmvSW.reset(); crsSW.reset(); baseSW.reset(); } SparseVectorPrimitiveMap pmv1 = new SparseVectorPrimitiveMap(nnz1 * sizeMultiple); SparseVectorPrimitiveMap pmv2 = new SparseVectorPrimitiveMap(nnz2 * sizeMultiple); SparseVectorHashMap hmv1 = new SparseVectorHashMap(nnz1 * sizeMultiple); SparseVectorHashMap hmv2 = new SparseVectorHashMap(nnz2 * sizeMultiple); for (int j = 0; j < nnz1; ++j) { int index = this.rand.nextInt(vectorSize) + 1; double value = this.rand.nextDouble(); pmv1.set(index, value); hmv1.set(index, value); } for (int j = 0; j < nnz2; ++j) { int index = this.rand.nextInt(vectorSize) + 1; double value = this.rand.nextDouble(); pmv2.set(index, value); hmv2.set(index, value); } SparseVector crsv1 = pmv1.buildSparseVector(); SparseVector crsv2 = pmv2.buildSparseVector(); hmvSW.start(); hmv1.dot(hmv2); hmvSW.stop(); pmvSW.start(); pmv1.dot(pmv2); pmvSW.stop(); crsSW.start(); crsv1.dot(crsv2); crsSW.stop(); baseSW.start(); baseSW.stop(); }

            hmvSW.logEndMessage();
            pmvSW.logEndMessage();
            crsSW.logEndMessage();
            baseSW.logEndMessage();
            log.debug("numTrials=" + numTrials + " vectorSize=" + vectorSize + " nnz1=" + nnz1 + " nnz2=" + nnz2 + " loadFactor=" + (100 / sizeMultiple) + "%");
            }

          Show
          Jason Rennie added a comment - David's right, I'm wrong---a primitive implementation didn't help (wrt speed). I tested the pcj IntKeyDoubleOpenHashMap vs. java.util.HashMap<Integer,Double>. Tried two load factors (I set initial capacity to 1/loadFactor): 25% and 50%. The two maps were about comparable for 25%. java.util.HashMap was faster for 50%. The CRS impl. was 2.3-3.6x faster than java.util.HashMap (after subtracting the SW "base" times). The details: /** <ul> <li> Finished HashMap dot product in 6.501 seconds <li> Finished PrimitiveMap dot product in 6.589 seconds <li> Finished CRS dot product in 2.632 seconds <li> Finished SW base time in 1.162 seconds <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100 loadFactor=25% </ul> <ul> <li> Finished HashMap dot product in 4.573 seconds <li> Finished PrimitiveMap dot product in 4.033 seconds <li> Finished CRS dot product in 2.290 seconds <li> Finished SW base time in 1.103 seconds <li> numTrials=1000000 vectorSize=1000 nnz1=200 nnz2=50 loadFactor=25% </ul> <ul> <li> Finished HashMap dot product in 6.244 seconds <li> Finished PrimitiveMap dot product in 7.417 seconds <li> Finished CRS dot product in 2.575 seconds <li> Finished SW base time in 1.054 seconds <li> numTrials=1000000 vectorSize=1000 nnz1=100 nnz2=100 loadFactor=50% </ul> <ul> <li> Finished HashMap dot product in 3.745 seconds <li> Finished PrimitiveMap dot product in 4.249 seconds <li> Finished CRS dot product in 2.270 seconds <li> Finished SW base time in 1.164 seconds <li> numTrials=1000000 vectorSize=1000 nnz1=200 nnz2=50 loadFactor=50% </ul> */ public void testSparseVectorPerformance() throws Exception { StopWatch hmvSW = new StopWatch("HashMap dot product", log, false); StopWatch pmvSW = new StopWatch("PrimitiveMap dot product", log, false); StopWatch crsSW = new StopWatch("CRS dot product", log, false); StopWatch baseSW = new StopWatch("SW base time", log, false); final int numTrials = 1000000; final int vectorSize = 1000; final int nnz1 = 100; final int nnz2 = 100; final int sizeMultiple = 2; for (int i = 0; i < numTrials; ++i) Unknown macro: { // ignore first 10% of iterations if (i == numTrials / 10) { hmvSW.reset(); pmvSW.reset(); crsSW.reset(); baseSW.reset(); } SparseVectorPrimitiveMap pmv1 = new SparseVectorPrimitiveMap(nnz1 * sizeMultiple); SparseVectorPrimitiveMap pmv2 = new SparseVectorPrimitiveMap(nnz2 * sizeMultiple); SparseVectorHashMap hmv1 = new SparseVectorHashMap(nnz1 * sizeMultiple); SparseVectorHashMap hmv2 = new SparseVectorHashMap(nnz2 * sizeMultiple); for (int j = 0; j < nnz1; ++j) { int index = this.rand.nextInt(vectorSize) + 1; double value = this.rand.nextDouble(); pmv1.set(index, value); hmv1.set(index, value); } for (int j = 0; j < nnz2; ++j) { int index = this.rand.nextInt(vectorSize) + 1; double value = this.rand.nextDouble(); pmv2.set(index, value); hmv2.set(index, value); } SparseVector crsv1 = pmv1.buildSparseVector(); SparseVector crsv2 = pmv2.buildSparseVector(); hmvSW.start(); hmv1.dot(hmv2); hmvSW.stop(); pmvSW.start(); pmv1.dot(pmv2); pmvSW.stop(); crsSW.start(); crsv1.dot(crsv2); crsSW.stop(); baseSW.start(); baseSW.stop(); } hmvSW.logEndMessage(); pmvSW.logEndMessage(); crsSW.logEndMessage(); baseSW.logEndMessage(); log.debug("numTrials=" + numTrials + " vectorSize=" + vectorSize + " nnz1=" + nnz1 + " nnz2=" + nnz2 + " loadFactor=" + (100 / sizeMultiple) + "%"); }
          Hide
          Jason Rennie added a comment -

          Btw, I'm running jdk-6u4-linux-x64.bin

          Show
          Jason Rennie added a comment - Btw, I'm running jdk-6u4-linux-x64.bin
          Hide
          Ted Dunning added a comment -

          Amazing.

          Were you able to measure garbage production?

          Show
          Ted Dunning added a comment - Amazing. Were you able to measure garbage production?
          Hide
          Grant Ingersoll added a comment -

          Does it make sense to be able to assign labels to the rows and columns and maybe even have it accessible as a map? For instance, I think I could use these for the bayesian classifier implementation I am working on and it would make sense to be able to label the features and the labels. Naturally, I can store the information elsewhere as well, but didn't know whether it made sense to keep the info w/ the matrix.

          Show
          Grant Ingersoll added a comment - Does it make sense to be able to assign labels to the rows and columns and maybe even have it accessible as a map? For instance, I think I could use these for the bayesian classifier implementation I am working on and it would make sense to be able to label the features and the labels. Naturally, I can store the information elsewhere as well, but didn't know whether it made sense to keep the info w/ the matrix.
          Hide
          Grant Ingersoll added a comment -

          Committed revision 637664. Thanks!

          Show
          Grant Ingersoll added a comment - Committed revision 637664. Thanks!
          Hide
          Grant Ingersoll added a comment -

          This was committed.

          Show
          Grant Ingersoll added a comment - This was committed.

            People

            • Assignee:
              Grant Ingersoll
              Reporter:
              Ted Dunning
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development