Compile time complexity of lazy-sort

[kchanqvq]

PETALISP> (let ((vec (compute (lazy-index-components (~ (expt 2 20))))))
            (time (compute (lazy-sort vec #'<))))

This never finishes the compilation phase and drop into ldb from memory exhaustion after a few minute (with 4GB heap size SBCL).

[marcoheisig]

Tracked the problem down to quadratic cost in petalisp.core:subdivide-shapes. Larger steps of Batcher's odd-even algorithm generate fusions with hundreds of shapes, leading to very costly IR conversion.

To illustrate:

(loop for i from 10 to 14 do 
  (time
   (petalisp.ir:ir-from-lazy-arrays
    (let ((vec (make-array (expt 2 i) :initial-element 0)))
      (list
       (lazy-sort vec #'<))))))

2^10 elements: 0.18s
2^11 elements: 0.16s
2^12 elements: 0.89s
2^13 elements: 29.0s
2^14 elements: 176.2s

I think I can rewrite that code to have linear complexity, after which your issue should disappear.

[marcoheisig]

Another algorithm with quadratic complexity is in petalisp.ir:potentially-superfluous-buffer-p. When I wrote those parts in 2020, I did not anticipate 100+ non-trivial references into one lazy array :)

[marcoheisig]

Oh, wow, sorting large arrays is really the ultimate stress test. Using hash tables instead of lists for determining whether any two dendrites are mergeable in ir-conversion.lisp gives plenty of speedup:

2^10 elements: 0.05
2^11 elements: 0.10
2^12 elements: 0.20
2^13 elements: 0.61
2^14 elements: 1.60
2^15 elements: 9.64
2^16 elements: 42.12 (fun fact: this program consists of 53627 buffers and 175672 kernels)

I'll upload this change once I have polished it, because the IR conversion code is now getting a bit unwieldy.

The next bottlenecks are all related to intersections of lists of shapes, which is what I'll tackle next.

[kchanqvq]

For some reason, large dimension on the perpendicular axes also has scaling issue?

CL-USER>  (petalisp:compute (petalisp:lazy-sort (petalisp:lazy-reshape 0.0 (petalisp:~ 512)) #'<)) 
... ;; This runs fine
CL-USER> (petalisp:compute (petalisp:lazy-sort (petalisp:lazy-reshape 0.0 (petalisp:~ 512 65536)) #'<))
;; This exhausts heap

[marcoheisig]

Isn't there a tilde missing in the second case? Perpendicular would be

(petalisp:compute (petalisp:lazy-sort (petalisp:lazy-reshape 0.0 (petalisp:~ 512 petalisp:~ 65536)) #'<))

That version seems to run just fine for me.

[kchanqvq]

That version seems to run just fine for me.

Indeed! :D Sorry for the noise!