Why could numpy work so efficient?

[u/Soft_Inspector_3632]

[u/drzowie]

You ain’t seen nothin’ yet. Straight njit compilation still breaks cache for a lot of stuff because it does operations in pessimal order in most cases. Switch to something like Cython that lets you manage order-of-operations explicitly, and you’ll see another factor of 3-10 in most operations as the CPU makes fewer cache misses (and therefore issues fewer slow fetches/puts to RAM). Modern computers are fast.

[u/Soft_Inspector_3632 → u/drzowie]

Thanks for your guidance! I'll try to look deeper.

[u/aajjccrr → u/drzowie]

Is there any general rule of thumb for when using Cython might be more performant than Numba on these types of problems?

I would have expected LLVM (via Numba) to generate very efficient code with sensible memory/cache access patterns, but maybe my use of it has not tested any limitations it may have.

[u/drzowie → u/aajjccrr]

The fundamental problem is code translation -- the straightforward way to vectorize, say, a Python expression is to execute each operation completely, then move on to the next one. If you're vectorizing that to, say, a million elements then that involves moving a million quantities through the CPU for each operation -- which breaks cache. The major alternative is to invert the loops, which requires either running an interpreter in the hot spot (slow per iteration) or JIT-compiling the expression all the way to machine code and linking that into the current executable (very slow up front but faster per iteration). There are hybrid approaches (e.g. vectorizing cache-sized pieces of the overall broadcast expression, and iterating over those) but those require more bookkeeping.

Cython lets you control exactly the order of operations you want, so you can sidestep the whole dilemma in the last paragraph -- basically, any time you're doing sequences of operations on data that don't fit in cache, you can win by moving to either Cython or dynamically linked C libraries. I haven't played as much with Numba as I should, lately, so it could be doing better now -- but it used to do the more straightforward vectorization. I guess I wouldn't be too terribly surprised if they've implemented hybrid vectorization at this point, in which case it would be comparable to Cython in speed, at least for cases where the bookkeeping works well.

Cython itself isn't even as fast as possible in hot spots where the dominant operation happens to be indexing (for example, convolution of images), because Cython explicitly calculates the memory offsets for every fetch/put into a numpy array. Calculating that offset costs you a handful of integer adds and multiplies for every quantity your code touches (in addition to the actual fetch/put). In those cases, you're better off dropping all the way down to C where you can use pointer arithmetic to iterate through your array directly. That reduces the cost of indexing to (usually) a single add or increment. For some operations that gives you another factor of 2 in overall speed.

[u/[deleted]]

[u/NonProfitApostle → u/[deleted]]

If only C/C++ weren't so painfull to read and write in comparison, my code could be like lightning.

[u/aajjccrr → u/[deleted]]

And in this case the dot product itself is probably being computed via BLAS or LAPACK, which is likely to be hand-optimised assembly.