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.

ABCL 0.22.0 released

On behalf of the developers of ABCL (Armed Bear Common Lisp) I'm glad to be able to announce the 0.22.0 release.

ABCL is a Common Lisp implementation implemented in Java and running on the JVM, featuring both an interpreter and a compiler. The compiler targets the JVM directly meaning that its output is runnable JVM bytecode. The fact that ABCL is written in Java allows for relatively easy embedding in larger applications. For integration with existing applications ABCL implements Java Specification Request (JSR) 223: Java scripting API.

The release is a small maintenance release: most efforts were focussed on work happening on branches some of which has already been merged to trunk for 0.23.

The release notes can be viewed at http://common-lisp.net/project/armedbear/release-notes-0.22.shtml.

and the list of changes at http://trac.common-lisp.net/armedbear/browser/trunk/abcl/CHANGES.

Latest and older binary and source distributions can be downloaded from http://common-lisp.net/project/armedbear/releases/

Parsing latin1 data with an utf-8 stream

We recently noticed that ABCL isn't capable of reading files containing certain latin1 characters, like the author comments in albert. ABCL's DecodingReader uses java.nio.charset.CharsetDecoder, which defaults to throwing exceptions when it finds unmappable character or input it otherwise considers malformed. Therefore, reading albert files, which contain Norwegian/Danish o-slashes resulted in an exception being thrown. Same result occurred with files that contain o-umlauts.

The remedy that seemed obvious was changing the CharsetDecoder's error handling strategy to replace malformed input and unmappable characters. Alas, this didn't work, to much surprise, as it resulted in the DecodingReader to loop endlessly. Despite this document, which seems to suggest that an utf-8 byte sequence can only start with f0-f4, it seemed that o-umlaut (f6) and o-slash (f8) threw the decoder off-balance.

After debugging the problem, we noticed that in the case of these characters, the DecodingReader reported an overflow but didn't advance the buffers it uses. So, after some consideration, we introduced a hack where, in case of an overflow that didn't advance the buffers at all, we advance the buffers manually by one byte and insert a ? character into the resulting stream. This reeks of a hack, but so far we haven't been able to find a more elegant solution. This solution does seem to enable us to parse files with such latin1 chars like o-umlaut and o-slash properly, and the fix was committed into ABCL trunk as commit r12902, and will be part of ABCL 0.22.

ABCL-0.21.0 released....

.... so long ago that it's time to release 0.22 in the week(s) to come.

URI Pathnames

Among other goodies, ABCL-0.20 includes good support for using URI resources as arguments to about any function you would specify a filepath. Any builtin scheme like "http" or "file" or "jar" works as a full-on Lisp Pathname, with the caveat that one may not write to an associated Stream. We should be generic enough in implementation that the JVM extension mechanism for extending the classloader works for us for the most common use case, OSGi.

We pick up the ability to refer to URI, associating an input Stream with its representation as a network (or local system) bytes easily as the following one-liner:

CL-USER> (with-open-file (stream #p"http://google.com/index.html")
           (format nil "~A" (read-line stream nil)))

Underneath we have implemented a new subtype of PATHNAME, namely the type >URL-PATHNAME. We name this URL as opposed to URI as the underlying Java object is a java.net.URL with associated java.net.URLConnection that we'll be relying on for input sources.

Looking through an APROPOS for URL-PATHNAME shows the following related symbols:

CL-USER> (apropos (type-of #p"http://google.com/index.html"))
EXTENSIONS::SET-URL-PATHNAME-SCHEME (fbound)
EXTENSIONS::SET-URL-PATHNAME-AUTHORITY (fbound)
EXTENSIONS::SET-URL-PATHNAME-QUERY (fbound)
EXTENSIONS::SET-URL-PATHNAME-FRAGMENT (fbound)
URL-PATHNAME
URL-PATHNAME-AUTHORITY (fbound)
URL-PATHNAME-SCHEME (fbound)
URL-PATHNAME-FRAGMENT (fbound)
URL-PATHNAME-QUERY (fbound)
; No value
CL-USER>

which we see the defined functions to set the AUTHORITY, SCHEME, FRAGMENT, and QUERY portions of a URL-PATHNAME.

After these modifications, the ABCL PATHNAME class now has two "beyond ANSI" subtypes, namely URL-PATHNAME and JAR-PATHNAME. A short document outlining the design of URL-PATHNAME can be found in our documentation directory.

In implementing URL-PATHNAME, we actually had the ability to analyze what another CL did for their implementation. We analyzed the CLForJava technical paper, but decided not to use their abstractions as detailed on a lengthy armedbear-devel post.

ABCL 0.20.0 released, including first funded feature

On behalf of the developers of ABCL (Armed Bear Common Lisp) I'm glad to be able to announce the 0.20.0 release.

ABCL is a Common Lisp implementation implemented in Java and running on the JVM, featuring both an interpreter and a compiler. The compiler targets the JVM directly meaning that its output is runnable JVM bytecode. The fact that ABCL is written in Java allows for relatively easy embedding in larger applications. For integration with existing applications ABCL implements Java Specification Request (JSR) 223: Java scripting API.

This release is the first to include a funded feature: funds were provided to implement the CLOS METACLASS feature and tests. Next to that, this release contains a large number of fixes and improvements, such

as the ability to use JARs and URLs as pathnames and the a new ASDF version (ASDF2). You can find the full release notes at:

http://common-lisp.net/project/armedbear/release-notes-0.20.shtml

and the list of changes at:

http://trac.common-lisp.net/armedbear/browser/trunk/abcl/CHANGES

Latest and older binary and source distributions can be downloaded from

http://common-lisp.net/project/armedbear/releases/