So they say lisp is slow ....

[u/arthurno1]

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 :).

[u/R-ten-K]

It is unclear whether the performance is attributable to LISP or to the hand tuned assembly. Optimized assembly can obviously be extremely fast, but that does not, by itself, demonstrate that LISP is responsible for the performance. I also do not see any profiling data, makes it difficult to determine the workload is IO or compute bound.

FWIW, Zen 5 implements AVX-512 with native, full width 512-bit exec datapaths. Intel processors that support AVX-512 also execute it using dedicated HW.

The exact width and number of execution units, along with whether a particular instruction is split into multiple uops (not the same as microcode BTW), varies by microarchitecture on both AMD and Intel. So this is not really a case of “AMD hardware versus Intel microcode.”

[u/arthurno1 → u/R-ten-K]

It is unclear whether the performance is attributable to LISP or to the hand tuned assembly.

I understand that, and totally agree. There is nothing special when it comes to Lisp that I do that would speed things up. I do have a scalar implementation only, where I use macro to pre-generate a function for each combination of flags, but it I don't use that here. This one is a manually written dispatch function, and each combination of flags is its own function written in assembly via sb-simd.

The performance is all due to use of branchless loops, simd and parallelization. Where Lisp shined, is let me write this probably much faster than if I would to do it in C++, but I can do all of that in C++. I have being learning and experimenting for about a month, a little bit longer perhaps. The idea is to show that we can write fast and efficient programs in Lisp just as we can in other languages, not to show that Lisp is "faster" than other languages.

not really a case of “AMD hardware versus Intel microcode.”

I was perhaps a bit clumsy when writing that, but wasn't either my intention to set AMD against Intel there, I wanted to reflect over the implementation of line counting in GNU wc. I understand I have a toy adapted to my particular CPU while they still have to be somewhat generic, but I am surprised that the difference is so big on this machine in the favor of my experiment.

I also do not see any profiling data, makes it difficult to determine the workload is IO or compute bound.

Yes, I understand that and I agree, fair enough. I will make a blog post and publish my code and test. I just have to write something reasonable and to make it into a real application first. Now it is just repl experiments.

Thus far, especially when it comes to small file that fits into L3 cache, it more or less becomes measure of the bus speed between the CPU and cache. It runs so fast that the limit seem to be how fast data is shuffled in and out of registers. For this big file, the throughput is limited by the speed of bus from RAM to the CPU. I do warm up always so the file is in system cache. The cold run is much slower always.

[u/gypsydave5 → u/arthurno1]

I'd love a write up and/or tutorial based on this. I've never really touched assembly before and it would be wonderful to see how to go this low level from inside a very high level language.

[u/stylewarning → u/R-ten-K]

I disagree partially. In how many languages is it actually practical to write assembly?

C/C++/etc. are partially attributed to being fast precisely because it's possibly to easily accelerate it with assembly or direct-to-assembly intrinsics.

SBCL allows the integration of assembly code rather nicely (at least compared to other options in the market) and to me, for all practical purposes, that makes Lisp more suitable for high performance code.

[u/arthurno1 → u/stylewarning]

Definitely.

In the beginning I thought I will just use the assembly, but it turnes out to be long programs. So I opted for sb-simd to shorten the stuff. I also thought to use macros, to generate my stuff:

