3 ms·
What make sparse matrices harder to JIT is proving that the loop bounds will not be exceeded, so all accesses re bound checked. In any case in my experience arr
by srean 11y ago
What make sparse matrices harder to JIT is proving that the loop bounds will not be exceeded, so all accesses re bound checked. In any case in my experience array bounds checking and escape analysis never gave the boost that theory and JVM fans promise. So even normal matrix multiply will trail behind. That said Hotspot JVM is possibly one of the most optimized VMs we have got.
A structural problem of JVM is that its runtime semantics is over-specified, there is very little room for the JIT to
do its stuff. For example function arguments are evaluated right to left, there goes an opportunity for parallelism.
- eonwe 11y agoFor normal dense matrix laid out as a double[] and accessed directly as i* N_ROW + j probably won't get its loop check elided. For double[][] I would _think_ that happens more easily. But how are sparse matrices then generally laid out? A naive approach would be some hash map, perhaps with some locality, in which I don't see JIT problems.
- srean 11y agoThere are some defacto standard formats such as CRS, CSC, list of tuples etc. Layout of the third should be obvious and it is not used much for cases where speed matters because one loses locality in this layout. For the other two they are laid out column after column (or row by row), row ids, and offsets to indicate the start and end of columns (rows).
- eonwe 11y agoThanks, this helped. Using CSC and CRS is probably quite problematic with JVM bounds check elimination (or the lack of it). So if they would need to be used on JVM, I think it would be wise to drop the safety and use _sun.misc.Unsafe_ for unchecked array access.