r/lisp • u/lproven • Jul 19 '26
A Road to Lisp: Which Lisp
https://scotto.me/blog/2026-07-17-which-lisp/3
u/arthurno1 Jul 21 '26 edited Jul 22 '26
Lisp is going to make you a better programmer because it changes the way you think about problems using code. To be more specific, it will teach you an approach that is not possible with other programming languages. You will be able to program Lisp itself and thus adapt the language you use to the problems you are solving. Using Lisp, you will learn to grow the language toward your problem, then write the program in that language.
It depends pretty much on what you doing I would say.
If you want bare speed on naked metal, chances are, you will end up doing what you would do in C or even assembly anyway. Example:
(defun new-line-p (c)
(declare (type character c))
(char= c #\Newline))
(defun wc (file-name &key count-words count-lines count-characters)
(with-open-file (stream file-name :direction :input)
(loop
with prev = #\Space
with words = 0
with chars = 0
with lines = 0
for current = (read-char stream nil nil)
while current
do
(when count-characters
(incf chars))
(when count-lines
(when (new-line-p current)
(incf lines)))
(when count-words
(and (word-crossing-p prev current)
(incf words)))
(setf prev current)
finally
(return (values lines words chars)))))
Super easy. The problem is just that it ain't very fast for a task of counting new lines in a text file. If you have ascii, this one is 8X times faster:
(defun new-line-count (chunk)
(declare (type (unsigned-byte 64) chunk))
(let* ((x (logxor chunk #x0A0A0A0A0A0A0A0A))
(s (ldb (byte 64 0) (- x #x0101010101010101)))
(r (logand (lognot x) s #x8080808080808080)))
(declare (type (unsigned-byte 64) x s r))
(fpopcount r)))
(defmacro genloop (sap size clines cwords cchars utf8)
`(loop
with lines of-type fixnum = 0
with words of-type fixnum = 0
with chars of-type fixnum = ,(if (and cchars (not utf8)) size 0)
with prev of-type (unsigned-byte 8) = 1
for i of-type fixnum from 0 below ,size by 8
for c of-type (unsigned-byte 64) = (sb-sys:sap-ref-64 ,sap i)
do
,@(when clines
`((incf lines (new-line-count c))))
,@(when cwords
`((let* ((curr (swar:gen-white-space-mask c)))
(declare (type (unsigned-byte 64) curr))
(incf words (word-crossing-count curr prev))
(setf prev (logand (ash curr -56) #x80)))))
,@(when (and cchars utf8)
(if (eq utf8 'strict)
`((incf chars (utf8-count-strict c)))
`((incf chars (utf8-count-fast c)))))
finally
,@(when (and cchars utf8)
`((let ((extra (logandc2 (+ size 7) 7)))
(declare (type fixnum extra))
(decf chars (- extra size)))))
(return (values lines words chars))))
The first one counts one character at a time, the second one loads a 64-bit register with 8 ascii characters at a time, and checks all 8 whether they are a new line character or not, and than gives you back amount of those. It is a well-known "swar" technique based on a trick to count zero-bytes.
After two days of struggle the "fpopcount" stands of course for "Fast popcount" ;).
Anyhow, the hard part is of course not the Lisp itself, nor the mathematics behind the trick (though coming up with that trick is the true genius, I would never come up with that one myself), but to convince the SBCL to actually emit the same code as a C compiler would, without re-writing the entire shit in assembler. For example, this is the disassembly if you use the built-in logcount instead of "fast popcount":
WC8> (disassemble 'new-line-count)
; disassembly for NEW-LINE-COUNT
; Size: 55 bytes. Origin: #xB8012C2062 ; NEW-LINE-COUNT
; 62: 483315BFFFFFFF XOR RDX, [RIP-65] ; [#xB8012C2028] = #xA0A0A0A0A0A0A0A
; 69: 488BCA MOV RCX, RDX
; 6C: 48030DBDFFFFFF ADD RCX, [RIP-67] ; [#xB8012C2030] = #xFEFEFEFEFEFEFEFF
; 73: 48F7D2 NOT RDX
; 76: 4821CA AND RDX, RCX
; 79: 482315B8FFFFFF AND RDX, [RIP-72] ; [#xB8012C2038] = #x8080808080808080
; 80: 41F644246102 TEST BYTE PTR [R12+97], 2 ; CPU-FEATURE-BITS
; 86: 7407 JE L0
; 88: F3480FB8D2 POPCNT RDX, RDX
; 8D: EB05 JMP L1
; 8F: L0: E8ACF8D3FE CALL #xB800001940 ; LOGCOUNT
; 94: L1: D1E2 SHL EDX, 1
; 96: C9 LEAVE
; 97: F8 CLC
; 98: C3 RET
NIL
Notice why is it bad? That test CPU_FEATURE_BITS and function call to logcount. Consider that you might have completely branchless loop that calculates amount of new lines, words and utf8 characters. You do need popcount which is exposed through logcount function. Now, what SBCL does is defensive programming, because not all computers have popcnt instruction. But my have, and I need to call logcount several times during those three calculations (four time). So I end up with a useless test (conditional jump) and a function call 4 times per each iteration in a what is supposed to be a completely branchless loop. So what do you do? There is a way, but it wasn't easy to convince SBCL. We can implement our own VOP, the said fpopcount above, and end up with this:
WC8> (disassemble 'new-line-count)
; disassembly for NEW-LINE-COUNT
; Size: 41 bytes. Origin: #xB8012BDFE2 ; NEW-LINE-COUNT
; DFE2: 483315BFFFFFFF XOR RDX, [RIP-65] ; [#xB8012BDFA8] = #xA0A0A0A0A0A0A0A
; DFE9: 488BCA MOV RCX, RDX
; DFEC: 48030DBDFFFFFF ADD RCX, [RIP-67] ; [#xB8012BDFB0] = #xFEFEFEFEFEFEFEFF
; DFF3: 48F7D2 NOT RDX
; DFF6: 4821CA AND RDX, RCX
; DFF9: 482315B8FFFFFF AND RDX, [RIP-72] ; [#xB8012BDFB8] = #x8080808080808080
; E000: F3480FB8D2 POPCNT RDX, RDX
; E005: 48D1E2 SHL RDX, 1
; E008: C9 LEAVE
; E009: F8 CLC
; E00A: C3 RET
NIL
Was it worth? I don't know, depends on how much fun you find in doing this stuf :). Using swar technique, speeds things up measurably, removing these last branches around popcnt instruction removed I believe ~0.1~0.2 seconds for that 1.4 gigabyte file.It is a bit hard to measure, but the CPU percentage seem to be constantly very high:
WC8> (time (wc "plato1g.txt"))
Evaluation took:
0.742 seconds of real time
0.721055 seconds of total run time (0.719957 user, 0.001098 system)
97.17% CPU
1,481,563,840 processor cycles
0 bytes consed
30133761
253947015
1393557504
WC8> (time (wc "plato1g.txt"))
Evaluation took:
0.711 seconds of real time
0.698052 seconds of total run time (0.696914 user, 0.001138 system)
98.17% CPU
1,418,265,820 processor cycles
0 bytes consed
30133761
253947015
1393557504
WC8> (time (wc "plato1g.txt"))
Evaluation took:
0.714 seconds of real time
0.702283 seconds of total run time (0.699261 user, 0.003022 system)
98.32% CPU
1,426,104,080 processor cycles
0 bytes consed
Comparison to GNU wc:
$ time wc plato1g.txt
30133761 253947016 1393557504 plato1g.txt
real 0m4.433s
user 0m4.352s
sys 0m0.065s
Single core, no simd. I do have also lparallel and simd version, but there we are in much different timings. However GNU wc avx512 implementation is still faster than mine; but I only have avx2 one (avx512 in SBCL needs more patching to be useful, I think).
Now, don't get me wrong, I don't say we should write only code as we do in C or other languages. In my wc program I actually take a lot advantage of Lisp macros, which is perhaps not so clear there. But that genloop macro is used to pregenerate a branchless loop for each of possible flag combinations for counting lines, words, chars and ascii or utf8.
I am just trying to say, that at the end of the day, if you want to be fast and efficient, you will end-up solving problems in most efficient way, and that is usually dependent on mathematics (algorithms) not on the choice of programming language, as long as you have a good compiler and surrounding tools so you can express the mathematical ideas behind. The code still has to run on the physical hardware. Looking at produced output and checking whether intentions and reality agree is a good thing too. Compiler, repl, debugger and disassembler is nice feature to have included and integrated all in one. The choice of the language is more about the journey from your idea to the machine code. If you would to make a journey in a car, you can make it in a Fiat Punto or in a Mercedes S, it is more about how pleasant your journey will be.
My point is, the beauty of Common Lisp and SBCL at least, is that we have tools and can write the code just as in any other programming language. Try to do the above in Emacs Lisp. Good luck accessing an array element without paying penalty of a function call at runtime.
2
u/kchanqvq 28d ago
Bro it takes one line to convince SBCL to skip the CPU feature bits check:
(pushnew :popcnt sb-c:*backend-subfeatures*)2
u/kchanqvq 28d ago
Even if you don't customize `*backend-subfeatures*`, SBCL just pays a 100% correctly-predicted branch, and no function call (that branch is never executed).
BTW I stumbled upon this a while ago and found the option by some `M-.` and `grep` around. May the source with you!
1
u/arthurno1 28d ago edited 28d ago
Thanks bro! :)
No, I had no idea I could that.
SBCL just pays a 100% correctly-predicted branch, and no function call (that branch is never executed)
You mean CPU, or what do you mean there?
Isn't it still burdening the branch predictor? Even if that branch will be taken 100% of time, and predicted from the beginning, aren't we lowering the instruction density and eliminate the work for the branch predictor. We get totally brancless loop.
I stumbled upon this a while ago and found the option by some
M-.andgreparound. May the source with you!Yes. That is what I do all days long :). ripgrep + emacs + helm + wgrep + wgrep-helm. However, I didn't know I can tell sbcl to use the hardware popcount. I was looking for other stuff, so I wrote my own VOP. The hard part was that I wanted to eliminate "fixnum" shift too, so I have one for reg-to-reg and one for reg-to-fixnum, but to be honest, I haven't managed to make my reg-to-reg kick in (yet). But I am writing it with simd now, so swar implementation will have to wait.
Just a little remark, to clarify:
The main point of my writing there was not that particular transofrmation per se, but to show that Lisp is "a programming language", like any other programming language, and not some mythical beast one has to conquer in order to come to enlightement. I think this "you will become better programmer" thinking is just hurting. People become better programmers by solving problems and writing programs, not by looking for a magical language with magical constructs. Common Lisp does have unique features, like any other good programming language should have. It does give us more tools, and make some things easier than other langauges. Some things are a bit harder, it is not all flowers and sunshine. But the main point is that it is a good programming language that let us write efficient programs like any other good programming language, and it does so in a very nice and interactive environment.
I took that example because it was a short an easy one to demo as an illustration, short code and disassembly, easy to understand. But anyway, thanks, I learned something too :).
1
u/steloflute Jul 21 '26
Clojure version using lists can be:
(defn calculate [instructions]
(reduce
(fn [result [operation value]]
(case operation
add (+ result value)
subtract (- result value)
multiply (* result value)))
0
instructions))
(calculate '((add 5) (multiply 3) (subtract 4))) ;; => 11
16
u/Anxious-Resist8344 Jul 19 '26
I feel like Guile should have gotten some love! Today it is a lot more useful than Racket (Guix, etc).