nullprogram.com/blog/2018/06/10/
In the past year I’ve written a number of minimalist C libraries,
particularly header libraries. The distinction for “minimalist” is, of
course, completely arbitrary and subjective. My definition in this
context isn’t about the library’s functionality being stupidly
trivial or even necessarily simple. I’m talking about
interface (API) complexity and the library’s run time requirements.
Complex functionality can, in some cases, be tucked behind a simple
interface.
In this article I’ll give my definition for minimalist C API, then take
you through some of my own recent examples.
Minimalist properties
A minimalist C library would generally have these properties.
(1) Small number of functions, perhaps even as little as one.
This one’s pretty obvious. More functions means more surface area in
the interface. Since these functions typically interact, the
relationship between complexity and number of functions will be
superlinear.
(2) No dynamic memory allocations.
The library mustn’t call malloc() internally. It’s up to the caller
to allocate memory for the library. What’s nice about this is that
it’s completely up to the application exactly how memory is allocated.
Maybe it’s using a custom allocator, or it’s not linked against the
standard library.
A common approach is for the application to provide allocation functions
to the library — e.g. function pointers at run time, or define functions
with specific, expected names. The library would call these instead of
malloc() and free(). While that’s perfectly reasonable, it’s not
really minimalist, so I’m not including this technique.
Instead a minimalist API is designed such that it’s natural for the
application to make the allocations itself. Perhaps the library only
needs a single, fixed allocation for all its operations. Or maybe the
application specifies its requirements and the library communicates
how much memory is needed to meet those requirements. I’ll give
specific examples shortly.
One nice result of this property is that it eliminates one of the
common failure conditions: the out of memory error. If the library
doesn’t allocate memory, then it can’t run out of it!
Another convenient, minor outcome is the lack of casts from void * to
the appropriate type (e.g. on the return from malloc()). These casts
are implicit in C but must be made explicit in C++. Often, completely by
accident, my minimalist C libraries can be compiled as C++ without any
changes. This is only a minor benefit since these casts could be made
explicit in C, too, if C++ compatibility was desired. It’s just ugly.
In simple terms, the library mustn’t use functions from stdio.h —
with the exception of the sprintf() family. Like with memory
allocation, it leaves input and output to the application, letting it
decide exactly how, where, and when information comes and goes.
Like with memory allocation, maybe the application prefers not to use
the C standard library’s buffered IO. Perhaps the application is using
cooperative or green threads, and it would be bad for the
library to block internally on IO.
Also like avoiding memory allocation, a library that doesn’t perform IO
can’t have IO errors. Combined, this means it’s quite possible that a
minimalist library may have no error cases at all. Eliminating those
error handling paths makes the library a lot simpler. The one major
error condition left that’s difficult to eliminate are those pesky
integer overflow checks.
Communicating IO preferences to libraries can be a real problem with
C, since the standard library lacks generic input and output. Putting
FILE * pointers directly into an API mingles it with the C standard
library in potentially bad ways. Passing file names as strings is an
option, but this limits IO to files — versus, say, sockets. On POSIX
systems, at least it could talk about IO in terms of file descriptors,
but even that’s not entirely flexible — e.g. output to a memory
buffer, or anything not sufficiently file-like.
Again, a common way to deal with this is for the application to
provide IO function pointers to the library. But a minimalist
library’s API would be designed such that not even this is needed,
instead operating strictly on buffers. I’ll also have a couple
examples of this shortly.
With IO and memory allocation out of the picture, another frequent,
accidental result is no dependency on the C standard library. The only
significant functionality left in the standard library are the
mathematical functions (math.h), float parsing, and a few of
the string functions (string.h), like memset() and memmove().
These are valuable since they’re handled specially by the
compiler.
(4) Define at most one structure, and perhaps even none.
More types means more complexity, perhaps even more so than having lots
of functions. Some minimalist libraries can be so straightforward that
they can operate solely on simple, homogeneous buffers. I’ll show some
examples of this, too.
As I said initially, minimalism is about interface, not implementation.
The library is free to define as many structures internally as it needs
since the application won’t be concerned with them.
One common way to avoid complicated types in an API is to make them
opaque. The structures aren’t defined in the API, and instead the
application only touches pointers, making them like handles.
struct foo;
struct foo *foo_create(...);
int foo_method(struct foo *, ...);
void foo_destroy(struct foo *);
However, this is difficult to pull off when the library doesn’t allocate
its own memory.
Bitmap library
The first example is a library for creating bitmap (BMP) images. As you
may already know, I strongly prefer Netpbm, which is so simple
that it doesn’t even need a library. But nothing is quite so universally
supported as BMP.
24-bit BMP (Bitmap) ANSI C header library
This library is a perfect example of minimalist properties 2, 3, and 4.
It also doesn’t use any of the C standard library, though only by
accident.
It’s not a general purpose BMP library. It only supports 24-bit true
color, ignoring most BMP features such as palettes. Color is
represented as a 24-bit integer, packed 0xRRGGBB.
unsigned long bmp_size(long width, long height);
void bmp_init(void *, long width, long height);
void bmp_set(void *, long x, long y, unsigned long color);
unsigned long bmp_get(const void *, long x, long y);
Strictly speaking, even the bmp_get() function could be tossed since
the library is not intended to load external bitmap images. The
application really shouldn’t need to read back previously set pixels.
There is no allocation, no IO, and no data structures. The application
indicates the dimensions of image it wants to create, and the library
says how large of a buffer it needs. The remaining functions all operate
on this opaque buffer. To write the image out, the application only
needs to dump the buffer to a file.
Here’s a complete, strict error checking example of its usage:
#define RED 0xff0000UL
#define BLUE 0x0000ffUL
unsigned long size = bmp_size(width, height);
if (!size || size > SIZE_MAX) die("invalid dimensions");
void *bmp = calloc(size, 1);
if (!bmp) die("out of memory");
bmp_init(bmp, width, height);
/* Checkerboard pattern */
for (long y = 0; y < height; y++)
for (long x = 0; x < width; x++)
bmp_set(bmp, x, y, x % 2 == y % 2 ? RED : BLUE);
if (!fwrite(bmp, size, 1, out))
die("output error");
free(bmp);
The only library function that can fail is bmp_size(). When the
given image dimensions would overflow one of the BMP header fields, it
returns zero to indicate as such.
In bmp_set(), how does it know the dimensions of the image so that
it can find the pixel? It reads that from the buffer just like a BMP
reader would — and in a endian-agnostic manner. There are
no bounds checks — that’s the caller’s job — so it only needs to read
the image’s width in order to find the pixel’s location.
Since IO is under control of the application, it can always choose load
the original buffer contents back from a file, allowing a minimal sort
of BMP loading. However, this only works for trusted input as there
are no validation checks on the buffer.
32-bit integer hash set library
The second example is an integer hash set library. It uses closed
hashing. I initially wrote this for r/dailyprogrammer solution and
then formalized it into a little reusable library.
C99 32-bit integer hash set header library
Here’s the entire API:
int set32_z(uint32_t max);
void set32_insert(uint32_t *table, int z, uint32_t v);
void set32_remove(uint32_t *table, int z, uint32_t v);
int set32_contains(uint32_t *table, int z, uint32_t v);
Again, it’s a good example of properties 2, 3, and 4. Like the BMP
library, the application indicates the maximum number of integers it
will store in the hash set, and the library returns the power of two
number of uint32_t it needs to allocate (and zero-initialize).
In this API I’m just barely skirting not defining a data structure.
The caller must pass both the table pointer and the power of two size,
and these two values would normally be bundled together into a
structure.
int z = set32_z(max);
unsigned long long n = 1ULL << z;
if (n > SIZE_MAX) die("table too large");
uint32_t *table = calloc(sizeof(*table), n);
if (!table) die("out of memory");
set32_insert(table, z, value);
if (set32_contains(table, z, value))
/* ... */;
set32_remove(table, z, value);
free(table);
Iteration is straightforward, which is why it’s not in the API: visit
each element in the allocated buffer. Zeroes are empty slots.
If a different maximum number of elements is needed, the application
initializes a new, separate table, then iterates over the old table
inserting each integer in turn.
Perhaps the most interesting part of the API is that it has no errors.
No function can fail.
Also, like the BMP library, it accidentally doesn’t use the standard
library, except for a typedef from stdint.h.
Fantasy name generator
Nearly a decade ago I cloned in Perl the RinkWorks Fantasy Name
Generator. This version was slow and terrible, and I’m sometimes
tempted to just delete it.
A few years later I rewrote it in JavaScript using an entirely
different approach. In order to improve performance, it has a template
compilation step. The compiled template is a hierarchical composition of
simple generator objects. It’s much faster, and easily enabled some
extensions to the syntax.
Germán Méndez Bravo ported the JavaScript version to C++. This
C++ implementation was recently adopted into IVAN, a
roguelike game.
This recent commotion made me realize something: I hadn’t yet
implemented it in C! So I did.
Fantasy name generator ANSI C header library
The entire API is just a single function with four possible return
values. It’s a perfect example of minimalist property 1.
#define NAMEGEN_SUCCESS 0
#define NAMEGEN_TRUNCATED 1 /* Output was truncated */
#define NAMEGEN_INVALID 2 /* Pattern is invalid */
#define NAMEGEN_TOO_DEEP 3 /* Exceeds maximum nesting depth */
int namegen(char *dest,
size_t len,
const char *pattern,
unsigned long *seed);
There’s no template compilation step, and it generates names straight
from the template.
There are three kinds of errors.
-
If the output buffer wasn’t large enough, it warns about the name
being truncated.
-
The template could be invalid — e.g. incorrectly paired brackets.
-
The template could have too much nesting. I decided to hard code the
maximum nesting depth to a generous 32 levels. This limitation makes
the generator a lot simpler without any practical impact. It also
protects against unbounded memory usage — particularly stack
overflows — by arbitrarily complex patterns. This means it’s
perfectly safe to generate names from untrusted, arbitrarily long
input patterns.
Here’s a usage example:
char name[64];
unsigned long seed = 0xb9584b61UL;
namegen(name, sizeof(name), "!sV'i (the |)!id", &seed);
/* name = "Engia'pin the Doltolph" */
The generator supports UTF-8, almost by accident. (I’d have to go out of
my way not to support it.)
Despite the lack of a compilation step, which requires the parsing the
template for each generated name, it’s an order of magnitude faster
than the C++ version, which caught me by surprise. The high
performance is due to name generation being a single pass over the
template using reservoir sampling.
Internally it maintains a stack of “reset” pointers, each pointing
into the output buffer where the current nesting level began its
output. Each time it hits an alternation (|), it generates a random
number and decides whether or not to use the new option. The first
time it’s a 1/2 chance it chooses the new option. The second time, a
1/3 chance. The third time a 1/4 chance, and so on. When the new
option is selected, the reset pointer is used to “undo” any previous
output for the current nesting level.
The reservoir sampling means it needs to generate more random numbers
(once per option) than the JavaScript and C++ version (once per nesting
level). However, it uses its own, fast internal PRNG rather than
rand(). Generating these random numbers is basically free.
Not using rand() means that, like the previous libraries, it doesn’t
need anything from the standard library. It also has better quality
results since the typical standard library rand() is total rubbish,
both in terms of speed and quality (and typically has a PLT
penalty). Finally it means the results are identical across all
platforms for the same template and seed, which is one reason it’s part
of the API.
Another slight performance boost comes from the representation of
pattern substitutions, i.e. i will select a random “idiot” name from a
fixed selection of strings. The obvious representation is an array of
string pointers, as seen in the C++ version. However, there are a lot of
these little strings, which makes for a lot of pointers cluttering up
the relocation table. Instead, I packed it all into few small
pointerless tables, which on x86-64 are accessed efficiently via
RIP-relative addressing. It’s efficient, though not friendly to
modification.
I’m very happy with how this library turned out.
UTF-7 encoder and decoder
The last example is a UTF-7 encoder and decoder. UTF-7 is a method
for encoding arbitrary Unicode text within ASCII text, created as a
nasty hack to allow Unicode messages to be sent over ASCII-limited email
infrastructure. The gist of it is that the Unicode parts of a message
are encoded as UTF-16, then base64 encoded, then interpolated into the
ASCII stream between delimiters.
Einstein (allegedly) said “If you can’t explain it to a six year old,
you don’t understand it yourself.” The analog for programming is to
replace the six year old with a computer, and explaining an idea to a
computer is done by writing a program. I wanted to understand UTF-7, so
I implemented it.
A UTF-7 stream encoder and decoder in ANSI C
Here’s the entire API. It’s modeled a little after the zlib API.
/* utf7_encode() special code points */
#define UTF7_FLUSH -1L
/* return codes */
#define UTF7_OK -1
#define UTF7_FULL -2
#define UTF7_INCOMPLETE -3
#define UTF7_INVALID -4
struct utf7 {
char *buf;
size_t len;
/* then some "private" internal fields */
};
void utf7_init(struct utf7 *, const char *indirect);
int utf7_encode(struct utf7 *, long codepoint);
long utf7_decode(struct utf7 *);
Finally a library that defines a structure! The other fields (not shown)
hold important state information, but the application is only concerned
with buf and len: an input or output buffer. The same structure is
used for encoding and decoding, though only for one task at a time.
Following the minimalist library principle, there is no memory
allocation. When encoding a UTF-7 stream, the application’s job is to
point buf to an output buffer, indicating its length with len. Then
it feeds code points one at a time into the encoder. When the output is
full, it returns UTF7_FULL. The application must provide a new buffer
and try again.
This example usage is more complicated than I anticipated it would be.
Properly pumping code points through the encoder requires a loop (or
at least a second attempt).
char buffer[1024];
struct utf7 ctx;
utf7_init(&ctx, 0);
ctx.buf = buffer;
ctx.len = sizeof(buffer));
/* Assumes "wide character" input is Unicode */
for (;;) {
wint_t c = fgetwc(stdin);
if (c == WEOF)
break;
while (utf7_encode(ctx, c) != UTF7_OK) {
/* Flush output and reset buffer */
fwrite(buffer, sizeof(buffer), 1, stdout);
ctx.buf = buffer;
ctx.len = sizeof(buffer));
}
}
/* Flush all pending output */
while (utf7_encode(ctx, UTF7_FLUSH) != UTF7_OK) {
fwrite(buffer, sizeof(buffer), 1, stdout);
ctx.buf = buffer;
ctx.len = sizeof(buffer));
}
/* Write remaining output */
fwrite(buffer, sizeof(buffer) - ctx.len, 1, stdout);
/* Check for errors */
if (fflush(stdout))
die("output error");
if (ferror(stdin))
die("input error");
Flushing (UTF7_FLUSH) is necessary since, due to base64 encoding,
adjacent Unicode characters usually share a base64 character. Just
because a code point was absorbed into the encoder doesn’t mean it was
written into the output buffer. The encoding for that character may
depend on the next character to come. The special “flush” input forces
this out. It’s valid to flush in the middle of a stream, though this
may penalize encoding efficiency (e.g. the output may be
larger than necessary).
It’s not possible for the encoder to fail, so there are no error
conditions to worry about from the library.
Decoding is a different matter. It works almost in reverse from the
encoder: buf points to the input and the decoder is pumped to
return one code point at a time. It returns one of:
-
A non-negative value: a valid code point (including ASCII).
-
UTF7_OK: Input was exhausted. Stopping here would be valid. This is
what you should get when there’s no more input.
-
UTF7_INVALID: The input was invalid. buf points at the invalid byte.
-
UTF7_INCOMPLETE: Input was exhausted, but more is expected. If
there is no more input, then the input must have been truncated,
which is an error.
So there are two possible errors for two kinds of invalid input.
Parsing errors are unavoidable when parsing input.
Again, this library accidentally doesn’t require the standard library.
It doesn’t even depend on the compiler’s locale being
compatible with ASCII since none of its internal tables use string or
character literals. It behaves exactly the same across all conforming
platforms.
More examples
I had a few more examples in mind, but this article has gone on long
enough.
Instead I’ll save these for other articles!
nullprogram.com/blog/2018/05/31/
Emacs 26.1 was recently released. As you would expect from a
major release, it comes with lots of new goodies. Being a bit of an
Emacs Lisp enthusiast, the two most interesting new features
are generators (iter) and native threads
(thread).
Correction: Generators were actually introduced in Emacs 25.1
(Sept. 2016), not Emacs 26.1. Doh!
Generators
Generators are one of those cool language features that provide a lot of
power at a small implementation cost. They’re like a constrained form of
coroutines, but, unlike coroutines, they’re typically built entirely on
top of first-class functions (e.g. closures). This means no additional
run-time support is needed in order to add generators to a language.
The only complication is the changes the compiler. Generators are not
compiled the same way as normal functions despite looking so similar.
What’s perhaps coolest of all about lisp-family generators, including
Emacs Lisp, is that the compiler component can be implemented
entirely with macros. The compiler need not be modified at all,
making generators no more than a library, and not actually part of the
language. That’s exactly how they’ve been implemented in Emacs Lisp
(emacs-lisp/generator.el).
So what’s a generator? It’s a function that returns an iterator
object. When an iterator object is invoked (e.g. iter-next) it
evaluates the body of the generator. Each iterator is independent.
What makes them unusual (and useful) is that the evaluation is
paused in the middle of the body to return a value, saving all the
internal state in the iterator. Normally pausing in the middle of
functions isn’t possible, which is what requires the special compiler
support.
Emacs Lisp generators appear to be most closely modeled after Python
generators, though it also shares some similarities to
JavaScript generators. What makes it most like Python is the use
of signals for flow control — something I’m not personally enthused
about (though see also). When a Python generator
completes, it throws a StopItertion exception. In Emacs Lisp, it’s
an iter-end-of-sequence signal. A signal is out-of-band and avoids
the issue relying on some special in-band value to communicate the end
of iteration.
In contrast, JavaScript’s solution is to return a “rich” object wrapping
the actual yield value. This object has a done field that communicates
whether iteration has completed. This avoids the use of exceptions for
flow control, but the caller has to unpack the rich object.
Fortunately the flow control issue isn’t normally exposed to Emacs Lisp
code. Most of the time you’ll use the iter-do macro or (my preference)
the new cl-loop keyword iter-by.
To illustrate how a generator works, here’s a really simple iterator
that iterates over a list:
(iter-defun walk (list)
(while list
(iter-yield (pop list))))
Here’s how it might be used:
(setf i (walk '(:a :b :c)))
(iter-next i) ; => :a
(iter-next i) ; => :b
(iter-next i) ; => :c
(iter-next i) ; error: iter-end-of-sequence
The iterator object itself is opaque and you shouldn’t rely on any
part of its structure. That being said, I’m a firm believer that we
should understand how things work underneath the hood so that we can
make the most effective use of at them. No program should rely on the
particulars of the iterator object internals for correctness, but a
well-written program should employ them in a way that best exploits
their expected implementation.
Currently iterator objects are closures, and iter-next invokes the
closure with its own internal protocol. It asks the closure to return
the next value (:next operation), and iter-close asks it to clean
itself up (:close operation).
Since they’re just closures, another really cool thing about Emacs
Lisp generators is that iterator objects are generally readable.
That is, you can serialize them out with print and bring them back to
life with read, even in another instance of Emacs. They exist
independently of the original generator function. This will not work if
one of the values captured in the iterator object is not readable (e.g.
buffers).
How does pausing work? Well, one of other exciting new features of
Emacs 26 is the introduction of a jump table opcode, switch. I’d
lamented in the past that large cond and cl-case expressions could
be a lot more efficient if Emacs’ byte code supported jump tables. It
turns an O(n) sequence of comparisons into an O(1) lookup and jump.
It’s essentially the perfect foundation for a generator since it can
be used to jump straight back to the position where evaluation was
paused.
Buuut, generators do not currently use jump tables. The generator
library predates the new switch opcode, and, being independent of it,
its author, Daniel Colascione, went with the best option at the time.
Chunks of code between yields are packaged as individual closures. These
closures are linked together a bit like nodes in a graph, creating a
sort of state machine. To get the next value, the iterator object
invokes the closure representing the next state.
I’ve manually macro expanded the walk generator above into a form
that roughly resembles the expansion of iter-defun:
(defun walk (list)
(let (state)
(cl-flet* ((state-2 ()
(signal 'iter-end-of-sequence nil))
(state-1 ()
(prog1 (pop list)
(when (null list)
(setf state #'state-2))))
(state-0 ()
(if (null list)
(state-2)
(setf state #'state-1)
(state-1))))
(setf state #'state-0)
(lambda ()
(funcall state)))))
This omits the protocol I mentioned, and it doesn’t have yield results
(values passed to the iterator). The actual expansion is a whole lot
messier and less optimal than this, but hopefully my hand-rolled
generator is illustrative enough. Without the protocol, this iterator is
stepped using funcall rather than iter-next.
The state variable keeps track of where in the body of the generator
this iterator is currently “paused.” Continuing the iterator is
therefore just a matter of invoking the closure that represents this
state. Each state closure may update state to point to a new part of
the generator body. The terminal state is obviously state-2. Notice
how state transitions occur around branches.
I had said generators can be implemented as a library in Emacs Lisp.
Unfortunately theres a hole in this: unwind-protect. It’s not valid to
yield inside an unwind-protect form. Unlike, say, a throw-catch,
there’s no mechanism to trap an unwinding stack so that it can be
restarted later. The state closure needs to return and fall through the
unwind-protect.
A jump table version of the generator might look like the following.
I’ve used cl-labels since it allows for recursion.
(defun walk (list)
(let ((state 0))
(cl-labels
((closure ()
(cl-case state
(0 (if (null list)
(setf state 2)
(setf state 1))
(closure))
(1 (prog1 (pop list)
(when (null list)
(setf state 2))))
(2 (signal 'iter-end-of-sequence nil)))))
#'closure)))
When byte compiled on Emacs 26, that cl-case is turned into a jump
table. This “switch” form is closer to how generators are implemented in
other languages.
Iterator objects can share state between themselves if they
close over a common environment (or, of course, use the same global
variables).
(setf foo
(let ((list '(:a :b :c)))
(list
(funcall
(iter-lambda ()
(while list
(iter-yield (pop list)))))
(funcall
(iter-lambda ()
(while list
(iter-yield (pop list))))))))
(iter-next (nth 0 foo)) ; => :a
(iter-next (nth 1 foo)) ; => :b
(iter-next (nth 0 foo)) ; => :c
For years there has been a very crude way to “pause” a function and
allow other functions to run: accept-process-output. It only works in
the context of processes, but five years ago this was sufficient for me
to build primitives on top of it. Unlike this old process
function, generators do not block threads, including the user interface,
which is really important.
Threads
Emacs 26 also bring us threads, which have been attached in a very
bolted on fashion. It’s not much more than a subset of pthreads: shared
memory threads, recursive mutexes, and condition variables. The
interfaces look just like they do in pthreads, and there hasn’t been
much done to integrate more naturally into the Emacs Lisp ecosystem.
This is also only the first step in bringing threading to Emacs Lisp.
Right now there’s effectively a global interpreter lock (GIL), and
threads only run one at a time cooperatively. Like with generators, the
Python influence is obvious. In theory, sometime in the future this
interpreter lock will be removed, making way for actual concurrency.
This is, again, where I think it’s useful to contrast with JavaScript,
which was also initially designed to be single-threaded. Low-level
threading primitives weren’t exposed — though mostly because
JavaScript typically runs sandboxed and there’s no safe way to expose
those primitives. Instead it got a web worker API that exposes
concurrency at a much higher level, along with an efficient interface
for thread coordination.
For Emacs Lisp, I’d prefer something safer, more like the JavaScript
approach. Low-level pthreads are now a great way to wreck Emacs with
deadlocks (with no C-g escape). Playing around with the new
threading API for just a few days, I’ve already had to restart Emacs a
bunch of times. Bugs in Emacs Lisp are normally a lot more forgiving.
One important detail that has been designed well is that dynamic
bindings are thread-local. This is really essential for correct
behavior. This is also an easy way to create thread-local storage
(TLS): dynamically bind variables in the thread’s entrance function.
;;; -*- lexical-binding: t; -*-
(defvar foo-counter-tls)
(defvar foo-path-tls)
(defun foo-make-thread (path)
(make-thread
(lambda ()
(let ((foo-counter-tls 0)
(foo-name-tls path))
...))))
However, cl-letf “bindings” are not thread-local, which makes
this otherwise incredibly useful macro quite dangerous in the
presence of threads. This is one way that the new threading API feels
bolted on.
Building generators on threads
In my stack clashing article I showed a few different ways to
add coroutine support to C. One method spawned per-coroutine threads,
and coordinated using semaphores. With the new threads API in Emacs,
it’s possible to do exactly the same thing.
Since generators are just a limited form of coroutines, this means
threads offer another, very different way to implement them. The
threads API doesn’t provide semaphores, but condition variables can fill
in for them. To “pause” in the middle of the generator, just wait on a
condition variable.
So, naturally, I just had to see if I could make it work. I call it a
“thread iterator” or “thriter.” The API is very similar to iter:
https://github.com/skeeto/thriter
This is merely a proof of concept so don’t actually use this library
for anything. These thread-based generators are about 5x slower than
iter generators, and they’re a lot more heavy-weight, needing an
entire thread per iterator object. This makes thriter-close all the
more important. On the other hand, these generators have no problem
yielding inside unwind-protect.
Originally this article was going to dive into the details of how
these thread-iterators worked, but thriter turned out to be quite a
bit more complicated than I anticipated, especially as I worked
towards feature matching iter.
The gist of it is that each side of a next/yield transaction gets its
own condition variable, but share a common mutex. Values are passed
between the threads using slots on the iterator object. The side that
isn’t currently running waits on a condition variable until the other
side frees it, after which the releaser waits on its own condition
variable for the result. This is similar to asynchronous requests in
Emacs dynamic modules.
Rather than use signals to indicate completion, I modeled it after
JavaScript generators. Iterators return a cons cell. The car indicates
continuation and the cdr holds the yield result. To terminate an
iterator early (thriter-close or garbage collection), thread-signal
is used to essentially “cancel” the thread and knock it off the
condition variable.
Since threads aren’t (and shouldn’t be) garbage collected, failing to
run a thread-iterator to completion would normally cause a memory leak,
as the thread sits there forever waiting on a “next” that will never
come. To deal with this, there’s a finalizer is attached to the
iterator object in such a way that it’s not visible to the thread. A
lost iterator is eventually cleaned up by the garbage collector, but, as
usual with finalizers, this is only a last resort.
The future of threads
This thread-iterator project was my initial, little experiment with
Emacs Lisp threads, similar to why I connected a joystick to Emacs
using a dynamic module. While I don’t expect the current thread
API to go away, it’s not really suitable for general use in its raw
form. Bugs in Emacs Lisp programs should virtually never bring down
Emacs and require a restart. Outside of threads, the few situations
that break this rule are very easy to avoid (and very obvious that
something dangerous is happening). Dynamic modules are dangerous by
necessity, but concurrency doesn’t have to be.
There really needs to be a safe, high-level API with clean thread
isolation. Perhaps this higher-level API will eventually build on top of
the low-level threading API.
nullprogram.com/blog/2018/05/27/
Update: There’s a good discussion on Hacker News.
Over on GitHub, David Yu has an interesting performance benchmark for
function calls of various Foreign Function Interfaces (FFI):
https://github.com/dyu/ffi-overhead
He created a shared object (.so) file containing a single, simple C
function. Then for each FFI he wrote a bit of code to call this function
many times, measuring how long it took.
For the C “FFI” he used standard dynamic linking, not dlopen(). This
distinction is important, since it really makes a difference in the
benchmark. There’s a potential argument about whether or not this is a
fair comparison to an actual FFI, but, regardless, it’s still
interesting to measure.
The most surprising result of the benchmark is that
LuaJIT’s FFI is substantially faster than C. It’s about
25% faster than a native C function call to a shared object function.
How could a weakly and dynamically typed scripting language come out
ahead on a benchmark? Is this accurate?
It’s actually quite reasonable. The benchmark was run on Linux, so the
performance penalty we’re seeing comes the Procedure Linkage Table
(PLT). I’ve put together a really simple experiment to demonstrate the
same effect in plain old C:
https://github.com/skeeto/dynamic-function-benchmark
Here are the results on an Intel i7-6700 (Skylake):
plt: 1.759799 ns/call
ind: 1.257125 ns/call
jit: 1.008108 ns/call
These are three different types of function calls:
- Through the PLT
- An indirect function call (via
dlsym(3))
- A direct function call (via a JIT-compiled function)
As shown, the last one is the fastest. It’s typically not an option
for C programs, but it’s natural in the presence of a JIT compiler,
including, apparently, LuaJIT.
In my benchmark, the function being called is named empty():
And to compile it into a shared object:
$ cc -shared -fPIC -Os -o empty.so empty.c
Just as in my PRNG shootout, the benchmark calls this function
repeatedly as many times as possible before an alarm goes off.
Procedure Linkage Tables
When a program or library calls a function in another shared object,
the compiler cannot know where that function will be located in
memory. That information isn’t known until run time, after the program
and its dependencies are loaded into memory. These are usually at
randomized locations — e.g. Address Space Layout Randomization
(ASLR).
How is this resolved? Well, there are a couple of options.
One option is to make a note about each such call in the binary’s
metadata. The run-time dynamic linker can then patch in the correct
address at each call site. How exactly this would work depends on the
particular code model used when compiling the binary.
The downside to this approach is slower loading, larger binaries, and
less sharing of code pages between different processes. It’s
slower loading because every dynamic call site needs to be patched
before the program can begin execution. The binary is larger because
each of these call sites needs an entry in the relocation table. And the
lack of sharing is due to the code pages being modified.
On the other hand, the overhead for dynamic function calls would be
eliminated, giving JIT-like performance as seen in the benchmark.
The second option is to route all dynamic calls through a table. The
original call site calls into a stub in this table, which jumps to the
actual dynamic function. With this approach the code does not need to
be patched, meaning it’s trivially shared between processes.
Only one place needs to be patched per dynamic function: the entries
in the table. Even more, these patches can be performed lazily, on
the first function call, making the load time even faster.
On systems using ELF binaries, this table is called the Procedure
Linkage Table (PLT). The PLT itself doesn’t actually get patched —
it’s mapped read-only along with the rest of the code. Instead the
Global Offset Table (GOT) gets patched. The PLT stub fetches the
dynamic function address from the GOT and indirectly jumps to that
address. To lazily load function addresses, these GOT entries are
initialized with an address of a function that locates the target
symbol, updates the GOT with that address, and then jumps to that
function. Subsequent calls use the lazily discovered address.
The downside of a PLT is extra overhead per dynamic function call,
which is what shows up in the benchmark. Since the benchmark only
measures function calls, this appears to be pretty significant, but in
practice it’s usually drowned out in noise.
Here’s the benchmark:
/* Cleared by an alarm signal. */
volatile sig_atomic_t running;
static long
plt_benchmark(void)
{
long count;
for (count = 0; running; count++)
empty();
return count;
}
Since empty() is in the shared object, that call goes through the PLT.
Indirect dynamic calls
Another way to dynamically call functions is to bypass the PLT and
fetch the target function address within the program, e.g. via
dlsym(3).
void *h = dlopen("path/to/lib.so", RTLD_NOW);
void (*f)(void) = dlsym("f");
f();
Once the function address is obtained, the overhead is smaller than
function calls routed through the PLT. There’s no intermediate stub
function and no GOT access. (Caveat: If the program has a PLT entry for
the given function then dlsym(3) may actually return the address of
the PLT stub.)
However, this is still an indirect function call. On conventional
architectures, direct function calls have an immediate relative
address. That is, the target of the call is some hard-coded offset from
the call site. The CPU can see well ahead of time where the call is
going.
An indirect function call has more overhead. First, the address has to
be stored somewhere. Even if that somewhere is just a register, it
increases register pressure by using up a register. Second, it
provokes the CPU’s branch predictor since the call target isn’t
static, making for extra bookkeeping in the CPU. In the worst case the
function call may even cause a pipeline stall.
Here’s the benchmark:
volatile sig_atomic_t running;
static long
indirect_benchmark(void (*f)(void))
{
long count;
for (count = 0; running; count++)
f();
return count;
}
The function passed to this benchmark is fetched with dlsym(3) so the
compiler can’t do something tricky like convert that indirect
call back into a direct call.
If the body of the loop was complicated enough that there was register
pressure, thereby requiring the address to be spilled onto the stack,
this benchmark might not fare as well against the PLT benchmark.
Direct function calls
The first two types of dynamic function calls are simple and easy to
use. Direct calls to dynamic functions is trickier business since it
requires modifying code at run time. In my benchmark I put together a
little JIT compiler to generate the direct call.
There’s a gotcha to this: on x86-64 direct jumps are limited to a 2GB
range due to a signed 32-bit immediate. This means the JIT code has to
be placed virtually nearby the target function, empty(). If the JIT
code needed to call two different dynamic functions separated by more
than 2GB, then it’s not possible for both to be direct.
To keep things simple, my benchmark isn’t precise or very careful
about picking the JIT code address. After being given the target
function address, it blindly subtracts 4MB, rounds down to the nearest
page, allocates some memory, and writes code into it. To do this
correctly would mean inspecting the program’s own memory mappings to
find space, and there’s no clean, portable way to do this. On Linux
this requires parsing virtual files under /proc.
Here’s what my JIT’s memory allocation looks like. It assumes
reasonable behavior for uintptr_t casts:
static void
jit_compile(struct jit_func *f, void (*empty)(void))
{
uintptr_t addr = (uintptr_t)empty;
void *desired = (void *)((addr - SAFETY_MARGIN) & PAGEMASK);
/* ... */
unsigned char *p = mmap(desired, len, prot, flags, fd, 0);
/* ... */
}
It allocates two pages, one writable and the other containing
non-writable code. Similar to my closure library, the lower
page is writable and holds the running variable that gets cleared by
the alarm. It needed to be nearby the JIT code in order to be an
efficient RIP-relative access, just like the other two benchmark
functions. The upper page contains this assembly:
jit_benchmark:
push rbx
xor ebx, ebx
.loop: mov eax, [rel running]
test eax, eax
je .done
call empty
inc ebx
jmp .loop
.done: mov eax, ebx
pop rbx
ret
The call empty is the only instruction that is dynamically generated
— necessary to fill out the relative address appropriately (the minus
5 is because it’s relative to the end of the instruction):
// call empty
uintptr_t rel = (uintptr_t)empty - (uintptr_t)p - 5;
*p++ = 0xe8;
*p++ = rel >> 0;
*p++ = rel >> 8;
*p++ = rel >> 16;
*p++ = rel >> 24;
If empty() wasn’t in a shared object and instead located in the same
binary, this is essentially the direct call that the compiler would have
generated for plt_benchmark(), assuming somehow it didn’t inline
empty().
Ironically, calling the JIT-compiled code requires an indirect call
(e.g. via a function pointer), and there’s no way around this. What
are you going to do, JIT compile another function that makes the
direct call? Fortunately this doesn’t matter since the part being
measured in the loop is only a direct call.
It’s no mystery
Given these results, it’s really no mystery that LuaJIT can generate
more efficient dynamic function calls than a PLT, even if they still
end up being indirect calls. In my benchmark, the non-PLT indirect
calls were 28% faster than the PLT, and the direct calls 43% faster
than the PLT. That’s a small edge that JIT-enabled programs have over
plain old native programs, though it comes at the cost of absolutely
no code sharing between processes.
nullprogram.com/blog/2018/05/01/
Update: There are discussions on Reddit and on Hacker
News.
So far this year I’ve been bitten three times by compiler edge cases
in GCC and Clang, each time catching me totally by surprise. Two were
caused by historical artifacts, where an ambiguous specification lead
to diverging implementations. The third was a compiler optimization
being far more clever than I expected, behaving almost like an
artificial intelligence.
In all examples I’ll be using GCC 7.3.0 and Clang 6.0.0 on Linux.
x86-64 ABI ambiguity
The first time I was bit — or, well, narrowly avoided being bit — was
when I examined a missed floating point optimization in both Clang and
GCC. Consider this function:
double
zero_multiply(double x)
{
return x * 0.0;
}
The function multiplies its argument by zero and returns the result. Any
number multiplied by zero is zero, so this should always return zero,
right? Unfortunately, no. IEEE 754 floating point arithmetic supports
NaN, infinities, and signed zeros. This function can return NaN,
positive zero, or negative zero. (In some cases, the operation could
also potentially produce a hardware exception.)
As a result, both GCC and Clang perform the multiply:
zero_multiply:
xorpd xmm1, xmm1
mulsd xmm0, xmm1
ret
The -ffast-math option relaxes the C standard floating point rules,
permitting an optimization at the cost of conformance and
consistency:
zero_multiply:
xorps xmm0, xmm0
ret
Side note: -ffast-math doesn’t necessarily mean “less precise.”
Sometimes it will actually improve precision.
Here’s a modified version of the function that’s a little more
interesting. I’ve changed the argument to a short:
double
zero_multiply_short(short x)
{
return x * 0.0;
}
It’s no longer possible for the argument to be one of those special
values. The short will be promoted to one of 65,535 possible double
values, each of which results in 0.0 when multiplied by 0.0. GCC misses
this optimization (-Os):
zero_multiply_short:
movsx edi, di ; sign-extend 16-bit argument
xorps xmm1, xmm1 ; xmm1 = 0.0
cvtsi2sd xmm0, edi ; convert int to double
mulsd xmm0, xmm1
ret
Clang also misses this optimization:
zero_multiply_short:
cvtsi2sd xmm1, edi
xorpd xmm0, xmm0
mulsd xmm0, xmm1
ret
But hang on a minute. This is shorter by one instruction. What
happened to the sign-extension (movsx)? Clang is treating that
short argument as if it were a 32-bit value. Why do GCC and Clang
differ? Is GCC doing something unnecessary?
It turns out that the x86-64 ABI didn’t specify what happens with
the upper bits in argument registers. Are they garbage? Are they zeroed?
GCC takes the conservative position of assuming the upper bits are
arbitrary garbage. Clang takes the boldest position of assuming
arguments smaller than 32 bits have been promoted to 32 bits by the
caller. This is what the ABI specification should have said, but
currently it does not.
Fortunately GCC also conservative when passing arguments. It promotes
arguments to 32 bits as necessary, so there are no conflicts when
linking against Clang-compiled code. However, this is not true for
Intel’s ICC compiler: Clang and ICC are not ABI-compatible on
x86-64.
I don’t use ICC, so that particular issue wouldn’t bite me, but if I
was ever writing assembly routines that called Clang-compiled code, I’d
eventually get bit by this.
Floating point precision
Without looking it up or trying it, what does this function return?
Think carefully.
int
float_compare(void)
{
float x = 1.3f;
return x == 1.3f;
}
Confident in your answer? This is a trick question, because it can
return either 0 or 1 depending on the compiler. Boy was I confused when
this comparison returned 0 in my real world code.
$ gcc -std=c99 -m32 cmp.c # float_compare() == 0
$ clang -std=c99 -m32 cmp.c # float_compare() == 1
So what’s going on here? The original ANSI C specification wasn’t
clear about how intermediate floating point values get rounded, and
implementations all did it differently. The C99 specification
cleaned this all up and introduced FLT_EVAL_METHOD.
Implementations can still differ, but at least you can now determine
at compile-time what the compiler would do by inspecting that macro.
Back in the late 1980’s or early 1990’s when the GCC developers were
deciding how GCC should implement floating point arithmetic, the trend
at the time was to use as much precision as possible. On the x86 this
meant using its support for 80-bit extended precision floating point
arithmetic. Floating point operations are performed in long double
precision and truncated afterward (FLT_EVAL_METHOD == 2).
In float_compare() the left-hand side is truncated to a float by the
assignment, but the right-hand side, despite being a float literal,
is actually “1.3” at 80 bits of precision as far as GCC is concerned.
That’s pretty unintuitive!
The remnants of this high precision trend are still in JavaScript, where
all arithmetic is double precision (even if simulated using
integers), and great pains have been made to work around
the performance consequences of this. Until recently, Mono had
similar issues.
The trend reversed once SIMD hardware became widely available and
there were huge performance gains to be had. Multiple values could be
computed at once, side by side, at lower precision. So on x86-64, this
became the default (FLT_EVAL_METHOD == 0). The young Clang compiler
wasn’t around until well after this trend reversed, so it behaves
differently than the backwards compatible GCC on the old x86.
I’m a little ashamed that I’m only finding out about this now. However,
by the time I was competent enough to notice and understand this issue,
I was already doing nearly all my programming on the x86-64.
Built-in Function Elimination
I’ve saved this one for last since it’s my favorite. Suppose we have
this little function, new_image(), that allocates a greyscale image
for, say, some multimedia library.
static unsigned char *
new_image(size_t w, size_t h, int shade)
{
unsigned char *p = 0;
if (w == 0 || h <= SIZE_MAX / w) { // overflow?
p = malloc(w * h);
if (p) {
memset(p, shade, w * h);
}
}
return p;
}
It’s a static function because this would be part of some slick
header library (and, secretly, because it’s necessary for
illustrating the issue). Being a responsible citizen, the function
even checks for integer overflow before allocating anything.
I write a unit test to make sure it detects overflow. This function
should return 0.
/* expected return == 0 */
int
test_new_image_overflow(void)
{
void *p = new_image(2, SIZE_MAX, 0);
return !!p;
}
So far my test passes. Good.
I’d also like to make sure it correctly returns NULL — or, more
specifically, that it doesn’t crash — if the allocation fails. But how
can I make malloc() fail? As a hack I can pass image dimensions that
I know cannot ever practically be allocated. Essentially I want to
force a malloc(SIZE_MAX), e.g. allocate every available byte in my
virtual address space. For a conventional 64-bit machine, that’s 16
exibytes of memory, and it leaves space for nothing else, including
the program itself.
/* expected return == 0 */
int
test_new_image_oom(void)
{
void *p = new_image(1, SIZE_MAX, 0xff);
return !!p;
}
I compile with GCC, test passes. I compile with Clang and the test
fails. That is, the test somehow managed to allocate 16 exibytes of
memory, and initialize it. Wat?
Disassembling the test reveals what’s going on:
test_new_image_overflow:
xor eax, eax
ret
test_new_image_oom:
mov eax, 1
ret
The first test is actually being evaluated at compile time by the
compiler. The function being tested was inlined into the unit test
itself. This permits the compiler to collapse the whole thing down to
a single instruction. The path with malloc() became dead code and
was trivially eliminated.
In the second test, Clang correctly determined that the image buffer is
not actually being used, despite the memset(), so it eliminated the
allocation altogether and then simulated a successful allocation
despite it being absurdly large. Allocating memory is not an observable
side effect as far as the language specification is concerned, so it’s
allowed to do this. My thinking was wrong, and the compiler outsmarted
me.
I soon realized I can take this further and trick Clang into
performing an invalid optimization, revealing a bug. Consider
this slightly-optimized version that uses calloc() when the shade is
zero (black). The calloc() function does its own overflow check, so
new_image() doesn’t need to do it.
static void *
new_image(size_t w, size_t h, int shade)
{
unsigned char *p = 0;
if (shade == 0) { // shortcut
p = calloc(w, h);
} else if (w == 0 || h <= SIZE_MAX / w) { // overflow?
p = malloc(w * h);
if (p) {
memset(p, color, w * h);
}
}
return p;
}
With this change, my overflow unit test is now also failing. The
situation is even worse than before. The calloc() is being
eliminated despite the overflow, and replaced with a simulated
success. This time it’s actually a bug in Clang. While failing a unit
test is mostly harmless, this could introduce a vulnerability in a
real program. The OpenBSD folks are so worried about this sort of
thing that they’ve disabled this optimization.
Here’s a slightly-contrived example of this. Imagine a program that
maintains a table of unsigned integers, and we want to keep track of
how many times the program has accessed each table entry. The “access
counter” table is initialized to zero, but the table of values need
not be initialized, since they’ll be written before first access (or
something like that).
struct table {
unsigned *counter;
unsigned *values;
};
static int
table_init(struct table *t, size_t n)
{
t->counter = calloc(n, sizeof(*t->counter));
if (t->counter) {
/* Overflow already tested above */
t->values = malloc(n * sizeof(*t->values));
if (!t->values) {
free(t->counter);
return 0; // fail
}
return 1; // success
}
return 0; // fail
}
This function relies on the overflow test in calloc() for the second
malloc() allocation. However, this is a static function that’s
likely to get inlined, as we saw before. If the program doesn’t
actually make use of the counter table, and Clang is able to
statically determine this fact, it may eliminate the calloc(). This
would also eliminate the overflow test, introducing a
vulnerability. If an attacker can control n, then they can
overwrite arbitrary memory through that values pointer.
The takeaway
Besides this surprising little bug, the main lesson for me is that I
should probably isolate unit tests from the code being tested. The
easiest solution is to put them in separate translation units and don’t
use link-time optimization (LTO). Allowing tested functions to be
inlined into the unit tests is probably a bad idea.
The unit test issues in my real program, which was a bit more
sophisticated than what was presented here, gave me artificial
intelligence vibes. It’s that situation where a computer algorithm did
something really clever and I felt it outsmarted me. It’s creepy to
consider how far that can go. I’ve gotten that even from
observing AI I’ve written myself, and I know for sure no human
taught it some particularly clever trick.
My favorite AI story along these lines is about an AI that learned
how to play games on the Nintendo Entertainment System. It
didn’t understand the games it was playing. It’s optimization task was
simply to choose controller inputs that maximized memory values,
because that’s generally associated with doing well — higher scores,
more progress, etc. The most unexpected part came when playing Tetris.
Eventually the screen would fill up with blocks, and the AI would face
the inevitable situation of losing the game, with all that memory
being reinitialized to low values. So what did it do?
Just before the end it would pause the game and wait… forever.
nullprogram.com/blog/2018/04/13/
My first exposure to C and C++ was a little over 20 years ago. I
remember it being some version of Borland C++, either 4.x
or 5.x, running on Windows 95. I didn’t have a mentor, so I
did the best I could slowly working through what was probably a poorly
written beginner C++ book, typing out the examples and exercises with
little understanding. Since I didn’t learn much from the experience,
there was a 7 or 8 year gap before I’d revisit C and C++ in college.
I thought it would be interesting to revisit this software, to
reevaluate it from a far more experienced perspective. Keep in mind
that C++ wasn’t even standardized yet, and the most recent C standard
was from 1989. Given this, what was it like to be a professional
software developer using a Borland toolchain on Windows 20 years ago?
Was it miserable, made bearable only by ignorance of how much better
the tooling could be? Or maybe it actually wasn’t so bad, and these
tools are better than I expect?
Ultimately my conclusion is that it’s a little bit of both. There are
some significant capability gaps compared to today, but the core
toolchain itself is actually quite reasonable, especially for the mid
1990s.
The setup
Before getting into the evaluation, let’s discuss how I got it all up
and running. While it’s technically possible to run Windows 95 on a
modern x86-64 machine thanks to the architecture’s extreme backwards
compatibility, it’s more compatible, simpler, and safer to
virtualize it. Most importantly, I can emulate older hardware that
will have better driver support.
Despite that early start in Windows all those years ago, I’m primarily
a Linux user. The premier virtualization solution on Linux these days
is KVM, a kernel module that turns Linux into a hypervisor and
makes efficient use of hardware virtualization extensions.
Unfortunately pre-XP Windows doesn’t work well on KVM, so instead I’m
using QEmu (with KVM disabled), a hardware emulator closely
associated with KVM. Since it doesn’t take advantage of hardware
virtualization extensions, it will be slower. This is fine since my
goal is to emulate slow, 20+ year old hardware anyway.
There’s very little practical difference between Windows 95 and
Windows 98. Since Windows 98 runs a lot smoother virtualized, I
decided to go with that instead. This will be perfectly sufficient for
my toolchain evaluation.
Software
To get started, I’ll need an installer for Windows 98. I thought this
would be difficult to find, but there’s a copy available on the
Internet Archive. I don’t know how “legitimate” this is, but it works.
Since it’s running in a virtual machine without network access, I also
don’t really care if this copy is somehow infected with malware.
Internet Archive: Windows 98 Second Edition
Also on the Internet Archive is a complete copy of Borland C++ 5.02,
with the same caveats of legitimacy. It works, which is good enough for
my purposes.
Internet Archive: Borland C++ 5.02
Thank you Internet Archive!
Hardware
I’ve got my software, now to set up the virtualized hardware. First I
create a drive image:
$ qemu-image create -fqcow2 win98.img 8G
I gave it 8GB, which is actually a bit overkill. Giving Windows 98 a
virtual hard drive with modern sizes would probably break the
installer. This sort of issue is a common theme among old software,
where there may be complaints about negative available disk space due
to signed integer overflow.
I decided to give the machine 256MB of memory (-m 256). This is also a
little excessive, but I wanted to be sure memory didn’t limit Borland’s
capabilities. This amount of memory is close to the upper bound, and
going much beyond will likely cause problems with Windows 98.
For the CPU I settled on a Pentium (-cpu pentium). My original goal
was to go a little simpler with a 486 (-cpu 486), but the Windows 98
installer kept crashing when I tried this.
I experimented with different configurations for the network card, but
I couldn’t get anything to work. So I’ve disabled networking (-net
none). The only reason I’d want this is that it would be easier to
move files in and out of the virtual machine.
Finally, here’s how I ran QEmu. The last two lines are only needed when
installing.
$ qemu-system-x86_64 \
-localtime \
-cpu pentium \
-no-acpi \
-no-hpet \
-m 256 \
-hda win98.img \
-soundhw sb16 \
-vga cirrus \
-net none \
-cdrom "Windows 98 Second Edition.iso" \
-boot d
Installation
Installation is just a matter of following the instructions. You’ll
need that product key listed on the Internet Archive site.
That copy of Borland is just a big .zip file. This presents two
problems.
-
Without network access, I’ll need to figure out how to get this
inside the virtual machine.
-
This version of Windows doesn’t come with software to unzip this
file. I’d need to find and install an unzip tool first.
Fortunately I can kill two birds with one stone by converting that .zip
archive into a .iso and mounting it in the virtual machine.
unzip "BORLAND C++.zip"
genisoimage -R -J -o borland.iso "BORLAND C++"
Then in the QEmu console (C-A-2) I attach it:
change ide1-cd0 borland.iso
This little trick of generating .iso files and mounting them is how I
will be moving all the other files into the virtual machine.
Borland C++
The first thing I did was play around with with Borland IDE. This is
what I would have been using 20 years ago.
Despite being Borland C++, I’m personally most interested in its ANSI
C compiler. As I already pointed out, this software pre-dates C++’s
standardization, and a lot has changed over the past two decades. On the
other hand, C hasn’t really changed all that much. The 1999 update to
the C standard (e.g. “C99”) was big and important, but otherwise little
has changed. The biggest drawback is the lack of “declare anywhere”
variables, including in for-loop initializers. Otherwise it’s the same
as writing C today.
To test drive the IDE, I made a couple of test projects, built and ran
them with different options, and poked around with the debugger. The
debugger is actually pretty decent, especially for the 1990s. It can be
operated via the IDE or standalone, so I could use it without firing up
the IDE and making a project.
The toolchain includes an assembler, and I can inspect the compiler’s
assembly output. To nobody’s surprise this is Intel-flavored assembly,
which is very welcome. Imagining myself as a software developer
in the mid 1990s, this means I can see exactly what the compiler’s doing
as well as write some of the performance sensitive parts in assembly if
necessary.
The built-in editor is the worst part of the IDE, which is unfortunate
since it really spoils the whole experience. It’s easy to jump between
warnings and errors, it has incremental search, and it has good syntax
highlighting. But these are the only positive things I can say about it.
If I had to work with this editor full-time, I’d spend my days pretty
irritated.
Like with the debugger, the Borland people did a good job modularizing
their development tools. As part of the installation process, all of the
Borland command line tools are added to the system PATH (reminder:
this is a single-user system). This includes compiler, linker,
assembler, debugger, and even an incomplete implementation of
make.
With this, I can essentially pretend the IDE doesn’t exist and replace
that crummy editor with something better: Vim.
The last version of Vim to support MS-DOS and Windows 95/98 is Vim 7.3,
released in 2010. I download those binaries, trim a few things from my
.vimrc, and smuggle it all into my virtual machine via a
virtual CD. I’ve now got a powerful text editor in Windows 98 and my
situation has drastically improved.
Since I hardly use features added since Vim 7.3, this feels right at
home to me. I can invoke the build from Vim, and it
can populate the quickfix list from Borland’s output, so I could
actually be fairly productive in these circumstances! I’m honestly
really impressed with how well this all works together.
At this point I only have two significant annoyances:
-
Borland’s command line tools belong to that category of irritating
programs that print their version banner on every invocation.
There’s not even a command line switch to turn this off. All this
noise is quickly tiresome. The Visual Studio toolchain does
the same thing by default, though it can be turned off (-nologo).
I dislike that some GNU tools also commit this sin, but at least
GNU limits this to interactive programs.
-
The Windows/DOS command shell and console is even worse than it
is today. I didn’t think that was possible. This is back when
it was still genuinely DOS and not just pretending to be (e.g. in
NT). The worst part by far is the lack of command history. There’s
no using the up-arrow to get previous commands. There’s no tab
completion. Forward slash is not a substitute for backslash in
paths. If I wanted to improve my productivity, replacing this
console and shell would be the first priority.
Update: In an email, Aristotle Pagaltzis informed me that Windows 98
comes with DOSKEY.COM, which provides command history for
COMMAND.EXE. Alternatively there’s Enhanced DOSKEY.com, an
open source, alternative implementation that also provides tab
completion for commands and filesnames. This makes the console a lot
more usable (and, honestly, in some ways better than the modern
defaults).
Building Enchive with Borland
Last year I wrote a backup encryption tool called Enchive,
and I still use it regularly. One of my design goals was high
portability since it may be needed to decrypt something important in
the distant future. It should be as bit-rot-proof as
possible. In software, the best way to future-proof is to
past-proof.
If I had a time machine that could send source code back in time, and
I sent Enchive to a competant developer 20 years ago, would they be
able to compile it and run it? If the answer is yes, then that means
Enchive already has 20 years of future-proofing built into it.
To accomplish this, Enchive is 3,300 lines of strict ANSI C,
1989-style, with no dependencies other than the C standard library and
a handful of operating system functions — e.g. functionality not in
the C standard library. In practice, any ANSI C compiler targeting
either POSIX, or Windows 95 or later, should be able to compile it.
My Windows 98 virtual machine includes an ANSI C compiler, and can be
used to simulate this time machine. I generated an “amalgamation” build
(make amalgamation) — essentially a concatenation of all the source
files — and sent this into the virtual machine. Before Borland was able
to compile it, I needed to make three small changes.
First, Enchive includes stdint.h to get fixed-width integers needed
for the encryption routines. This header comes from C99, and C89 has
no equivalent. I anticipated this problem from the beginning and made
it easy for the person performing the build to correct it. This header
is included exactly once, in config.h, and this is placed at the top
of the amalgamation build. The include only needs to be replaced with
a handful of manual typedefs. For Borland that looks like this:
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned long uint32_t;
typedef unsigned __int64 uint64_t;
typedef long int32_t;
typedef __int64 int64_t;
#define INT8_C(n) (n)
#define INT16_C(n) (n)
#define INT32_C(n) (n##U)
Second, in more recent versions of Windows, GetFileAttributes() can
return the value INVALID_FILE_ATTRIBUTES. Checking for an error that
cannot happen is harmless, but this value isn’t defined in Borland’s
SDK. I only had to eliminate that check.
Third, the CryptGenRandom() interface isn’t defined in
Borland’s SDK. This is used by Enchive to generate keys. MSDN reports
this function wasn’t available until Windows XP, but it’s definitely
there in Windows 98, exported by ADVAPI32.dll. I’m able to call it,
though it always reports an error. Perhaps it’s been disabled in this
version due to cryptographic export restrictions?
Regardless of what’s wrong, I ripped this out and replaced it with a
fatal error. This version of Enchive can’t generate new keys — unless
derived from a passphrase — nor encrypt files, including the use of a
protection key to encrypt the secret key. However, it can decrypt
files, which is the important part that needs to be future-proofed.
With this three changes — which took me about 10 minutes to sort out —
Enchive builds and runs, and it correctly decrypts files I encrypted on
Linux. So Enchive has at least 20 years of past-proofing! The
screenshot at the top of this article shows it running successfully in
an MS-DOS console window.
What’s wrong? What’s missing?
I mentioned that there were some gaps. The most obvious is the lack of
the standard POSIX utilities, especially a decent shell. I don’t know if
any had been ported to Windows in the mid 1990s. But that could be
solved one way or another without too much trouble, even if it meant
doing some of that myself.
No, the biggest capability I’d miss, and which wouldn’t be easily
obtained, is Git, or a least a decent source control system. I really
don’t want to work without proper source control. Git’s support for
Windows is second tier, and the port to modern Windows is already a
bit of a hack. Getting it to run in Windows 98 would probably be a
challenge, especially if I had to compile it with Borland.
The other major issue is the lack of stability. In this experiment, I’ve
been seeing this screen a lot:
I remember Windows crashing a lot back in those days, and it certainly
had a bad reputation for being unstable, but this is far worse than I
remembered. While the hardware emulator may be somewhat at fault here,
keep in mind that I never installed third party drivers. Most of these
crashes are Windows’ fault. I found I can reliably bring the whole
system down with a single GetProcAddress() call on a system DLL. The
only way I can imagine this instability was so tolerated back then was
general ignorance that computing could be so much better.
I was tempted to write this article in Vim on Windows 98, but all this
crashing made me too nervous. I didn’t want some stupid filesystem
corruption to wipe out my work. Too risky.
A better alternative
If I was stuck working in Windows 98 — or was at least targeting it as a
platform — but had access to a modern tooling ecosystem, could I do
better than Borland? Yes! Programs built by Mingw-w64 can be
run even as far back as Windows 95.
Now, there’s a catch. I thought it would be this simple:
$ i686-w64-mingw32-gcc -Os hello.c
But when I brought the resulting binary into the virtual machine it
crashed when ran it: illegal instruction. Turns out it contained a
conditional move (cmov) which is an instruction not available until
the Pentium Pro (686). The “pentium” emulation is just a 586.
I tried to disable cmov by picking the specific architecture:
$ i686-w64-mingw32-gcc -march=pentium -Os hello.c
This still didn’t work because the statically-linked part of the CRT
contained the cmov. I’d have to recompile that as well.
I could have switched the QEmu options to “upgrade” to a Pentium Pro,
but remember that my goal was really the 486. Fortunately this was easy
to fix: compile my own Mingw-w64 cross-compiler. I’ve done this a number
of times before, so I knew it wouldn’t be difficult.
I could go step by step, but it’s all fairly well documented in the
Mingw-64 “howto-build” document. I used GCC 7.3 (the latest version),
and for the target I picked “i486-w64-mingw32”. When it was done I could
compile binaries on Linux to run in my Windows 98 virtual machine:
$ i486-w64-mingw32-gcc -Os hello.c
This should enable quite a bit of modern software to run inside my
virtual machine if I so wanted. I didn’t actually try this (yet?),
but, to take this concept all the way, I could use this cross-compiler
to cross-compile Mingw-w64 itself to run inside the virtual machine,
directly replacing Borland C++.
And the only thing I’d miss about Borland is its debugger.
nullprogram.com/blog/2018/03/27/
For the past couple of months I’ve been using a custom package manager
to manage a handful of software packages within various unix-like
environments. Packages are installed in my home directory under
~/.local/bin, and the package manager itself is just a 110 line Bourne
shell script. It’s is not intended to replace the system’s package
manager but, instead, compliment it in some cases where I need more
flexibility. I use it to run custom versions of specific pieces of
software — newer or older than the system-installed versions, or with my
own patches and modifications — without interfering with the rest of
system, and without a need for root access. It’s worked out really
well so far and I expect to continue making heavy use of it in the
future.
It’s so simple that I haven’t even bothered putting the script in its
own repository. It sits unadorned within my dotfiles repository with the
name qpkg (“quick package”):
Sitting alongside my dotfiles means it’s always there when I need it,
just as if it was a built-in command.
I say it’s crude because its “install” (-I) procedure is little more
than a wrapper around tar. It doesn’t invoke libtool after installing a
library, and there’s no post-install script — or postinst as Debian
calls it. It doesn’t check for conflicts between packages, though
there’s a command for doing so manually ahead of time. It doesn’t manage
dependencies, nor even have them as a concept. That’s all on the user to
screw up.
In other words, it doesn’t attempt solve most of the hard problems
tackled by package managers… except for three important issues:
-
It provides a clean, guaranteed-to-work uninstall procedure. Some
Makefiles do have a token “uninstall” target, but it’s often
unreliable.
-
Unlike blindly using a Makefile “install” target, I can check for
conflicts before installing the software. I’ll know if and how a
package clobbers an already-installed package, and I can manage, or
ignore, that conflict manually as needed.
-
It produces a compact, reusable package file that I can reinstall
later, even on a different machine (with a couple of caveats). I
don’t need to keep around the original source and build directories
should I want to install or uninstall later. I can also rapidly
switch back and forth between different builds of the same software.
The first caveat is that the package will be configured for exactly my
own home directory, so I usually can’t share it with other users, or
install it on machines where I have a different home directory. Though I
could still create packages for different installation prefixes.
The second caveat is that some builds tailor themselves by default to
the host (e.g. -march=native). If care isn’t taken, those packages may
not be very portable. This is more common than I had expected and has
mildly annoyed me.
Birth of a package manager
While the package manager is new, I’ve been building and installing
software in my home directory for years. I’d follow the normal process
of setting the install prefix to $HOME/.local, running the build,
and then letting the “install” target do its thing.
$ tar xzf name-version.tar.gz
$ cd name-version/
$ ./configure --prefix=$HOME/.local
$ make -j$(nproc)
$ make install
This worked well enough for years. However, I’ve come to rely a lot on
this technique, and I’m using it for increasingly sophisticated
purposes, such as building custom cross-compiler toolchains.
A common difficulty has been handling the release of new versions of
software. I’d like to upgrade to the new version, but lack a way to
cleanly uninstall the previous version. Simply clobbering the old
version by installing it on top usually works. Occasionally it
wouldn’t, and I’d have to blow away ~/.local and start all over again.
With more and more software installed in my home directory, restarting
has become more and more of a chore that I’d like to avoid.
What I needed was a way to track exactly which files were installed so
that I could remove them later when I needed to uninstall. Fortunately
there’s a widely-used convention for exactly this purpose: DESTDIR.
It’s expected that when a Makefile provides an “install” target, it
prefixes the installation path with the DESTDIR macro, which is
assigned to the empty string by default. This allows the user to install
the software to a temporary location for the purposes of packaging.
Unlike the installation prefix (--prefix) configured before the build
began, the software is not expected to function properly when run in the
DESTDIR location.
$ DESTDIR=_destdir
$ mkdir $DESTDIR
$ make DESTDIR=destdir install
A different tool will used to copy these files into place and actually
install it. This tool can track what files were installed, allowing them
to be removed later when uninstalling. My package manager uses the tar
program for both purposes. First it creates a package by packing up the
DESTDIR (at the root of the actual install prefix):
$ tar czf package.tgz -C $DESTDIR$HOME/.local .
So a package is nothing more than a gzipped tarball. To install, it
unpacks the tarball in ~/.local.
$ cd $HOME/.local
$ tar xzf ~/package.tgz
But how does it uninstall a package? It didn’t keep track of what was
installed. Easy! The tarball itself contains the package list, and it’s
printed with tar’s t mode.
cd $HOME/.local
for file in $(tar tzf package.tgz | grep -v '/$'); do
rm -f "$file"
done
I’m using grep to skip directories, which are conveniently listed with
a trailing slash. Note that in the example above, there are a couple of
issues with file names containing whitespace. If the file contains a
space character, it will word split incorrectly in the for loop. A
Makefile couldn’t handle such a file in the first place, but, in case
it’s still necessary, my package manager sets IFS to just a newline.
If the file name contains a newline, then my package manager relies on
a cosmic ray striking just the right bit at just the right
instant to make it all work out, because no version of tar can
unambiguously print such file names. Crossing your fingers during this
process may help.
Commands
There are five commands, each assigned to a capital letter: -B, -C,
-I, -V, and -U. It’s an interface pattern inspired by Ted
Unangst’s signify (see signify(1)). I also used this
pattern with Blowpipe and, in retrospect, wish I had also used
with Enchive.
Build (-B)
Unlike the other three commands, the “build” command isn’t essential,
and is just for convenience. It assumes the build uses an Autoconfg-like
configure script and runs it automatically, followed by make with the
appropriate -j (jobs) option. It automatically sets the --prefix
argument when running the configure script.
If the build uses something other and an Autoconf-like configure script,
such as CMake, then you can’t use the “build” command and must perform
the build yourself. For example, I must do this when building LLVM and
Clang.
Before using the “build” command, the package must first be unpacked and
patched if necessary. Then the package manager can take over to run the
build.
$ tar xzf name-version.tar.gz
$ cd name-version/
$ patch -p1 < ../0001.patch
$ patch -p1 < ../0002.patch
$ patch -p1 < ../0003.patch
$ cd ..
$ mkdir build
$ cd build/
$ qpkg -B ../name-version/
In this example I’m doing an out-of-source build by invoking the
configure script from a different directory. Did you know Autoconf
scripts support this? I didn’t know until recently! Unfortunately some
hand-written Autoconf-like scripts don’t, though this will
be immediately obvious.
Once qpkg returns, the program will be fully built — or stuck on a
build error if you’re unlucky. If you need to pass custom configure
options, just tack them on the qpkg command:
$ qpkg -B ../name-version/ --without-libxml2 --with-ncurses
Since the second and third steps — creating the build directory and
moving into it — is so common, there’s an optional switch for it: -d.
This option’s argument is the build directory. qpkg creates that
directory and runs the build inside it. In practice I just use “x” for
the build directory since it’s so quick to add “dx” to the command.
$ tar xzf name-version.tar.gz
$ qpkg -Bdx ../name-version/
With the software compiled, the next step is creating the package.
Create (-C)
The “create” command creates the DESTDIR (_destdir in the working
directory) and runs the “install” Makefile target to fill it with files.
Continuing with the example above and its x/ build directory:
Where “name” is the name of the package, without any file name
extension. Like with “build”, extra arguments after the package name are
passed to make in case there needs to be any additional tweaking.
When the “create” command finishes, there will be new package named
name.tgz in the working directory. At this point the source and build
directories are no longer needed, assuming everything went fine.
$ rm -rf name-version/
$ rm -rf x/
This package is ready to install, though you may want to verify it
first.
Verify (-V)
The “verify” command checks for collisions against installed packages.
It works like uninstallation, but rather than deleting files, it checks
if any of the files already exist. If they do, it means there’s a
conflict with an existing package. These file names are printed.
The most common conflict I’ve seen is in the info index (info/dir)
file, which is safe to ignore since I don’t care about it.
If the package has already been installed, there will of course be tons
of conflicts. This is the easiest way to check if a package has been
installed.
Install (-I)
The “install” command is just the dumb tar xzf explained above. It
will clobber anything in its way without warning, which is why, if that
matters, “verify” should be used first.
When qpkg returns, the package has been installed and is probably
ready to go. A lot of packages complain that you need to run libtool to
finalize an installation, but I’ve never had a problem skipping it. This
dumb unpacking generally works fine.
Uninstall (-U)
Obviously the last command is “uninstall”. As explained above, this
needs the original package that was given to the “install” command.
Just as “install” is dumb, so is “uninstall,” blindly deleting anything
listed in the tarball. One thing I like about dumb tools is that there
are no surprises.
I typically suffix the package name with the version number to help keep
the packages organized. When upgrading to a new version of a piece of
software, I build the new package, which, thanks to the version suffix,
will have a distinct name. Then I uninstall the old package, and,
finally, install the new one in its place. So far I’ve been keeping the
old package around in case I still need it, though I could always
rebuild it in a pinch.
Package by accumulation
Building a GCC cross-compiler toolchain is a tricky case that doesn’t
fit so well with the build, create, and install process illustrated
above. It would be nice for the cross-compiler to be a single, big
package, but due to the way it’s built, it would need to be five or so
packages, a couple of which will conflict (one being a subset of
another):
- binutils
- C headers
- core GCC
- C runtime
- rest of GCC
Each step needs to be installed before the next step will work. (I don’t
even want to think about cross-compiling a cross-compiler.)
To deal with this, I added a “keep” (-k) option that leaves the
DESTDIR around after creating the package. To keep things tidy, the
intermediate packages exist and are installed, but the final, big
cross-compiler package accumulates into the DESTDIR. The final
package at the end is actually the whole cross compiler in one package,
a superset of them all.
Complicated situations like these are where I can really understand the
value of Debian’s fakeroot tool.
My use case, and an alternative
The role filled by my package manager is actually pretty well suited for
pkgsrc, which is NetBSD’s ports system made available to other
unix-like systems. However, I just need something really lightweight
that gives me absolute control — even more than I get with pkgsrc — in
the dozen or so cases where I really need it.
All I need is a standard C toolchain in a unix-like environment (even a
really old one), the source tarballs for the software I need, my 110
line shell script package manager, and one to two cans of elbow grease.
From there I can bootstrap everything I might need without root access,
even in a disaster. If the software I need isn’t written in C, it
can ultimately get bootstrapped from some crusty old C compiler, which
might even involve building some newer C compilers in between. After a
certain point it’s C all the way down.
nullprogram.com/blog/2018/02/22/
This week I made a mistake that ultimately enlightened me about the
nature of function objects in Emacs Lisp. There are three kinds of
function objects, but they each behave very differently when evaluated
as objects.
But before we get to that, let’s talk about one of Emacs’
embarrassing, old missteps: eval-after-load.
Taming an old dragon
One of the long-standing issues with Emacs is that loading Emacs Lisp
files (.el and .elc) is a slow process, even when those files have
been byte compiled. There are a number of dirty hacks in place to deal
with this issue, and the biggest and nastiest of them all is the
dumper, also known as unexec.
The Emacs you routinely use throughout the day is actually a previous
instance of Emacs that’s been resurrected from the dead. Your undead
Emacs was probably created months, if not years, earlier, back when it
was originally compiled. The first stage of compiling Emacs is to
compile a minimal C core called temacs. The second stage is loading
a bunch of Emacs Lisp files, then dumping a memory image in an
unportable, platform-dependent way. On Linux, this actually requires
special hooks in glibc. The Emacs you know and love is this
dumped image loaded back into memory, continuing from where it left
off just after it was compiled. Regardless of your own feelings on the
matter, you have to admit this is a very lispy thing to do.
There are two notable costs to Emacs’ dumper:
-
The dumped image contains hard-coded memory addresses. This means
Emacs can’t be a Position Independent Executable (PIE). It can’t
take advantage of a security feature called Address Space Layout
Randomization (ASLR), which would increase the difficulty of
exploiting some classes of bugs. This might be
important to you if Emacs processes untrusted data, such as when it’s
used as a mail client, a web server or generally
parses data downloaded across the network.
-
It’s not possible to cross-compile Emacs since it can only be dumped
by running temacs on its target platform. As an experiment I’ve
attempted to dump the Windows version of Emacs on Linux using
Wine, but was unsuccessful.
The good news is that there’s a portable dumper in the works
that makes this a lot less nasty. If you’re adventurous, you can
already disable dumping and run temacs directly by setting
CANNOT_DUMP=yes at compile time. Be warned, though, that a
non-dumped Emacs takes several seconds, or worse, to initialize
before it even begins loading your own configuration. It’s also
somewhat buggy since it seems nobody ever runs it this way
productively.
The other major way Emacs users have worked around slow loading is
aggressive use of lazy loading, generally via autoloads. The major
package interactive entry points are defined ahead of time as stub
functions. These stubs, when invoked, load the full package, which
overrides the stub definition, then finally the stub re-invokes the
new definition with the same arguments.
To further assist with lazy loading, an evaluated defvar form will
not override an existing global variable binding. This means you can,
to a certain extent, configure a package before it’s loaded. The
package will not clobber any existing configuration when it loads.
This also explains the bizarre interfaces for the various hook
functions, like add-hook and run-hooks. These accept symbols — the
names of the variables — rather than values of those variables as
would normally be the case. The add-to-list function does the same
thing. It’s all intended to cooperate with lazy loading, where the
variable may not have been defined yet.
eval-after-load
Sometimes this isn’t enough and you need some some configuration to
take place after the package has been loaded, but without forcing it
to load early. That is, you need to tell Emacs “evaluate this code
after this particular package loads.” That’s where eval-after-load
comes into play, except for its fatal flaw: it takes the word “eval”
completely literally.
The first argument to eval-after-load is the name of a package. Fair
enough. The second argument is a form that will be passed to eval
after that package is loaded. Now hold on a minute. The general rule
of thumb is that if you’re calling eval, you’re probably doing
something seriously wrong, and this function is no exception. This is
completely the wrong mechanism for the task.
The second argument should have been a function — either a (sharp
quoted) symbol or a function object. And then instead of eval it
would be something more sensible, like funcall. Perhaps this
improved version would be named call-after-load or run-after-load.
The big problem with passing an s-expression is that it will be left
uncompiled due to being quoted. I’ve talked before about the
importance of evaluating your lambdas. eval-after-load not
only encourages badly written Emacs Lisp, it demands it.
;;; BAD!
(eval-after-load 'simple-httpd
'(push '("c" . "text/plain") httpd-mime-types))
This was all corrected in Emacs 25. If the second argument to
eval-after-load is a function — the result of applying functionp is
non-nil — then it uses funcall. There’s also a new macro,
with-eval-after-load, to package it all up nicely.
;;; Better (Emacs >= 25 only)
(eval-after-load 'simple-httpd
(lambda ()
(push '("c" . "text/plain") httpd-mime-types)))
;;; Best (Emacs >= 25 only)
(with-eval-after-load 'simple-httpd
(push '("c" . "text/plain") httpd-mime-types))
Though in both of these examples the compiler will likely warn about
httpd-mime-types not being defined. That’s a problem for another
day.
A workaround
But what if you need to use Emacs 24, as was the situation that
sparked this article? What can we do with the bad version of
eval-after-load? We could situate a lambda such that it’s evaluated,
but then smuggle the resulting function object into the form passed to
eval-after-load, all using a backquote.
;;; Note: this is subtly broken
(eval-after-load 'simple-httpd
`(funcall
,(lambda ()
(push '("c" . "text/plain") httpd-mime-types)))
When everything is compiled, the backquoted form evalutes to this:
(funcall #[0 <bytecode> [httpd-mime-types ("c" . "text/plain")] 2])
Where the second value (#[...]) is a byte-code object.
However, as the comment notes, this is subtly broken. A cleaner and
correct way to solve all this is with a named function. The damage
caused by eval-after-load will have been (mostly) minimized.
(defun my-simple-httpd-hook ()
(push '("c" . "text/plain") httpd-mime-types))
(eval-after-load 'simple-httpd
'(funcall #'my-simple-httpd-hook))
But, let’s go back to the anonymous function solution. What was broken
about it? It all has to do with evaluating function objects.
Evaluating function objects
So what happens when we evaluate an expression like the one above with
eval? Here’s what it looks like again.
First, eval notices it’s been given a non-empty list, so it’s probably
a function call. The first argument is the name of the function to be
called (funcall) and the remaining elements are its arguments. But
each of these elements must be evaluated first, and the result of that
evaluation becomes the arguments.
Any value that isn’t a list or a symbol is self-evaluating. That is,
it evaluates to its own value:
If the value is a symbol, it’s treated as a variable. If the value is a
list, it goes through the function call process I’m describing (or one
of a number of other special cases, such as macro expansion, lambda
expressions, and special forms).
So, conceptually eval recurses on the function object #[...]. A
function object is not a list or a symbol, so it’s self-evaluating. No
problem.
;; Byte-code objects are self-evaluating
(let ((x (byte-compile (lambda ()))))
(eq x (eval x)))
;; => t
What if this code wasn’t compiled? Rather than a byte-code object,
we’d have some other kind of function object for the interpreter.
Let’s examine the dynamic scope (shudder) case. Here, a lambda
appears to evaluate to itself, but appearances can be deceiving:
(eval (lambda ())
;; => (lambda ())
However, this is not self-evaluation. Lambda expressions are not
self-evaluating. It’s merely coincidence that the result of
evaluating a lambda expression looks like the original expression.
This is just how the Emacs Lisp interpreter is currently implemented
and, strictly speaking, it’s an implementation detail that just so
happens to be mostly compatible with byte-code objects being
self-evaluating. It would be a mistake to rely on this.
Instead, dynamic scope lambda expression evaluation is
idempotent. Applying eval to the result will return
an equal, but not identical (eq), expression. In contrast, a
self-evaluating value is also idempotent under evaluation, but with
eq results.
;; Not self-evaluating:
(let ((x '(lambda ())))
(eq x (eval x)))
;; => nil
;; Evaluation is idempotent:
(let ((x '(lambda ())))
(equal x (eval x)))
;; => t
(let ((x '(lambda ())))
(equal x (eval (eval x))))
;; => t
So, with dynamic scope, the subtly broken backquote example will still
work, but only by sheer luck. Under lexical scope, the situation isn’t
so lucky:
;;; -*- lexical-scope: t; -*-
(lambda ())
;; => (closure (t) nil)
These interpreted lambda functions are neither self-evaluating nor
idempotent. Passing t as the second argument to eval tells it to
use lexical scope, as shown below:
;; Not self-evaluating:
(let ((x '(lambda ())))
(eq x (eval x t)))
;; => nil
;; Not idempotent:
(let ((x '(lambda ())))
(equal x (eval x t)))
;; => nil
(let ((x '(lambda ())))
(equal x (eval (eval x t) t)))
;; error: (void-function closure)
I can imagine an implementation of Emacs Lisp where dynamic
scope lambda expressions are in the same boat, where they’re not even
idempotent. For example:
;;; -*- lexical-binding: nil; -*-
(lambda ())
;; => (totally-not-a-closure ())
Most Emacs Lisp would work just fine under this change, and only code
that makes some kind of logical mistake — where there’s nested
evaluation of lambda expressions — would break. This essentially
already happened when lots of code was quietly switched over to
lexical scope after Emacs 24. Lambda idempotency was lost and
well-written code didn’t notice.
There’s a temptation here for Emacs to define a closure function or
special form that would allow interpreter closure objects to be either
self-evaluating or idempotent. This would be a mistake. It would only
serve as a hack that covers up logical mistakes that lead to nested
evaluation. Much better to catch those problems early.
Solving the problem with one character
So how do we fix the subtly broken example? With a strategically
placed quote right before the comma.
(eval-after-load 'simple-httpd
`(funcall
',(lambda ()
(push '("c" . "text/plain") httpd-mime-types)))
So the form passed to eval-after-load becomes:
;; Compiled:
(funcall (quote #[...]))
;; Dynamic scope:
(funcall (quote (lambda () ...)))
;; Lexical scope:
(funcall (quote (closure (t) () ...)))
The quote prevents eval from evaluating the function object, which
would be either needless or harmful. There’s also an argument to be
made that this is a perfect situation for a sharp-quote (#'), which
exists to quote functions.
nullprogram.com/blog/2018/02/15/
I’ve put together two online, interactive, demonstrations of chaotic
motion. One is 2D and the other is 3D, but both are rendered
using WebGL — which, for me, is the most interesting part.
Both are governed by ordinary differential equations. Both are
integrated using the Runge–Kutta method, specifically RK4.
Far more knowledgeable people have already written introductions for
chaos theory, so here’s just a quick summary. A chaotic system is
deterministic but highly sensitive to initial conditions. Tweaking a
single bit of the starting state of either of my demos will quickly
lead to two arbitrarily different results. Both demonstrations have
features that aim to show this in action.
This ain’t my first chaotic system rodeo. About eight years ago I made
water wheel Java applet, and that was based on some Matlab code I
collaborated on some eleven years ago. I really hope you’re not equipped
to run a crusty old Java applet in 2018, though. (Update: now
upgraded to HTML5 Canvas.)
If you want to find either of these demos again in the future, you
don’t need to find this article first. They’re both listed in my
Showcase page, linked from the header of this site.
Double pendulum
First up is the classic double pendulum. This one’s more intuitive
than my other demo since it’s modeling a physical system you could
actually build and observe in the real world.
Source: https://github.com/skeeto/double-pendulum
I lifted the differential equations straight from the Wikipedia article
(derivative() in my code). Same for the Runge–Kutta method (rk4() in
my code). It’s all pretty straightforward. RK4 may not have been the
best choice for this system since it seems to bleed off energy over
time. If you let my demo run over night, by morning there will obviously
be a lot less activity.
I’m not a fan of buttons and other fancy GUI widgets — neither
designing them nor using them myself — prefering more cryptic, but
easy-to-use keyboard-driven interfaces. (Hey, it works well for
mpv and MPlayer.) I haven’t bothered with a mobile
interface, so sorry if you’re reading on your phone. You’ll just have
to enjoy watching a single pendulum.
Here are the controls:
- a: add a new random pendulum
- c: imperfectly clone an existing pendulum
- d: delete the most recently added pendulum
- m: toggle between WebGL and Canvas rendering
- SPACE: pause the simulation (toggle)
To witness chaos theory in action:
- Start with a single pendulum (the default).
- Pause the simulation (SPACE).
- Make a dozen or so clones (press c for awhile).
- Unpause.
At first it will appear as single pendulum, but they’re actually all
stacked up, each starting from slightly randomized initial conditions.
Within a minute you’ll witness the pendulums diverge, and after a minute
they’ll all be completely different. It’s pretty to watch them come
apart at first.
It might appear that the m key doesn’t actually do
anything. That’s because the HTML5 Canvas rendering — which is what I
actually implemented first — is really close to the WebGL rendering.
I’m really proud of this. There are just three noticeable differences.
First, there’s a rounded line cap in the Canvas rendering where the
pendulum is “attached.” Second, the tail line segments aren’t properly
connected in the Canvas rendering. The segments are stroked separately
in order to get that gradient effect along its path. Third, it’s a lot
slower, particularly when there are many pendulums to render.
In WebGL the two “masses” are rendered using that handy old circle
rasterization technique on a quad. Either a triangle fan
or pre-rendering the circle as a texture would probably have been a
better choices. The two bars are the same quad buffers, just squeezed
and rotated into place. Both were really simple to create. It’s the
tail that was tricky to render.
When I wrote the original Canvas renderer, I set the super convenient
lineWidth property to get a nice, thick tail. In my first cut at
rendering the tail I used GL_LINE_STRIP to draw a line primitive.
The problem with the line primitive is that an OpenGL implementation
is only required to support single pixel wide lines. If I wanted
wider, I’d have to generate the geometry myself. So I did.
Like before, I wasn’t about to dirty my hands manipulating a
graphite-filled wooden stick on a piece of paper to solve this
problem. No, I lifted the math from something I found on the internet
again. In this case it was a forum post by paul.houx, which
provides a few vector equations to compute a triangle strip from a
line strip. My own modification was to add a miter limit, which keeps
sharp turns under control. You can find my implementation in
polyline() in my code. Here’s a close-up with the skeleton rendered
on top in black:
For the first time I’m also using ECMAScript’s new template
literals to store the shaders inside the JavaScript source. These
string literals can contain newlines, but, even cooler, I it does
string interpolation, meaning I can embed JavaScript variables
directly into the shader code:
let massRadius = 0.12;
let vertexShader = `
attribute vec2 a_point;
uniform vec2 u_center;
varying vec2 v_point;
void main() {
v_point = a_point;
gl_Position = vec4(a_point * ${massRadius} + u_center, 0, 1);
}`;
Allocation avoidance
If you’ve looked at my code you might have noticed something curious.
I’m using a lot of destructuring assignments, which is another
relatively new addition to ECMAScript. This was part of a little
experiment.
function normalize(v0, v1) {
let d = Math.sqrt(v0 * v0 + v1 * v1);
return [v0 / d, v1 / d];
}
/* ... */
let [nx, ny] = normalize(-ly, lx);
One of my goals for this project was zero heap allocations in the
main WebGL rendering loop. There are no garbage collector hiccups
if there’s no garbage to collect. This sort of thing is trivial
in a language with manual memory management, such as C and C++. Just
having value semantics for aggregates would be sufficient.
But with JavaScript I don’t get to choose how my objects are allocated.
I either have to pre-allocate everything, including space for all the
intermediate values (e.g. an object pool). This would be clunky and
unconventional. Or I can structure and access my allocations in such a
way that the JIT compiler can eliminate them (via escape analysis,
scalar replacement, etc.).
In this case, I’m trusting that JavaScript implementations will
flatten these destructuring assignments so that the intermediate array
never actually exists. It’s like pretending the array has value
semantics. This seems to work as I expect with V8, but not so well
with SpiderMonkey (yet?), at least in Firefox 52 ESR.
Single precision
I briefly considered using Math.fround() to convince
JavaScript to compute all the tail geometry in single precision. The
double pendulum system would remain double precision, but the geometry
doesn’t need all that precision. It’s all rounded to single precision
going out to the GPU anyway.
Normally when pulling values from a Float32Array, they’re cast to
double precision — JavaScript’s only numeric type — and all operations
are performed in double precision, even if the result is stored back
in a Float32Array. This is because the JIT compiler is required to
correctly perform all the intermediate rounding. To relax this
requirement, surround each operation with a call to
Math.fround(). Since the result of doing each operation in
double precision with this rounding step in between is equivalent to
doing each operation in single precision, the JIT compiler can choose
to do the latter.
let x = new Float32Array(n);
let y = new Float32Array(n);
let d = new Float32Array(n);
// ...
for (let i = 0; i < n; i++) {
let xprod = Math.fround(x[i] * x[i]);
let yprod = Math.fround(y[i] * y[i]);
d[i] = Math.sqrt(Math.fround(xprod + yprod));
}
I ultimately decided not to bother with this since it would
significantly obscures my code for what is probably a minuscule
performance gain (in this case). It’s also really difficult to tell if
I did it all correctly. So I figure this is better suited for
compilers that target JavaScript rather than something to do by hand.
Lorenz system
The other demo is a Lorenz system with its famous butterfly
pattern. I actually wrote this one a year and a half ago but never got
around to writing about it. You can tell it’s older because I’m still
using var.
Source: https://github.com/skeeto/lorenz-webgl
Like before, the equations came straight from the Wikipedia article
(Lorenz.lorenz() in my code). They math is a lot simpler this time,
too.
This one’s a bit more user friendly with a side menu displaying all
your options. The keys are basically the same. This was completely by
accident, I swear. Here are the important ones:
- a: add a new random solution
- c: clone a solution with a perturbation
- C: remove all solutions
- SPACE: toggle pause/unpause
- You can click, drag, and toss it to examine it in 3D
Witnessing chaos theory in action is the same process as before: clear
it down to a single solution (C then a), then add
a bunch of randomized clones (c).
There is no Canvas renderer for this one. It’s pure WebGL. The tails are
drawn using GL_LINE_STRIP, but in this case it works fine that they’re
a single pixel wide. If heads are turned on, those are just GL_POINT.
The geometry is threadbare for this one.
There is one notable feature: The tails are stored exclusively in
GPU memory. Only the “head” is stored CPU-side. After it computes
the next step, it updates a single spot of the tail with
glBufferSubData(), and the VBO is actually a circular buffer. OpenGL
doesn’t directly support rendering from circular buffers, but it
does have element arrays. An element array is an additional buffer
of indices that tells OpenGL what order to use the elements in the
other buffers.
Naively would mean for a tail of 4 segments, I need 4 different
element arrays, one for each possible rotation:
array 0: 0 1 2 3
array 1: 1 2 3 0
array 2: 2 3 0 1
array 3: 3 0 1 2
With the knowledge that element arrays can start at an offset, and
with a little cleverness, you might notice these can all overlap in a
single, 7-element array:
Array 0 is at offset 0, array 1 is at offset 1, array 2 is at offset 2,
and array 3 is at offset 3. The tails in the Lorenz system are drawn
using drawElements() with exactly this sort of array.
Like before, I was very careful to produce zero heap allocations in the
main loop. The FPS counter generates some garbage in the DOM due to
reflow, but this goes away if you hide the help menu (?). This
was long enough ago that destructuring assignment wasn’t available, but
Lorenz system and rendering it were so simple that using pre-allocated
objects worked fine.
Beyond just the programming, I’ve gotten hours of entertainment
playing with each of these systems. This was also the first time I’ve
used WebGL in over a year, and this project was a reminder of just how
working with it is so pleasurable. The specification is
superbly written and serves perfectly as its own reference.