Formula for optimal matrix block-size #75
Description
Hi @Bergvca
I think that the optimal matrix block-size, or the maximum number of strings Nmax for the master Series (beyond which cache-misses begin to dominate the computation and thus lead to computational slowdown) would be directly proportional to the CPU cache-size MCPU and inversely proportional to the density ρright of the right operand-matrix encoding the strings in master. That is,
Nmax ∝ MCPU / ρright .
Since for my computer, Nmax = 8 × 104, MCPU = 6MB and ρright is a number I don't know yet but can easily find during runtime (that is, the number of nonzero matrix-elements divided by the total number of matrix-elements), we can then determine the constant of proportionality and use it to find Nmax for any other computer whose CPU cache-size is known or can be queried (using python package psutil, for example).
What do you think?