ABCL hash tables: threading and CLOS

More people are starting to use ABCL in threaded environments - I have been doing so myself since spring 2008. My own use revealed some threading issues in the compiler which have been long solved now.

Last April, David Kirkman mailed the list with some threading problems in our CLOS implementation. Because of other work - including implementation of METACLASS support - there wasn't much time to do much about the issue.

This week, he mailed having found the problem - accompanied with a patch with a solution. Because of our need to support the four Common Lisp equality operators, ABCL implements its own hash tables -four of them - with a shared ancestor class which requires implementation of a few primitive operations. Hash access from the Lisp world was being synchronized by the common ancestor. However, in some locations on the Java side the - unsynchronized - primitives were being called directly.

The solution was of course to add synchronization to the primitives as well. Evaluating the result, the new situation was rather unsatisfying: only a single thread could be reading or writing at the same time, meaning only a single CLOS effective method dispatch could be happening at the same time. You probably understand my reluctance to accept the status quo.

The quick solution to the CLOS dispatch problem was to use the java.util.concurrent.ConcurrentHashMap type: we were keying on symbols, which have EQ equility in the Java world (ie in terms of Object.equals()).

That still left the lisp world with rather unsatisfactory threading performance of our own hash tables and since those were repeating large chunks of code in their specialized primitives, I decided to refactor them completely.

The result is - admittedly by looking very closely at ConcurrentHashTable - a single hash table implementation with 4 Comparator classes, which have nearly-lockless reads from all threads. Inserts into the hash table are still synchronized from all threads, but that's expected to be a lesser problem: you'd primarily expect many reads per write in a hash table.

Concluding, the only (known) CLOS threading issue has been fixed - there are presumably many more, please report if you find them - and as a bonus we have a much more efficient hash table implementation.

Maxima on ABCL: full pass on the test suite

Over the past two weeks Raymond Toy helped out to fix the last 9 failures in the Maxima test suite running: ABCL now passes the full 8.666 Maxima tests! We achieved a goal set for ABCL more than two years ago!

Thinking back to the days when Peter Graves had just handed over the project shows just how far we have come: back in September 2008 lots of tests (423, according to Hunter Monroe) would plainly terminate the test suite. That number had come down from over 1000 tests crashing the test suite in January of that year.

After manually disabling the crashing tests, Hunter Monroe writes on September 27 (2008) that he's been able to complete the tests with a total number of failures of 612 (out of 4454 tests) .

Many of the problems were caused by incorrect handling of special variables which was one of the first things to be addressed in ABCL - stabilizing over the first half of 2009. Other improvements which contributed to the stability of Maxima were fixes to the code generating non-local returns (THROW, GOTO stepping out of a closure, RETURN-FROM stepping out of a closure). Next to its reduction in specials, the Maxima team had to change lots of number comparisons from EQ to EQL, because in ABCL integers aren't (guaranteed) to be EQ - which is allowed by the spec, but not very customary in CL implementations.

At the same time evaluation time of the test suite has gone down considerably too - not due to increased processing power, but due to improvements on both sides. One example of an improvement which has greatly benefitted ABCL's performance is the gradual elimination of specials is Maxima - an on-going effort in their team. On the other side, binding and unwinding specials has become much faster in ABCL too, reducing the impact of remaining excessive specials.

The last few tests to be fixed required adjustments to the Maxima test suite as well as fixes to ABCL. Thanks to everybody who helped achieve this result, most notably Robert Dodier, Hunter Monroe and Raymond Toy from the Maxima team as well as Ville Voutilainen and Mark Evenson from the ABCL team.