Initial thoughts on XCVB

Having struggled with the build system at work lately, I have decided to force myself to learn another build system at home: I am using XCVB for my UNIVAC emulator project.

I was intrigued by XCVB when I read about it in ILC'09. ASDF has always felt unfinished, even though it's a vast improvement over loading files manually (or using customized system definitions). However, I've run into problems with ASDF and I'm not against other options.

Some thoughts I had during the building, installation and use of XCVB:

• The name needs to change. Is it possible to pick a name that is not some strained acronym? Ant. Maven. Make. These are reasonable (if not goofy) names. XCVB (and for that matter, ASDF) is just alphabet soup. Pick a word and go with it.
• cl-launch feels like a whole lot of magic, but I've seen a whole lot of other magic work before.
• The process of building your own systems is a bit awkward right now. xcvb make-makefile --build foo when in the directory with the build file for foo is excessive specification. Building the system is even more awkward: make -f xcvb.mk obj/foo.image. Something akin to make foo would be much nicer.
• The idea of introducing metadata into a source file to indicate its dependencies doesn't sit well with some people. Personally, I like information about dependencies being close at hand; whether it comes from textual information or system queries doesn't matter. I'm content with textual information at the level of a file for now, but I suspect maintaining that information will become a pain. On the other hand, I found maintaining ASDF system definition files to be a pain (especially with refactoring and reorganization). As much as I would prefer to not use files in a Lisp system, files are a reality. I think starting with file-level meta-information is a good place to start in order find out what works and what doesn't.

Hopefully I get some time to try and help out with the project since I think it's ambitious enough to work.

Postscript to the jump-tables stuff

As some commenters pointed out in my last jump tables post, my recommendation to not really worry about jump tables misses uses cases related to compiler and macro writers. It may be there are cases where hundreds (or even thousands) of cases will appear in a single conditional.

I should have been more clear in what I was trying to say: If you're writing case expressions directly (not generated), then you probably never have to worry about jump tables. That is, if you think you should take your case expression and write a jump table macro for it, you're probably wasting your time. If you are generating case expressions, you may have to consider the possibility when the number of cases is very large since the data indicates hundreds or thousands of cases does make a difference.

Of course, these measurements assumed that the case expression used elements such that a jump table was even reasonably representable (see Duane Rettig's comment). It's a relatively narrow use case, but is likely applicable to most other situations where the number of conditions is hovering around ten.

Thanks to the those who commented. It helps keep these things honest. :) (Comments are the peer review of blogging, after all.) Hopefully I'll get around to looking at some other aspects of this work soon.

SMP in Allegro CL 9.0

Franz's latest tech update states that SMP is coming to Allegro CL 9.0 and recommends people work on migrating their code, since it may break things.

With this news, I must say I'm looking forward to trying out ACL 9.0.

Jump tables follow-up

Based on comments from my previous post on jump tables, I decided to follow-up with a slightly more comprehensive analysis.

Below is the running time, in milliseconds, to execute a given case-style macro one million times with n branches; each execution resulted in the code taking the default case. These running times include the changes suggested by Juho Snellman (seconded by Duane Rettig) to make the times somewhat more accurate, that is, use funcall on a function object instead of a symbol.

At the request of Michael Weber, I included his ecase macro, except that has been renamed to case/tree and changed slightly to accept a default case.

A '—' means that I could not get the given use case to compile.

Jump table running times (ms)
Clozure Common Lisp 1.3-RC1		case	ncase	switch	case/tree
n	10	45	52	361	42
	100	278	51	443	68
	1000	3447	51	725	88
SCBL 1.0.29.54.rc2
n	10	54	60	222	63
	100	218	59	203	88
	1000	2029	60	222	112
ACL (free edition) 8.1
n	10	40	50	280	50
	100	40	50	270	50
	1000	4160	40	340	70
Lispworks Personal 5.1.1
n	10	43	44	288	48
	100	258	43	237	54
	1000	3064	—	277	69
CLISP 2.47
n	10	363	550	615	804
	100	390	549	693	1332
	1000	368	549	612	1898

