Wandering Thoughts archives

On Lisp's fundamental data structure

One of the joys of learning new programming languages is the aha moments when something really clicks. The biggest aha moment I've ever had was with Prolog, when an assignment went from nigh impossible to trivial in a blinding flash of obvious insight.

But the one I remember most distinctly is from years ago, when I was looking at Lisp (again), and finally realized that the fundamental data structure of Lisp is not lists but cons cells.

While the major use of cons cells is building lists, cons cells can be used for a great deal more. The most straightforward thing is binary trees, with each node being just '(left . right)' (in the traditional Lisp cons cell notation). If one wants more, Peter Seibel's Practical Common Lisp has an entire chapter called Beyond Lists: Other Uses for Cons Cells.

(Cons cells also show Lisp's roots in the very old days of computing, since they are a very simple data structure: a pair of addresses. The Lisp CAR and CDR functions even take their names from how cons cells were implemented in the first Lisp on IBM 704 computers; see here.)

What I use asserts for

Somewhat recently a discussion came up about the proper use of asserts over on Ned Batchelder's blog, with a number of people feeling that they were overused or outright misused by being applied to situations that really should have actual error recovery. (One nice phrase used was 'exploding comments'.)

I'll admit it: I use asserts in my code. I use them when I don't think something can happen in an algorithm, but I'm not absolutely sure and if I turn out to be wrong (despite my best testing and thinking about it) the code will explode. This means that my asserts are usually about post-conditions, things like 'however we exit this loop, the buffer must have been emptied', instead of pre-conditions.

(This makes 'exploding comments' not a bad description.)

Checking pre-conditions generally seems like error checking, and I think that asserts are a bad way of checking for errors, whether these are errors in the environment (such as 'out of memory') or errors in how your code is being used. The right way to deal with errors is to raise an exception or return an error status or the like, and thus to make handling them a routine and required part of the interface. (And then you should unit-test these code paths.)

Part of this thinking is due to a long exposure to the Linux kernel mailing list, where people periodically have to point out that panic()'ing on an error crashes the user's machine, so perhaps your code could deal with things like running out of memory a little bit more gracefully.

Waiting for both network IO and inter-thread notifications

People doing lots of network IO in threaded programs have historically had a problem: waiting for both network IO and for IPC from threads at the same time.

Generally you want to wait for network IO using select() or poll(); trying to use lots of threads, each doing one blocking IO operation, is usually catastrophic to your performance. But both of these only wait on file descriptors, and inter-thread communication in libraries is almost always implemented with mutexes, semaphores, queues, and so on, none of which are select()'able.

Communication between the threads is not the problem, since it's easy to implement a threaded queue if your thread library doesn't already have one. The trick is making the main thread wake up to check the queue.

The best answer on Unix is to use a pipe. The main IO loop selects (or polls) on the readable end's file descriptor as well as its network IO file descriptors; other threads signal the main thread by writing a byte to the writable end. While you can attach meaning to the byte's value, the simplest way is just to use it as a signal to the main thread to check workqueues and so on.

When the main thread processes the queues, it reads an appropriate number of bytes from the pipe and just discards them; the signal has been received. (If the main thread will always clear all of your queues, it can simply read() everything in the pipe in one shot.)

Typical pipes on Unix systems can accumulate at least 4K of pending data before writes to them block, so as long as the main thread is reasonably responsive your other threads can poke it asynchronously. (This is one reason to write only one byte per signal.)

If you spawn other processes, you will need to make sure that they don't inherit either end of the pipe.

Sidebar: order of operations

Just to cover a trivial root: the correct order of operations is:

• other threads: queue first, then poke main thread.
• main thread: read from the pipe, then remove from queue.

This insures that wakeup signals never get lost and work is never missed.

If you have queues with a non-blocking 'remove from queue' operation, you can empty the pipe in one shot and then get everything from the queue. In some circumstances you'll wake up from a signal only to find nothing in the queue, but this is harmless.