I’ve just posted the first binary release package for Radian, which means that you can now try the language out without having to build the compiler yourself. It’s a Mac OS X build and the version number is 0.0.0. It includes the Radian compiler, the standard library, and a sample program.
I pushed up the first working implementation of the new garbage collector last night. It’s a tracing copy collector, designed to efficiently compact small heaps. Radian has a branching generational memory model: a subtask can operate in its own allocation zone, with read-only access to objects from other zones. When the task completes, we can copy its live set into the parent zone, then release the subtask zone as a whole block.
By running tasks in separate allocation zones, we can avoid the cost of mutex locking, as threads no longer need to contend for access to the same allocator. Further, since allocation zones operate on a page-level granularity, tasks running on separate processors need not touch the same cache lines. Only at the point when subtask results are reintegrated into the parent do we need a lock – but we already have to lock that operation anyway.
This allocator/collector project has been a lot of work, and I really hope it turns out to have been worth the engineering time. Radian’s semantics are not very much like those of a conventional object-oriented language, and I believe that a memory management system designed around its needs will perform much better than a generic allocator & collector ever could have. The whole point of this project is to maximize processor throughput, after all – the fancy loop splitting stuff is not going to do us any good if the cores spend all their time contending over allocator locks.
Relaxed radix balanced trees: efficient immutable vectors
Immutable vectors are a convenient data structure for func-
tional programming and part of the standard library of modern languages
like Clojure and Scala. The common implementation is based on wide
trees with a xed number of children per node, which allows fast in-
dexed lookup and update operations. In this paper we extend the vector
data type with a new underlying data structure, Relaxed Radix Balanced
Trees (RRB-Trees), and show how this structure allows immutable vector
concatenation, insert-at and splits in O(logN) time while maintaining the
index, update and iteration speeds of the original vector data structure.
They compare this new structure to finger trees, which I used for Radian’s array container:
2-3 fi nger trees achieve a lgN time for indexing and update while at the sametime maintaining an amortized constant time for adding items to the vector. Concatenation can be accomplished in lgN time too. Although attractive, using this data structure for vectors does compromise the 1/5 lgN time for index, making it theoretically 5 times slower.
Three months since the last update – it was a busy summer!
The garbage collector / multithreaded allocator project is stalled at about 80% complete. It took a global change to calling conventions, which inevitably turned up a lot of odd corners and difficult debugging problems.
On another branch, I’ve built a new non-LLVM-based X64 code generator. This is not to imply anything negative about LLVM, which is a fine piece of software engineering, but it is an extremely large, complex library, dwarfing the rest of the Radian compiler by an order of magnitude, and to justify that footprint it must offer correspondingly extreme benefits. Yet I suspect that much of LLVM’s value is in its array of sophisticated solutions to problems that Radian doesn’t have. As part of the parallelization architecture, I’ve pushed a lot of the analysis work which typically happens in the backend up into the frontend semantics engine, and what reaches the code generator is a long stream of tiny functions which contain no loops, branches, aliasing, or other complications. Loop analysis is finished, register allocation is almost trivial due to the low level of register pressure, and there is basically no type information left. What optimization opportunities I do see tend to be specific to Radian semantics, and I doubt whether LLVM is equipped to do much about them.
I’ll benchmark the two code generators against each other, then, and see whether this Radian-specific EmitX64 module can hold its own against LLVM. If so, I’ll be able to radically simplify the Radian compiler build process and reduce its memory and disk footprint; if not, I’ll learn exactly what it is that makes LLVM worth all that weight.
Interesting reference material: it seems obvious in retrospect, but it had never occurred to me that the process of rendering a floating-point number into a string was the sort of project people might write papers about.
Here’s something I bet you never think about, and for good reason: how are floating-point numbers rendered as text strings? This is a surprisingly tough problem, but it’s been regarded as essentially solved since about 1990.
References to the “Dragon4″ algorithm, and to a recent improvement, “Grisu3″.
Comparing language performance and memory usage in C and Python, using a simple program to remove duplicate lines from a text file.
Radian’s current feature set ought to be enough to build this test; I wonder how it would stack up.
Multicore Garbage Collection with Local Heaps, by Simon Marlow and Simon Peyton-Jones:
In a parallel, shared-memory, language with a garbage collected heap, it is desirable for each processor to perform minor garbage collections independently. Although obvious, it is difficult to make this idea pay off in practice, especially in languages where muta- tion is common. We present several techniques that substantially improve the state of the art. We describe these techniques in the context of a full-scale implementation of Haskell, and demonstrate that our local-heap collector substantially improves scaling, peak performance, and robustness.
Bruno Jouhler’s Yield – Resume vs. Asynchronous Callbacks – An Equivalence continues a series of interesting explorations on asynchronous behavior using JavaScript.
Y-R Javascript is a small extension to Javascript. It introduces a new operator that can be applied to function definitions and function calls. The @ sign is the yield and resume operator. When present in a function definition, it means that the function executes asynchonously. Somewhere in its body, the function yields to the system and the system calls it back with a result or an error. It may actually yield and resume more than once before returning to its caller. I will call such a function an asynchronous function, in contrast with normal Javascript functions (defined without @) that I will naturally call synchronous functions.
In this post I want to investigate the relationship between this fictional Y-R Javascript language on one side and Javascript with asynchronous callbacks on the other side.
I will show that any program written in Y-R Javascript can be mechanically translated into an equivalent Javascript program with asynchronous callbacks, and vice versa.
The foreign-function interface can just about do something useful now. You can load a function pointer from some external library, explain how you’d like to marshal values, then invoke it as an IO action. The value it returns will be marshalled back, according to your previous specification, into some kind of Radian object.
I’ve been sort of picking gently at the remaining bugs in the system while I think about a better syntax for doing asynchronous I/O. All Radian I/O operations are asynchronous, by nature, since the only way to execute an IO action is to yield it back to the system. Thus you must construct I/O activity as a callback-driven state machine.
This is actually the way I learned to do I/O back in the ’80s, on the non-preemptive classic Mac OS, and I’ve used similar techniques in microcontroller code. Nostalgic as the style may be, however, Radian’s lack of shared mutable state makes doing actual work this way something of a mind-bender.
There’s no getting around the fact that IO is asynchronous and callback-driven, but the pattern for writing sequential IO code in such an environment is predictable, and it should be possible to build in some support that makes the process less tedious. I’d like to introduce an async statement, or an async operator, which does all the relevant housekeeping work. It would split the current function apart: anything downstream of the returned value would be captured and passed in as an implicit callback function, which would carry on with the results of the process whenever the initial IO action had completed.
It has been difficult to wrap my head around this semantic transformation, but I think I’ve come up with a way to do it. Along the way I accidentally found a way to implement C-style continue, break, and return statements, and worked out most of what I would need to do in order to introduce Python-style generator functions (yield, or in C# yield return), so it’s been some productive thinking-time even if I haven’t written much code.
It always feels like there is a lot of work piled up ahead of me, but I’ve been keeping a to-do list, and after the async system is done, the only significant task left before “first public beta” is the garbage collector. At that point I plan to spend some time polishing things up, writing documentation, and preparing an installer package.
The first batch of marshaling objects are in the library now. They all live in the ffi module for now, but they will be useful in any situation where one might want to render values as bytes or retrieve values from bytes, so I may end up breaking them out into their own module. The current list is uint64, int64, uint32, int32, uint16, int16, uint8, int8, ascii, and utf8. A marshaling object is one that implements the to_bytes and from_bytes methods; these methods accept a value and return a sized sequence of bytes, and accept a byte buffer and return a value, respectively.