It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler.
The signum(x) function that is equivalent to CMP(X, 0) can be done in 3 or 4 instructions depending on your architecture without any comparison operations:
It is such a famous example, that compilers probably optimize CMP(X, 0) to that, but I have not checked. Coincidentally, the expansion of CMP(X, 0) is on the bit hacks list.
There are a few more superoptimized mathematical operations listed here:
Definitely a microbenchmark and probably wouldn’t be generally representative of performance. This page gives pretty good standards for OS benchmarking practic, although admittedly geared more for academia https://gernot-heiser.org/benchmarking-crimes.html
I worked through this a few years ago and it is wonderful, but I found chapter 9 on the replace function totally impenetrable, so I wrote a blog post in the same dialogue style intended as a gentler prelude to it. A few people have emailed me saying they found it and it helped them. https://ahelwer.ca/post/2022-10-13-little-typer-ch9/
Aycock & Horspool came up with a 'practical' method for implementing Earley parsing (conversion to a state-machine) that has pretty humorously good performance delta over "naive" Earley, and is still reasonable to implement. Joop Leo figured out how to get the worst-case of Earley parsing down to either O(n) (left-recursive, non-ambiguous) or O(n^2) (right-recursive, non-ambiguous). That means the Earley algorithm is only O(n^3) on right-recursive, ambiguous grammars; and, if you're doing that, you're holding your language wrong.
A somewhat breathless description of all of this is in the Marpa parser documentation:
https://jeffreykegler.github.io/Marpa-web-site/
In practice, I've found that computers are so fast, that with just the Joop Leo optimizations, 'naive' Earley parsing is Good Enough™:
Examples (for Common Lisp, so not citing Emacs): reddit v1, Google's ITA Software that powers airfare search engines (Kayak, Orbitz…), Postgres' pgloader (http://pgloader.io/), which was re-written from Python to Common Lisp, Opus Modus for music composition, the Maxima CAS, PTC 3D designer CAD software (used by big brands worldwide), Grammarly, Mirai, the 3D editor that designed Gollum's face, the ScoreCloud app that lets you whistle or play an instrument and get the music score,
but also the ACL2 theorem prover, used in the industry since the 90s, NASA's PVS provers and SPIKE scheduler used for Hubble and JWT, many companies in Quantum Computing, companies like SISCOG, who plans the transportation systems of european metropolis' underground since the 80s, Ravenpack who's into big-data analysis for financial services (they might be hiring), Keepit (https://www.keepit.com/), Pocket Change (Japan, https://www.pocket-change.jp/en/), the new Feetr in trading (https://feetr.io/, you can search HN), Airbus, Alstom, Planisware (https://planisware.com),
Make sure you use zram (or zswap) as well. May also consider enabling userspace oom handler like others already suggested, but it's less important than the rest.
Except it wasn't. Common Lisp was different from most Lisps in that it was a standard and not an implementation. Implementations were different, from small to large scale. The initial CLtL1 language definition was a small part of Lisp Machine Lisp with some stuff added in (type declarations, lexical binding, ...).
CLtL1 lacked
* a way to start or quit Lisp
* command line arguments
* memory management (like garbage collection, finalization, memory areas)
* virtual machine
* threads
* stack groups
* continuations
* interrupts
* fexprs
* error handling
* object system or any way to define extensible operations
* user defined stream types
* networking
* internationlization features (like international character sets, multilanguage support, ...)
* a higher level iteration construct
* tail call elimination
* stack introspection (backtraces, ...)
* pretty printer interface
* MLISP / RLISP syntax
* library & source code management
* 'weak' data structures
* extensible hash tables
* terminal interface
* assembler
* advising
* source retrieval
* pattern matcher
* calling external programs
* locatives
* big floats
* single namespace for functions and variables
and more. None of that was in CLtL1. Much of that also is not in ANSI CL.
Read through Lisp manuals (MIT Scheme, MacLisp, MDL, Lisp Machine Lisp, Interlisp, ...) from that time (when CLtL1 was published) and much of that existed.
Implementations provided more. Just like, say, Interlisp-D (which also was an operating system with applications) provided much more than most Common Lisp implementations.
My particular interests would see me appreciating access to cache structure, cache behavior, prefetching, cache coherency, memory management unit control, instruction pipelining, and maybe register renaming control.
I am not particularly qualified to try and design a better ISA, I just know there are some things I would like the option to control at some times (or at least I imagine I would). A lot of the list above is about exposing more of the architecture to user control as a general principle. However, I’d rather see some areas of hardware design change to facilitate something other than coding paradigms and practices that stretch back nearly 40 years. Chisnall’s ‘C is not a Low Level Language’ article discusses several architectural directions I would like to see happen, but also talks about how as long as the ISA remains the same moving to new programming styles/philosophies continues to be a difficult proposition.
> Programming languages aren't just for machines to execute. There are for humans to communicate and collaborate.
"All it does is segfault!" I wake up in a cold sweat. It's still dark; a quick glance at the clock shows that it's about 3 in the morning. There's a stir besides me.
"Was it the dream again?" My wife says from the darkness to my side.
"It's fine, just go back to sleep."
She mumbles something incoherent and in a few moments she's snoring quietly. I lie down, but I already know there's no more sleep for me tonight.
+++
In the morning I arrive late in the office. I was in the parking lot at 7:30, but it took me an hour and a half to work up the nerve to walk in the building. They're at it again. The "collaborators". After we invented the perfect programming language for human communication and collaboration (we-lang) software developers took to calling themselves 'collaborators'. Today they're rehashing the same argument that they've been on for the past month.
"Michael, why are you always late? The computer is doing it again, and you know you're the only one who gets it." A loose mob of collaborators are standing around a 50 inch monitor on the wall. A half blank terminal monopolizes the screen. It seems to have been in the middle of producing log output, but now the cursor blinks lazily at a final message: "generic fault encountered".
It started with looks of confusion, then contempt, and finally resignation. And now I stare back, knowing how today is going to go. The same way as all days. "Yes, there are two problems, which is what I was trying to say yesterday. The first problem is that we're launching multiple threads and then they're all trying to modify the same unlocked data. And the second," I take a deep breath, "and the second is that the goal is kind of an open problem. We're potentially ambiguous in a few places and even if we weren't then it could take decades for the fastest computers to brute force a solution that conforms to the spec."
"Michael, we've been over this before. We all agreed that this is the nature that the UI should follow. We all agreed that this is how the back end ought to work. Why can't you, those mathematicians you keep talking about, and the computer all just get with the program. Maybe try being a team player for once." In the mob heads nod in ascent. We-Lang is perfect. Everyone agrees and understands everyone else. The collaboration between humanity has been achieved as if we were a single person. One mind. Unification.
But when we run it on the computer, all it does is segfault.
