|
Based on conversation with previous committers for the RealMatrixImpl code, I discovered that I had accidentally removed some performance enhancement code. I have put this back in and am resubmitting a fresh patch.
In addition to the changes described in the initial comment, the change here are: svn diff containing diffs against trunk for the following files:
src/java/org/apache/commons/math/linear/LUDecompositionImpl.java
Quick and dirty test (to measure wallclock times for multiplying RealMatrixImpls using the original method (currently in svn), the getEntry() method (from the original patch submission), and the rolled back method (using data[][] as fallback). My test times on a 64-bit AMD dual-core laptop with 2GB RAM is shown below: size data[][] getEntry() restored data[][] One issue with the proposed implementation is that it causes excessive objective allocation. Each non-zero entry involves a HashMap.Entry, a Point and a Double. This is quite inefficient in terms of memory usage.
One alternative would be to use a specialised HashMap with open addressing that would only take double primitives as values (similar to TObjectDoubleHashMap from Trove). Using this approach, the only object would be Point. It's possible to avoid that too, but that's more complicated (look at Colt's SparseDoubleMatrix2D for an example). Thanks for the pointer to TObjectDoubleHashMap. So basically what you
are suggesting is for the incoming (x,y) object, whatever that is, to be hashed to a single int object which is modded against the internal one-dimensional array length. Finally the hash/mod result needs to be checked against the internal double array to see if it is already occupied, and if so, another location should be found. Here are the relevant links: That /would/ definitely decrease the size of the matrix, but would make Rather than add this impl, then, it may be better to open the door for Or we could just add the appropriate specialised Map to commons-math. Are there objections to that? I could provide one, it's relatively easy to do. I think the best approach might even be one not mentioned above. Use a Map.Entry object with two ints and a double. This has a few advantages:
(1) We use chaining instead of open addressing, so we can use a higher load factor with good performance (e.g. 0.75 instead of 0.50). This should mitigate the additional memory used by the Map.Entry object. (2) We use a single array of Map.Entry objects instead of two arrays (one for keys and one for values). When testing the performance for Scala HashMap implementations (which converts to bytecode very similar to the one generated by Java), it seems that using two arrays performs quite a bit worse (although the test was using Strings instead of primitives for the value)[1]. (3) Gets don't require any boxing if we provide a get(int, int) method (this is the same as using open addressing with primitives only though). A rough sample of the implementation outline: class IntPairToDoubleHashMap { double get(int firstKey, int secondKey) This would be an internal map for usage by SparseRealMatrixImpl. I think HotSpot would be able to inline calls to it, but we could also just have the relevant code in SparseMatrixImpl. I think it's important to provide an implementation that has the right performance characteristics by default. What do you think? [1] http://www.nabble.com/-scala--Open-versus-Chained-HashMap-td19254845.html >> Or we could just add the appropriate specialised Map to commons-math. Are there objections to that?
I cannot answer this one, since I am not a developer on the project - my observation is that there are no dependencies for this project save the JDK, which leads me to believe that there may have been a concious decision to keep it that way, but I could be wrong. As for adding it into commons-math, my personal opinion is that it belongs in a data structure package such as commons-collections or such, but thats just my view. >> I think it's important to provide an implementation that has the right performance characteristics And if it is implemented as a private inner class, then it is visible only from within the implementation, so I think there should be no issues. And it would be completely justifiable, since we are basically creating a fast data structure to serve the impl. However, it is already assigned to be reviewed, so I am guessing that when Luc gets to this bug, he will post his review. FWIW, I think that if we do end up including the SparseMatrixImpl, then definitely your approach with the open/chained hashmap would be preferable to the one thats in there. If you have th bandwidth to build it, then I think it may be quite helpful. Yes, when I said "add the appropriate specialised Map to commons-math", I meant it as an internal implementation detail of SparseRealMatrixImpl. I will try to post something here during the weekend and we'll let Luc decide.
I looked into this more carefully and I have a few comments (note that I don't speak for commons-math, just an interested onlooker who might use it in the near future):
public double[][] getData() { throw new UnsupportedOperationException( "Not supported because sparse matrices are usually chosen when " + "the matrix to be modeled is too large to fit into memory, trying " + "to build the data array from this may result in an OutOfMemoryException."); } Also, it seems to override most (if not all) of the methods. Is it perhaps better to introduce an AbstractRealMatrix containing the shared methods and have both RealMatrixImpl and SparseRealMatrix extend it? I notice that this won't fix the getData() issue though, would it make sense to move that method into the dense matrix? (only possible if 2.0 can break compatibility).
There is another case of containsKey that is unnecessary because it's followed by a get after it, but once the specialised map exists the code will be even simpler so we can leave that for later. An initial untested implementation of the IntPairToDoubleHashMap. It doesn't have javadoc and does not implement a custom Serialization mechanism yet. If Luc agrees that this class should be used, I will add some tests and polish it up.
Instead of using an IntPairToDoubleHashMap, we can use a IntToDoubleHashMap and simply do compute (row * columnCount + column) to find the key. This means that we have one less int in each Entry object. With this change, it starts to look like an open addressed hash map might be better. I will work on that next.
I will try to fix
I will let you polish your solution and check it afterwards. Please, don't assume I am the one who decides, here. I am just one developer among others in this community project. I wasn't aware of that ticket. Indeed that would simplify things. Thanks for looking into it.
issue
Could you update your patch to make it consistent with the new abstract class ? This attachment includes:
There are a few things from Sujit's patch that this one does not include:
Because of the missing LUDecomposition changes, some tests in SparseRealMatrixTest are failing. I am going to be away for a few days, so if Sujit or anyone else wants to update LUDecomposition to work with any matrix type, that would be good. On the other hand, perhaps those changes could be in a separate bug since adding the SparseRealMatrix is a decent amount of work on its own. Added a few more tests to increase coverage to 100% and add License header to one file.
I have reviewed the path, I am basically OK with it.
The only thing that bothers me is the design decision to use a static inner class for OpenIntToDoubleHashMap. Since we already have a util package with a ResizableDoubleArray, I think it could be put there too and referenced from SparseRealMatrix. It doesn't seem to be too specialized as a strorage for matrices, and even uses a single integer as a key. So it could perhaps be made public. Bill Barker also said he would review the patch on the dev list. Let's wait for his comments. I don't have a strong opinion either way. It currently only implements the methods that are needed by SparseRealMatrix so if we were to move it to the util package, it would probably be a good idea to add at least two methods:
This would expose a basic set of operations. Convenience methods could then be added later if and when needed. Apologies for not getting back earlier on this, I had a chance to look at the diff this morning. I will work on making the SparseMatrix tests pass this evening and post the patch tomorrow morning.
However, looking at the patch, I notice that this method is used to find the key to the internal map for storing the entry: + private int computeKey(int row, int column) { + return row * columnDimension + column; + } This effectively flattens out the matrix so a matrix like this: Now if you wanted to look for entry (1,2) you look for entry (1*4 + 2) = 6. So we will always get a unique key for a given matrix position, given that by specifying the row and column dimension we are always specifying a fixed size rectangular matrix. This is quite beautiful and clever (note to Ismael: Thanks for doing this, and I wish I had thought of this But the question is: do we still need an open-addressed map structure? It seems to me that we can now just represent the sparse matrix internally with a Map<Integer,Double>? That way we don't even have to think about whether we want to put it as an inner class or in utils. Thoughts? Yes, we still need an open addressed map if we want to have good space characteristics. A comparison of how much space each entry takes for each case follows (note that I ignore the things that take constant space independent of the number of entries like size and such):
For HashMap<Integer,Double>, assuming a 32-bit JVM (would be much worse for the 64-bit one) and that the map has reached the maximum load factor (in bytes):
For OpentIntToDoubleHashMap, assuming a 32-bit JVM (would be similar in 64-bit JVM since it doesn't rely on pointers in the non constant variables) that the map has reached the maximum load factor (in bytes):
So, HashMap takes more than 50% more space for a 32-bit JVM and quite a bit more for the 64-bit one (since it's pointer heavy and alignment issues make it worse) and it's harder on the GC because all those Double, Integer and Map.Entry objects must be collected. Furthermore, the additional space doesn't even necessarily help with cache locality since Map.Entry only holds references to the actual objects (unfortunately, until we get value types, a.k.a. structs, we can't implement the ideal HashMap). I should add that I was a bit conservative in the load factor of OpenIntHashMap. We can reduce the space of the OpenIntToDoubleHashMap to 19.69 bytes by using a load factor of 0.66 (which is the default for the python dict).
Ok, thanks, now understand more fully the justification for the OpenIntHashMap, thanks for the lucid explanation.
I am uploading the following attachments: I think the next step would be to make LUDecompositionImpl work without RealMatrix.getData() and use get/setEntry() methods instead. I've started applying the patch with slight changes (like curly braces, javadoc).
The most important change was to extract the map class and put it into the util packages, adding the containsKey() and keys() methods as suggested. I have random test failures occurring in testRemove2(). The failures are triggered by the assertEquals(mapSize, map.size()) in the assertPutAndGet mathod called at the end of testRemove2(). mapSize was 2009 while map.size was 2010. I have succeded once (and only once) to trigger the failure under debugger. In that case, the key was -1035761067. It appeared in the map both at index 627 with status FULL and value 0.9939107277401076 and at index 1363 with status FREE and value 0.0. In the javaMap it was associated with value 0.21972202724338397. The load factor was 0.5 so array size was 4096 I think. Trying to reuse the values above in a dedicated new test with various combinations of put and remove didn't reproduce the bug. I don't understand what happens yet and since it appears randomly (due to the use of java.util.Random within the test), it is quite difficult to analyze. Interesting Luc. I will try to reproduce this. Thanks for the additional information.
After running the test suite a few times, I also got a failure. I should be able to create a test case that does not involve randomness by adding some code to track puts, gets and removes. By the way, the reason why the initial tests involved random numbers is precisely for their ability to find weird corner cases like this (similar to QuickCheck and ScalaCheck, but done manually). They are not the best way to narrow down the problem though.
 That was a tricky one. Luc, since you've done some changes to the code, it might be easier for me to just paste the methods that have changed.
In OpenIntToDoubleHashMapTest, please add: /**
* Regression test for a bug in findInsertionIndex where the hashing in the second probing
* loop was inconsistent with the first causing duplicate keys after the right sequence
* of puts and removes.
*/
public void testPutKeysWithCollisions() {
OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
int key1 = -1996012590;
double value1 = 1.0;
map.put(key1, value1);
int key2 = 835099822;
map.put(key2, value1);
int key3 = 1008859686;
map.put(key3, value1);
assertEquals(value1, map.get(key3));
assertEquals(3, map.size());
map.remove(key2);
double value2 = 2.0;
map.put(key3, value2);
assertEquals(value2, map.get(key3));
assertEquals(2, map.size());
}
/**
* Similar to testPutKeysWithCollisions() but exercises the codepaths in a slightly
* different manner.
*/
public void testPutKeysWithCollision2() {
OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
int key1 = 837989881;
double value1 = 1.0;
map.put(key1, value1);
int key2 = 476463321;
map.put(key2, value1);
assertEquals(2, map.size());
assertEquals(value1, map.get(key2));
map.remove(key1);
double value2 = 2.0;
map.put(key2, value2);
assertEquals(1, map.size());
assertEquals(value2, map.get(key2));
}
and also update setUp to be like (I added some negative keys just in case): @Override
protected void setUp() throws Exception {
javaMap.put(50, 100.0);
javaMap.put(75, 75.0);
javaMap.put(25, 500.0);
javaMap.put(Integer.MAX_VALUE, Double.MAX_VALUE);
javaMap.put(0, -1.0);
javaMap.put(1, 0.0);
javaMap.put(33, -0.1);
javaMap.put(23234234, -242343.0);
javaMap.put(23321, Double.MIN_VALUE);
javaMap.put(-4444, 332.0);
javaMap.put(-1, -2323.0);
javaMap.put(Integer.MIN_VALUE, 44.0);
/* Add a few more to cause the table to rehash */
javaMap.putAll(generate());
}
Run the tests and they should show at least one failure (I am not sure if the second collisions test will fail with the version you have, but I added it to verify a potential bug that I visually identified while modifying findInsertionIndex). Then change findInsertionIndex to be like: private static int findInsertionIndex(int[] keys, byte[] states, int key, int mask) { int hash = hashOf(key); int index = hash & mask; if (states[index] == FREE) return index; else if (states[index] == FULL && keys[index] == key) return changeIndexSign(index); int perturb = perturb(hash); int j = index; if (states[index] == FULL) { while (true) { j = probe(perturb, j); index = j & mask; perturb >>= PERTURB_SHIFT; if (states[index] != FULL || keys[index] == key) break; } } if (states[index] == FREE) return index; /* * Due to the loop exit condition, if (states[index] == FULL) then * keys[index] == key */ else if (states[index] == FULL) return changeIndexSign(index); int firstRemoved = index; while (true) { j = probe(perturb, j); index = j & mask; if (states[index] == FREE) return firstRemoved; else if (states[index] == FULL && keys[index] == key) return changeIndexSign(index); perturb >>= PERTURB_SHIFT; } } All tests should pass after that. Nice catch by the way, it was a nasty bug. fixed in trunk as of r726460
The map class has been put in the util packages. Iteration support has been added. Thanks for committing this Luc. Good point about specialised implementations of add and subtract. However, the current implementation has a lot of overhead due to the allocation of Entry objects. Since the iterator doesn't implement java.util.Iterator anyway, we can do better by using an iterator similar to Trove's. I will paste part of the javadoc below:
/** * Iterator for maps of type int and double. * * <p>The iterator semantics for Trove's primitive maps is slightly different * from those defined in <tt>java.util.Iterator</tt>, but still well within * the scope of the pattern, as defined by Gamma, et al.</p> * * <p>This iterator does <b>not</b> implicitly advance to the next entry when * the value at the current position is retrieved. Rather, you must explicitly * ask the iterator to <tt>advance()</tt> and then retrieve either the <tt>key()</tt>, * the <tt>value()</tt> or both. This is done so that you have the option, but not * the obligation, to retrieve keys and/or values as your application requires, and * without introducing wrapper objects that would carry both. As the iteration is * stateful, access to the key/value parts of the current map entry happens in * constant time.</p> * * <p>In practice, the iterator is akin to a "search finger" that you move from * position to position. Read or write operations affect the current entry only and * do not assume responsibility for moving the finger.</p> * * <p>Here are some sample scenarios for this class of iterator:</p> * * <pre> * // accessing keys/values through an iterator: * for (TIntDoubleIterator it = map.iterator(); * it.hasNext();) { * it.advance(); * if (satisfiesCondition(it.key()) { * doSomethingWithValue(it.value()); * } * } * (snipped) */ Shall I file a separate issue for that? No need to file another issue. I have fixed this as of r726490.
Hope this is better now. Thanks, that is indeed what I meant by the API. I didn't have a chance to look at the implementation in detail, but seems right.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|
Improvement
Closed
Minor
Implement Sparse Matrix Support
src/java/org/apache/commons/math/linear/LUDecompositionImpl.java
src/java/org/apache/commons/math/linear/RealMatrix.java
src/java/org/apache/commons/math/linear/MatrixUtils.java
src/java/org/apache/commons/math/linear/RealMatrixImpl.java