[MAHOUT-1640] Better collections would significantly improve vector-operation speed

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 0.11.0
• Fix Version/s: 0.11.2
• Labels: legacy math scala

Environment

Darwin lithium.local 14.1.0 Darwin Kernel Version 14.1.0: Mon Dec 22 23:10:38 PST 2014; root:xnu-2782.10.72~2/RELEASE_X86_64 x86_64 i386 MacBookPro10,1 Darwin

java version "1.8.0_31"
Java(TM) SE Runtime Environment (build 1.8.0_31-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.31-b07, mixed mode)

• Assignee: Suneel Marthi
• Reporter: Sebastiano Vigna
• Created: 05/Feb/15 09:13
• Updated: 31/Jan/24 22:15
• Resolved: 08/Mar/16 20:57

Description

The collections currently used by Mahout to implement sparse vectors are extremely slow. The proposed patch (localized to RandomAccessSparseVector) uses fastutil's maps and the speed improvements in vector benchmarks are very significant. It would be interesting to see whether these improvements percolate to high-level classes using sparse vectors.

I had to patch two unit tests (an off-by-one bug and an overfitting bug; both were exposed by the different order in which key/values were returned by iterators).

The included files speed-std and speed-fastutil show the speed improvement. Some more speed might be gained by using everywhere the standard java.util.Map.Entry interface instead of Element.

DISCLAIMER: The "Times" set of tests has been run multiplying two identical vectors. The standard tests multiply two random vectors, so in fact they just test the speed of the underlying map remove() method, as almost all products are zero. This is not very realistic and was heavily penalizing fastutil's "true deletions". Better tests, with a typical overlap of nonzero entries, would be even more realistic.