Thursday, April 25, 2013

la4j's performance


Recently, I've bumped into this web-site. I was quite surprised that they used la4j for benchmarking (see demo video). It is always pleasure to see when people use your 'just-for-fun' library. Anyway, I didn't except that la4j is so slow. I wrote an email to the guys who was testing la4j and ask them to provide me benchmark sources. So, the sources was looking good and there is nothing I can do there to improve la4j's performance. But something, I already did.

They was testing la4j-0.3.0 and it is much slower than a current 0.4.0 version. I've done several significant improvements, that speeded up whole the library.

First of all, I've rewrote sparse matrices to use binary search instead of linear one. Binary search works for logarithmic time O(log n) and if gives me up to 2.2x speed up for get/set operations.

The other good thing that I did - is improvement matrix-by-matrix multiply algorithm. I've speeded it up to 3x for dense matrices and up to 11x for sparse ones.

Here is some numbers that I got today. Performnace of matrix-by-matrix multiply:

la4j-0.3.0 Basic1DMatrix(1000x1000) - 3784ms
la4j-0.3.0 Basic2DMatrix(1000x1000) - 3946ms

la4j-0.3.0 CRSMatrix(500x500) - 45897ms
la4j-0.3.0 CCSMatrix(500x500) - 219312ms

la4j-0.4.0 Basic2DMatrix(1000x1000) - 1476ms
la4j-0.4.0 Basic1DMatrix(1000x1000) - 1489ms

la4j-0.4.0 CRSMatrix(500x500) - 20245ms
la4j-0.4.0 CCSMatrix(500x500) - 12413ms

The new version of la4j - version 0.4.0 will be avaliable this summer. It is currently avaliable at it's GitHub page: https://github.com/vkostyukov/la4j

No comments:

Post a Comment