5 ms·

Could you elaborate a bit on how JVM hinders reaching maximum FLOPS when multiplying sparse matrices? I could think some examples where lacking SSE/AVX support

by eonwe 11y ago

Could you elaborate a bit on how JVM hinders reaching maximum FLOPS when multiplying sparse matrices? I could think some examples where lacking SSE/AVX support would hinder it, but I don't see the connection with sparse matrices.

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 ago
  For 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 ago
    There 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 ago
      Thanks, 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.

by eonwe 11y ago

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 ago
For 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 ago
  There 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 ago
    Thanks, 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.