Speed up execution of small arrays on the native backend.

[marcoheisig]

The native backend is not yet optimized for operating on small arrays. Detect the case where multithreading is more expensive than the work itself and, if so, run on a single thread without synchronization.

[kchanqvq]

Thanks you for considering this use case! I'm trying to hack this right now, just laying down some thoughts to keep us on the same page:

I plan to remove the multiple thread dispatch first and see how much this help. This shouldn't take too much effort and I guess I'll have a prototype today. As the next step, I plan to statically compile the schedule/list of invocations, because if there's only one worker, these can be statically determined. This will get the evaluator function to look like big progn of funcall's. The next step is to inline the funcalls but maybe not doing that is already good enough.

Just for my use case (repeatedly calling the evaluator), I plan to implement two additional interface with-fast-evaluate and fast-evaulate. fast-evaluate should only be called inside the dynamic extent of with-fast-evaluate. This way allocation/pinning can be moved out of the hot loop.

My prototype is reusing many native-backend internals right now, I wonder if that's ok in the long run? I think it would be ok if this lite-backend end up being part of native-backend. On the other hand it might be helpful to extract an interface of the reusable parts of native-backend (e.g. compute-schedule), but that might be too much extra effort for now.

The results I'm aiming for:

(let ((x (make-array nil :element-type 'double-float :initial-element 1.0))
      (y (make-array nil :element-type 'double-float :initial-element 2.0))
      (z (make-array nil :element-type 'double-float))
      (ev (let ((x (petalisp:make-unknown :element-type 'double-float))
                (y (petalisp:make-unknown :element-type 'double-float)))
            (petalisp:evaluator (list x y) (list (petalisp:lazy #'+ x y))))))
  (time (dotimes (_ 100000) (funcall ev z x y)))
  z)
(defun generic-+ (x y) (+ x y)
(let ((x 1.0)
      (y 2.0)
      (z 0.0))
  (time (dotimes (_ 100000) (setq z (generic-+ x y))))
  z)

Currently, the Petalisp evaluator above take 14000x 800x time than GENERIC-+. My goal is to get this down to 10x.

[kchanqvq]

Update: by removing the synchronizations alone, the above 14000x 800x factor is down to 900x 50x. Two more order of magnitudes to go! I'm going for allocation and pinning as the next step.

Update 2: with the with-fast-evaluate interface, the factor is down to 310x 10x. The inner loop is two nested loop (over action-vector and invocations) of funcall's. Still not ideal for my use case yet, so I'll try compiling the schedule into progn statically…

Update 2.1: actually after some profiling, I found that the time spent is already primarily inside kfn invocations, the outer two nested loop is not spending much time so eliminating them probably won't give any benefit.

I guess I'm stuck without understanding what is happening inside kfn's. What are the reasons they are slower than GENERIC-+? In principle, both GENERIC-+ and kfn involves full function call, and GENERIC-+ has to do type dispatch which kfn doesn't. kfn involves memory references to get the float out of the (rank-0) array, but this surely does not cost 2.5 order of magnitudes? What is happening under the hood?

Update 2.2: Turns out my original benchmark code is wrong, and SBCL specialized + to an inline instruction. I have to use a function indirection to benchmark GENERIC-+ correctly. Turns out with-fast-evaluate already gets down to 10x overhead, and this is totally viable for my application! Sorry for the noise!

I wonder if the overhead can be cut even further. In principle kfn does no more work than GENERIC-+. What cause the remaining overhead?

[marcoheisig]

Oh, wow, thanks for investigating so thoroughly!

I think the proper solution is to use some cost function to estimate the cost of running an evaluator. If that cost is below some threshold, we run on the calling thread directly and skip multithreading. This way, we wouldn't need an extra evaluation interface, and everything should "just work".

Is your with-fast-evaluate code uploaded somewhere? I'd really like to have a look :)

[kchanqvq]

Is your with-fast-evaluate code uploaded somewhere? I'd really like to have a look :)

Sure! Uploaded here: https://gist.github.com/kchanqvq/3019243d81ec41532aeed31a94bc64c4.

Now I think while the single thread part is useful, it's probably a dead end to try to optimize performance for very small arrays (~10 elements)? The example for rank-0 array in the gist runs in 0.0013 seconds with type-declared Common Lisp, a 100x overhead for Petalisp even using with-fast-evaluate.

The problem I'm trying to solve is to support time series analysis, which uses sequential operators over arrays with pretty large size on the time dimension (>1M), and varying size on "orthogonal" dimensions (5~1K). The above investigation is a by-product of my experiment that uses an outer driving loop (which iterates over time dimension) to call Petalisp which operates on slices of those orthogonal dimensions, and now I think it's probably a dead end. I guess the only viable option is to wait for the array-processor/rank operator?

An operator that converts between Petalisp array of dimensions (x ... y ...) with scalar elements and Petalisp array of dimensions (x ...) with Lisp array elements of dimensions (y ...) will also be expressive enough for me. Is that easier to add?

[marcoheisig]

Thanks for sharing your code! I will try to see how low I can get the overhead, but I'm not sure whether I can make it competitive for < 100 elements. It is a nice challenge, though :)

I already have some interesting progress regarding the array-processor / rank operator. The main conceptual challenge remaining is that of array lifetime. For example, I can write a function that takes a rank R lazy array and a number of leading axes N, and that returns a rank R minus N lazy array whose elements are Common Lisp arrays of rank N containing the elements of the first N axes. However, these Common Lisp arrays would then all be managed by the garbage collector.

Alternatively, I could introduce an array-processor mechanism that uses a similar calling convention as the functions returned by evaluator. We could then declare that the contents of each argument and result array are unspecified once the processing function returns, so that their memory can be reused.

I'm leaning towards the latter approach with the evaluator-like interface.

[kchanqvq]

Thanks for sharing your code! I will try to see how low I can get the overhead, but I'm not sure whether I can make it competitive for < 100 elements. It is a nice challenge, though :)

Thanks! I guess we don't need to worry too much about overhead for < 100 elements for now. After restructuring my code, they stop being a problem.

Alternatively, I could introduce an array-processor mechanism that uses a similar calling convention as the functions returned by evaluator. We could then declare that the contents of each argument and result array are unspecified once the processing function returns, so that their memory can be reused.

Indeed! This is also what comes to my mind. One remaining question: should the arrays be of type simple-array or array? It's easier to write fast (on SBCL at least) Common Lisp functions on simple-array. I recently come to discover that, with a helper function resolve-array that finds the storage vector and offset of non-simple arrays, it's probably just as easy to get good performance for non-simple array. Can displaced arrays make use of "native" memory representation of Petalisp without copying? If that's the case then we can expect array-processor to run almost as fast as native Petalisp code.

By the way, the Common Lisp backend is already really fast, congratulations! For my workload, the generated code delivers similar performance to C++, and of course, faster than NumPy solution I used before. It also compiles order of magnitudes faster, to the extent that #31 become a non-issue, compiling new kernels at 60fps. I have since switched to lisp-compiler-mixin as my daily driver. Imagine what is possible after we have SIMD! (No rush, it's already competitively fast)

[marcoheisig]

should the arrays be of type simple-array or array

Right now compute coerces all arrays to simple arrays, but since native backend operates on raw pointers anyway, I can easily extend it to support displaced arrays, too. Fun fact: the reason why the native backend operates on raw pointers is because I want to use it on Numpy arrays once https://github.com/marcoheisig/lang is operational.

By the way, the Common Lisp backend is already really fast, congratulations!

Thanks! I really hate having to compile to C++ for the last bit of performance, and you cannot imagine how eager I am to ditch all that in favor of sb-simd.