I should point out that you shouldn't put much stock into the n = 1000 case since any case macro that uses 1000 or more cases is almost certainly pathological. Duane made this point in the comments of my previous post and I think it's important to consider. It might be tempting to say that CLISP has a "better" case macro since it has the same performance on 10 elements as it does for 1000; however, this would miss the point that most other Lisp systems are about 6-9 times faster in the vast majority of cases. Even n = 100 is probably so rare that you'd never see it in daily work unless you went digging.

Below is a bar graph of the performance of ncase, switch and case/tree relative to case. Each bar represents the relative difference for the performance of a given macro on n branches compared to case; I omitted the case of n = 1000 since I can't see it being practical. A value of 0 indicates it is equivalent to case. For example, in Lispworks, the ncase macro is 5 times faster with 100 branches than case (represented by the dark blue colour █ bar). Conversely, in Clozure CL, the switch macro is about 7 times slower with 10 branches than the case macro (the red colour █ bar).

What is clear from the graphs is that switch doesn't provide any benefits over case (when the cases are all single integer values, anyway). Also, using ncase or case/tree is of some benefit when the number of cases is large, except when using Allegro CL or CLISP. Probably the most interesting aspect is that ncase and case/tree tend to be slightly worse for small numbers of branches.

There are still some interesting questions that could be explored here (Can a compelling use case for switch be made? How often do large branch case expressions appear in actual code?), but it seems to me that jump table macros are, for the most part, of academic interest only. You can probably feel pretty confident that using case is sufficient.

Tinkering with jump tables

I've often wondered whether writing a case or cond-like macro that uses jump tables is worth the effort. To get an idea as to how much I should pursue this, I decided to take Tim Bradshaw's ncase macro and pit it against case.

Tim admits that ncase is meant to show what is possible with macros and that it may be the case it may not make any performance improvement at all. Still, I think it would be interesting to compare it and see the results, simply because I really don't know what will happen.

In addition to Tim's jump table, I wrote a simple jump table implementation called switch that uses a hash table to look up the value and associates the body with a thunk; the hash table is computed with an load-time-value to minimize table creation overhead. switch has the disadvantage of performing a hash table lookup and calling a function with the advantage that the values to match can be anything you would compare with equal.

To compare the running times, I generated functions that contain 10, 100 and 1000 branches respectively (plus the default branch). This was done for each of case, ncase and switch. Each branch would compare a single integer and return that integer. For example, the body of case-100 would look something like the following.

(case v (1 1) (2 2) ... (100 100) (t nil))

It's easy to see why I generated these function bodies with macros...

I ran each function one million times, making it hit the default case each time. The time required to run the function one million times on different Lisp systems are given below in milliseconds. These were run on a 2.16 GHZ 17" Macbook Pro running Mac OS X 10.5.7.

SBCL 1.0.29.54.rc2	case	ncase	switch
10	469	469	633
100	631	471	612
1000	2455	469	630
CLISP 2.47	case	ncase	switch
10	348	558	579
100	391	561	645
1000	375	560	571
ACL Free edition 8.1	case	ncase	switch
10	40	40	280
100	40	50	270
1000	4290	50	350

I was quite surprised at the results. I ran these a few times to make sure I wasn't missing something. In particular, I'm drawn to the results from CLISP. It seems lookups with case is constant. The reason this is so compelling is that SBCL and ACL are quite slow in these cases. ACL seems to be very fast otherwise.

I'll have to take a closer look at the disassembled code to see what is going on (or perhaps you can mention something in the comments if you know). Regardless, it's something that deserves some more attention.

Some notes:

• SBCL took approximately 4 minutes to compile the ncase with 1000 branches. It also used up an awful lot of memory in the process. It took more than 10 seconds to compile the switch with 1000 cases.
• The code I used to get these numbers can be found on paste.lisp.org.

Franz's facelift

I guess it's been a while since I visited Franz's website. It appears to have gotten a serious makeover. Last I checked, it looked very 1990s-ish. It looks much better now.

I'd rank it about as effective as SBCL's simplicity and considerably better than the cluttered CLISP bucket 'o links.

Thanks to the ILC 2009 Twitterers

Just wanted to say thanks to all those who posted updates about ILC 2009 on Twitter. It made me feel bad for having to miss the conference, but at least I got to keep up on what was going on.

Now, anyone up for writing a blog entry providing a little more detail?