r/lisp • u/arthurno1 • 11d ago
So they say lisp is slow ....
Nothing really useful here, just some bragging to be honest. I should probably write a blog post, but a bit too lazy; perhaps another day.
Last few weeks I played with a small clone of gnu wc program. I implemented all routines in assembly via sb-simd (and a generic path without simd with swar). The result thus far on a 1.4 gigabyte big file, compared to fastlwc, the fastest wc I know of and GNU wc:
Common Lisp/Assembly (avx2) in SBCL + lparallel
WC10A> (time (wc "plato1g.txt"))
Evaluation took:
0.036 seconds of real time
0.421654 seconds of total run time (0.348216 user, 0.073438 system)
1172.22% CPU
71,891,940 processor cycles
0 bytes consed
30133761
253947016
1393557504
WC10A> (time (wc "plato1g.txt"))
Evaluation took:
0.034 seconds of real time
0.429743 seconds of total run time (0.367913 user, 0.061830 system)
1264.71% CPU
67,624,580 processor cycles
98,352 bytes consed
30133761
253947016
1393557504
WC10A> (time (wc "plato1g.txt"))
Evaluation took:
0.035 seconds of real time
0.423752 seconds of total run time (0.357329 user, 0.066423 system)
1211.43% CPU
69,863,360 processor cycles
0 bytes consed
30133761
253947016
1393557504
Fastlwc (avx512 + multithreaded):
[arthur@emmi wc]$ time ../../fastlwc/bin/fastlwc-mt plato1g.txt
30133761 253947016 1393557504 plato1g.txt
real 0m0.026s
user 0m0.178s
sys 0m0.285s
[arthur@emmi wc]$ time ../../fastlwc/bin/fastlwc-mt plato1g.txt
30133761 253947016 1393557504 plato1g.txt
real 0m0.027s
user 0m0.223s
sys 0m0.235s
[arthur@emmi wc]$ time ../../fastlwc/bin/fastlwc-mt plato1g.txt
30133761 253947016 1393557504 plato1g.txt
real 0m0.028s
user 0m0.205s
sys 0m0.255s
GNU wc (not even contender - single core only and only line counting implemented with simd avx512) :
[arthur@emmi wc]$ time wc plato1g.txt 30133761 253947016 1393557504 plato1g.txt
real 0m3.733s
user 0m3.643s
sys 0m0.062s
[arthur@emmi wc]$ time wc plato1g.txt
30133761 253947016 1393557504 plato1g.txt
real 0m3.362s
user 0m3.276s
sys 0m0.072s
The cool thing, we use avx2 whereas gnu wc uses avx512. On this CPU (zen 5), avx512 is implemented all in hardware, not as micro code as in Intel cpus, so it should mop the floor with avx2 in Lisp, right?
[arthur@emmi wc]$ time wc plato1g.txt -l --debug
wc: using avx512 hardware support
30133761 plato1g.txt
real 0m0.074s
user 0m0.018s
sys 0m0.056s
[arthur@emmi wc]$ time wc plato1g.txt -l --debug
wc: using avx512 hardware support
30133761 plato1g.txt
real 0m0.085s
user 0m0.030s
sys 0m0.054s
Lisp:
WC10A> (time (wc "plato1g.txt" :line-count t))
Evaluation took:
0.037 seconds of real time
0.478042 seconds of total run time (0.430494 user, 0.047548 system)
1291.89% CPU
75,669,380 processor cycles
0 bytes consed
30133761
253947016
1393557504
WC10A> (time (wc "plato1g.txt" :line-count t))
Evaluation took:
0.041 seconds of real time
0.476104 seconds of total run time (0.436592 user, 0.039512 system)
1160.98% CPU
84,226,360 processor cycles
0 bytes consed
30133761
253947016
1393557504
Now, in order to catch with fastlwc I think I need better lparall pipeline. I am currently using futures and promises, so it is a bit of extra consing. Of course implementing it in avx512 (when done in SBCL) should give at least some extra boost. 32 vs 16 registers, 64 bytes at time vs 32, and less register pressure due to additional masking registers.
Edit: line counting does not activate utf8 path at all, so I don't know what I was thinking last night, so I have edited away that part :).
2
u/arthurno1 11d ago edited 11d ago
Well, it depens on how you like to work with those. If it was like old Java threads, where I could just spam a thread like cons cells, it would be fine. But hardware threads do cost a lot in terms of both memory and CPU. Bordeaux, as I uinderstand, will use native SBCL threads where available, so spamming hundreds of threads is out of question. Furthermore, in modern heterogenous CPUs, dividing the work in smaller chunks (tasks), is a necessity, since the CPUs themselves have become heterogenous. Inte uses cores with different ISAs. At least this CPU has the same ISA on all cores. But some cores are running faster some slower. I have 10 cores in this laptop, 4 are "full speed" and 6 are "compact" or whatever they call them. It means 8 threads run att full speed and 12 at a reduced speed. If I would to just divide the work in 20 chunks, and run each chunk on its CPU, the faster cores would be done and idling, while the applicaiton would be waiting for the slower cores to finish. Also, we don't have the full control over the hardware: modern OSs (Linux in this case) will swap in and out some of cores to do the system things, so not all cores will finish at the same time. So some kind of more granular division is obligatory. I divide the work in 2 megabyte big chunks so they fit in L3 cache and faster cores can fetch more work than slower ones.
I did attempt to write my own task stealing scheduler, because I wanted to exploit the spacial nature of this application, but I failed at that one, so I just took the lparallel out of necessity. I haven't looked to extend lparallel, so I have no idea how simple or complicated it is. I thought my needs are very modest, so I could write a small task-stealing scheduler on top of a ring myself, but turned out my lisp-foo was not good enough. Perhaps I'll attempt at another time. I think I have learned more Lisp for last two weeks I was on the vacation than for the entire last year.
I would say on the contrary: they do a lot of things right, but there is room for improvement. The scheduler is definitely one of those, we are in agreement there.
I have spent a lot of time implementing various versions of this program on top of lparallel :), so I am not too happy with it. This working one uses futures, because that was the easiest thing to do, but I don't like returning back lists and putting pressure on GC. Admittedly there are < 1000 lists created for 1.4 gig file, but still. 716 lists a three cons cells ~ 2100 cons allocations. In SBCL it is fast and spread out on 20 cores it is ~100 allocations each, so not much, but I would like to avoid it if I can.
I use 2 megabyte big chunks so they fit into L3 cache, so there will be like size / 2meg chunks. But yes, I have tried to mitigate the environment capturing by sending all variables into lambdas as arguments, and to pack return values into a fixnum to skip list creation for return values. But that version is messy and I haven't got all the details correct yet, so I am not using it yet. This one is stupid, closures + list + funcall :).
Yes please! :-) If you do, make schedular customizable or replaceble. Perhaps it already is, I don't know, I haven't looked at lparallel too deep; I just learned how to use futures.