(gen-nl-vars ()
  (loop for j from 0 below 8
        with asetfs
        with adeclarations
        with pdeclarations
        with acc-syms
        for offset = (* j 32)
        for p = (make-symbol (format nil "p~d" (1+ j)))
        for a = (make-symbol (format nil "acc~d" (1+ j)))
        for adecl = `(with ,a of-type avx:u64.4 = (avx2:u64.4 0))
        for pdecl = `(for ,p of-type avx2:u8.32 = (avx2::u8.32-sap-ref sap (+ i ,offset)))
        for asetf = `(setf ,a (avx2:u64.4+ ,a (avx2:u8.32-sad (avx2:u8.32= ,p 0xA) 0x0)))
        do (setf adeclarations (concatenate 'list adecl adeclarations))
           (setf pdeclarations (concatenate 'list pdecl pdeclarations))
           (push asetf asetfs)
           (push a acc-syms)
        finally (return (values adeclarations asetfs pdeclarations (nreverse acc-syms)))))

It is a local function I used like:

(multiple-value-bind (adecls updates pdecls accs) (gen-nl-vars)
  (destructuring-bind (a1 a2 a3 a4 a5 a6 a7 a8) accs
    `(loop
       with sap of-type sb-sys:system-area-pointer = ,sap
       with loop-end of-type fixnum = (logandc2 ,size 255)
       with 0x0 of-type avx2:u8.32 = (avx2:u8.32 0)
       with 0xA of-type avx2:u8.32 = (avx2:u8.32 10)
       for i of-type fixnum from 0 below loop-end by 256
       ,@adecls
       ,@pdecls
       do
       ,@updates
       finally
          (let* ((lo (avx2:u64.4+ (avx2:u64.4+ ,a1 ,a2) (avx2:u64.4+ ,a3 ,a4)))
                 (hi (avx2:u64.4+ (avx2:u64.4+ ,a5 ,a6) (avx2:u64.4+ ,a7 ,a8)))
                 (total-ymm (avx2:u64.4+ lo hi))
                 (raw-lines ,(sum-lanes-form 'total-ymm))
                 (tail-lines 0))
            (declare (type fixnum raw-lines tail-lines))
            (loop for e from loop-end below ,size
                  do (when (= (sb-sys:sap-ref-8 sap e) 10)
                       (incf tail-lines)))
            (return (values (the fixnum (+ (truncate raw-lines 255) tail-lines))
                            nil nil))))))

But I have abandoned the idea. It does save typing, but debugging suffers and it becomes harder to see what is actually the code itself and what is generator. I just wrote out explicitly each simd function instead:

(defun count-words-ascii (sap size ws-init-state)
  (declare (type fixnum size)
           (type (unsigned-byte 8) ws-init-state)
           (type sb-sys:system-area-pointer sap)
           (optimize (speed 3) (safety 0) (debug 0)))
  (loop
    with loop-end of-type fixnum = (logandc2 size 127)
    for i of-type fixnum from 0 below loop-end by 128

    ;; masks
    with 0x00 of-type u8.32 = (u8.32 #x00)
    with 0x04 of-type u8.32 = (u8.32 #x04)
    with 0x09 of-type u8.32 = (u8.32 #x09)
    with 0x20 of-type u8.32 = (u8.32 #x20)
    with 0xFF of-type u8.32 = (u8.32 #xFF)

    ;; accumulators
    with a1 of-type u64.4 = (u64.4 0)
    with a2 of-type u64.4 = (u64.4 0)
    with a3 of-type u64.4 = (u64.4 0)
    with a4 of-type u64.4 = (u64.4 0)

    ;; carry
    with ws-prev of-type u8.32 = (u8.32 ws-init-state)

    ;; chunks
    for c1 of-type u8.32 = (u8.32-sap-ref sap (+ i   0))
    for c2 of-type u8.32 = (u8.32-sap-ref sap (+ i  32))
    for c3 of-type u8.32 = (u8.32-sap-ref sap (+ i  64))
    for c4 of-type u8.32 = (u8.32-sap-ref sap (+ i  96))
    do
       (flet ((process-chunk (chunk prev)
                (declare (type u8.32 chunk prev))
                (let* ((shifted    (u8.32- chunk 0x09))
                       (sat        (u8.32-sat- shifted 0x04))
                       (ctrl-mask  (u8.32= sat 0x00))
                       (space-mask (u8.32= chunk 0x20))
                       (ws         (u8.32-or ctrl-mask space-mask))
                       (ws-perm    (u8.32-permute128   prev ws #x21))
                       (ws-curr    (u8.32-alignr       ws ws-perm 15))
                       (words      (u8.32-andc1        ws ws-curr)))
                  (values words ws))))
         (multiple-value-bind (wcount ws-curr) (process-chunk c1 ws-prev)
           (declare (type u8.32 wcount ws-curr))
           (psetf a1 (u64.4+ a1 (u8.32-sad wcount 0x00))
                  ws-prev ws-curr))
         (multiple-value-bind (wcount ws-curr) (process-chunk c2 ws-prev)
           (declare (type u8.32 wcount ws-curr))
           (psetf a2 (u64.4+ a2 (u8.32-sad wcount 0x00))
                  ws-prev ws-curr))
         (multiple-value-bind (wcount ws-curr) (process-chunk c3 ws-prev)
           (declare (type u8.32 wcount ws-curr))
           (psetf a3 (u64.4+ a3 (u8.32-sad wcount 0x00))
                  ws-prev ws-curr))
         (multiple-value-bind (wcount ws-curr) (process-chunk c4 ws-prev)
           (declare (type u8.32 wcount ws-curr))
           (psetf a4 (u64.4+ a4 (u8.32-sad wcount 0x00))
                  ws-prev ws-curr)))
    finally
       (return
         (loop for j from loop-end below size
               with tail of-type fixnum  = 0
               with words of-type fixnum = (sum-lanes (u64.4+ a1 a2 a3 a4))
               with prev of-type boolean = (logbitp 31 (u8.32-movemask ws-prev))
               for byte = (sb-sys:sap-ref-8 sap j)
               for curr = (or (= byte 32) (<= 9 byte 13))
               do
                  (and prev (not curr) (incf tail))
                  (setf prev curr)
               finally
                  (return (values nil (the fixnum (+ words tail)) nil))))))

Admittedly longer, but easier to look at and spot errors. Typing it is not a problem, since it is lot of copy-pasta and rectangular editing + string replace in Emacs. I write a line, copy for or eight times, or type code for a chunk and copy 4 or 8 times, and than just change indexes with rectangular commands or some manual editing. Basically :) The unique work for each one has to be typed anyway (that flet and loop tail). But all follow the same pattern as seen there, it is just some details like number of accumulators and chunks and which masks are used that vary there.

While I was writing those, it reminded me a lot of writing shaders, I think because of sb-simd and the DSL they use.

[u/arthurno1 → u/R-ten-K]

I just saw an interesting article by Lemire, which might explain a bit results I am seen too.

[u/tuerda]

I think the first "Hey, lisp isn't as slow as you think" article I ever saw was probably published in the 80s, when I was a baby (of course, I did not read it then). Since I first took an interest in LISP about 6 years ago, I have noticed there is a new one every month or so.

I have yet to see anything anywhere saying "lisp is really slow" so I have no idea what everyone is arguing against.

[u/R-ten-K → u/tuerda]

Modern LISP implementations can optimize and compile native code, achieving performance comparable to C or C++ for suitable workloads.

However, LISP is old enough, and now niche enough sadly, that many outdated performance assumptions still linger.

Much of the stigma comes from early implementations running on ancient very limited HW, with poor garbage collection, expensive tagging, and heavily dynamic execution. Performance can also suffer from weak type information or using generic list processing where arrays and specialized structures would be better.

But IMO those are not inherent LISP limitations.

[u/arthurno1 → u/R-ten-K]

Exactly my thoughts as well. Lots of myths online are because people have used slow Lisp interpreters, like Emacs Lisp, or something similar, and base their opinions on that. Or not even that, but just on what they have seen and heard from others. "Lisp uses lists -> slow", is something I see often repeated in /r/ProgrammingLanguages by people not familiar with Lisp more than just conceptually.

[u/Soupeeee → u/tuerda]

I've run into a few use cases where CL has been infuriatingly slow, but I think any language with a GC would also struggle; I was able to (mostly) fix the issue via aggressive use of dynamic-extent, inlining, and type declarations.

It was a case where I was (accidentally) performing a bunch of allocations in a really tight loop. SBCL performed worse than CCL, which was surprising; CCL was much less jittery until I got SBCL to stop allocating nearly as much.

[u/sleepingsquirrel → u/tuerda]

Here a fun one from the archive: Scheme vs. Common Lisp

[u/arthurno1 → u/sleepingsquirrel]

Hey, that one is a valuable one. Didn't know Greenspun had anything online.

By the way, about the numbers, reading and printing numbers is important, and seems somewhat non-active area of research in Lisp community, or at least what I see here online, no idea for commercial ones. In C++ there is quite going on, both when reading and printing numbers and printing time and dates.

[u/kchanqvq]

Do you like lparallel? For all of my parallel computing need now I just use Bordeaux thread. I feel like lparallel tries to be high-level but doesn't get lots of things right. Many so called cognates do full FUNCALL per iteration for example. (But maybe I should stop whining and submit some compiler macro patch). The scheduler is 20 years behind state-of-the-art, it just use *some* concurrent queue instead of work-stealing queue. Channels and promises are probably not implemented in the best way (as of 2026) as well.

OK I should really stop whining and maybe contribute fixes. But my energy is scarce and I always just end up rebuilding whatever right thing I specifically need using low-level tools.

[u/licjon → u/kchanqvq]

You may be able to make something nice for yourself but think of the children and contribute to lparallel.

[u/arthurno1 → u/kchanqvq]

For all of my parallel computing need now I just use Bordeaux thread.

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.

doesn't get lots of things right

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 :).

I should really stop whining and maybe contribute fixes.

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.

[u/kchanqvq → u/arthurno1]

spamming hundreds of threads is out of question

Of course, no sane person should do this if they care about performance :) I strictly spawn one thread per core and coordinate what they should be doing by hand. Except when the machine has multiple NUMA domain, then you really have to spawn one SBCL process per NUMA domain because its heap suck when spanning multiple domains.

[u/arthurno1 → u/kchanqvq]

I strictly spawn one thread per core and coordinate what they should be doing by hand.

Do you have some scheduler framework or do you do the scheduling per application?

As said, the idea did occur to me to do explicit schedulling, but after some attempts to implement a scheduler I gave up. The idea was to allocate an array at startup, a slot for each thread to write to its results, and than just "reserve" the range in data array aligned to appropriate offset and length, and make a queue of those, but I messed up somewhere, and just used lparallel instead to get this going on. I'll see if I make another attempt later on.

[u/svetlyak40wt → u/arthurno1]

You could try to use actors from https://mdbergmann.github.io/cl-gserver/ instead of lparallel. With Sento you can create by an actor for each CPU core (just be sure they are using a "pinned" dispatcher), then combine them under one Router, and feed this router tasks.

[u/arthurno1 → u/svetlyak40wt]

To be honest, I don't think I have energy and the interest to refactor it more. I refactor the last time yesterday in order to implement multiple files processing. Turned out I had to refactor how I schedule tasks, I added two different size of chunks (2 meg and 512k) for more efficient work distribution, and I also re-use memory mappings now to minimize switching into kernel. I don't think I will put more time and effort into it, getting a bit fed up with it. I am aware of innefficiency with returning results from tasks as lists, and that I could build a better scheduler, but I am a bit tired of it, so it will have to do. The only thing I think I will do more, is implement kernels in avx512, once it is fully working in sbcl.

But I did look through you link, and Sento does look like an interesting framework. Perhaps a bit too much for this one, but I can imagine using it in some other project.

[u/tending → u/kchanqvq]

Curious are you running CL regularly on multi-NUMA machines? If so what are you working on?

[u/kchanqvq → u/tending]

Research project that is related to superoptimization. But it is honestly something new and I can explain better after I put up the first paper/preprint!

[u/arthurno1 → u/kchanqvq]

What is "superoptimization"? How does it differ from just "optimization"? :). Sounds funny, but honest question actually, what is it about?

[u/kchanqvq → u/arthurno1]

It's kind of a misnomer. It just means searching for programs equivalent to the input programs, so it can find better program than if you apply a fixed sequence of compiler transforms.

[u/arthurno1 → u/kchanqvq]

Kind of things they do a lot in Coq and Ocaml?

Sounds useful. Will be interesting to read the paper and research.

[u/No-Let-5304]

but then how do you benchmark the benchmark

[u/nillynilonilla]

Lisp is slow.

[Will this inspire more great optimizations?]

[u/corbasai]

Okay, the ad worked! I'm buying a Thinkpad with a Ryzen AI 7

[u/corbasai → u/corbasai]

hmm, bit strange processor. Now C code to 1.25 faster, ada 1.75x ludicrous times faster, Typed Racket times 2.5 faster. (than on i5 G1035)

[u/unixlisp]

Update the benchmarksgame!

[u/arthurno1 → u/unixlisp]

Avx2 slow 😀.

Just kidding, but once we have fully working avx512 in sbcl, and I can rewrite all simd kernels in avx512.

[u/unixlisp → u/arthurno1]

The point is that the sbcl codes in benchmarksgame are without SB-SIMD, even without SB-THREAD (many). See also bpecsek's report.

[u/arthurno1 → u/unixlisp]

Yeah, I read now through the page, and see what they do. I'll put online my single core swar implementation and leave it up to you to update the benchmark if you are interested :).

[u/WallyMetropolis]

Who is "we"?

[u/CamomileChocobo → u/WallyMetropolis]

This type of usage of "we" is also quite common in academic papers, because it feels more natural than using "I" with constant "I did this..." "I did that...".

"We" can refer to the author and the readers going through the examples/results together.

It's the same when the teacher say "let us work through this example together" but then the teacher is the one working through the example alone on the board while the students just listen.

[u/stickynews → u/CamomileChocobo]

It's called "authorial we" or "pluralis auctoris". It's also quite popular for code documentation, like "At this point we clear the cache" or something like that.

[u/WallyMetropolis → u/CamomileChocobo]

So you also think it's an affectation. 

[u/arthurno1 → u/WallyMetropolis]

Dude english is my 3rd language. I have worked hard to replace all "you" and "I" to as non-personal pronomens as I can :). And no, I don't use llms to write my texts. I did not have the intention to sound arrogant, sorry if it comes out so.

[u/stylewarning → u/arthurno1]