Faster SBCL hash-tables

Posted on 2007-10-01 in Lisp
9 comments

Long time, no blog. I have an excuse though, since I moved to Switzerland for a new job a month ago, and haven't had a lot of time for things like blogging or hacking Lisp (the latter is usually a prerequisite for the former for me).

Anyway, I finally finished and committed the third rewrite of my patch for speeding up the embarrassingly slow hash-tables in SBCL. It turned out to be a really frustrating game of whack-a-mole, with every change uncovering either some new deficiency or another interaction between the GC and the hash-tables that the old implementation had handled by always inhibiting GC during a hash-table operation.

The main user-visible change is that SBCL no longer does its own locking for hash-tables (the fact that it locked the tables was always just an implementation detail, not a part of the public interface). This follows the usual SBCL policy of requiring applications to do take care of locking when sharing data structures between threads.

The exact details are pretty boring, so I won't repeat them here (read the commit message if you really want to know). Instead I'm just going to post a pretty benchmark graph, since it's been way too long since I last did one of these:

Sadly those improvements don't mean that SBCL now has the fastest hash-tables in the West, it just means they don't completely suck. For some reason the issue of SBCL hash-table speed has come up more often during the last couple of months than during the previous three years combined, so it was probably time to get this sorted out.

Next Pretty SBCL backtraces (2007-12-19)
Previous ICFP 2007 (2007-07-25)

Comments

By w-g on 2007-10-01

Thanks a LOT for your work on this. I have some code that does heavy use of hashtables, and this will really speed up my program! :-)

By Geoff Wozniak on 2007-10-01

Looks good. I just tried it out and I get speed-ups of nearly 50% in my tests. It also makes a good case study for my work on meta-programming that takes into account system changes.

Thanks!

By Andy Wingo on 2007-10-01

Abdulaziz Ghuloum just presented a paper yesterday at the 2007 scheme and functional programming workshup entitled "Generation-friendly Eq Hash Tables". Thought you might be interested, whenever it is that those papers will hit the web!

By Juho on 2007-10-01

Heh, heh. The parts of the SBCL implementation that I just got rid of were actually the things that made it generation-friendly (if I understand the term correctly). This is a pretty clever design, probably originally by William Lott over 15 years ago. It's hard to say for sure, the cvs logs from that far back are pretty patchy, and the commit logs tend to be of the form "random mods for generational GC system". Later cleverness was added by dtc about 10 years ago.

Anyway, this implementation can basically do partial rehashes, and only needs to rehash any keys that moved. But it turns out that it's just not worth it in SBCL due to the compromises that you need to make elsewhere in the implementation.

But thanks for the pointer, I'll have a look once the paper appears. Either it'll have some useful hints, or it'll turn out to be a reimplementation of something that the CMUCL hackers of 15 years ago thought ordinary enough to not warrant even a mention in a CVS commit message :-)

By w-g on 2007-10-01

BTW, what did you use to generate those graphs?

By Juho on 2007-10-01

That was done with gnumeric. I usually use gnuplot, but I didn't remember to copy them to the laptop before moving, and the desktop is still in storage.

By Juho on 2007-10-29

Nope, I mostly hack C++ at work. Google isn't exactly a Lisp company :-)

By Abdulaziz Ghuloum on 2007-10-31

Greetings,

The Scheme workshop paper was posted recently on the conference's website. You can get it from http://sfp2007.ift.ulaval.ca/procPaper3.pdf It's certainly possible that some lisp hacker has figured it out 15 years ago, but I certainly would like to see where and when it was done. Please let me know what you think.

Aziz,,,

Name
Message

As an antispam measure, you need to write a super-secret password below. Today's password is "xyzzy" (without the quotes).

Password

Formatting guidelines for comments: No tags, two newlines can be used for separating paragraphs, http://... is automatically turned into a link.