Factor: a practical stack language

Factor 0.94 now available

2010-09-18T23:40:00.003-04:00

Factor 0.94 is now available from the Factor website, five months after the previous release, Factor 0.93. Binaries are provided for 10 platforms.

As usual, contributors did most of the work. Thanks to Daniel Ehrenberg, Dmitry Shubin, Doug Coleman, Erik Charlebois, Joe Groff, John Benediktsson, Jose A. Ortega Ruiz, Niklas Waern, Samuel Tardieu, Sascha Matzke and everyone else who helped out this time around!

Incompatible changes:

The PowerPC architecture is no longer supported. (Slava Pestov)
The require-when word now supports dependencies on multiple vocabularies. (Daniel Ehrenberg)
The C-ENUM: word in the C library interface has been replaced with ENUM:, a much improved word for defining type-safe enumerations. (Erik Charlebois, Joe Groff)
Tuple slot setter words with stack effect ( value object -- ) are now named foo<< instead of (>>foo). Most code is unaffected since it uses the >>foo form. (Slava Pestov)
The older system-micros word, which returned microseconds since the Unix epoch as an integer, has been removed. For a while, the recommended way to get the current time has been to call the now word from the calendar vocabulary, which returned a timestamp instance. (Doug Coleman)
A few sequence-related words were moved from the generalizations vocabulary to sequences.generalizations. (Slava Pestov)
The alarms vocabulary has been renamed to timers to better explain its true purpose, with improved timing accuracy and robustness. (Doug Coleman)
cocoa.subclassing: the syntax for defining new Objective-C classes has been changed to improve readability. (Slava Pestov)
io.streams.limited: the ability to throw errors on EOF was extracted from limited streams, and limited streams simplified as a result. Throwing on EOF is now implemented by the io.streams.throwing vocabulary. (Doug Coleman)

New libraries:

boyer-moore: efficient text search algorithm (Dmitry Shubin)
checksums.internet: implementation of checksum algorithm used by ICMP for the checksums framework (John Benediktsson)
gdbm: disk-based hash library binding (Dmitry Shubin)
io.encodings.detect: binary file/text encoding detection heuristics from jEdit (Joe Groff)
javascriptcore: FFI to the WebKit JavaScript engine (Doug Coleman)
lua: FFI to the Lua scripting language (Erik Charlebois)
oauth: minimal implementation of client-side OAuth (Slava Pestov)
sequences.unrolled: efficient unrolled loops with constant iteration count (Joe Groff)

Improved libraries:

cuda: various improvements (Joe Groff, Doug Coleman)
game.input: now uses XInput2 on X11 (Niklas Waern)
gpu.render, gpu.buffers: various improvements (Joe Groff)
math.combinatorics: various improvements (John Benediktsson)
math.primes: various improvements (Samuel Tardieu)
math.vectors.simd.cords: compound "256-bit" SIMD types now support the full set of SIMD operations (Joe Groff)
mongodb: various improvements (Sascha Matzke)
twitter: now uses OAuth as required by Twitter (Slava Pestov)
unix.users, unix.groups: various improvements (Doug Coleman)

Compiler improvements:

Improved instruction selection, copy propagation, representation selection, and register allocation; details in a blog post. (Slava Pestov)
An instruction scheduling pass now runs prior to register allocation, intended to reduce register pressure by moving uses closer to definitions; details in a blog post. (Daniel Ehrenberg)
The code generation for the C library interface has been revamped; details in a blog post. (Slava Pestov)
Something similar to what C++ and C# programmers refer to as "value types"; binary data can now be allocated on the call stack, and passed to C functions like any other pointer. The with-out-parameters combinator replaces tricky code for allocating and juggling multiple temporary byte arrays used as out parameters for C function calls, making this idiom easier to read and more efficient. The with-scoped-allocation combinator presents a more general, lower-level interface. (Slava Pestov)
The compiler can now use the x87 floating point unit on older CPUs where SSE2 is not available. However, this is not recommended, because the build farm does not test Factor (or build any binaries) in x87 mode, so this support can break at any time. To use x87 code generation, you must download the source code and bootstrap Factor yourself, on a CPU without SSE2. (Slava Pestov)

Miscellaneous improvements:

fuel: Factor's Ultimate Emacs Library has seen many improvements, and also some keyboard shortcuts have changed; see the README. (Erik Charlebois, Dmitry Shubin, Jose A. Ortega Ruiz)
A new factor.cmd script is now included in the build-support directory, to automate the update/build/bootstrap cycle for those who build from source. Its functionality is a subset of the factor.sh script for Unix. (Joe Groff)
The default set of icons shipped in misc has been tweaked, with better contrast and improved appearance when scaled down. (Joe Groff)

An overview of Factor's I/O library

2010-09-11T22:23:00.006-04:00

Factor has grown a very powerful and high-level I/O library over the years, however it is easy to get lost in the forest of reference documentation surrounding the io vocabulary hierarchy. In this blog post I'm attempting to give an overview of the functionality available, with some easy-to-digest examples, along with links for futher reading. I will also touch upon some common themes that come up throughout the library, such as encoding support, timeouts, and uses for dynamically-scoped variables.

Factor's I/O library is the work of many contributors over the years. Implementing FFI bindings to native I/O APIs, developing high-level abstractions on top, and making the whole thing cross-platform takes many people. In particular Doug Coleman did a lot of heavy lifting early on for the Windows port, and also implemented several new cross-platform features such as file system metadata and memory mapped files.

Our I/O library is competitive with Python's APIs and Java's upcoming NIO2 in breadth of functionality. I like to think the design is quite a bit cleaner too, because instead of being a thin wrapper over POSIX we try to come up with clear and conherent APIs that make sense on both Windows and Unix.

First example: converting a text file from MacRoman to UTF8

The io.files vocabulary defines words for reading and writing files. It supports two modes of operation in a pretty standard fashion:

Stream-based: with-file-reader, with-file-writer
Entire file: file-contents, set-file-contents, file-lines, set-file-lines

What makes Factor's file I/O interesting is that it takes advantage of pervasive support for I/O encoding. In Factor, a string is not a sequence of bytes; it is a sequence of Unicode code points. When reading and writing strings on external resources, which only consist of bytes, an encoding parameter is given to specify the conversion from strings to byte arrays.

Let's convert foo.txt from MacRoman, an older encoding primarily used by classic Mac OS, to UTF8:

USING: io.encodings.8-bit.mac-roman io.encodings.utf8 io.files ;

"foo.txt" mac-roman file-contents
"foo.txt" utf8 set-file-contents

This is a very simple and concise implementation but it has the downside that the entire file is read into memory. For most small text files this does not matter, but if efficiency is a concern then we can do the conversion a line at a time:

USING: io io.encodings.8-bit.mac-roman io.encodings.utf8
io.files ;

"out.txt" utf8 [
    "in.txt" mac-roman [
        [ print ] each-line
    ] with-file-reader
] with-file-writer

Converting a directory full of files from MacRoman to UTF8

The io.files vocabulary defines words for listing and modifying directories. Let's make the above example more interesting by performing the conversion on a directory full of files:

USING: io.directories io.encodings.8-bit.mac-roman
io.encodings.utf8 io.files ;

: convert-directory ( path -- )
    [
        [
            [ mac-roman file-contents ] keep
            utf8 set-file-contents
        ] each
    ] with-directory-files ;

An aside: generalizing the "current working directory"

If you run the following, you will see that with-directory-files returns relative, and not absolute, file names:

"/path/to/some/directory"
[ [ print ] each ] with-directory-files

So the question is, how did file-contents above know what directory to look for files in? The answer is that in addition to calling the quotation with the directory's contents, the with-directory-files word also rebinds the current-directory dynamic variable.

This directory is the Factor equivalent of the familiar Unix notion of "current working directory". It generalizes the Unix feature by making it dynamically-scoped; within the quotation passed to the with-directory combinator, relative paths are resolved relative to that directory, but other coroutines executing at the time, or code after the quotation, is unaffected. This functionality is implemented entirely at the library level; all pathname strings are "normalized" with the normalize-pathname word before being handed off to the operating system.

When calling a shell command with io.launcher, the child process is run from the Factor current-directory so relative pathnames passed on the command line will just work. However, when making C FFI calls which take pathnames, you pass in absolute paths only, or normalize the path with normalize-path first, otherwise the C code wlll search for it in the wrong place.

Checking free disk space

The io.files.info vocabulary defines two words which return tuples containing information about a file, and the file system containing the file, respectively:

Let's say your application needs to install some files in the user's home directory, but instead of failing half-way through in the event that there is insufficient space, you'd rather display a friendly error message upfront:

ERROR: buy-a-new-disk ;

: gb ( m -- n ) 30 2^ * ;

: check-space ( -- )
    home file-system-info free-space>> 10 gb <
    [ buy-a-new-disk ] when ;

Now if there is less than 10gb available, the check-space word will throw a buy-a-new-disk error.

The file-system-info word reports a bunch of other info. There is a Factor implementation of the Unix df command in the tools.files vocabulary:

( scratchpad ) file-systems.
+device-name+ +available-space+ +free-space+ +used-space+ +total-space+ +percent-used+ +mount-point+
/dev/disk0s2  15955816448       16217960448  183487713280 199705673728  91             /
fdesc         0                 0            1024         1024          100            /dev
fdesc         0                 0            1024         1024          100            /dev
map -hosts    0                 0            0            0             0              /net
map auto_home 0                 0            0            0             0              /home
/dev/disk1s2  15922262016       15922262016  383489052672 399411314688  96             /Users/slava

Doug has two blog posts about these features, part 1 and part 2.

Unix only: symbolic links

Factor knows about symbolic links on Unix. The io.files.links vocabulary defines a pair of words, make-link and make-hard-link. The link-info word is like file-info except it doesn't follow symbolic links. Finally, the directory hierarchy traversal words don't follow links, so a link cycle or bogus link to / somewhere won't break everything.

File system monitoring

The io.monitors vocabulary implements real-time file and directory change monitoring. Unfortunately at this point in time, it is only supported on Windows, Linux and Mac. Neither one of FreeBSD and OpenBSD exposes the necessary information to user-space.

Here is an example for watching a directory for changes, and logging them:

USE: io.monitors

: watch-loop ( monitor -- )
    dup next-change path>> print flush watch-loop ;

: watch-directory ( path -- )
    [ t [ watch-loop ] with-monitor ] with-monitors ;

Try pasting the above code into a Factor listener window, and then run home watch-directory. Every time a file in your home directory is modified, its full pathname will be printed in the listener.

Java will only begin to support symbolic links and directory monitoring in the upcoming JDK7 release.

Memory mapped files

The io.mmap vocabulary defines support for working with memory-mapped files. The highest-level and easiest to use interface is the with-mapped-array combinator. It takes a file name, a C type, and a quotation. The quotation can perform generic sequence operations on the mapped file.

Here is an example which reverses each group of 4 bytes:

USING: alien.c-types grouping io.mmap sequences
specialized-arrays ;
SPECIALIZED-ARRAY: char

"mydata.dat" char [
    4 <sliced-groups>
    [ reverse! drop ] each
] with-mapped-array

The <sliced-groups> word returns a view of an underlying sequence, grouped into n-element subsequences. Mutating one of these subsequences in-place mutates the underlying sequence, which in our case is a mapped view of a file.

A more efficient implementation of the above is also possible, by mapping in the file as an int array and then performing bitwise arithmetic on the elements.

Launching processes

Factor's io.launcher vocabulary was originally developed for use by the build farm. The build farm needs to launch processes with precise control over I/O redirection and timeouts, and so a rich set of cross-platform functionality was born.

The central concept in the library is the process, tuple, constructed by calling <process>. Various slots of the process tuple can be filled in to specify the command line, environment variables, redirection, and so on. Then the process can be run in various ways, running in the foreground, in the background, or with input and output attached to Factor streams.

The launcher's I/O redirection is very flexible. If you don't touch the redirection slots in a process tuple, the subprocess will just inherit the current standard input and output. You can specify a file name to read or write from, a file name to append to, or even supply a pipe object, constructed from the io.pipes vocabulary.

<process>
    "rotate-logs" >>command
    +closed+ >>stdin
    "out.txt" >>stdout
    "error.log" <appender> >>stderr

It is possible to specify a timeout when running a process:

<process>
    { "ssh" "myhost" "-l" "jane" "do-calculation" } >>command
    15 minutes >>timeout
    "results.txt" >>stdout
run-process

The process will be killed if it runs for longer than the timeout period. Many other features are supported; setting environment variables, setting process priority, and so on. The io.launcher vocabulary has all the details.

Support for timeouts is a cross-cutting concern that touches many ports of the I/O API. This support is consolidated in the io.timeouts vocabulary. The set-timeout generic word is supported by all external resources which provide interruptible blocking operations.

Timeouts are implemented on top of our monotonic timer support; changing your system clock while Factor is running won't screw with active network connections.

Unix only: file ownership and permissions

The io.files.unix vocabulary defines words for reading and writing file ownership and permissions. Using this vocabulary, we can write a shell script to a file, make it executable, and run it. An essential component of any multi-language quine:

USING: io.encodings.ascii io.files io.files.info.unix
io.launcher ;

"""
#!/bin/sh
echo "Hello, polyglot"
""" "script.sh" ascii set-file-contents
OCT: 755 "script.sh" set-file-permissions
"./script.sh" run-process

There are even more Unix-specific words in the unix.users and unix.groups vocabularies. Using these words enables listing all users on the system, converting user names to UIDs and back, and even setuid and setgid.

Networking

Factor's io.sockets vocabulary supports stream and packet-based networking.

Stream-based: with-client, <server>, accept
Packet-based: <datagram>, send, receive

Network addresses are specified in a flexible manner. Specific classes exist for IPv4, IPv6 and Unix domain socket addressing. When a network socket is constructed, that endpoint is bound to a given address specifier.

Connecting to http://www.apple.com, sending a GET request, and reading the result:

USING: io io.encodings.utf8 io.sockets ;

"www.apple.com" 80 <inet> utf8 [
    """GET / HTTP/1.1\r
host: www.apple.com\r
connection: close\r
\r
""" write flush
    contents
] with-client
print

SSL support is almost transparent; the only difference is that the address specifier is wrapped in <secure>:

USING: io io.encodings.utf8 io.sockets
io.sockets.secure ;

"www.cia.gov" 443 <inet> <secure> utf8 [
    """GET / HTTP/1.1\r
host: www.cia.gov\r
connection: close\r
\r
""" write flush
    contents
] with-client
print

For details, see the io.sockets.secure documentation, and my blog post about SSL in Factor..

Of course you'd never send HTTP requests directly using sockets; instead you'd use the http.client vocabulary.

Network servers

Factor's io.servers.connection vocabulary is so cool, that a couple of years back I made a screencast about it. Nowadays the sample application developed in that screencast is in the extra/time-server; the implementation is very concise and elegant.

Under the hood

All of this functionality is implemented in pure Factor code on top of our excellent C library interface and extensive bindings to POSIX and Win32 in the unix and windows vocabulary hierarchies, respectively.

As much as possible, I/O is performed with non-blocking operations; synchronous reads and writes only suspend the current coroutine and switch to the next runnable one rather than hanging the entire VM. I recently rewrote the coroutines implementation to use direct context switching rather than continuations.

Co-ordination and scheduling of coroutines is handled with a series of simple concurrency abstractions.

Making Factor's continuous build system more robust

2010-09-05T20:50:00.006-04:00

I've done some work on Factor's continuous build system over the weekend to make it more robust in the face of failure, with improved error reporting and less manual intervention required to fix problems when they come up. The current build system is called "mason", because it is based on an earlier build system named "builder" that was written by Eduardo Cavazos. Every binary package you download from factorcode.org was built, tested and benchmarked by mason.

Checking for disk space

Every once in a while build machines run out of disk space. This is a condition that Git doesn't handle very gracefully; if a git pull fails half way through, it leaves the repository in an inconsistent state. Instead of failing during source code checkout or testing, mason now checks disk usage before attempting a build. If less than 1 Gb is free, it sends out a warning e-mail and takes no further action. Disk usage is also now part of every build report; for example, take a look at the latest Mac OS X report. Finally, mason does a better job of cleaning up after itself when builds fail, reducing the rate of disk waste overall.

I must say the disk space check was very easy to implement using Doug Coleman's excellent cross-platform file-system-info library. Factor's I/O libraries are top-notch and everything works as expected across all of the platforms we run on.

Git repository corruption

Git is not 100% reliable, and sometimes repositories will end up in a funny state. One cause is when the disk fills up in the middle of a pull, but it seems to happen in other cases too. For example, just a few days ago, our 64-bit Windows build machine started failing builds with the following error:

From git://factorcode.org/git/factor
 * branch            master     -> FETCH_HEAD
Updating d386ea7..eece1e3

error: Entry 'basis/io/sockets/windows/windows.factor' not uptodate. Cannot merge.

Of course nobody actually edits files in the repository in question, its a clone of the official repo that gets updated every 5 minutes. Why git messed up here I have no clue, but instead of expecting software to be perfect, we can design for failure.

If a pull fails with a merge error, or if the working copy somehow ends up containing modified or untracked files, mason deletes the repository and clones it again from scratch, instead of just falling over and requiring manual intervention.

Error e-mail throttling

Any time mason encounters an error, such as not being able to pull from the Factor Git repository, disk space exhaustion, or intermittent network failure, it sends out an e-mail to Factor-builds. Since it checks for new code every 5 minutes, this can get very annoying if there is a problem with the machine and nobody is able to fix it immediately; the Factor-builds list would get spammed with hundreds of duplicate messages. Now, mason uses a heuristic to limit the number of error e-mails sent out. If two errors are sent within twenty minutes of each other, no further errors are sent for another 6 hours.

More robust new code check

Previously mason would initiate a build if a git pull had pulled in patches. This was insufficient though, because if a build was killed half way through, for example due to power failure or machine reboot, it would not re-attempt a build when it came back up until new patches were pushed. Now mason compares the latest git revision with the last one that was actually built to completion (whether or not there were errors).

Build system dashboard

I've put together a simple dashboard page showing build system status. Sometimes VMs will crash (FreeBSD is particularly flaky when running under VirtualBox, for example) and we don't always notice that a VM is down until several days after, when no builds are being uploaded. Since mason now sends out heartbeats every 5 minutes to a central server, it was easy to put together a dashboard showing which machines have not sent any heartbeats for a while. These machines are likely to be down. The dashboard also allows a build to be forced even if no new code was pushed to the repository; this is useful to test things out after changing machine configuration.

The dashboard nicely complements my earlier work on live status display for the build farm.

Conclusion

I think mason is one of the most advanced continuous integration systems among open source language implementations, nevermind the less mainstream ones such as Factor. And thanks to Factor's advanced libraries, it is only 1600 lines of code. Here is a selection of the functionality from Factor's standard library used by mason:

io.files.info - checking disk usage
io.launcher - running processes, such as git, make, zip, tar, ssh, and of course the actual Factor instance being tested
io.timeouts - timeouts on network operations and child processes are invaluable; Factor's consistent and widely-used timeout API makes it easy
http.client - downloading boot images, making POST requests to builds.factorcode.org for the live status display feature
smtp - sending build report e-mails
twitter - Tweeting binary upload notifications
oauth - yes, Factor has a library to support the feared OAuth. Everyone complains about how hard OAuth is, but if you have easy to use libraries for HMAC, SHA1 and HTTP then it's no big deal at all.
xml.syntax - constructing HTML-formatted build reports using XML literal syntax

Two things every Unix developer should know

2010-09-03T23:57:00.003-04:00

Unix programming can be tricky. There are many subtleties many developers are not aware of. In this post, I will describe just two of them... my favorite Unix quirks, if you will.

Interruptible system calls

On Unix, any system call which blocks can potentially fail with an errno of EINTR, which indicates that the caller must retry the system call. The EINTR error can be raised at any time for any reason, so essentially every I/O operation on a Unix system must be prepared to handle this error properly. Surprisingly to some, this includes the C standard library functions such as fread(), fwrite(), and so on.

For example, if you are writing a network server, then most of the time, you want to ignore the SIGPIPE signal which is raised when the client closes its end of a socket. However, this ignored signal can cause some pending I/O in the server to return EINTR.

A commonly-held belief is that setting the SA_RESTART flag with the sigaction() system call means that if that signal is delivered, system calls are restarted for you and EINTR doesn't need to be handled. Unfortunately this is not true. The reason is that certain signals are unmaskable. For instance, on Mac OS X, if your process is blocking reading on standard input, and the user suspends the program by sending it SIGSTOP (usually by pressing ^Z in the terminal), then upon resumption, your read() call will immediately fail with EINTR.

Don't believe me? The Mac OS X cat program is not actually interrupt-safe, and has this bug. Run cat with no arguments in a terminal, press ^Z, then type %1, and you'll get an error from cat!

$ cat
^Z
[1]+  Stopped                 cat
$ %1
cat
cat: stdin: Interrupted system call
$

As far as I'm aware, Factor properly handles interruptible system calls, and has for a while now, thanks to Doug Coleman explaining the issue to me 4 years ago. Not having to deal with crap like this (not to mention being able to write cross-platform code that runs on both Unix and Windows) is one of the advantages of using a high-level language like Factor or Java over C.

Subprocesses inherit semi-random things from the parent process

When you fork() your process, various things are copied from the parent to the child; environment variables, file descriptors, the ignored signal mask, and so on. Less obvious is the fact that exec() doesn't reset everything. If shared file descriptors such as stdin and stdout were set to non-blocking in the parent, the child will start with these descriptors non-blocking also, which will most likely break most programs. I've blogged about this problem before.

A similar issue is that if you elect to ignore certain signals with the SIG_IGN action using sigaction(), then subprocesses will inherit this behavior. Again, this can break processes. Until yesterday, Factor would ignore SIGPIPE using this mechanism, and child processes spawned with the io.launcher vocabulary that expected to receive SIGPIPE would not work properly. There are various workarounds; you can reset the signal mask before the exec() call, or you can do what I did in Factor, and ignore the signal by giving it an empty signal handler instead of a SIG_IGN action.

Overhauling Factor's C library interface

2010-07-28T02:36:00.002-04:00

For the last while I've been working on an overhaul of Factor's C library interface and associated compiler infrastructure. The goals of the rewrite were three-fold:

Improving performance
Cleaning up some crusty old code that dates back to my earliest experiments with native code generation
Laying the groundwork for future compiler improvements

These changes were all behind-the-scenes; I did not introduce any new functionality or language changes, and I think Factor's FFI is already quite stable and feature-complete.

The previous FFI implementation

I started work on Factor's C library interface (FFI) almost immediately after I bootstrapped the native implementation off of JFactor. I began experimenting with an SDL-based UI early on and immediately decided I wanted to have a real FFI, instead of extending the VM with primitives which wrap C functions by hand.

Over time, both the FFI and compiler have evolved in parallel, but there was little integration between them, other than the fact that both used the same assembler DSL under the hood. The result is that FFI calls were generated in a somewhat inefficient way. Since the optimizing compiler had no knowledge of how they work, it would save all values to the data stack first. Then the FFI code generator would take over; it would pop the input parameters one by one, pass them to a per-type C function in the Factor VM which unboxed the value, then stored the value in the stack frame. Finally, the target C function would be invoked, then another C function in the VM would box the return value, and the return value would be pushed to the stack. The optimizing compiler would then take over, possibily generating code to pop the value from the stack.

The redundant stack traffic was wasteful. In some cases, the optimizing compiler would generate code to box a value and push it to the stack, only to have the FFI then generate code to pop it and unbox it immediately after. To make matters worse, over time the optimizing compiler gained the ability to box and unbox values with open-coded assembly sequences, but the FFI would still make calls into the VM to do it.

All in all, it was about time I rewrote the FFI, modernizing it and integrating it with the rest of the compiler in the process.

Factoring FFI calls into simpler instructions

Most low-level IR instructions are very simple; FFI calls used to be the exception. Now I've split these up into smaller instructions. Parameters and return values are now read and written from the stack with the same ##peek and ##replace instructions that everything else uses, and boxing and unboxing parameters and return values is now done with the representation selection pass. A couple of oddball C types, such as long long on x86-32, still require VM calls to box and unbox, and I added new instructions for those.

One slightly tricky thing that came up was that I had to re-engineer low-level IR to support instructions with multiple output values. This is required for C calls which return structs and long long types by value, since each word-size chunk of the return value is returned in its own register, and these chunks have to be re-assembled later. In the future, I will be able to use this support to add instructions such as the x86 division instruction, which computes x / y and x mod y simultaneously.

I also had to change low-level IR to distinguish between instructions with side effects and those without. Previously, optimization passes would assume any instruction with an output value did not have side effects, and could be deleted if the output value was not used. This is no longer true for C calls; a C function might both have a side effect and return a value.

GC maps

Now that FFI calls no longer force the optimizer to sync all live values to the data and retain stacks, it can happen that SSA values are live across an FFI call. These values get spilled to the call stack by the register allocator. Spilling to the call stack is cheaper than spilling to the data and retain stacks, because floating point values and integers do not need to be boxed, and since the spilling is done later in the optimization process, optimizations can proceed across the call site instead of being stumped by pushes and pops on either side.

However, since FFI calls can invoke callbacks, which in turn run Factor code, which can trigger a garbage collection, the garbage collector must be able to identify spill slots in call frames which contain tagged pointers.

The technique I'm using is to record "GC maps". This idea comes from a paper titled Compiler Support for Garbage Collection in a Statically Typed Language (Factor is dynamically typed, and the paper itself doesn't have anything specific to static typing in it, so I found the title a bit odd). The Java HotSpot VM uses the same technique. The basic idea is that for every call site, you record a bitmap indicating which spill slots contain tagged pointers. This information is then stored in a per-code-block map, where the keys are return addresses and the values are these bitmaps.

In the future, I intend on using GC maps at call sites of Factor words as well, instead of spilling temporary values to the retain stack; then I can eliminate the retain stack altogether, freeing up a register. After this is done the data stack will only be used to pass parameters between words, and not to store temporaries within a word. This will allow more values to be unboxed in more situations, and it will improve accuracy of compiler analyses.

In fact, getting GC maps worked out was my primary motivation for this FFI rewrite; the code cleanups and performance improvements were just gravy.

Callback support improvements

Another one of those things that only makes sense when you look at how Factor evolved is that the body of an FFI callback was compiled with the non-optimizing compiler, rather than the optimizing compiler. It used to be that only certain definitions could be optimized, because static stack effects were optional and there were many common idioms which did not have static stack effects. It has been more than a year since I undertook the engineering effort to make the compiler enforce static stack safety, and the implementation of callbacks was the last vestigial remnant from the bad old days.

This design made callbacks harder to debug than they should be; if you used up too many parameters, or forgot to push a return value, you'd be greeted with a runtime error instead of a compiler error. Now this has been fixed, and callbacks are fully compiled with the optimizing compiler.

Factor talk in Boston, July 26th

2010-07-02T00:53:00.002-04:00

I will be presenting Factor at the Boston Lisp Users' Group on July 26th, 2010. Details in François-René Rideau's announcement. I'm also going to be giving a quick talk at the Emerging Languages Camp in Portland, July 22nd. Unfortunately registration for this camp is already full.

Comparing Factor's performance against V8, LuaJIT, SBCL, and CPython

2010-05-29T04:46:00.019-04:00

Together with Daniel Ehrenberg and Joe Groff, I'm writing a paper about Factor for DLS2010. We would appreciate feedback about the draft version of the paper. As part of the paper we include a performance comparison between Factor, V8, LuaJIT, SBCL, and Python. The performance comparison consists of some benchmarks from the The Computer Language Benchmarks Game. I'm posting the results here first, in case there's something really stupid here.

Language implementations

Factor and V8 were built from their respective repositories. SBCL is version 1.0.38. LuaJIT is version 2.0.0beta4. CPython is version 3.1.2. All language implementations were built as 64-bit binaries and run on an 2.4 GHz Intel Core 2 Duo.

Benchmark implementations

Factor implementations of the benchmarks can be found in our source repository:

Implementations for the other languages can be found at the language benchmark game CVS repository:

	LuaJIT	SBCL	V8	CPython
binary-trees	binarytrees.lua-2.lua	binarytrees.sbcl	binarytrees.javascript	binarytrees.python3-6.python3
fasta	fasta.lua	fasta.sbcl	fasta.javascript-2.javascript	fasta.python3-2.python3
knucleotide	knucleotide.lua-2.lua	knucleotide.sbcl-3.sbcl	knucleotide.javascript-3.javascript	knucleotide.python3-4.python3
nbody	nbody.lua-2.lua	nbody.sbcl	nbody.javascript	nbody.python3-4.python3
regex-dna		regexdna.sbcl-3.sbcl	regexdna.javascript	regexdna.python3
reverse-complement	revcomp.lua	revcomp.sbcl	revcomp.javascript-2.javascript	revcomp.python3-4.python3
spectral-norm	spectralnorm.lua	spectralnorm.sbcl-3.sbcl	spectralnorm.javascript	spectralnorm.python3-5.python3

In order to make the reverse complement benchmark work with SBCL on Mac OS X, I had to apply this patch; I don't understand why:

--- bench/revcomp/revcomp.sbcl 9 Feb 2007 17:17:26 -0000 1.4
+++ bench/revcomp/revcomp.sbcl 29 May 2010 08:32:19 -0000
@@ -26,8 +26,7 @@
 
 (defun main ()
   (declare (optimize (speed 3) (safety 0)))
-  (with-open-file (in "/dev/stdin" :element-type +ub+)
-    (with-open-file (out "/dev/stdout" :element-type +ub+ :direction :output :if-exists :append)
+  (let ((in sb-sys:*stdin*) (out sb-sys:*stdout*))
       (let ((i-buf (make-array +buffer-size+ :element-type +ub+))
             (o-buf (make-array +buffer-size+ :element-type +ub+))
             (chunks nil))
@@ -72,4 +71,4 @@
                         (setf start 0)
                         (go read-chunk))))
            end-of-input
-             (flush-chunks)))))))
+             (flush-chunks))))))

Running the benchmarks

I used Factor's deploy tool to generate minimal images for the Factor benchmarks, and then ran them from the command line:

./factor -e='USE: tools.deploy "benchmark.nbody-simd" deploy'
time benchmark.nbody-simd.app/Contents/MacOS/benchmark.nbody-simd

For the scripting language implementations (LuaJIT and V8) I ran the scripts from the command line:

time ./d8 ~/perf/shootout/bench/nbody/nbody.javascript -- 1000000
time ./src/luajit ~/perf/shootout/bench/nbody/nbody.lua-2.lua 1000000

For SBCL, I did what the shootout does, and compiled each file into a new core:

ln -s ~/perf/shootout/bench/nbody/nbody.sbcl .

cat > nbody.sbcl_compile <<EOF
(proclaim '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0) (space 0)))
(handler-bind ((sb-ext:defconstant-uneql (lambda (c) (abort c))))
  (load (compile-file "nbody.sbcl" )))
(save-lisp-and-die "nbody.core" :purify t)
EOF

sbcl --userinit /dev/null --load nbody.sbcl_compile

cat > nbody.sbcl_run <<EOF
(proclaim '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0) (space 0)))
(main) (quit)
EOF

time sbcl --dynamic-space-size 500 --noinform --core nbody.core --userinit /dev/null --load nbody.sbcl_run 1000000

For CPython, I precompiled each script into bytecode first:

python3.1 -OO -c "from py_compile import compile; compile('nbody.python3-4.py')"

Benchmark results

All running times are wall clock time from the Unix time command. I ran each benchmark 5 times and used the best result.

	Factor	LuaJIT	SBCL	V8	CPython
fasta	2.597s	1.689s	2.105s	3.948s	35.234s
reverse-complement	2.377s	1.764s	2.955s	3.884s	1.669s
nbody	0.393s	0.604s	0.402s	4.569s	37.086s
binary-trees	1.764s	6.295s	1.349s	2.119s	19.886s
spectral-norm	1.377s	1.358s	2.229s	12.227s	1m44.675s
regex-dna	0.990s	N/A	0.973s	0.166s	0.874s
knucleotide	1.820s	0.573s	0.766s	1.876s	1.805s

Benchmark analysis

Some notes on the results:

There is no Lua implementation of the regex-dna benchmark.
Some of the SBCL benchmark implementations can make use of multiple cores if SBCL is compiled with thread support. However, by default, thread support seems to be disabled on Mac OS X. None of the other language implementations being tested have native thread support, so this is a single-core performance test.
Factor's string manipulation still needs work. The fasta, knucleotide and reverse-complement benchmarks are not as fast as they should be.
The binary-trees benchmark is a measure of how fast objects can be allocated, and how fast the garbage collector can reclaim dead objects. LuaJIT loses big here, perhaps because it lacks generational garbage collection, and because Lua's tables are an inefficient object representation.
The regex-dna benchmark is a measure of how efficient the regular expression implementation is in the language. V8 wins here, because it uses Google's heavily-optimized Irregexp library.
Factor beats the other implementations on the nbody benchmark because it is able to make use of SIMD.
For some reason SBCL is slower than the others on spectral-norm. It should be generating the same code.
The benchmarks exercise insufficiently-many language features. Any benchmark that uses native-sized integers (for example, an implementation of the SHA1 algorithm) would shine on SBCL and suffer on all the others. Similarly, any benchmark that requires packed binary data support would shine on Factor and suffer on all the others. However, the benchmarks in the shootout mostly consist of scalar floating point code, and text manipulation only.

Conclusions

Factor's performance is coming along nicely. I'd like to submit Factor to the computer language shootout soon. Before doing that, we need a Debian package, and the deploy tool needs to be easier to use from the command line.

A collection of small compiler improvements

2010-05-10T18:23:00.003-04:00

One of the big optimizations I'm planning on implementing in Factor is support for computations on machine-word-sized integers. The motivation is as follows. While code that operates on small integers (fixnums) does not currently allocate memory for intermediate values, and as a result can compile very efficiently if type checks are eliminated, sometimes fixnum precision is not quite enough. Using bignums in algorithms such as SHA1 that require 32-bit or 64-bit arithmetic incurs a big performance hit over writing the code in a systems language. My plan is to have the compiler support machine integers as an intermediate step between fixnums and bignums. Machine integers would be boxed and unboxed at call boundaries, but tight loops operating on them will run in registers.

While I haven't yet implemented the above optimization, I've laid the groundwork and made it possible to represent operations on untagged integers at the level of compiler IR at least. While unboxed floats do not cause any complications for the GC, unboxed integers do, because they share a register file with tagged pointers. To make Factor's precise GC work, the compiler can now distinguish registers containing tagged pointers from those containing arbitrary integer data, by breaking down the register class of integer registers into two "representations", tagged and untagged.

Since the above reworking touched many different parts of the compiler, I also took the time to implement some minor optimizations and clean up some older code. These improvements will be the topic of this post.

To understand this post better, you should probably skim the list of low-level IR instructions defined in compiler.cfg.instructions first. Also, feel free to post comments here or e-mail me questions about the design of the Factor compiler.

Improvements to value numbering

In the x86 architecture, almost any instruction can take a memory operand, and memory operands take the form (base + displacement * scale + offset), where base and displacement are registers, offset is a 32-bit signed integer, and scale is 1, 2, 4 or 8. While using a complex addressing mode is not any faster than writing out the arithmetic by hand with a temporary register used to store the final address, it can reduce register pressure and code size.

The compiler now makes better use of complex addressing modes. Prior to optimization, the low level IR builder lowers specialized array access to the ##load-memory-imm and ##store-memory-imm instructions. For example, consider the following code:

USING: alien.c-types specialized-arrays ;
SPECIALIZED-ARRAY: float

: make-data ( -- seq ) 10 iota [ 3.5 + sqrt ] float-array{ } map-as ;

The inner loop consists of the following low level IR:

##integer>float 23 14
##sqrt 24 23
##load-integer 25 2
##slot-imm 26 15 2 7
##load-integer 27 4
##mul 28 14 27
##tagged>integer 29 26
##add-imm 30 29 7
##add 31 30 28
##store-memory-imm 24 31 0 float-rep f
##load-integer 32 1
##add 33 14 32

The ##mul, ##add-imm and ##add instructions compute the address input to ##store-memory-imm. After value numbering, these three instructions have been fused with ##store-memory-imm to form ##store-memory:

##integer>float 62 57
##sqrt 63 62
##slot-imm 65 48 2 7
##tagged>integer 68 65
##store-memory 63 68 57 2 7 float-rep f
##add-imm 72 57 1

Optimistic copy propagation

While the low-level optimizer's value numbering and alias analysis passes only operate on individual basic blocks (local optimizations), the copy propagation pass is global, meaning it takes the entire procedure being compiled into account.

Eventually I will merge the local alias analysis and value numbering passes with the copy propagation pass to get an optimization known as "global value numbering with redundant load elimination". One step along this road is a rewrite that makes the copy propagation pass optimistic, in the following sense.

Copy propagation concerns itself with eliminating ##copy instructions, which correspond to assignments from one SSA value to another (new) value:

y = x

When such an instruction is processed, all usages of the value y can be replaced with the value x, in every basic block, and the definition of y deleted.

A simple extension of the above treats a ##phi instruction where all inputs are equal the same as a copy. This optimizes cases such as:

 a = ...
if(...)
{
    b = a
}
c = phi(b,a)

The case of ##phi instructions where one of the inputs is carried by a back edge in the control flow graph (ie, a loop) is where the optimistic assumption comes in. Consider the following code, where the definition of x'' is carried by a back edge:

x' = 0

while(...)
{
    x = phi(x',x'')
    x'' = ...
}

Optimistic copy propagation is able to eliminate the phi node entirely. Switching from pessimistic to optimistic copy propagation eliminated about 10% of copy instructions. While this is not a great amount, it did reduce spilling in a few subroutines I looked at, and there is no increase in code complexity from this new approach.

Representation selection improvements

The low-level IR now includes three new instructions, ##load-double, ##load-float and ##load-vector. These are inteded for loading unboxed floating point values and SIMD vectors into vector registers without using an integer register to temporarily hold a pointer to the boxed value.

Uses of these instructions are inserted by the representation selection pass. If the destination of a ##load-reference is used in an unboxed representation, then instead of inserting a memory load following the ##load-reference, the instruction is replaced with one of the new variants.

Loads from constant addresses directly into floating point and vector registers are only possible on x86, and not PowerPC, so the optimization is not performed on the latter architecture. On x86-32, an immediate displacement can encode any 32-bit address. On x86-64, loading from an absolute 64-bit address requires an integer register, however instruction pointer-relative addressing is supported with a 32-bit displacement. To make use of this capability, the compiler now supports a new "binary literal area" for unboxed data that compiled code can reference. The unboxed data is placed immediately following a word's machine code, allowing RIP-relative addressing to be used on x86-64.

This optimization, together with value numbering improvements, helps reduce pressure on integer registers in floating point loops.

Register allocator improvements

Once representation selection has run, each SSA value has an associated representation and register class. Each representation always belongs to one specific register class; a register class is a finite set of registers from which the register allocator is allowed to choose a register for this type of value.

Before register allocation, the SSA destruction pass transforms ##phi instructions into ##copys, and then subsequently performs live range coalescing to eliminate as many of the copies as possible.

Coalescing two SSA values from different register classes does not make sense; the compiler will not be able to generate valid machine code if a single SSA value is used as both a float and an integer, since on most CPUs the integer and floating point register files are distinct.

However, coalescing values with different representations, but the same register class, is okay. Consider the case where a double-precision float is computed, and then converted into a single precision float, and subsequently stored into memory. If the double-precision value is not used after the conversion, then the same register that held the input value can be reused to store the result of the single-precision conversion.

Previously this pass only coalesced values with identical representations; now I've generalized it to coalescing values with the same register class but possibly different representations. This reduces register pressure and spilling.

The tricky part about making it work is that the register allocator needs to know the value's representation, not just its register class, for generating correct spills and reloads. For example, a spilled value with register class float-regs can use anywhere from 4 to 16 bytes in the stack frame, depending on the specific representation: single precision float, double precision float, or SIMD vector. Clearly, if coalescing simply lost this fine-grained representation information and only retained register classes, the register allocator would not have enough information to generate valid code.

The solution is to have live range coalescing compute the equivalence classes of SSA values without actually renaming any usages to point to the canonical representative. The renaming map is made available to the register allocator. Most places in the register allocator where instruction operands are examined make use of the renaming map.

Until the splitting phase, these equivalence classes are in one-to-one correspondence with live intervals, and each live interval has a single machine register and spill slot. However, when spill and reload decisions are made, the register allocator uses the original SSA values to look up representations.

If Factor's compiler did not use SSA form at all, there would still be a copy coalescing pass, and the register allocator could also support coalescing values with different representations, by first performing a dataflow analysis known as reaching definitions. This would propagate representation information to use sites.

Retaining SSA structure all the way until register allocation gives you the results of this reaching definitions analysis "for free". In both the SSA and non-SSA case, you still don't want definitions with multiple different representations reaching the same call site. The SSA equivalent of this would be a phi instruction whose inputs had different representations. The compiler ensures this doesn't happen by first splitting up the set of SSA values into strongly-connected components (SCCs) whose edges are phi nodes. The same representation is then assigned to each member of every SCC; if an agreeable representation is not found then it falls back on boxing and tagging all members.

Notice that while both representation selection and SSA destruction group values into equivalence classes, the groupings do not correspond to each other and neither one is a refinement of the other. Not all copies resulting from phi nodes get coalesced away, so a single SCC may intersect multiple coalescing classes. This can happen if the first input to a phi node is live at the definition point of the second:

b = ...

if(...)
{
    a = ...
    foo(b)
}
/* 'c' can be coalesced with 'a' or 'b' -- but not both.
All three values belong to the same SCC and must have the same
representation */
c = phi(a,b)

On the other hand, two values from different SCCs might also get coalesced together:

a = some-double-float
/* if 'a' is not live after this instruction, then 'a' and 'b'
can share a register. They belong to different SCCs and have
different representations */
b = double-to-single-precision-float(a)

Compiler code cleanups

In addition to just adding new optimizations I've also simplified and refactored the internals of some of the passes I worked on.

One big change is that the "machine representation" used at the very end of the compilation process is gone. Previously, after register allocation had run, the control flow graph would be flattened into a list of instructions with CFG edges replaced by labels and jumps. The code generator would then iterate over this flat representation and emit machine code for each virtual instruction. However since no optimization passes ran on the flat representation, it was generated and then immediately consumed. Combining the linearization pass with the code generation pass let me eliminate about a dozen IR instructions that were specific to the flat representation (anything dealing with labels and jumps to labels). It also sped up compilation time slightly.

Value numbering's common subexpression elimination now uses a simpler and more efficient scheme for hashed lookup of expressions. New algebraic simplifications are also easier to add now, because the def-use graph is easier to traverse.

Some instructions which could be expressed in terms of others were removed, namely the ##string-nth and ##set-string-nth-fast instructions. Reading and writing characters from strings can be done by combining simpler memory operations already present in the IR.

A number of instructions were combined. All of the instructions for reading from memory in different formats, ##alien-unsigned-1, ##alien-signed-4, ##alien-double, have been merged into a single ##load-memory instruction which has a constant operands storing the C type and representation of the data being loaded. Similarly, ##set-alien-signed-8, etc have all been merged into ##store-memory. This restructuring allows optimization passes to more easily treat all memory accesses in a uniform way.

A bug fix for alias analysis

While working on the above I found an interesting bug in alias analysis. It would incorrectly eliminate loads and stores in certain cases. The optimizer assumed that a pointer to a freshly-allocated object could never alias a pointer read from the heap. However the problem of course is that such a pointer could be stored in another object, and then read back in.

Here is a Factor example that demonstrates the problem. First, a couple of tuple definitions; the type declarations and initial value are important further on.

USING: typed locals ;

TUPLE: inner { value initial: 5 } ;
TUPLE: outer { value inner } ;

Now, a very contrieved word which takes two instances of outer,
mutates one, and reads a value out of the other:

TYPED: testcase ( x: outer y: outer -- )
    inner new :> z               ! Create a new instance of 'inner'
    z x value<<                  ! Store 'z' in 'x'
    y value>> :> new-z           ! Load 'new-z' from 'y'
    10 new-z value<<             ! Store a value inside 'new-z'  
    z value>>                    ! Read a value out of 'z'
    ;

Note that the initial value of the value slot in the inner tuple is 5, so inner new creates a new instance holding the value 5. In the case where x and y point at the same object, new-z and z will point to the same object, and the newly-allocated object's value is set to 10. However, the compiler did not realize this, and erronously constant-folded z value>> down to 5!

This bug never came up in actual code; the facepalm moment came while I was doing some code refactoring and noticed that the above case was not being handled.

Instruction scheduling to reduce register pressure

I'm not the only one who's been busy improving the Factor compiler. One of the co-inventors of Factor has cooked up an instruction scheduler and improved method inlining. The scheduler has been merged, and the it looks like the method inlining improvements should be ready in a few days.

Some benchmarks

Here is a comparison between the April 17th build of Factor with the latest code from the GIT repository. I ran a few of the language shootout benchmarks on a 2.4 GHz MacBook Pro. Factor was built in 32-bit mode, because the new optimizations are most effective on the register-starved x86.

Benchmark	Before (ms)	After (ms)
nbody-simd	415	349
fasta	2667	2485
knucleotide	182	177
regex-dna	109	86
spectral-norm	1641	1347

Factor 0.93 now available

2010-04-16T18:24:00.004-04:00

After two months of development, Factor 0.93 is now available for download from the Factor website. A big thanks to all the contributors, testers and users. This release would not be possible without your help. A summary of the most important changes follows:

Incompatible changes:

Factor no longer supports NetBSD, due to limitations in that operating system. (Slava Pestov)
sets, hash-sets, bit-sets: these vocabularies have been redesigned around a new generic protocol for sets (Daniel Ehrenberg)
Strings can no longer be used to refer to C types in FFI calls; you must use C type words instead. Also, ABI specifiers are now symbols rather than strings. So for example, the following code will no longer work:
```
: my-callback ( -- callback ) "int" { "int" "int" } "cdecl" [ + ] alien-callback ;
```
you must now write:
```
: my-callback ( -- callback ) int { int int } cdecl [ + ] alien-callback ;
```
(Joe Groff)
The behavior of string types has changed. The char* C type is now just a bare pointer; to get the automatic conversion to and from Factor strings, use the c-string type. See the documentation for details. (Joe Groff)
FFI function return values which are pointers to structs are now boxed in a struct class, instead of returning a bare alien. This means that many memory>struct calls can be removed. If the return value is actually a pointer to an array of structs, use specialized arrays as before. (Joe Groff)
C-ENUM: now takes an additional parameter which is either the name of a new C type to define, or f. This type is aliased to int. (Erik Charlebois)
The stack checker now supports row polymorphic stack effects, for improved error checking. See the documentation for details. (Joe Groff)

New features:

Co-operative threads now use efficient context-switching primitives instead of copying stacks with continuations (Slava Pestov)
Added final class declarations, to prohibit classes from being subclassed. This enables a few compiler optimizations (Slava Pestov)
Added platform support metadata for vocabularies. Vocabulary directories can now contain a platforms.txt file listing operating system names which they can be loaded under. (Slava Pestov)
The deploy tool can now deploy native libraries and resource files, and supports custom icons. (Joe Groff)
Joint behavior of vocabularies - the new require-when word can be used to express that a vocabulary should be loaded if two existing vocabularies have been loaded (Daniel Ehrenberg)
Callstack overflow is now caught and reported on all platforms except for Windows and OpenBSD. (Slava Pestov)
The prettyprinter now has some limits set by default. This prevents out of memory errors when printing large structures, such as the global namespace. Use the without-limits combinator to disable limits. (Slava Pestov)
Added fastcall and thiscall ABIs on x86-32 (Joe Groff)
The build farm's version release process is now more automated (Slava Pestov)

Improved libraries:

delegate: add BROADCAST: syntax, which delegates a generic word with no outputs to an array of multiple delegates. (Joe Groff)
game.input: X11 support. (William Schlieper)
gpu: geometry shader support. (Joe Groff)
opengl: OpenGL 4.0 support. (Joe Groff)

New libraries:

bit.ly: Factor interface to the bit.ly URL shortening service. (Slava Pestov)
chipmunk: binding for Chipmunk 2D physics library. (Erik Charlebois)
cuda: binding to NVidia's CUDA API for GPU computing. (Doug Coleman, Joe Groff)
cursors: experimental library for iterating over collections, inspired by STL iterators. (Joe Groff)
elf: parsing ELF binaries. The elf.nm vocabulary is a demo which prints all symbols in an ELF binary. (Erik Charlebois)
images.pbm, images.pgm, images.ppm: libraries for loading PBM, PGM and PPM images (Erik Charlebois)
macho: parsing Mach-O binaries. (Erik Charlebois)
opencl: binding for the OpenCL standard interface for GPU computing. (Erik Charlebois)
path-finding: implementation of A* and BFS path finding algorithms. (Samuel Tardieu)
windows.ddk: binding for Windows hardware abstraction layer. (Erik Charlebois)

Frame-based structured exception handling on Windows x86-64

2010-04-08T20:16:00.002-04:00

Factor used to use vectored exception handlers, registered with AddVectoredExceptionHandler, however vectored handlers are somewhat problematic. A vectored handler is always called prior to any frame-based handlers, so Factor could end up reporting bogus exceptions if the FFI is used to call a library that uses SEH internally. This prompted me to switch to frame-based exception handlers. Unfortunately, these are considerably more complex to use, and the implementation differs between 32-bit and 64-bit Windows.

I briefly discussed frame-based SEH on 32-bit Windows in my previous post. During the switch to 64 bits, Microsoft got rid of the old frame-based SEH implementation and introduced a new, lower-overhead approach. Instead of pushing and popping exception handlers onto a linked list at runtime, the system maintains a set of function tables, where each function table stores exception handling and stack frame unwinding information.

Normally, the 64-bit Windows function tables are written into the executable by the native compiler. However, language implementations which generate code at runtime need to be able to define new function tables dynamically. This is done with the RtlAddFunctionTable() function.

It took me a while to figure out the correct way to call this function. I found the os_windows_x86.cpp source file from Sun's HotSpot Java implementation was very helpful, and I based my code on the register_code_area() function from this file.

Factor and HotSpot only use function tables in a very simple manner, to set up an exception handler. Function tables can also be used to define stack unwinding behavior; this allows debuggers to generate backtraces, and so on. Doing that is more complicated and I don't understand how it works, so I won't attempt to discuss it here.

The RtlAddFunctionTable() function takes an array of RUNTIME_FUNCTION structures and a base address. For some unknown reason, all pointers in the structures passed to this function are 32-bit integers relative to the base address.

For a runtime compiler that does not need to perform unwinding, it suffices to map the entire code heap to one RUNTIME_FUNCTION. A RUNTIME_FUNCTION has three fields:

BeginAddress - the start of the function
EndAddress - the end of the function
UnwindData - a pointer to unwind data

All pointers are relative to the base address passed into RtlAddFunctionTable(). The unwind data can take various forms. For the simple case of no unwind codes and an exception handler, the following structure is used:

struct UNWIND_INFO {
    UBYTE Version:3;
    UBYTE Flags:5;
    UBYTE SizeOfProlog;
    UBYTE CountOfCodes;
    UBYTE FrameRegister:4;
    UBYTE FrameOffset:4;
    ULONG ExceptionHandler;
    ULONG ExceptionData[1];
};

The Version and Flags fields should be set to 1, the ExceptionHandler field set to a function pointer, and the rest of the fields set to 0. The exception handler pointer must be within relative to the base address, and it must also be within the memory range specified by the BeginAddress and EndAddress fields of the RUNTIME_FUNCTION structure. The exception handler has the same function signature as in the 32-bit SEH case:

LONG exception_handler(PEXCEPTION_RECORD e, void *frame, PCONTEXT c, void *dispatch)

In both Factor and HotSpot, the exception handler is a C function, however the RtlAddFunctionTable() API requires that it be within the bounds of the runtime code heap. To get around the restriction, both VMs allocate a small trampoline in the code heap which simply jumps to the exception handler, and use a pointer to the trampoline instead. Similarly, because the "pointers" in these structures are actually 32-bit integers, it helps to allocate the RUNTIME_FUNCTION and UNWIND_INFO in the code heap as well, to ensure that everything is within the same 4Gb memory range.

The above explanation probably didn't make much sense, so I invite you to check out the source code instead: os-windows-nt-x86.64.cpp.

Switching call stacks on different platforms

2010-04-04T16:24:00.005-04:00

User-space implementations of coroutines and green threads need to be able to switch the CPU's call stack pointer between different memory regions. Since this is inherently CPU- and OS-specific, I'll limit my discussion to CPUs and platforms that Factor supports.

System APIs for switching call stacks

Windows has an API for creating and switching between contexts, which it calls "fibers". The main functions to look at are CreateFiber() and SwitchToFiber(). On Windows, by far the easiest way to switch call stacks is to just use fibers.
Most Unix systems have a set of functions operating on ucontexts, such as makecontext(), swapcontext() and so on. On some systems, these APIs are poorly implemented and documented.
The C standard library functions setjmp() and longjmp() can be (ab)used to switch contexts. The jmpbuf structure stored to by setjmp() and read from by longjmp() contains a snapshot of all registers, including the call stack pointer. Once you've allocated your own call stack, you can capture a jmp_buf with setjmp(), change the call stack pointer, and then resume execution with longjmp(). As far as I know, this is completely undocumented and unsupported with every major C compiler.
The most direct way is to write some assembly to switch the relevant registers directly. Paradoxically, this approach is the most portable out of all of these, because while it is CPU-specific, the details are pretty much the same across most OSes, Windows being the exception. Switching call stacks on Windows is a bit more involved than just changing the ESP register, and requires updating some Windows-specific in-memory structures. However, it is still easy enough to do directly, if you do not wish to use the fiber API. I will describe the details at the end of this post.

High-level libraries for switching call stacks

A couple of existing libraries implement high-level, cross-platform abstractions using some combination of the above mechanisms.

libcoroutine uses fibers on Windows, and ucontext and longjmp on Unix.
libcoro uses a handful of Unix-specific APIs if they're available, or falls back onto some hand-coded assembly routines. The latter works on Windows.

NetBSD/x86 limitation

There is no realiable way to switch call stacks on NetBSD/x86, because of a limitation in the implementation of libpthread. Even if your program doesn't use pthreads, it might link with a library that does, such as Glib. The pthread library replaces various C standard library functions with its own versions, and since this includes some extremely common calls such as malloc(), almost nothing will work as a result.

The reason is that the NetBSD pthread library uses a silly trick to implement thread-local storage, one which unfortunately assumes that every native thread has exactly one call stack. The trick is to always allocate thread call stacks on multiples of the maximum call stack size. Then, each thread's unique ID can just be the result of masking the call stack pointer by the maximum call stack size.

Windows-specific concerns

So far, I've only worked out the details of switching call stacks on 32-bit Windows. I'll talk about 64-bit Windows in another post.

Windows has a mechanism known as Structured Exception Handling, which is a sort of scoped exception handling mechanism with kernel support. Windows uses SEH to deliver processor traps to user-space applications (illegal memory access, division by zero, etc). Some C++ compilers also use SEH to implement C++ exceptions.

On Windows, simply changing the ESP register to point at another memory region is insufficient because structured exception handling must know the current call stack's beginning and end, as well as a pointer to the innermost exception handler record.

These three pieces of information are stored in a per-thread information block, known as the TIB. The fiber switching APIs update the TIB for you, which is why Microsoft recommends their use.

The TIB

The TIB is defined by the NT_TIB struct in winnt.h:

typedef struct _NT_TIB {
    struct _EXCEPTION_REGISTRATION_RECORD *ExceptionList;
    PVOID StackBase;
    PVOID StackLimit;
    PVOID SubSystemTib;
    _ANONYMOUS_UNION union {
        PVOID FiberData;
        DWORD Version;
    } DUMMYUNIONNAME;
    PVOID ArbitraryUserPointer;
    struct _NT_TIB *Self;
} NT_TIB,*PNT_TIB;

The relevant fields that must be updated when switching call stacks are ExceptionList, StackBase and StackLimit.

Note that since the x86 call stack grows down, StackLimit is the start of the call stack's memory region and StackBase is the end.

Structured exception handlers

Structured exception handlers are stored in a linked list on the call stack, with the head of the list pointed at by the ExceptionList field of the TIB:

struct _EXCEPTION_REGISTRATION_RECORD
{
     PEXCEPTION_REGISTRATION_RECORD Next;
     PEXCEPTION_DISPOSITION Handler;
} EXCEPTION_REGISTRATION_RECORD, *PEXCEPTION_REGISTRATION_RECORD;

The exception list should be saved and restored when switching between call stacks, and a new call stack should begin with an empty list (ExceptionList set to NULL).

If the ExceptionList field of the TIB or the Next field of an exception record point outside the call stack, then the handler in question will not be called at all.

Accessing the TIB

On x86-32, the current thread's TIB is stored starting at address 0 in the segment pointed at by the FS segment register. The Self field always points at the struct itself. Since Windows uses flat addressing, the segment storing the TIB begins somewhere in the linear 32-bit address space, so an assembly routine to fetch the TIB and return a pointer to it in EAX looks like this:

fetch_tib:
    mov eax,[fs:24]
    ret

This assembly routine can then be called from C code, which can manipulate the TIB like any other structure.

Sample code for updating Windows-specific structures

The basis/cpu/x86/32/winnt/bootstrap.factor file defines assembly subroutines for updating the TIB when switching call stacks. These routines are invoked by the x86-32 non-optimizing compiler backend:

Incompatible change in Mach exception handler behavior on Mac OS X 10.6

2010-03-23T04:29:00.004-04:00

On Mac OS X, Factor uses Mach exceptions rather than Unix signals to receive notifications of illegal memory accesses and arithmetic exceptions from the operating system. This is used to catch datastack underflows, division by zero, and the like. The code implementing this can be found in vm/mach_signal.c in the Factor repository. This file is based on code from the GNU libsigsegv project, with special permission to use it under a BSD license instead of the restrictive GPL.

It seems that as of Mac OS X 10.6, exceptions raised by child processes are now reported to the parent if the parent has an exception handler thread. This caused a problem in Factor if a child process crashed with an access violation; Factor would think the access violation occurred in Factor code, and die with an assertion failure when attempting to map the thread ID back into a Factor VM object. It seems the simplest way is to add the following clause to the catch_exception_raise() function:

if(task != mach_task_self()) return KERN_FAILURE;

This fix should be applicable to the original libsigsegv code as well, along with other projects, such as CLisp, that use this library.

Adding a recaptcha to the Factor pastebin

2010-03-11T03:16:00.005-05:00

Lately the Factor pastebin has been flooded with penis enlargement spam. The pastebin had its own very weak captcha that worked well enough for a while: there was a form field that was required to be left blank, and if it was not blank validation would fail. However, spammers have started working around it so we needed something stronger. I decided to solve the problem once and for all by integrating Doug Coleman's furnace.recaptcha vocabulary into the pastebin. Doing this was surprisingly easy.

First, I changed the USING: form in webapps.pastebin to reference the furnace.recaptcha vocabulary:

USING: namespaces assocs sorting sequences kernel accessors
hashtables db.types db.tuples db combinators
calendar calendar.format math.parser math.order syndication urls
xml.writer xmode.catalog validators
html.forms
html.components
html.templates.chloe
http.server
http.server.dispatchers
http.server.redirection
http.server.responses
furnace
furnace.actions
furnace.redirection
furnace.auth
furnace.auth.login
furnace.boilerplate
furnace.recaptcha
furnace.syndication
furnace.conversations ;

Next, I changed the validate-entity word. This word is used to validate a form submission when adding a new paste or a new annotation. Instead of validating a captcha using the old simple scheme, it now calls validate-recaptcha:

: validate-entity ( -- )
    {
        { "summary" [ v-one-line ] }
        { "author" [ v-one-line ] }
        { "mode" [ v-mode ] }
        { "contents" [ v-required ] }
    } validate-params
    validate-recaptcha ;

Finally, I edited the new-paste.xml and new-annotation.xml templates to add a recaptcha component inside the t:form tag:

<tr><td colspan="2"><t:recaptcha /></td></tr>

The implementation of the furnace.recaptcha vocabulary is very straightforward and takes advantage of several features of Factor's web framework. It uses http.client to communicate with the recaptcha server, and furnace.conversations to pass the validation error between requests. Finally, it uses the CHLOE: parsing word to define the t:recaptcha tag for use in templates:

CHLOE: recaptcha drop [ render-recaptcha ] [xml-code] ;

Final classes and platform-specific vocabularies

2010-02-24T02:35:00.006-05:00

Final classes

I added final classes, in the Java sense. Attempting to inherit from a final class raises an error. To declare a class as final, suffix the definition with "final", in the same manner that words can be declared "inline" or "foldable":

TUPLE: point x y z ; final

The motivation for final classes was not obvious. There are three main reasons I added this feature.

Unboxed tuple arrays used to have the caveat that if you store an instance of a subclass into a tuple array of a superclass, then the slots of the subclass would be "sliced off":

TUPLE: point-2d x y ;

TUPLE-ARRAY: point-2d

TUPLE: point-3d < point-2d z ;

SYMBOL: my-array

1  my-array set

1 2 3 point-3d boa my-array get set-first

my-array get first .
=> T{ point-2d { x 1 } { y 2 } }

This warranted a paragraph in the documentation, and vigilance on the part of the programmer. Now, tuple arrays simply enforce that the element class is final, and if it is not, an error is raised. This removes a potential source of confusion; it is always nice when written warnings in the documentation can be replaced by language features.

Joe Groff's typed library has a similar problem. This library has a feature where input and output parameters which are read-only tuples are passed by value to improve performance. This could cause the same "slicing problem" as above. Now, typed only passes final read-only tuples by value.

Finally, there was a previous mechanism for prohibiting subclassing, but it wasn't exposed as part of the syntax. It was used by the implementation of struct classes to prevent subclassing of structs. The struct class implementation now simply declares struct classes as final.

Typed words can now be declared foldable and flushable

Factor has a pretty unique feature; the user can declare words foldable (which makes them eligible for constant folding at compile time if the inputs are all literal) or flushable (which makes them eligible for dead code elimination if the output results are not used). These declarations now work with typed words.

Platform-specific vocabularies

I added a facility to declare what operating systems a vocabulary runs on. Loading a vocabulary on an unsupported platform raises an error, with a restart if you know what you're doing. The load-all word skips vocabularies which are not supported by the current platform.

If a platforms.txt file exists in the vocabulary's directory, this file is interpreted as a newline-separated list of operating system names from the system vocabulary. This complements the existing vocabulary metadata for authors, tags, and summary.

This feature helps the build farm avoid loading code for the wrong platform. It used to be that vocabularies with the "unportable" tag set would be skipped by load-all, however this was too coarse-grained. For example, both the curses and DirectX bindings were tagged as unportable, and so the build farm was not loading or testing them on any platform. However, curses is available on Unix systems, and DirectX is available on Windows systems. With the new approach, there is a extra/curses/platforms.txt file listing unix as a supported platform, and the various DirectX vocabulary directories have platforms.txt files listing windows.

Factor 0.92 now available

2010-02-16T03:47:00.003-05:00

I'm proud to announce the release of Factor 0.92. This release comes two years after the last release, 0.91. Proceed to the Factor website or directly to downloads directory to obtain a copy.

More than 30 developers have contributed code to this release. I would like to thank all of the users and contributors for their efforts; Factor would not be at the stage it is today without your help.

Since there have been so many changes since the last release, the below changelog is only an incomplete summary. In particular, there have been many incompatible syntax and core library changes since the last release.

The next release cycle will not last as long as this one; from this point on, I'm planning on having monthly releases or so. There will be fewer incompatible language changes in the upcoming months; the core language has almost been finalized at this point.

Language improvements

Static stack effects enforced for all words (Slava Pestov, Daniel Ehrenberg)
New object system: generic accessors, inheritance replaces delegation, type declarations on slots, read only slots, singletons (Slava Pestov)
Data flow combinators (Eduardo Cavazos)
Partial application syntax (Eduardo Cavazos)
Integers-as-sequences is no longer supported; use the iota virtual sequence instead (Doug Coleman, Slava Pestov)

Notable new libraries

db: Relational database access library with SQLite and PostgreSQL backends (Doug Coleman)
furnace: web framework that runs concatenative.org (Slava Pestov)
io.encodings: Extensive support for I/O encodings. All operations that transform strings to bytes and vice versa now take an encoding parameter (Daniel Ehrenberg)
unicode: Unicode-aware case conversion, character classes, collation, breaking, and normalization (Daniel Ehrenberg)
regexp: DFA-based regular expression matching. Supports Unicode and compiles to machine code (Daniel Ehrenberg)
io.sockets.secure: secure sockets with OpenSSL (Slava Pestov)
io.files.info, io.monitors: File system metadata and change monitoring (Doug Coleman, Slava Pestov)
images: loading and displaying BMP, TIFF, PNG, JPEG and GIF images (Doug Coleman, Marc Fauconneau)
gpu, game: Frameworks for GPU rendering and game development using OpenGL (Joe Groff)
math.floats.env: advanced IEEE floating point features (Joe Groff)
math.blas, alien.fortran: bindings to BLAS linear algebra library, built on top of a new Fortran FFI
math.vectors.simd: high-performance SIMD arithmetic with support for SSE versions up to 4.2 (Joe Groff)
specialized-arrays, specialized-vectors, classes.struct: high-performance support for unboxed value types (Slava Pestov, Joe Groff)

Implementation improvements

Thanks to the continuous integration system, binary packages are now available for 13 platforms (Eduardo Cavazos, Slava Pestov)
The compiler has been rewritten to improve compile time, performance of generated code, and correctness (1, 2, 3, 4, 5, 6) (Slava Pestov)
Polymorphic inline caching (Slava Pestov)
The garbage collector has been rewritten. A more precise write barrier speeds up minor collections, and a mark-sweep-compact algorithm is now used for full collections (Slava Pestov)
The Factor UI now supports Unicode font rendering, and the UI developer tools have all seen significant improvements (Slava Pestov)

Editor integration

fuel: Factor's Ultimate Emacs Library, a powerful emacs mode for editing Factor code. See misc/fuel/README in the Factor download for details (Jose A Ortega)

Replacing GNU assembler with Factor code

2010-01-25T14:44:00.013-05:00

Lately a major goal of mine has been to get the Factor VM to be as close as possible to standard C++, and to compile it with at least one non-gcc compiler, namely Microsoft's Windows SDK.

I've already eliminated usages of gcc-specific features from the C++ source (register variables mostly) and blogged about it.

The remaining hurdle was that several of the VM's low-level subroutines were written directly in GNU assembler, and not C++. Microsoft's toolchain uses a different assembler syntax, and I don't fancy writing the same routines twice, especially since the code in question is already x86-specific. Instead, I've decided to eliminate assembly code from the VM altogether. Factor's compiler infrastructure has perfectly good assembler DSLs for x86 and PowerPC written in Factor itself already.

Essentially, I rewrite the GNU assembler source files in Factor itself. The individual assembler routines have been replaced by new functionality added to both the non-optimizing and optimizing compiler backends. This avoids the issue of the GNU assembler -vs- Microsoft assembler syntax entirely. Now all assembly in the implementation is consistently written in the same postfix Factor assembler syntax.

The non-optimizing compiler already supports "sub-primitives", words whose definition consists of assembler opcodes, inlined at each call site. I added new sub-primitives to these files to replace some of the VM's assembly routines:

A few entry points are now generated by the optimizing compiler, too. The optimizing compiler has complicated machinery for generating arbitrary machine code. I extended this with a Factor language feature similar to C's inline assembly, where Factor's assembler DSL is used to generate arbitrary assembly within a word's compiled definition. This is more flexible than the non-optimizing compiler's sub-primitives, and has wide applications beyond the immediate task of replacing a few GNU assembler routines with Factor code.

Factor platform ABI

Before jumping into a discussion of the various assembly routines in the VM, it is important to understand the Factor calling convention first, and how it differs from C.

Factor's machine language calling convention in a nutshell:

Two registers are reserved, for the data and retain stacks, respectively.

Both registers point into an array of tagged pointers. Quotations and words pass and receive parameters as tagged pointers on the data stack.

On PowerPC and x86-64, an additional register is reserved for the current VM instance.

The call stack register (ESP on x86, r1 on PowerPC) is used like in C, with call frames stored in a contiguous fashion.

Call frames must have a bit of metadata so that the garbage collector can mark code blocks that are referenced via return addresses. This ensures that currently-executing code is not deallocated, even if no other references to it remain.

This GC meta-data consists of three things: the stack frame's size in bytes, a pointer to the start of a compiled code block, and a return address inside that code block. Since every frame records its size and the next frame immediately follows, the garbage collector can trace and update all return addresses accurately.

A call frame can have arbitrary size, but the garbage collector does not inspect the additional payload; its can be any blob of binary data at all. The optimizing compiler generates large call frames in a handful of rare situations when a scratch area is needed for raw data.

Quotations must be called with a pointer to the quotation object in a distinguished register (even on x86-32, where the C ABI does not use registers at all). Remaining registers do not have to be preserved, and can be used for any purpose in the compiled code.

Tail calls to compiled words must load the program counter into a special register (EBX on x86-32). This allows polymorphic inline caches at tail call sites to patch the call address if the cache misses. A non-tail call PIC can look at the return address on the call stack, but for a space-saving tail-call, this is not available, so to make inline caching work in all cases, tail calls have to pass this address directly. The only compiled blocks that read the value of this register on entry are tail call PIC miss stubs.

All other calls to compiled words are made without any registers having defined contents at all, so effectively all registers that are not reserved for a specific purpose are volatile.

The call stack pointer must be suitably aligned so that SIMD code can spill vector data to the call frame. This is already the case in the C ABI on all platforms except non-Mac 32-bit x86.

Replacing the `c_to_factor()` entry point

There are two situations where C code needs to jump into Factor; when Factor is starting up, and when C functions invoke function pointers generated by alien-callback.

There used to be a c_to_factor() function defined in a GNU assembly source file as part of the VM, that would take care of translating from the C ABI to the Factor ABI. C++ code can call assembly routines that obey the C calling convention directly.

Now that the special assembly entry point is gone from the VM, a valid question to ask is how is it even possible to switch ABIs and jump out into Factor-land, without stepping outside the bounds of C++, by writing some inline assembler at least. It seems like an impossible dilemma.

The Factor VM ensures that the transition stub that C code uses to call into Factor is generated seemingly out of thin air. It turns out the only unportable C++ feature you really need when bootstrapping a JIT is the ability to cast a data pointer into a function pointer, and call the result.

The new factor_vm::c_to_factor() method, called on VM startup, looks for a function pointer in a member variable named factor_vm::c_to_factor_func. Initially, the value is NULL, and if this is the case, it dynamically generates the entry point and then calls the brand-new function pointer:

void factor_vm::c_to_factor(cell quot)
{
    /* First time this is called, wrap the c-to-factor sub-primitive inside
    of a callback stub, which saves and restores non-volatile registers
    as per platform ABI conventions, so that the Factor compiler can treat
    all registers as volatile */
    if(!c_to_factor_func)
    {
        tagged<word> c_to_factor_word(special_objects[C_TO_FACTOR_WORD]);
        code_block *c_to_factor_block = callbacks->add(c_to_factor_word.value(),0);
        c_to_factor_func = (c_to_factor_func_type)c_to_factor_block->entry_point();
    }

    c_to_factor_func(quot);
}

All machine code generated by the Factor compiler is stored in the code heap, where blocks of code can move. But c_to_factor() needs a stable function pointer to make the initial jump out of C and into Factor. As I briefly mentioned in a blog post about mark sweep compact garbage collection, Factor has a separate callback heap for allocating unmovable function pointers intended to be passed to C.

This callback heap is used for the initial startup entry point too, as well as callbacks generated by alien-callback..

As mentioned in the comment, the callback stub now takes care of saving
and restoring non-volatile registers, as well as aligning the stack frame. You can see how callback stubs are defined with the Factor assembler by grepping for callback-stub in the non-optimizing compiler backend.

The new callback stub covers part of what the old assembly c_to_factor() entry point did. The remaining component is calling the quotation itself, and this is now done by a special word c-to-factor.

The c-to-factor word loads the data stack and retain stack pointers and jumps to the quotation's compiled definition. Grep for c-to-factor-impl in the non-optimizing compiler backend.

In effect, by abusing the non-optimizing compiler's support for "subprimitives", machine code for the C-to-Factor entry point can be generated by the VM itself.

Callbacks generated by alien-callback in the optimizing compiler used to contain a call to the c_to_factor() assembly routine. The equivalent machine code is now generated directly by the optimizing compiler.

Replacing the `throw_impl()` entry point

When Factor code throws an error, a continuation is popped off the catch stack, and resumed. When the VM needs to throw an error, it has to go through the same motions, but perform a non-local return to unwind any C++ stack frames first, before it can jump back into Factor and resume another continuation.

There used to be an assembly routine named throw_impl() which would take a quotation and a new value for the stack pointer.

This is now handled in a similar manner to c_to_factor(). The unwind-native-frames word in kernel.private is another one of those very special sub-primitives that uses the C calling convention for receiving parameters. It reloads the data and retain stack registers, and changes the call stack pointer to the given parameter. The call is coming in from C++ code, and the contents of these registers are not guaranteed since they play no special role in the C ABI. Grep for unwind-native-frames in the non-optimizing compiler backend.

Replacing the `lazy_jit_compile_impl()` and `set_callstack()`entry points

As I discussed in my most recent blog post, on the implementation of closures in Factor, quotation compilation is deferred, and initially all quotations point to the same shared entry point. This shared entry point used to be an assembly routine in the VM. It is now the lazy-jit-compile sub-primitive.

The set-callstack primitive predates the existence of sub-primitives, so it was implemented as an assembly routine in the VM for historical reasons.

These two entry points are never called directly from C++ code in the VM, so unlike c_to_factor() and throw_impl(), there is no C++ code to fish out generated code from a special word and turn it into a function pointer.

Inline assembly with the `alien-assembly` combinator

I added a new word, alien-assembly. In the same way as alien-invoke, it generates code which marshals Factor data into C values, and passes them according to the C calling convention; but where alien-invoke would generate a
subroutine call, alien-assembly just calls the quotation at
compile time instead, no questions asked. The quotation can emit
any machine code it desires, but the result has to obey the C calling
convention.

Here is an example: a horribly unportable way to add two floating-point numbers that only works on x86.64:

: add ( a b -- c )
    double { double double } "cdecl"
    [ XMM0 XMM1 ADDPD ]
    alien-assembly ;

1.5 2.0 add .
3.5

The important thing is that unlike assembly code in the VM, using this feature the same assembly code will work regardless of whether the Factor VM was compiled with gcc or the Microsoft toolchain!

Replacing FPU state entry points

The remaining VM assembly routines were used to save and restore FPU state used for advanced floating point features. The math.floats.env vocabulary would call these assembly routines as if they were ordinary C functions, using alien-invoke. After the refactoring, the optimizing compiler now generates code for these routines using alien-assembly instead. A hook dispatching on CPU type is used to pick the implementation for the current CPU.

See these files for details:

On PowerPC, using non-gcc compilers is not a goal, so these routines remain in the VM, and the vm/cpu-ppc.S source file still exists. It contains these FPU routines along with one other entry point for flushing the instruction cache (this is a no-op on x86).

Compiling Factor with the Windows SDK

With this refactoring out of the way, the Factor VM can now be compiled using the Microsoft toolchain, in addition to Cygwin and Mingw. The primary benefit of using the Microsoft toolchain is that it has allowed me to revive the 64-bit Windows support.

Last time I managed to get gcc working successfully on Win64, the Factor VM was written in C. The switch to C++ killed the Win64 port, because the 64-bit Windows Mingw port is a huge pain to install correctly. I never got gcc to produce a working executable after the C++ rewrite of the VM, and as a result we haven't had a binary package on this platform since April 2009.

Microsoft's free (as in beer) Windows SDK includes command-line compilers for x86-32 and x86-64, together with various tools, such as a linker, and nmake, a program similar to Unix make. Factor now ships with an Nmakefile that uses the SDK tools to build the VM:

nmake /f nmakefile

After fixing some minor compile errors, the Windows SDK produced a working Win64 executable. After updating the FFI code a little, I quickly got it passing all of the compiler tests. As a result of this work, Factor binaries for 64-bit Windows will be available again soon.

How Factor implements closures

2010-01-18T02:45:00.009-05:00

The recent blog post from the Clozure CL team on Clozure CL's implementation of closures inspired me to do a similar writeup about Factor's implementation. It is often said that "closures are a poor man's objects", or "objects are a poor man's closures". Factor takes the former view, because as you will see they are largely implemented within the object system itself.

Quotations

First, let us look at quotations, and what happens internally when a quotation is called. A quotation is a sequence of literals and words. Quotations do not close over any lexical environment; they are entirely self-contained, and their evaluation semantics only depend on their elements, not any state from the time they were constructed. So quotations are anonymous functions but not closures.

Internally, a quotation is a pair, consisting of an array and a machine code entry point. The array stores the quotation's elements, and when you print a quotation with the prettyprinter, this is how Factor knows what its elements are:

( scrachpad ) [ "out.txt" utf8 [ "Hi" print ] with-file-writer ] .
[ "out.txt" utf8 [ "Hi" print ] with-file-writer ]

The machine code entry point refers to a code block in the code heap containing the quotation's compiled definition.

The call generic word calls quotations. This word can take any callable, not just a quotation, and has a method for each type of callable. The callable class includes quotations, as well as curry and compose which are discussed below. This means that closure invocation is implemented on top of method dispatch in Factor.

For reasons that will become clear in the last section on compiler optimizations, most quotations never have their entry points called directly, and so it would be a waste of time to compile all quotations as they are read by the parser.

Instead, all freshly-parsed quotations have their entry points set to the lazy-jit-compile primitive from the kernel.private vocabulary.

The call generic word has a method on the quotation class. This method invokes the (call) primitive from the kernel.private vocabulary. The (call) primitive does not type check, since by the time it is called it is known that the input is in fact a quotation. This primitive has a very simple machine code definition:

mov eax,[esi]    ! Pop datastack
sub esi,4
jmp [eax+13]     ! Jump to quotation's entry point

Note that the quotation is stored in the EAX register; this is important. Recall that initially, a quotation's entry point is set to the lazy-jit-compile word, and that all quotations initially share this entry point.

This word, which is not meant to be invoked directly, compiles quotations the first time they are called. Since all quotations share the same initial entry point, it needs to know which quotation invoked it. This is done by passing the quotation to this word in the EAX register. The lazy-jit-compile word compiles this quotation, sets its entry point to the new compiled code block, and then calls it again. On subsequent calls of the same quotation, the new compiled definition will be jumped to directly, and the lazy-jit-compile entry point is not involved.

If you're interested in the definition of lazy-jit-compile, search for it in these files:

The curry and compose words

curry

The curry word is the fundamental constructor for making closures. It takes a value and a callable, and returns something that prints out as if it were a new quotation:

( scratchpad ) 5 [ + 2 * ] curry .
[ 5 + 2 * ]

This is not a quotation though, but rather an instance of the curry class. Instances of this class are pairs of elements: an object, and another callable.

Instances of curry are callable, because the call generic word has a method on curry. This method pushes the first element of the pair on the data stack, then recursively calls call on the second element.

Calls to curry can be chained together:

( scratchpad ) { "a" "b" "c" } 1 2 [ 3array ] curry curry map .
{ { "a" 1 2 } { "b" 1 2 } { "c" 1 2 } }

Note that using curry, many callables can be constructed which share the same compiled definition; only the data value differes.

Technically, curry is just an optimization -- it would be possible to simulate it by using sequence words to construct a new quotation with the desired value prepended, but this would be extremely inefficient. Prepending an element would take O(n) time, and furthermore, result in the new quotation being compiled the first time the result was called. Indeed, in some simpler concatenative languages such as Joy, quotations are just linked lists, and they execute in the interpreter, so partial application can be done by using the cons primitive for creating a new linked list.

compose

The compose word takes two callables and returns a new instance of the compose class. Instances of this class are pairs of callables.

( scratchpad ) [ 3 + ] [ sqrt ] compose .
[ 3 + sqrt ]

As with curry, the call generic word has a method on the compose class. This method recursively applies call to both elements.

It is possible to express the effect of compose using curry and dip:

: my-compose ( quot1 quot2 -- compose )
    [ [ call ] dip call ] curry curry ; inline

The main reason compose exists as a distinct type is to make the result prettyprint better. Were it defined as above, the result would not prettyprint in a nice way:

( scratchpad ) [ 3 + ] [ sqrt ] [ [ call ] dip call ] curry curry .
[ [ 3 + ] [ sqrt ] [ call ] dip call ]

The curry and compose constructors are sufficient to express all higher-level forms of closures.

An aside: compose and dip

It is possible to express compose using curry and dip. Conversely, it is also possible to express dip using compose and curry.

: my-dip ( a quot -- ) swap [ ] curry compose call ;

Here is an example of how this works. Suppose we have the following code:

123 321 [ number>string ] my-dip

Using the above definition of my-dip, we get

123 321 [ number>string ] swap [ ] curry compose call  ! substitute definition of 'my-dip'
123 [ number>string ] 321 [ ] curry compose call       ! evaluate swap
123 [ number>string ] [ 321 ] compose call             ! evaluate curry
123 [ number>string 321 ] call                         ! evaluate compose
123 number>string 321                                  ! evaluate call
"123" 321                                              ! evaluate number>string

Fry syntax

The fry syntax provides nicer syntax sugar for more complicated usages of curry and compose. Beginners learning Factor should start with fry syntax, and probably don't need to know about curry and compose at all; but this syntax desugars trivially into curry and compose, as explained in the documentation.

Lexical variables

Code written with the locals vocabulary can create closures by referencing lexical variables from nested quotations. For example, here is a word from the compiler which computes the breadth-first order on a control-flow graph:

:: breadth-first-order ( cfg -- bfo )
    <dlist> :> work-list
    cfg post-order length  :> accum
    cfg entry>> work-list push-front
    work-list [
        [ accum push ]
        [ dom-children work-list push-all-front ] bi
    ] slurp-deque
    accum ;

In the body of the word, three lexical variables are used; the input parameter cfg, and the two local bindings work-list and accum.

When the parser reads the above definition, it creates several quotations whose bodies reference local variables, for example, [ accum push ]. Before defining the new word, however, the :: parsing word rewrites this into concatenative code.

Suppose we were doing this rewrite by hand. The first step would be to make closed-over variables explicit. We can do this by currying the values of accum and work-list onto the two quotations passed to bi:

:: breadth-first-order ( cfg -- bfo )
    <dlist> :> work-list
    cfg post-order length  :> accum
    cfg entry>> work-list push-front
    work-list [
        accum [ push ] curry
        work-list [ [ dom-children ] dip push-all-front ] curry bi
    ] slurp-deque
    accum ;

And now, we can do the same transformation on the quotation passed to slurp-deque:

:: breadth-first-order ( cfg -- bfo )
    <dlist> :> work-list
    cfg post-order length  :> accum
    cfg entry>> work-list push-front
    work-list accum work-list [
        [ [ push ] curry ] dip
        [ [ dom-children ] dip push-all-front ] curry bi
    ] curry curry slurp-deque
    accum ;

Note how three usages of curry have appeared, and all lexical variable usage now only occurs at the same level where the variable is actually defined. The final rewrite into concatenative code is trivial, and involves some tricks with dup and dip.

A lexical closure closing over many variables will be rewritten into code which builds a long chain of curry instances, essentially a linked list. This is less efficient than closure representations used in Lisp implementations, where typically all closed-over values are stored in a single array. However in practice this is not usually a problem, because of optimizations outlined below.

Mutable local variables

Mutable local variables are denoted by suffixing their name with !. Here is an example of a loop that counts a mutable variable up to 100:

:: counted-loop-test ( -- )
    0 :> i!
    100 [ i 1 + i! ] times ;

Factor distinguishes between binding (done with :>) and assignment (done with foo! where foo is a local previously declared to be mutable). At a fundamental level, all bindings and closures are immutable; code using mutable locals is rewritten to close over a mutable heap-allocated box instead, and reads and writes involve an extra indirection. The previous example is roughly equivalent to the following, where we use an immutable local variable holding a mutable one-element array:

:: counted-loop-test ( -- )
    { 0 } clone :> i
    100 [ i first 1 + i set-first ] times ;

For this reason, code that uses mutable locals does not optimize as well, and iterative loops that uses mutable local variables can run slower than tail-recursive functions which uses immutable local variables. This might be addressed in the future with improved compiler optimizations.

Optimizations

Quotation inlining

If after inlining, the compiler sees that call is applied to a literal quotation, it inlines the quotation's body at the call site. This optimization works very well when quotations are used as "downward closures", and this is why most quotations never have their dynamic entry point invoked at all.

Escape analysis

Since curry and compose are ordinary tuple classes, any time some code constructs instances of curry and compose, and immediately unpacks them, the compiler's escape analysis pass can eliminate the allocations entirely.

The escape analysis pass has no special knowledge of curry and compose; it applies an optimization intended for object-oriented code.

Again, this helps optimize code with "downward closures", with the result that most usages of curry and compose will never allocate any memory at run time.

For more details, see my blog post about Factor's escape analysis algorithm.

Factor's bootstrap process explained

2010-01-10T09:34:00.001-05:00

Separation of concerns between Factor VM and library code

The Factor VM implements an abstract machine consisting of a data heap of objects, a code heap of machine code blocks, and a set of stacks. The VM loads an image file on startup, which becomes the data and code heap. It then begins executing code in the image, by calling a special startup quotation.

When new source files are loaded into a running Factor instance by the developer, they are parsed and compiled into a collection of objects -- words, quotations, and other literals, along with executable machine code. The new data and code heaps can then be saved into another image file, for faster loading in the future.

Factor's core data structures, object system, and source parser are implemented in Factor and live in the image, so the Factor VM does not have enough machinery to start with an empty data and code heap and parse Factor source files by itself. Instead, the VM needs to start from a data and code heap that already contains enough Factor code to parse source files. This poses a chicken-and-egg problem; how do you build a Factor system from source code? The VM can be compiled with a C++ compiler, but the result is not sufficient by itself.

Some image-based language systems cannot generate new images from scratch at all, and the only way to create a new image is to snapshot an existing session. This is the simplest approach but it has serious downsides -- it lacks determinism and reproducability, and it is difficult to make big changes to the system.

While Factor can snapshot the current execution state into an image, it also has a tool to generate "fresh" image from source. While this tool is written in Factor and runs inside of an existing Factor system, the resulting images depend as little as possible on the particular state of the system that generated it.

Stage 1 bootstrap: creating a boot image

The initial data heap comes from a boot image, which is built from an existing Factor system, known as the host. The result is a new boot image which can run in the target system. Boot images are created using the bootstrap.image tool, whose main entry point is the make-image tool. This word can be invoked from the listener in a running Factor instance:

"x86.32" make-image

The make-image word parses source files using the host's parser, and the code in those source files forms the target image. This tool can be thought of as a form of cross-compiler, except boot images only contain a data heap, and not a code heap. The code heap is generated on the target by the VM, and later by the target's optimizing compiler in Factor.

The make-image word runs the source file core/bootstrap/stage1.factor, which kicks off the bootstrap process.

Building the embryo for the new image

The global namespace is most important object stored in an image file. The global namespace contains various global variables that are used by the parser, along them the dictionary. The dictionary is a hashtable mapping vocabulary names to vocabulary objects. Vocabulary objects contain various bits of state, among them a hashtable mapping word names to word objects. Word objects store their definition as a quotation. The dictionary is how code is represented in memory in Factor; it is built and modified by loading source files from disk.

One of the tasks performed by stage1.factor is to read the source file core/bootstrap/primitives.factor. This source file creates a minimal global namespace and dictionary that target code can be loaded into. This initial dictionary consists of primitive words corresponding to all primitives implemented in the VM, along with some initial state for the object system, consisting of built-in classes such as array. The code in this file runs in the host, but it constructs objects that will ultimately end up in the boot image of the target.

A second piece of code that runs in order to prepare the environment for the target is the CPU-specific backend for the VM's non-optimizing compiler. Again, these are source files which run on the host:

basis/cpu/x86/bootstrap.factor

basis/cpu/x86/32/bootstrap.factor

basis/cpu/x86/64/bootstrap.factor

basis/cpu/ppc/bootstrap.factor

The non-optimizing compiler does little more than glue chunks of machine code together, so the backends are relatively simple and consist of several dozen short machine code definitions. These machine code chunks are stored as byte arrays, constructed by Factor's x86 and PowerPC assemblers.

Loading core source files

Once the initial global environment consisting of primitives and built-in classes has been prepared, source files comprising the core library are loaded in. From this point on, code read from disk does not run in the host, only in the target. The host's parser is still being used, though.

Factor's vocabulary system loads dependencies automatically, so stage1.factor simply calls require on a few essential vocabularies which end up pulling in everything in the core vocabulary root.

During normal operation, any source code at the top level of a source file, not in any definition, is run when the source file is loaded. During stage1 bootstrap, top-level forms from source files in core are not run on the host. Instead, they need to be run on the target, when the VM is is launched with the new boot image.

After loading all source files from core, this startup quotation is constructed. The startup quotation begins by calling top-level forms in core source files in the order in which they were loaded, and then runs basis/bootstrap/stage2.factor.

Serializing the result

At this point, stage1 bootstrap has constructed a new global namespace consisting of a dictionary, object system meta-data, and other objects, together with a startup quotation which can kick off the next stage of bootstrap.

Data heap objects that the VM needs to know about, such as the global namespace, startup quotation, and non-optimizing compiler definitions, are stored in an array of "special objects". Entries are defined in vm/objects.hpp, and in the image file they are stored in the image header.

This object graph, rooted at the special objects array, is now serialized to disk into an image file. The bootstrap image generator serializes objects in the same format in which they are stored in the VM's heap, but it does this without dumping VM's memory directly. This allows object layouts to be changed relatively easily, by first updating the bootstrap image tool, generating an image with the new layouts, then updating the VM and running the new VM with the new image.

The bootstrap image generator also takes care to write the resulting data with the correct cell size and endianness. Along with containing CPU-specific machine code templates for the non-optimizing compiler, this is what makes boot images platform-specific.

Stage 2 bootstrap: fleshing out a development image

At this point, the host system has writen a boot image file to disk, and the next stage of bootstrap can begin. This stage runs on the target, and is initiated by starting the Factor VM with the new boot image:

./factor -i=boot.x86.32.image

The VM reads the new image into an empty data heap. At this point, it also notices that the boot image does not have a code heap, so it cannot start executing the boot quotation just yet.

Early initialization

Boot images have a special flag set in them which kicks off the "early init" process in the VM. This only takes a few seconds, and entails compiling all words in the image with the non-optimizing compiler. Once this is done, the VM can call the startup quotation. Quotations are also compiled by the non-optimizing compiler the first time they are called.

This startup quotation was constructed during stage1 bootstrap. It runs top-level forms in core source files, then runs basis/bootstrap/stage2.factor.

Loading major subsystems

Whereas the goal of stage1 bootstrap is to generate a minimal image that contains barely enough code to be able to load additional source files, stage2 creates a usable development image containing the optimizing compiler, documentation, UI tools, and everything else that makes it into a recognizable Factor system.

The major vocabularies loaded by stage2 bootstrap include:

Optimizing compiler -- after the optimizing compiler has been loaded, all words in the image are compiled again. This is the longest part of stage2 bootstrap, taking several minutes.
Help system
Developer tools
UI framework
UI tools

Finishing up

The last step taken by stage2 bootstrap is to install a new startup quotation. This startup quotation does the usual command-line processing; if no switches are specified, it starts the UI listener, otherwise it runs a source file or vocabulary given on the command line.

Once the new startup quotation has been installed, the current session is saved to a new image file using the save-image-and-exit word.

Freeing Factor from gcc's embrace-and-extend C language extensions

2009-12-27T06:59:00.001-05:00

I have completed a refactoring of the Factor VM, eliminating usage of gcc-specific language extensions, namely global register variables, and on x86-32, the regparm calling convention. My motivation for this is two-fold.

First of all, I'd like to have the option of compiling the Factor VM with compilers other than gcc, such as Visual Studio. While gcc runs on all of Factor's supported platforms and then some, setting up a build environment using the GNU toolchain on Windows takes a bit of work, especially on 64-bit Windows. Visual Studio will provide an easier alternative for people who wish to build Factor from source on that platform. In the future, I'd also like to try using Clang to build Factor.

The second reason is that the global register variable extension is poorly implemented in gcc. Anyone who has followed Factor development for a while will know that gcc bugs come up pretty frequently, and most of these seem to be related to global register variables. This is quite simply one of the less well-tested corners of gcc, and the gcc developers seem to mostly ignore optimizer bugs triggered by this feature.

The Factor VM used a pair of register variables to hold data stack and retain stack pointers. These are just ordinary fields in a struct now. Back in the days when Factor was interpreted and the interpreter was part of the VM, a lot of time was spent executing code within the VM itself, and keeping these pointers in registers was important. Nowadays the Factor implementation compiles to machine code even during interactive use, using a pair of compilers called the non-optimizing compiler and optimizing compiler. Code generated by Factor's compilers tends to dominate the performance profile, rather than code in the VM itself. Compiled code can utilize registers in any matter desired, and so it continues to access the data stack and retain stack through registers. To make it work with the modified VM, the compiler generates code for saving and restoring these registers in the VM's context structure before and after calls into the VM.

A few functions defined in the VM used gcc's regparm calling convention. Normally, on x86-32, function parameters are always passed in an array on the call stack in the esp register; regparm functions instead pass the first 1, 2 or 3 arguments in registers. Whether or not this results in a performance boost is debatable, but my motivation for using this feature was not performance but perceived simplicity. The optimizing compiler would generate calls to these functions, and the machine code generated is a little simpler if it can simply stick parameters in registers instead of storing them on the call stack. Eliminating regparm did not in reality make anything more complex, as only a few locations were affected and the issue was limited to the x86-32 backend only.

I'm pretty happy with how the refactoring turned out. It did not seem to affect performance at all, which was not too surprising, since code generated by Factor's optimizing compiler did not change, and the additional overhead surrounding Factor to C calls is lost in the noise.

My goal of getting Factor to build with other compilers is not quite achieved yet, however. While the gcc extensions are gone from C++ code, the VM still has some 800 lines of assembly source using GNU assembler syntax, in the files cpu-x86.32.S, cpu-x86.64.S, and cpu-ppc.S. This code includes fundamental facilities which cannot be implemented in C++, such as the main C to Factor call gate, the low-level set-callstack primitive used by the continuations implementation, and a few other things. The assembly source also has a few auxilliary CPU-dependent functions, for example for saving and restoring FPU flags, and detecting the SSE version on x86.

I plan on elimiating the assembly from the VM entirely, by having the Factor compiler generate this code instead. The non-optimizing compiler can generate things such as the C to Factor call gate. For the the remaining assembly routines, such as FPU feature access and SSE version detection, I plan on adding an "inline assembly" facility to Factor itself, much like gcc's asm statement. The result will be that the VM will be a pure C++ codebase, and the machine code generation will be entirely offloaded into Factor code, where it belongs. Factor's assembler DSL is much nicer to use than GNU assembler.

Reducing image size by eliminating literal tables from code heap entries

2009-12-06T02:00:00.001-05:00

Introduction

The compiled code heap consists of code blocks which reference other code blocks and objects in the data heap. For example, consider the following word:

: hello ( -- ) "Hello world" print ;

The machine code for this word is the following:

000000010ef55f10: 48b87b3fa40d01000000  mov rax, 0x10da43f7b
000000010ef55f1a: 4983c608              add r14, 0x8
000000010ef55f1e: 498906                mov [r14], rax
000000010ef55f21: 48bb305ff50e01000000  mov rbx, 0x10ef55f30 (hello+0x20)
000000010ef55f2b: e9e0ffabff            jmp 0x10ea15f10 (print)

The immediate operand of the first mov instruction (0x10da43f7b) is the address of the string "Hello world" in the data heap. The immediate operand of the last jmp instruction (0x10ea15f10) is the address of the machine code of the print word in the code heap.
Unlike some dynamic language JITs where all references to data and compiled code from machine code are done via indirection tables, Factor embeds the actual addresses of the data in the code. This means that the garbage collector needs to be able to find all pointers in a code heap block (for the "sweep" phase of garbage collection), and update them (for the "compact" phase).

Relocation tables

Associated to each code block is a relocation table, which tells the VM what instruction operands contain special values that it must be aware of. The relocation table is a list of triples, packed into a byte array:

The relocation type is an instance of the relocation_type enum in instruction_operands.hpp. This value tells the VM what kind of value to deposit in the operand -- possibilities include a data heap pointer, the machine code of a word, and so on.
The relocation class is an instance of the relocation_class enum in instruction_operands.hpp. This value tells the VM how the operand is represented -- the instruction format, whether or not it is a relative address, and such.
The relocation offset is a byte offset from the start of the code block where the value is to be stored.

Code that needs to inspect relocation table entries uses the each_instruction_operand() method defined in code_block.hpp. This is a template method which can accept any object overloading operator().

Literal tables

The next part is what I just finished refactoring. I'll describe the old approach first. The simplest way, and what Factor used until now, is the following. Relocation table entries that expect a parameter, such as those that deposit addresses from the data heap and code heap, take the parameter from a literal table associated to each code block. When the compiler compiles a word, it spits out some machine code and a literal table. It hands these off to the Factor VM. The "sweep" phase of the garbage collector traces each code block's literal table, and the "compact" phase, after updating the literal table, stores the operands back in each instruction referenced from the relocation table.

Eliminating literal tables

The problem with the old approach is that the garbage collector doesn't really need the literal table. The address of each data heap object and code block referenced from machine code is already stored in the machine code itself. Indeed, the only thing missing until now was a way to read instruction operands out of instructions. With this in place, code blocks no longer had to hold on to the literal table after being constructed. Each code block's literal table is only used to deposit the initial values into machine code when a code block is first compiled by the compiler. Subsequently, the literal table becomes garbage and is collected by the garbage collector. When tracing code blocks, the garbage collector traverses the instruction operands themselves, using the relocation table alone. In addition to the space savings gained by not keeping these arrays of literals around, another interesting side-effect of this refactoring is that a full garbage collection no longer resets generic word call sites back to the cold call entry point, which would effectively discard all inline caches (read about inline caching in Factor).

Coping with code redefinition

A call to a word is compiled as a direct jump in Factor. This means that if a word is redefined and recompiled, existing call sites need to be updated to point to the new definition. The implementation of this is slightly more subtle now that literal tables are gone. Every code block in the code heap has a reference to an owner object in its header (see the code_block struct in code_blocks.cpp). The owner is either a word or a quotation. Words and quotations, in turn, have a field which references a compiled code heap block. The latter always points at the most recent compiled definition of that object (note that quotations are only ever compiled once, because they are immutable. Words, however, can be redefined by reloading source files). At the end of each compilation unit, the code heap is traversed, and each code block is updated in turn. The code block's relocation table is consulted, and instruction operands which reference compiled code heap blocks are updated. Before this would be done by overwriting all call targets from the literal table. Now, this is accomplished by looking at the owner object of the current target, and then storing the owner's most recent code block back in the instruction operand. This is implemented in the update_word_references() method defined in code_blocks.cpp. In addition to helping with redefinition, the owner object reference is used to construct call stack traces.

Additional space savings in deployed binaries

Normally, every compiled code block references its owner object, so that code redefinition can work. This means that if a word or quotation is live, then the code block corresponding to its most recent definition will be live, and vice versa. In deployed images where the compiler and debugger have been stripped out, words cannot be redefined and stack traces are not needed, so the owner field can be stripped out. This means that a word object can get garbage collected at deploy time even if its compiled code block is called. As it turns out, most words are never used as objects, and can be stripped out in this manner. So the literal table removal has an even bigger effect in deployed images than development images.

Size comparison

The following table shows image sizes before and after this change on Mac OS X x86-64.

Image	Before (Megabytes)	After (Megabytes)
Development image	92 Mb	90 Mb
Minimal development image	8.6 Mb	8.2 Mb
Deployed hello-ui	2.3 Mb	1.5 Mb
Deployed bunny	3.5 Mb	3.1 Mb

Mark-compact garbage collection for oldest generation, and other improvements

2009-11-16T03:24:00.006-05:00

Factor now uses a mark-sweep-compact garbage collector for the oldest generation (known as tenured space), in place of the copying collector that it used before. This reduces memory usage. The mark-sweep collector used for the code heap has also been improved. It now shares code with the data heap collector and uses the same compaction algorithm.

Mark-sweep-compact garbage collection for tenured space

Mark phase

During the mark phase, the garbage collector computes the set of reachable objects by starting from the "roots"; global variables, and objects referenced from runtime stacks. When an object is visited, the mark phase checks if the object has already been marked. If it hasn't yet been marked, it is marked, and any object that it refers to are then also visited in turn. If an object has already been marked, nothing is done. As described above, the algorithm is recursive, which is problematic. There are two approaches to turn it into an iterative algorithm; either objects yet to be visited are pushed on a mark stack, and a top-level loop drains this stack, or a more complicated scheme known as "pointer inversion" is used. I decided against pointer inversion, since the mark stack approach is simpler and I have yet to observe the mark stack grow beyond 128Kb or so anyway. I use an std::vector for the mark stack and it works well enough. The mark stack and the loop that drains it are implemented in full_collector.cpp. There are several approaches to representing the set of objects which are currently marked, also. The two most common are storing a mark bit for each object in the object's header, and storing mark bits in a bitmap off to the side. I chose the latter approach, since it speeds up the sweep and compact phases of the garbage collector, and doesn't require changing object header layout. Each bit in the mark bitmap corresponds to 16 bytes of heap space. For reasons that will become clear, when an object is marked mark bitmap, every bit corresponding to space taken up by the object is marked, not just the first bit. The mark bitmap is implemented in mark_bits.hpp.

Sweep phase

Once the mark phase is complete, the mark bitmap now has an up-to-date picture of what regions in the heap correspond to reachable objects, and which are free. The sweep phase begins by clearing the free list, and then computes a new one by traversing the mark bitmap. For every contiguous range of clear bits, a new entry is added to the free list. This is why I use a mark bitmap instead of mark bits in object headers; if I had used mark bits in headers, then the sweep phase would need to traverse the entire heap, not just the mark bitmap, which has significantly worse locality. The sweep phase is implemented by the free_list_allocator::sweep() method in free_list_allocator.hpp. The key to an efficient implementation of the sweep algorithm is the log2() function in bitwise_hacks.hpp; it is used to find the first set bit in a cell. I use the BSR instruction on x86 and cntlzw on PowerPC. The sweep phase also needs to update the object start offset map used for the card marking write barrier. When collecting a young generation, the garbage collector scans the set of marked cards. It needs to know where the first object in each card is, so that it can properly identify pointers. This information is maintained by the object_start_map class defined in object_start_map.cpp. If an object that happens to be the first object in a cardwas deallocated by the sweep phase, the object start map must be updated to point at a subsequent object in that card. This is done by the object_start_map::update_for_sweep() method.

Compact phase

The compact phase is optional; it only runs if the garbage collector determines that there is too much fragmentation, or if the user explicitly requests it. The compact phase does not require that the sweep phase has been run, only the mark phase. Like the sweep phase, the compact phase relies on the mark bitmap having been computed. Whereas the sweep phase identifies free blocks and adds them to the free list, the compact phase slides allocated space up so that all free space ends up at the end of the heap, in a single block. The compact phase has two steps. The first step computes a forwarding map; a data structure that can tell you the final destination of every heap block. It is easy to see that the final destination of every block can be determined from the number of set bits in the mark bitmap that precede it. Since the forwarding map is consulted frequently -- once for every pointer in every object that is live during compaction -- it is important that lookups are as fast as possible. The forwarding map should also be space-efficient. This completely rules out using a hashtable (with many small objects in the heap, it would grow to be almost as big as the heap itself) or simply scanning the bitmap and counting bits every time (since now compaction will become an O(n^2) algorithm). The correct solution is very simple, and well-known in language implementation circles, but I wasn't aware of it until I studied the Clozure Common Lisp garbage collector. You count the bits set in every group of 32 (or 64) bits in the mark bitmap, building an array of cumulative sums as you go. Then, to count the number of bits that are set up to a given element, you look up the pre-computed population count for the nearest 32 (or 64) bit boundary, and manually compute the population count for the rest. This gives you a forwarding map with O(1) lookup time. This algorithm relies on a fast population count algorithm; I used the standard CPU-independent technique in the popcount() function of bitwise_hacks.hpp. Nowadys, as of SSE 4.2, x86 CPUs even include a POPCNT instruction, but since compaction spends most of its time in memmove(), I didn't investigate if this would offer a speedup. It would require a CPUID check at runtime and the fallback would still need to be there for pre-Intel i7 CPUs and PowerPC, so it didn't seem worth the extra complexity to me. Once the forwarding map has been computed, objects can be moved up and pointers that they contain updated in one pass. A mark-compact cycle takes roughly twice as long as a mark-sweep, which is why I elected not to perform a mark-compact on every full collection. The latter leads to a simpler implementation (no sweep phase, and no free list; allocation in tenured space is done by bumping a pointer just as with a copying collector) however the performance penalty didn't seem worth the minor code size reduction to me.

Code heap compaction

Code heap compaction has been in Factor for a while, in the form of the save-image-and-exit word. This used an inefficient multi-pass algorithm (known as the "LISP-2 compaction algorithm") however since it only ran right before exiting Factor, it didn't matter too much. Now, code heap compaction can happen at any time as a result of heap fragmentation, and uses the same efficient algorithm as tenured space compaction. Compaction moves code around, and doing this at a time other than right before the VM exiting creates a few complications:

Return addresses in the callstack need to be updated.
If an inline cache misses, a new inline cache is compiled, and the call site for the old cache is patched. Inline cache construction allocates memory and can trigger a GC, which may in turn trigger a code heap compaction; if this occurs, the return address passed into the inline cache miss stub may have moved, and the code to patch the call site needs to be aware of this.
If a Factor callback is passed into C code, then moving code around in the code heap may invalidate the callback, and the garbage collector has no way to update any function pointers that C libraries might be referencing.

The solution to the first problem was straightforward and involved adding some additional code to the code heap compaction pass. The second problem is trickier. I added a new code_root smart pointer class, defined in code_roots.hpp, to complement the data_root smart pointer (see my blog post about moving the VM to C++ for details about that). The inline cache compiler wraps the return address in a code_root to ensure that if the code block that contains it is moved by any allocations, the return address can be updated properly. I solved the last problem with a layer of indirection (that's how all problems are solved in CS, right?). Callbacks are still allocated in the code heap, but the function pointer passed to C is actually stored in a separate "callback heap" where every block consists of a single jump instruction and nothing else. When a code heap compaction occurs, code blocks in the code heap might be moved around, and all jumps in the callback heap are updated. Blocks within the callback heap are never moved around (or even deallocated, since that isn't safe either).

New object alignment and tagging scheme

The last major change I wanted to discuss is that objects are now aligned on 16-byte boundaries, rather than 8-byte boundaries. This wastes more memory, but I've already offset most of the increase with some space optimizations, with more to follow. There are several benefits to this new system. First of all, the binary payload of byte array objects now begins on a 16-byte boundary, which allows SIMD intrinsics to use aligned access instructions, which are much faster. Second, it simplifies the machine code for inline caches and megamorphic method dispatch. Since the low 4 bits of every pointer are now clear, this allows all built-in VM types to fit in the pointer tag itself, so the logic to get a class descriptor for an object in a dispatch stub is very simple now; here is pseudo-code for the assembly that gets generated:

cell tag = ptr & 15; if(tag == tuple_tag) tag = ptr[cell - tuple_tag]; ... dispatch on tag ...

Improved write barriers in Factor's garbage collector

2009-10-15T07:16:00.009-04:00

The Factor compiler has been evolving very quickly lately; it has been almost completely rewritten several times in the last couple of years. The garbage collector, on the other hand, hasn't seen nearly as much action. The last time I did any work on it was May 2008, and before that, May 2007. Now more than a year later, I've devoted a week or so to working on it. The result is a cleaner implementation, and improved performance.

Code restructuring

I re-organized the garbage collector code to be more extensible and easier to maintain. I did this by splitting off a bunch of the garbage collector methods from the factor_vm class into their own set of classes. I made extensive use of template metaprogramming to help structure code in a natural way. Many people dislike C++, primarily because of templates, but I don't feel that way at all. Templates are my favorite C++ feature, and if it wasn't for templates C++ would just be a shitty object-oriented dialect of C.

First up is the collector template class, defined in collector.hpp:

template<typename TargetGeneration, typename Policy> struct collector

This class has two template parameters:

TargetGeneration - this is the generation that the collector will be copying objects to. A generation is any class that implements the allot() method.
Policy - this is a class that simulates a higher-order function. It implements a should_copy_p() method that tells the collector if a given object should be promoted to the target generation, or left alone.

On its own, the collector class can't do any garbage collection itself; it just implements methods which trace GC roots: trace_contexts() (traces active stacks), trace_roots() (traces global roots), and trace_handle() (traces one pointer).

Next up is the copying_collector template class, defined in copying_collector.hpp:

template<typename TargetGeneration, typename Policy> struct copying_collector

This class has the same two template parameters as collector; the target generation must define one additional method, next_object_after(). This is used when scanning newly copied objects. This class implements logic for scanning marked cards, as well as Cheney's algorithm for copying garbage collection.

Then, there are four subclasses implementing each type of GC pass:

nursery_collector - copies live objects from the nursery into aging space, defined in nursery_collector.hpp and nursery_collector.cpp
aging_collector - copies live objects from the first aging semi-space to the second aging semi-space, defined in aging_collector.hpp and aging_collector.cpp
to_tenured_collector - copies live objects from aging space into tenured space, defined in to_tenured_collector.hpp and to_tenured_collector.cpp
full_collector - copies live objects from the first tenured semi-space to the second tenured semi-space, defined in nursery_collector.hpp and nursery_collector.cpp

Each class subclasses copying_collector and specializes the two template arguments. For example, let's take a look at the declaration of the nursery collector:

struct nursery_collector : copying_collector<aging_space,nursery_policy>

This subclass specializes its superclass to copy objects to tenured space, using the following policy class:

struct nursery_policy {
 factor_vm *myvm;

 nursery_policy(factor_vm *myvm_) : myvm(myvm_) {}

 bool should_copy_p(object *untagged)
 {
  return myvm->nursery.contains_p(untagged);
 }
};

That is, any object that is in the nursery will be copied to aging space by the nursery_collector. Other collector subclasses are similar.

This code all uses templates, rather than virtual methods, so every collector pass will have a specialized code path generated for it. This gives higher performance, with cleaner code, than was is possible in C. The old garbage collector was a tangle of conditionals, C functions, and global state.

Partial array card marking

When a pointer to an object in the nursery is stored into a container in aging or tenured space, the container object must be added to a "remembered set" so that on the next minor collection, so that it can be scanned, and its elements considered as GC roots.

Old way

Storing a pointer into an object marks the card containing the header of the object. On a minor GC, all marked cards are be scanned; if a marked card was bound, then every object whose header is contained in this card would be scanned.

Problem

Storing a pointer into an array would necessitate the array to be scanned in its entirety on the next minor collection. This is bad if the array is large. Consider an algorithm that stores successive elements into an array on every iteration, and also performs enough work per iteration to trigger a nursery collection. Now every nursery collection -- and hence every iteration of the loop -- is scanning the entire array. We're doing a quadratic amount of work for what should be a linear-time algorithm.

New way

Storing a pointer into an object now marks the card containing the slot that was mutated. On a minor GC, all marked cards are scanned. Every object in every marked card is inspected, but only the subrange of slots that fit inside the card are scanned. This greatly reduces the burden placed on the GC from mutation of large arrays. The implementation is tricky. I need to spend some time thinking about and simplifying the code, as it stands the card scanning routine has three nested loops, and two usages of goto!

Implementation

copying_collector.hpp, trace_cards()

New object promotion policy

When aging space is being collected, objects contained in marked cards in tenured space must be traced.

Old way

These cards would be scanned, but could not be unmarked, since the objects they refer to were copied to the other aging semi-space, and would need to be traced on the next aging collection.

The problem

The old way was bad because these cards would remain marked for a long time, and would be re-scanned on every collection. Furthermore the objects they reference would likely live on for a long time, since they're referenced from a tenured object, and would needlessly bounce back and forth between the two aging semi-spaces.

New way

Instead, an aging collection proceeds in two phases: the first phase promotes aging space objects referenced from tenured space to tenured space, unmarking all marked cards. The second phase copies all reachable objects from aging to second aging semi-space. This promotes objects likely to live for a long time all the way to tenured space, and scans less cards on an aging collection since more cards can get unmarked.

Implementation

aging_collector.cpp

Faster code heap remembered set

If a code block references objects in the nursery, the code block needs to be updated after a nursery collection. This is because the machine code of compiled words directly refers to objects; there's no indirection through a literal table at runtime. This improves performance but increases garbage collector complexity.

Old way

When a new code block was allocated, a global flag would be set. A flag would also be set in the code block's header. On the next nursery collection, the entire code heap would be scanned, and any code blocks with this flag set in them would have their literals traced by the garbage collector.

New way

The problem with the old approach is that adding a single code block entails a traversal of the entire code heap on the next minor GC, which is bad for cache. While most code does not allocate in the code heap, the one major exception is the compiler itself. When loading source code, a significant portion of running time was spent scanning the code heap during minor collections. Now, the list of code blocks containing literals which refer to the nursery and aging spaces are stored in a pair of STL sets. On a nursery or aging collection, these sets are traversed and the code blocks they contain are traced. These sets are typically very small, and in fact empty most of the time.

Implementation

code_heap.cpp, write_barrier()
copying_collector.hpp, trace_code_heap_roots()

Faster card marking and object allocation

The compiler's code generator now generates tighter code for common GC-related operations too. A write barrier looks like this in pseudo-C:

cards[(obj - data_heap_start) >> card_bits] = card_mark_mask;

Writing out the pointer arithmetic by hand, we get:

*(cards + (obj - data_heap_start) >> card_bits) = card_mark_mask;

Re-arranging some operations,

*(obj >> card_bits + (cards - data_heap_start >> card_bits) = card_mark_mask;

Now, the entire expression

(cards - data_heap_start >> card_bits)

is a constant. Factor stores this in a VM-global variable, named cards_offset. The value used to be loaded from the global variable every time a write barrier would execute. Now, its value is inlined directly into machine code. This requires code heap updates if the data heap grows, since then either the data heap start or the card array base pointer might change. However, the upside is that it eliminates several instructions from the write barrier. Here is a sample generated write barrier sequence; only 5 instructions on x86.32:

0x08e3ae84: lea    (%edx,%eax,1),%ebp
0x08e3ae87: shr    $0x8,%ebp
0x08e3ae8a: movb   $0xc0,0x20a08000(%ebp)
0x08e3ae91: shr    $0xa,%ebp
0x08e3ae94: movb   $0xc0,0x8de784(%ebp)

Object allocations had a slight inefficiency; the code generated to compute the effective address of the nursery allocation pointer did too much arithmetic. Adding support to the VM for embedding offsets of VM global variables directly into machine code saved one instruction from every object allocation. Here is some generated machine code to box a floating point number; only 6 instructions on x86.32 (of course Factor does float unboxing to make your code even faster):

0x08664a33: mov    $0x802604,%ecx
0x08664a38: mov    (%ecx),%eax
0x08664a3a: movl   $0x18,(%eax)
0x08664a40: or     $0x3,%eax
0x08664a43: addl   $0x10,(%ecx)
0x08664a46: movsd  %xmm0,0x5(%eax)

Implementation

cpu/x86/x86.factor: %write-barrier, %allot
cpu/ppc/ppc.factor: %write-barrier, %allot

Performance comparison

I compared the performance of a Mac OS X x86-32 build from October 5th, with the latest sources as of today.

Bootstrap time saw a nice boost, going from 363 seconds, down to 332 seconds.

The time to load and compile all libraries in the source tree (load-all) was reduced from 537 seconds to 426 seconds.

Here is a microbenchmark demonstrating the faster card marking in a very dramatic way:

: bench ( -- seq ) 10000000 [ >bignum 1 + ] map ;

The best time out of 5 iterations on the old build was 12.9 seconds. Now, it has gone down to 1.9 seconds.

A survey of domain-specific languages in Factor

2009-09-30T23:52:00.007-04:00

Factor has good support for implementing mini-languages as libraries. In this post I'll describe the general techniques and look at some specific examples. I don't claim any of this is original research -- Lisp and Forth programmers have been doing DSLs for decades, and recently the Ruby, Haskell and even Java communities are discovering some of these concepts and adding a few of their own to the mix. However, I believe Factor brings some interesting incremental improvements to the table, and the specific combination of capabilities found in Factor is unique.

Preliminaries

How does one embed a mini-language in Factor? Let us look at what goes on when a source file is parsed:

The parser reads the input program. This consists of definitions and top-level forms. The parser constructs syntax trees, and adds definitions to the dictionary. The result of parsing is the set of top-level forms in the file.
The compiler is run with all changed definitions. The compiler essentially takes syntax trees as input, and produces machine code as output. Once the compiler finishes compiling the new definitions, they are added to the VM's code heap and may be executed.
The top level forms in the file are run, if any.

In Factor, all of these stages are extensible. Note that all of this happens when the source file is loaded into memory -- Factor is biased towards compile-time meta-programming.

Extending the parser with parsing words

Parsing words which execute at parse time can be defined. Parsing words can take over the parser entirely and parse custom syntax. All of Factor's standard syntax, such as : for defining words and [ for reading a quotation, is actually parsing words defined in the syntax vocabulary. Commonly-used libraries such as memoize and specialized-arrays add their own parsing words for custom definitions and data types. These don't qualify as domain-specific languages since they're too trivial, but they're very useful.

Homoiconic syntax

In most mainstream languages, the data types found in the syntax tree are quite different from the data types you operate on at runtime. For example, consider the following Java program:

if(x < 3) { return x + 3; } else { return foo(x); }

This might parse into something like

IfNode(
    condition: LessThan(Identifier(x),Integer(3))
    trueBranch: ReturnNode(Add(Identifier(x),Integer(3)))
    falseBranch: ReturnNode(MethodCall(foo,Identifier(x)))
)

You cannot work with an "if node" in your program, the identifier x does not exist at runtime, and so on.

In Factor and Lisp, the parser constructs objects such as strings, numbers and lists directly, and identifiers (known as symbols in Lisp, and words in Factor) are first-class types. Consider the following Factor code,

x 3 < [ x 3 + ] [ x foo ] if

This parses as a quotation of 6 elements,

The word x
The integer 3
The word <
A quotation with three elements, x, 3, and +
A quotation with two elements, x, and foo
The word if

An array literal, like { 1 2 3 }, parses as an array of three integers; not an AST node representing an array with three child AST nodes representing integers.

The flipside of homoiconic syntax is being able to print out (almost) any data in a form that can be parsed back in; in Factor, the . word does this.

What homoiconic syntax gives you as a library author is the ability to write mini-languages without writing a parser. Since you can input almost any data type wth literal syntax, you can program your mini-language in parse trees directly. The mini-language can process nested arrays, quotations, tuples and words instead of parsing a string representation first.

Compile-time macros

All of Factor's data types, including quotations and words, can be constructed at runtime. Factor also supports compile-time macros in the Lisp sense, but unlike Lisp where they are used to prevent evaluation, a Factor macro is called just like an ordinary word, except the parameters have to be compile-time literals. The macro evaluates to a quotation, and the quotation is compiled in place of the macro call.

Everything that can be done with macros can also be done by constructing quotations at runtime and using call( -- macros just provide a speed boost.

Parsing word-based DSLs

Many DSLs have a parsing word as their main entry point. The parsing word either takes over the parser completely to parse custom syntax, or it defines some new words and then lets the main parser take over again.

Local variables

A common misconception among people taking a casual look at Factor is that it doesn't offer any form of lexical scoping or named values at all. For example, Reg Braithwaite authoritatively states on his weblog:

the Factor programming language imposes a single, constraining set of rules on the programmer: programmers switching to Factor must relinquish their local variables to gain Factor’s higher-order programming power.

In fact, Factor supports lexically scoped local variables via the locals vocabulary. and this library is used throughout the codebase. It looks like in a default image, about 1% of all words use lexical variables.

The locals vocabulary implements a set of parsing words which augment the standard defining words. For example, :: reads a word definition where input arguments are stored in local variables, instead of being on the stack:

:: lerp ( a b c -- d )
    a c *
    b 1 c - *
    + ;

The locals vocabulary also supports "let" statements, lambdas with full lexical closure semantics, and mutable variables. The locals vocabulary compiles lexical variable usage down to stack shuffling, and curry calls (for constructing quotations that close over a variable). This makes it quite efficient, especially since in many cases the Factor compiler can eliminate the closure construction using escape analysis. The choice of whether or not to use locals is one that can be made purely on a stylistic basis, since it has very little effect on performance.

Parsing expression grammars

Parsing expression grammars describe a certain class of languages, as well as a formalism for parsing these languages.

Chris Double implemented a PEG library in Factor. The peg vocabulary offers a combinator-style interface for constructing parsers, and peg.ebnf builds on top of this and defines a declarative syntax for specifying parsers.

A simple example of a PEG grammar can be found in Chris Double's peg.pl0 vocabulary. More elaborate examples can be found in peg.javascript (JavaScript parser by Chris Double) and smalltalk.parser (Smalltalk parser by me).

One downside of PEGs is that they have some performance problems; the standard formulation has exponential runtime in the worst case, and the "Packrat" variant that Factor uses runs in linear time but also linear space. For heavy-duty parsing, it appears as if LL and LR parsers are best, and it would be nice if Factor had an implementation of such a parser generator.

However, PEGs are still useful for simple parsing tasks and prototyping. They are used throughout the Factor codebase for many things, including but not limited to:

Parsing regular expressions in the regexp vocabulary (source)
Parsing URLs in the urls vocabulary (source)
Parsing HTTP headers in the http.server and http.client vocabularies (source)

PEGs can also be used in conjunction with parsing words to embed source code written with custom grammars in Factor source files directly. The next DSL is an example of that.

Infix expressions

Philipp Brüschweiler's infix vocabulary defines a parsing word which parses an infix math expression using PEGs. The result is then compiled down to locals, which in turn compile down to stack code.

Here is a word which solves a quadratic equation ax^2 + bx + c = 0 using the quadratic formula. Infix expressions can only return one value, so this word computes the first root only:

USING: infix locals ;

:: solve-quadratic ( a b c -- r )
    [infix (-b + sqrt(b*b-4*a*c))/2*a infix] ;

Note that we're using two mini-languages here; :: begins a definition with named parameters stored in local variables, and [infix parses an infix expression which can access these local variables.

XML literals

Daniel Ehrenberg's XML library defines a convenient syntax for constructing XML documents. Dan describes it in detail in a blog post, with plenty of examples, so I won't repeat it here. The neat thing here is that by adding a pair of parsing words, [XML and <XML, he was able to integrate XML snippets into Factor, with parse-time well-formedness checking, no less.

Dan's XML library is now used throughout the Factor codebase, particularly in the web framework, for both parsing and generating XML. For example, the concatenative.org wiki uses a markup language called "farkup". The farkup markup language, developed by Dan, Doug Coleman and myself, makes heavy use of XML literals. Farkup is implemented by first parsing the markup into an abstract syntax tree, and then converting this to HTML using a recursive tree walk that builds XML literals. We avoid constructing XML and HTML through raw string concatenation; instead we use XML literals everywhere now. This results in cleaner, more secure code.

Compare the design of our farkup library with markdown.py used by reddit.com. The latter is implemented with a series of regular expression hacks and lots of ad-hoc string processing which attempts to produce something resembling HTML in the end. New markup injection attacks are found all the time; there was a particularly clever one involving a JavaScript worm that knocked reddit right down a few days ago. I don't claim that Farkup is 100% secure by any means, and certainly it has had an order of magnitude less testing, but without a doubt centralizing XHTML generation makes it much easier to audit and identify potential injection problems.

C library interface

Our C library interface (or FFI) was quite low-level initially but after a ton of work by Alex Chapman, Joe Groff, and myself, it has quite a DSLish flavor. C library bindings resemble C header files on mushrooms. Here is a taste:

TYPEDEF: int cairo_bool_t

CONSTANT: CAIRO_CONTENT_COLOR HEX: 1000
CONSTANT: CAIRO_CONTENT_ALPHA HEX: 2000
CONSTANT: CAIRO_CONTENT_COLOR_ALPHA HEX: 3000

STRUCT: cairo_matrix_t
    { xx double }
    { yx double }
    { xy double }
    { yy double }
    { x0 double }
    { y0 double } ;
    
FUNCTION: void
cairo_transform ( cairo_t* cr, cairo_matrix_t* matrix ) ;

The Factor compiler generates stubs for calling C functions on the fly from these declarative descriptions; there is no C code generator and no dependency on a C compiler. In fact, C library bindings are so easy to write that for many contributors, it is their first project in Factor. When Doug Coleman first got involved in Factor, he began by writing a PostgreSQL binding, followed by an implementation of the MD5 checksum. Both libraries have been heavily worked on since then are still in use.

For complete examples of FFI usage, check out any of the following:

unix - POSIX bindings
windows - Windows API bindings
db.sqlite.ffi - SQLite bindings
opengl.gl - OpenGL bindings

There are many more usages of the FFI of course. Since Factor has a minimal VM, all I/O, graphics and interaction with the outside world in general is done with the FFI. Search the Factor source tree for source files that use the alien.syntax vocabulary.

GPU shaders

Joe Groff cooked up a nice DSL for passing uniform parameters to pixel and vertex shaders. In his blog post, Joe writes:

The library makes it easy to load and interactively update shaders, define binary formats for GPU vertex buffers, and feed parameters to shader code using Factor objects.

Here is a snippet from the gpu.demos.raytrace demo:

GLSL-SHADER-FILE: raytrace-vertex-shader vertex-shader "raytrace.v.glsl"
GLSL-SHADER-FILE: raytrace-fragment-shader fragment-shader "raytrace.f.glsl"
GLSL-PROGRAM: raytrace-program
    raytrace-vertex-shader raytrace-fragment-shader ;

UNIFORM-TUPLE: sphere-uniforms
    { "center" vec3-uniform  f }
    { "radius" float-uniform f }
    { "color"  vec4-uniform  f } ;

UNIFORM-TUPLE: raytrace-uniforms
    { "mv-inv-matrix"    mat4-uniform f }
    { "fov"              vec2-uniform f }
    
    { "spheres"          sphere-uniforms 4 }

    { "floor-height"     float-uniform f }
    { "floor-color"      vec4-uniform 2 }
    { "background-color" vec4-uniform f }
    { "light-direction"  vec3-uniform f } ;

The GLSL-SHADER-FILE: parsing word tells Factor to load a GLSL shader program. The GPU framework automatically checks the file for modification, reloading it if necessary.

The UNIFORM-TUPLE: parsing word defines a new tuple class, together with methods which destructure the tuple and bind textures and uniform parameters. Uniform parameters are named as such because they define values which remain constant at every pixel or vertex that the shader program operates on.

Instruction definitions in the compiler

This one is rather obscure and technical, but it has made my job easier over the last few weeks. I blogged about it already.

Other examples

The next set of DSLs don't involve parsing words as much as just clever tricks with evaluation semantics.

Inverse

Daniel Ehrenberg's inverse library implements a form of pattern matching by computing the inverse of a Factor quotation. The fundamental combinator, undo, takes a Factor quotation, and executes it "in reverse". So if there is a constructed tuple on the stack, undoing the constructor will leave the slots on the stack. If the top of the stack doesn't match anything that the constructor could've produced, then the inverse fails, and pattern matching can move on to the next clause. This library works by introspecting quotations and the words they contain. Dan gives many details and examples in his paper on inverse.

Help system

Factor's help system uses an s-expression-like markup language. Help markup is parsed by the Factor parser without any special parsing words. A markup element is an array where the first element is a distinguished word and the rest are parameters. Examples:

"This is " { $strong "not" } " a good idea"

{ $list
    "milk"
    "flour"
    "eggs"
}

{ $link "help" }

This markup is rendered either directly on the Factor UI (like in this screenshot) or via HTML, as on the docs.factorcode.org site.

The nice thing about being able to view help in the UI environment is the sheer interactive nature of it. Unlike something like javadoc, there is no offline processing step which takes your source file and spits out rendered markup. You just load a vocabulary into your Factor instance and the documentation is available instantly. You can look at the help for any documented word by simply typing something like

\ append help

in the UI listener. While working on your own vocabulary, you can reload changes to the documentation and see them appear instantly in the UI's help browser.

Finally, it is worth mentioning that because of the high degree of semantic information encoded in documentation, many kinds of mistakes can be caught in an automated fashion. The help lint tool finds inconsistencies between the actual parameters that a function takes, and the documented parameters, as well as code examples that don't evaluate to what the documentation claims they evaluate to, and a few other things.

You won't find a lot of comments in Factor source, because the help system is much more useful. Instead of plain-text comments that can go out of date, why not have rich text with hyperlinks and semantic information?

For examples of help markup, look at any file whose name ends with -docs.factor in the Factor source tree. There are plenty.

x86 and PowerPC assemblers

I put this one last since its not really a DSL at all, just a nice API. The lowest level of Factor's compiler generates machine code from the compiler's intermediate form in a CPU-specific way. The CPU backends for x86 and PowerPC use the cpu.x86.assembler and cpu.ppc.assembler vocabularies for this, respectively. The way the assemblers work is that they define a set of words corresponding to CPU instructions. Instruction words takes operands from the stack -- which are objects representing registers, immediate values, and in the case of the x86, addressing modes. They then combine the operands and the instruction into a binary opcode, and add it to a byte vector stored in a dynamically-scoped variable. So instead of calling methods on, and passing around, an 'assembler object' as you would in say, a JIT coded in C++, you wrap the code generation in a call to Factor's make word, and simply invoke instruction words therein. The result looks like assembler source, except it is postfix. Here is an x86 example:

[
    EAX ECX ADD
    XMM0 XMM1 HEX: ff SHUFPS
    AL 7 OR
    RAX 15 [+] RDI MOV
] B{ } make .

When evaluated, the above will print out the following;

B{ 1 200 15 198 193 255 131 200 7 72 137 120 15 }

Of course, B{ is the homoiconic syntax for a byte array. Note the way indirect memory operands are constructed; first, we push the register (RAX) then the displacement (here the constant 15, but register displacement is supported by x86 too). Then we call a word [+] which constructs an object representing the addressing mode [RAX+15].

The rationale for choosing this somewhat funny syntax for indirect operands (there is also a [] word for memory loads without a displacement), rather than some kind of parser hack that allows one to write [RAX] or [R14+RDI] directly, is that in reality the compiler only rarely deals with hard-coded register assignments. Instead, the register allocator makes decisions a level above, and passes them to the code generator. Here is a typical compiler code generation template from the cpu.x86 vocabulary:

M:: x86 %check-nursery ( label temp1 temp2 -- )
    temp1 load-zone-ptr
    temp2 temp1 cell [+] MOV
    temp2 1024 ADD
    temp1 temp1 3 cells [+] MOV
    temp2 temp1 CMP
    label JLE ;

Here, I'm using the locals vocabulary together with the assembler. The temp1 and temp2 parameters are registers and label is, as its name implies, a label to jump to. This snippet generates machine code that checks whether or not the new object allocation area has enough space; if so, it jumps to the label, otherwise it falls through (code to save live registers and call the GC is generated next). The load-zone-ptr word is like an assembler macro here; it takes a register and generates some more code with it.

The PowerPC assembler is a tad more interesting. Since the x86 instruction set is so complex, with many addressing modes and so on, the x86 assembler is implemented in a rather tedious manner. Obvious duplication is abstracted out. However, there is a lot of case-by-case code for different groups of instructions, with no coherent underlying abstraction allowing the instruction set to be described in a declarative way.

On PowerPC, the situation is better. Since the instruction set is a lot more regular (fixed width instructions, only a few distinct instruction formats, no addressing modes), the PowerPC assembler itself is built using a DSL specifically for describing PowerPC instructions:

D: ADDI 14
D: ADDIC 12
D: ADDIC. 13
D: ADDIS 15
D: CMPI 11
D: CMPLI 10
...

The PowerPC instruction format DSL is defined in the cpu.ppc.assembler.backend vocabulary, and as a result the cpu.ppc.assembler vocabulary itself is mostly trivial.

Last words

Usually my blog posts describe recent progress in the Factor implementation, and I tend to write about what I'm working on right now. I'm currently working on code generation for SIMD vector instructions in the Factor compiler. I was going to blog about this instead, but decided not to do it until the SIMD implementation and API settles down some more.

With this post I decided to try something a bit different, and instead just describe an aspect of Factor that interests to me, without any of it being particularly breaking news. If you've been following Factor development closely, there is literally nothing in this post that you would not have seen already, however I figured people who don't track the project so closely might appreciate a general survey like this. I'm also thinking of writing a post describing Factor's various high-level I/O libraries. I'd appreciate any feedback, suggestions and ideas on this matter.

Advanced floating point features: exceptions, rounding modes, denormals, unordered compares, and more

2009-09-12T23:20:00.010-04:00

Factor now has a nice library for introspecting and modifying the floating point environment. Joe Groff implemented most of it, and I helped out with debugging and additional floating point comparison operations. All of these features are part of the IEEE floating point specification and are implemented on all modern CPUs, however few programming languages expose a nice interface to working with them. C compilers typically provide hard-to-use low-level intrinsics and other languages don't tend to bother at all. Two exceptions are the SBCL compiler and the D language.

The new functionality is mostly contained in the math.floats.env vocabulary, with a few new words in math for good measure. The new code is in the repository but it is not completely stable yet; there are still some issues we need to work out on the more obscure platforms.

To follow along with the examples below, you'll need to get a git checkout from the master branch and load the vocabulary in your listener:

USE: math.floats.env

The first two features, floating point exceptions and traps, are useful for debugging numerical algorithms and detecting potentially undesirable situations (NaNs appearing, underflow, overflow, etc).

Floating point exceptions

One of the first things people learn about floating point is that it has "special" values: positive and negative infinity, and not-a-number (NaN) values. These appear as the results of computations where the answer is undefined (division by zero, square root of -1, etc) or the answer is too small or large to be represented as a float (2 to the power of 10000, etc). A less widely-known fact is that when a special value is computed, "exception flags" are set in a hardware register which can be read back in. Most languages do not offer any way to access this functionality.

In Factor, exception flags can be read using the collect-fp-exceptions combinator, which first clears the flags, calls a quotation, then outputs any flags which were set. For example, division by zero sets the division by zero exception flag and returns infinity:

( scratchpad ) [ 1.0 0.0 / ] collect-fp-exceptions . .
{ +fp-zero-divide+ }
1/0.

Dividing 1 by 3 sets the inexact flag, because the result (0.333....) cannot be represented as a float:

( scratchpad ) [ 1.0 3.0 / ] collect-fp-exceptions . .
{ +fp-inexact+ }
0.3333333333333333

The fact that 1/3 does not have a terminating decimal or binary expansion is well-known, however one thing that many beginners find surprising is that some numbers which have terminating decimal expansions nevertheless cannot be represented precisely as floats because they do not terminate in binary (one classic case is 1.0 - 0.9 - 0.1 != 0.0):

( scratchpad ) [ 4.0 10.0 / ] collect-fp-exceptions . .
{ +fp-inexact+ }
0.4

Raising a number to a power that is too large sets both the inexact and overflow flags, and returns infinity:

( scratchpad ) [ 2.0 10000.0 ^ ] collect-fp-exceptions . .
{ +fp-inexact+ +fp-overflow+ }
1/0.

The square root of 4 is an exact value; no exceptions were set:

( scratchpad ) [ 4.0 sqrt ] collect-fp-exceptions . .
{ }
2.0

The square root of 2 is not exact on the other hand:

( scratchpad ) [ 2.0 sqrt ] collect-fp-exceptions . .
{ +fp-inexact+ }
1.414213562373095

Factor supports complex numbers, so taking the square root of -1 returns an exact value and does not set any exceptions:

( scratchpad ) [ -1.0 sqrt ] collect-fp-exceptions . .
{ }
C{ 0.0 1.0 }

However, we can observe the invalid operation exception flag being set if we call the internal fsqrt word, which operates on floats only and calls the libc function (or uses the SQRTSD instruction on SSE2):

( scratchpad ) USE: math.libm [ -1.0 fsqrt ] collect-fp-exceptions . .
{ +fp-invalid-operation+ }
NAN: 8000000000000

I describe the new NAN: syntax later in this post.

Signaling traps

Being able to inspect floating point exceptions set after a piece of code runs is all well and good, but what if you have a tricky underflow bug, or a NaN is popping up somewhere, and you want to know exactly where? In this case it is possible to set a flag in the FPU's control register which triggers a trap when an exception is raised. This trap is delivered to the Factor process as a signal (Unix), Mach exception (Mac OS X), or SEH exception (Windows). Factor then throws it as an exception which can be caught using any of Factor's error handling words, or just left unhandled in which case it will bubble up to the listener.

The with-fp-traps combinator takes a list of traps and runs a quotation with those traps enabled; when the quotation completes (or throws an error) the former FPU state is restored again (indeed it has to be this way, since running the Factor UI's rendering code with traps enabled quickly kills it). The all-fp-exceptions word is equivalent to specifying { +fp-invalid-operation+ +fp-overflow+ +fp-underflow+ +fp-zero-divide+ +fp-inexact+ }. Here is an example:

( scratchpad ) all-fp-exceptions [ 0.0 0.0 / ] with-fp-traps
Floating point trap

Without the combinator wrapped around it, 0.0 0.0 / simply returns a NaN value without throwing anything.

Rounding modes

Unlike exceptions and traps, which do not change the result of a computation but merely set status flags (or interrupt it), the next two features, the rounding mode and denormal mode, actually change the results of computations. As with exceptions and traps, they are implemented as scoped combinators rather than global state changes to ensure that code using these features is 'safe' and cannot change floating point state of surrounding code.

If a floating point operation produces an inexact result, there is the question of how the result will be rounded to a value representable as a float. There are four rounding modes in IEEE floating point:

+round-nearest+
+round-down+
+round-up+
+round-zero+

Here is an example of an inexact computation done with two different rounding modes; the default (+round-nearest+) and +round-up+:

( scratchpad ) 1.0 3.0 / .
0.3333333333333333
( scratchpad ) +round-up+ [ 1.0 3.0 / ] with-rounding-mode .
0.3333333333333334

Denormals

Denormal numbers are numbers where the exponent consists of zero bits (the minimum value) but the mantissa is not all zeros. Denormal numbers are undesirable because they have lower precision than normal floats, and on some CPUs computations with denormals are less efficient than with normals. IEEE floating point supports two denormal modes: you can elect to have denormals "flush" to zero (+denormal-flush+), or you can "keep" denormals (+denormal-keep+). The latter is the default:

( scratchpad ) +denormal-flush+ [ 51 2^ bits>double 0.0 + ] with-denormal-mode .
0.0
( scratchpad ) 51 2^ bits>double 0.0 + .
1.112536929253601e-308

Ordered and unordered comparisons

In math, for any two numbers a and b, one of the following three properties hold:

a < b
a = b
a > b

In floating point, there is a fourth possibility; a and b are unordered. This occurs if one of the two values is a NaN. The unordered? predicate tests for this possibility:

( scratchpad ) NAN: 8000000000000 1.0 unordered? .
t

If an ordered comparison word such as < or >= is called with two values which are unordered, they return f and set the +fp-invalid-operation+ exception:

( scratchpad ) NAN: 8000000000000 1.0 [ < ] collect-fp-exceptions . .
{ +fp-invalid-operation+ }
f

If traps are enabled this will throw an error:

( scratchpad ) NAN: 8000000000000 1.0 { +fp-invalid-operation+ } [ < ] with-fp-traps    
Floating point trap

If your numerical algorithm has a legitimate use for NaNs, and you wish to run it with traps enabled, and have certain comparisons not signal traps when inputs are NaNs, you can use unordered comparisons in those cases instead:

( scratchpad ) NAN: 8000000000000 1.0 [ u< ] collect-fp-exceptions . .
{ }
f

Unordered versions of all the comparisons are defined now, u<, u<=, u>, and u>=. Equality of numbers is always unordered, so it does not raise traps if one of the inputs is a NaN. In particular, if both inputs are NaNs, equality always returns f:

( scratchpad ) NAN: 8000000000000 dup [ number= ] collect-fp-exceptions . .
{ }
f

Half-precision floats

Everyone and their drunk buddy know about IEEE single (32-bit) and double (64-bit) floats; IEEE also defines half-precision 16-bit floats. These are not used nearly as much; they come up in graphics programming for example, since GPUs use them for certain calculations with color components where you don't need more accuracy. The half-floats vocabulary provides some support for working with half-floats. It defines a pair of words for converting Factor's double-precision floats to and from half-floats, as well as C type support for passing half-floats to C functions via FFI, and building packed arrays of half-floats for passing to the GPU.

Literal syntax for NaNs and hexadecimal floats

You may have noticed the funny NAN: syntax above. Previously all NaN values would print as 0/0., however this is inaccurate since not all NaNs are created equal; because of how IEEE floating point works, a value is a NaN if the exponent consists of all ones, leaving the mantissa unspecified. The mantissa is known as the "NaN payload" in this case. NaNs now print out, and can be parsed back in, using a syntax that makes the payload explicit. A NaN can also be constructed with an arbitrary payload using the <fp-nan> word:

( scratchpad ) HEX: deadbeef <fp-nan> .
NAN: deadbeef

The old 0/0. syntax still works; it is shorthand for NAN: 8000000000000, the canonical "quiet" NaN.

Some operations produce NaNs with different payloads:

( scratchpad ) USE: math.libm
( scratchpad ) 2.0 facos .
NAN: 8000000000022

In general, there is very little you can do with the NaN payload.

A more useful feature is hexadecimal float literals. When reading a float from a decimal string, or printing a float to a decimal string, there is sometimes ambiguity due to rounding. No such problem exists with hexadecimal floats.

An example of printing a number as a decimal and a hexadecimal float:

( scratchpad ) USE: math.constants
( scratchpad ) pi .
3.141592653589793
( scratchpad ) pi .h
1.921fb54442d18p1

Java supports hexadecimal float literals as of Java 1.5. Hats off to the Java designers for adding this! It would be nice if they would add the rest of the IEEE floating point functionality in Java 7.

Signed zero

Unlike twos-complement integer arithmetic, IEEE floating point has both positive and negative zero. Negative zero is used as a result of computations of very small negative numbers that underflowed. They also have applications in complex analysis because they allow a choice of branch cut to be made. Factor's abs word used to be implemented incorrectly on floats; it would check if the input was negative, and if so multiply it by negative one. However this was a problem because negative zero is not less than zero, and so the absolute value of negative zero would be reported as negative zero. The correct implementation of the absolute value function on floats is to simply clear the sign bit. It works properly now:

( scratchpad ) -0.0 abs .
0.0

Implementation

The implementation of the above features consists of several parts:

Cross-platform Factor code in the math.floats.env vocabulary implementing the high-level API
Assembly code in vm/cpu-x86.32.S, vm/cpu-x86.64.S, and vm/cpu-ppc.S to read and write x87, SSE2 and PowerPC FPU control registers
Low-level code in math.floats.env.x86 and math.floats.env.ppc which implements the high-level API in terms of the assembly functions, by calling them via Factor's FFI and parsing control registers into a cross-platform representation in terms of Factor symbols
Miscellaneous words for taking floats apart into their bitwise representation in the math vocabulary
Compiler support for ordered and unordered floating point compare instructions in compiler.cfg.instructions
CPU-specific code generation for ordered and unordered floating point compare instructions in cpu.x86 and cpu.ppc

Eliminating some boilerplate in the compiler

2009-09-02T06:59:00.003-04:00

Adding new instructions to the low-level optimizer was too hard. Multiple places had to be updated, and I would do all this by hand:

The instruction tuple itself is defined in the compiler.cfg.instructions vocabulary with the INSN: class, which also creates a word with the same name that constructs the instruction and adds it to the current sequence.
Instructions which have a destination register have convenient constructors in compiler.cfg.hats which creates a fresh virtual register, creates an instruction with this register as the destination, and outputs it. So for example, 1 2 ^^add would create an add instruction with a fresh destination register, and output this register. It might be equivalent to something like 0 1 2 ##add.
Instructions that use virtual registers are be added to the vreg-insn union, and respond to methods defs-vreg, uses-vregs, and temp-vregs in compiler.cfg.def-use. This 'def-use' information is used by SSA construction, dead code elimination, copy coalescing, register allocation, among other things.
Methods have to be defined for the instruction in compiler.cfg.renaming.functor. This functor is used to generate code for renaming virtual registers in instructions. The renaming code is used for SSA construction, representation selection, register allocation, among other things.
Instructions which use non-integer representations (eg, operations on floats) must respond to methods defs-vreg-rep, uses-vreg-reps, and temp-vreg-reps in compiler.cfg.representations.preferred.
Instructions must respond to the generate-insn method, defined in compiler.codegen.
Instructions which participate in value numbering must define an "expression" variant, and respond to the >expr method defined in compiler.cfg.value-numbering.expressions

As you can see, this is a lot of duplicated work. I used inheritance and mixins to model relationships between instructions and reduce some of this duplication by defining methods on common superclasses rather than individual instructions where possible, but this never seemed to work out well.

If you look at the latest versions of the source files I linked to above, you'll see that all the repetitive copy-pasted code has been replaced with meta-programming. The new approach extends the INSN: parsing word so now all relevant information is specified in one place. Also there is a new PURE-INSN: parsing word, to mark instructions which participate in value numbering; previously this was done with a superclass. For example,

PURE-INSN: ##add
def: dst/int-rep
use: src1/int-rep src2/int-rep ;

This defines an instruction tuple, an expression tuple, def/use information, representation information, a method for converting instructions to expressions, and a constructor, all at the same time.

For the code generator's generate-insn method, not every instruction has a straightforward implementation; some, like GC checks and FFI calls, postpone a fair amount of work until the very last stage of compilation. However, for most instructions, this method simply extracts all the slots from the instruction tuple, then calls a CPU-specific hook in the cpu.architecture vocabulary to generate code. For these cases, a CODEGEN: parsing word sets up the relevant boilerplate;

CODEGEN: ##add %add

is equivalent to

M: ##add generate-insn [ dst>> ] [ src1>> ] [ src2>> ] tri %add ;

This nicely cleans up all the repetition I mentioned in the bullet points at the top.

I've been aware of this boilerplate for a while but wanted the design of the compiler to settle down first. Now that most of the machinery is in place, I feel comfortable cooking up some complex meta-programming to clean things up. Adding new instructions should be easier. I plan on adding some SSE2 vector operations soon, and this was the main motivation behind this cleanup.

How would you do this in other languages? In Lisp, you would use a macro which expands into a bunch of defclass, defmethod, etc forms. In Java, you might use annotations:

public class AddInsn extends Insn {
    @Def @Representation("int") Register dst;
    @Use @Representation("int") Register src1;
    @Use @Representation("int") Register src2;
}

Struct arrays benchmark revisited: trig function calls are slow in Java, but without them Factor is still 3x faster

2009-08-29T21:44:00.015-04:00

My struct arrays benchmark generated a fair amount of discussion on reddit, with some people disputing the benchmark's validity. Certainly I'm not claiming that Factor is faster than Java HotSpot in general (on most tasks it is slower, sometimes much more so), however I think the benchmark legitimately demonstrates the performance advantage of value semantics over reference semantics.

A few people pointed out that the Java version of the benchmark was spending a lot of time in trigonometric functions, and that Java computes sin and cosine "by hand" rather than using x87 FPU instructions. However, the same is also true of the Factor implementation, its just that none of the Java advocates bothered to check. I don't use x87 instructions either, and call into libc for sin and cos, just like Java. Indeed, Factor's sin and cos are even more heavyweight than Java's, because they also support complex numbers; Factor's compiler converts them to their real-valued equivalents if it can prove the inputs are real.

Despite this, I modified the benchmark to not call trig functions, and instead just initialize each point as (n+1,n+2,(n+3)*(n+3)/2). Factor is still faster by roughly the same margin as before:

Java	829ms (best run out of 8)
Factor	284ms

A few people also mentioned that by only running the test 8 times I wasn't giving HotSpot enough time to "warm up". However, the benchmark does not make any polymorphic calls in the inner loops, so there's really no "warm up" needed at all; and indeed I got the best time on the third iteration.

I improved Factor's code generation for trigonometric function calls. Trig function calls are treated like instructions by the low-level optimizer now, which means they participate in value numbering and do not split basic blocks. Instead, the register allocator spills all live registers at the call site at the very end of code generation. This strategy does not work in general for all FFI calls, because the case where the FFI calls invokes a Factor callback needs additional runtime support. However, neither sin nor cos do this. After implementing this, I noticed that my struct-arrays benchmark was calling sin() twice on the same input, and value numbering was folding the second call away. Neat optimization to get "for free".

This code generation change improves performance of both the struct-arrays and partial-sums benchmarks:

Benchmark	Before	After
struct-arrays	1483ms	749ms
partial-sums	1233ms	938ms

Here is the disassembly for benchmark.struct-arrays with this optimization performed, and this is the patch.

For what its worth, Java HotSpot runs the partial-sums benchmark in 1293ms. Hopefully HotSpot's trig function call performance will receive some attention at some point.

Performance comparison between Factor and Java on a contrived benchmark

2009-08-28T05:21:00.008-04:00

Recently, Joe Groff has been working on struct classes, with the aim of completely replacing Factor's existing support for C structure types. The interesting thing about Joe's struct classes is that unlike the clunky old FFI struct support which operated on byte arrays, struct classes really are Factor classes; instances look and feel like Factor objects, there's literal syntax and prettyprinter support, and structure fields are accessed using accessor words that look exactly like Factor tuple slot accessors.

So whereas the old C structure support didn't have much use outside of the FFI, the new struct classes become a useful and type-safe abstraction in themselves. Tuples are composed of dynamically-typed slots which reference Factor values, and structs are composed of scalar data stored in contiguous memory. This makes them useful in code that otherwise does not use the FFI.

What makes struct classes even more useful in performance-sensitive code is the related struct-arrays vocabulary. This presents a sequence of struct values, stored in contiguous memory, as a Factor sequence. This allows ordinary high-level sequence operations and combinators (map, filter, change-each, ...) to be used on scalar data with a very efficient in-memory representation.

It is interesting that Factor's core is rather high-level and dynamically typed, but various libraries built off to the side using meta-programming facilities implement features useful for systems programming, such as specialized array types, allowing binary pointerless data to be represented and manipulated efficiently. This is unprecedented in dynamic languages, where the usual approach is to farm out performance-intensive work to another language.

The performance difference between, say, an array of pointers to boxed floats, and a raw array of floats, cannot be understated. Further levels of structure make the difference even more dramatic: an array of pointers to objects where each one has three fields pointing to boxed floats (what a mouthful), is considerably less efficient to work with than an array of structures with three float fields each. In the former case, a great many objects are allocated and pointers traversed while working with the data; in the latter case, all data can be stored in one contiguous memory block, that appears as a simple byte array to the garbage collector.

Dynamic languages with advanced JITs, such as the recent JavaScript implementations, hit a performance barrier imposed by their in-memory object representations. Even Java, which has a reputation of being very fast as far as managed, GC'd languages go, suffers here. While Java can pack scalar data into a single instance (so if an object has three float fields, the float data is stored directly in the object); however it does not offer arrays of objects where the objects are stored directly in the array. This negatively impacts performance, as you will see.

There is a buzzword that describes this approach of dealing with data: value semantics. If you find some whiny C++ programmers, soon enough one of them will mumble something about value semantics, and with good reason: because C++ offers value semantics, it often has a performance edge over other programming languages. While production-ready Java and C++ implementations both implement a similar set of optimizations, language semantics contribute to C++ being faster for a lot of code. Of course, C++ is low-level and has unsafe pointers; however, as Factor demonstrates, you can have a high-level managed language that still provides support for value semantics in a safe way.

I decided to whip up a simple benchmark. Here is what it does:

It works on points, which are triplets of single-precision floats, (x,y,z)
First, the benchmark creates a list of 5000000 points for i=0..4999999, where the ith point is (sin(i),cos(i)*3,sin(i)*sin(i)/2).
Then, each point is normalized; the x, y, and z components are divided by sqrt(x*x+y*y+z*z).
Finally, the maximum x, y, and z components are found, for all points, and this is printed out.

Note that in-place operations, and re-using temporary objects, is allowed.

Here is the code:

The Factor version is both shorter, and has more blank lines.

Note that the Factor version is intended to be run as a vocabulary from the Factor environment, using the time word, as follows:

[ "benchmark.struct-arrays" run ] time

Run it a few of times so that the data heap can grow to a stable size.

The Java code is self-contained; run it with

java -Xms512m -server silly

The Java version runs the benchmark 8 times, and prints the best time; this gives the HotSpot Server JIT a chance to 'warm up'.

The JVM shipped with Mac OS X 10.5 (build 1.5.0_19-b02-304) runs the benchmark in 4.6 seconds, and the Factor version ran in 2.2 seconds using a Factor build from earlier this evening. I made a couple of further improvements to the Factor compiler, bringing the runtime of the Factor version of the benchmark down to 1.4 seconds in the latest source tree:

Added intrinsics for min and max so that when they are applied to values known to be floating point at compile-time, the SSE2 instructions MINSD and MAXSD are used.
Added some optimizations to unbox intermediate <displaced-alien> values constructed by the struct array code. A displaced alien is a value representing a pointer and an offset; it is a heap-allocated object with two slots. This is how struct classes internally implement the backing store for objects which are stored 'in the middle' of a byte array.

The Factor code is several layers of abstraction removed from the low-level machine code that is generated in the end. It takes the following optimizations to get good performance out of it:

All words declared inline are inlined, all higher-order functions are inlined.
Literal quotations (written in square brackets) are inlined at their call sites.
Macros, such as sum-outputs are expanded.
Sequence words, struct field accessors, and generic math operations are all replaced with lower-level type-specific equivalents using type inference; in many cases, these operations, such as adding floats, map directly to machine instructions
The incrementing counter for initializing points is converted into a fixed-precision integer because interval and def-use analysis determine it is safe to do so
Escape analysis determines that various temporary objects can be stack-allocated:
- closures created by various combinators, such as tri-curry, each, and so on
- the struct array object created with <struct-array>
- the struct class instances created inside the many calls to each
- the struct created at the end to store the maximum value
Of the remaining memory allocations, those that create small objects are completely inlined, and do not call into the VM at all
Stack analysis eliminates most of the runtime data stack manipulation in favor of keeping values in CPU registers
Representation analysis figures out that all of the intermediate float values can be unboxed and stored in floating point registers, except for this that live across the sin/cos calls
While the sin and cos functions result in calls into libc, sqrt is open-coded as an SSE2 instruction
Value numbering eliminates redundant pointer arithmetic and the boxing/unboxing of pointer values
GC checks are open-coded and inlined at every basic block which performs an allocation; the GC check compares the nursery pointer against the limit, and in the fast case, where the nursery is not full, no subroutine call is made, and no registers need to be saved and restored
The coalescing pass eliminates unnecessary register to register copy instructions that arise from SSA form, as well as ensuring that in most cases, the result of an arithmetic instruction is the same as the first operand; this helps x86 instruction selection
The register allocator assigns virtual registers to real CPU registers; in this case there is no spilling at all on x86-64

So what does this say about language expressiveness? Any dynamic language that a) offers the same set of metaprogramming tools as Factor b) has a reasonably advanced JIT could do the same. On the other hand, working value semantics into something like Java is pretty much impossible. I invite you implement this benchmark in your favorite language and share your timings.

New tool for locating external resource leaks

2009-08-24T21:59:00.006-04:00

While having garbage collection solves the problem of manually deallocating a block of memory when its lifetime ends, it doesn't help with external resources, such as sockets and file handles, at all. And even in a GC'd language, memory has to be managed manually sometimes, for example when passing data to and from a C library using FFI. So Factor has had a generic disposal protocol, as well as destructors, for quite some time. What was missing was tooling support.

I wanted to build a tool that would help me debug code that was leaking external resources by forgetting to dispose them. Thankfully, this doesn't come up often; as C++ programmers using RAII like to note, scoped destructors solve resource management in 90% of all cases, and Factor's resource management combinators are even more flexible. However, sometimes an external resource can have a complex lifetime, because of caching, pooling, and other advanced idioms. In these cases, having tools to help track leaks down can really help.

I took inspiration from Doug Coleman's managed malloc and free implementation. Whereas some languages use finalizers to ensure that an external resource gets cleaned up if you forget to dispose of it explicitly, I take the opposite approach; all active disposable objects are stored in a central registry, explicitly preventing the GC from cleaning them up.

The new tools.destructors vocabulary introduces two words, disposables. and leaks. The first word prints a tally of all active resources:

Clicking 'list instances' next to a disposable class opens an inspector window with all active instances of this resource; for example, here we can list all file descriptors that Factor has open right now:

You can even dispose of the resource right there, as if you had called the dispose word on it:

The leaks combinator compares active resources before and after a quotation runs, and lists any that were not disposed of. For example, in the following, I construct a file-reader, read a line, and never dispose of it:

Notice how a file descriptor, together with a few associated resources, was leaked as a result of this.

If I wanted to, I could click on 'show instances' and dispose of the input-port in the inspector; this would dispose of the other two associated objects as well. Also, opening the inspector on a disposable resource that was allocated inside a leaks call will display a stack trace, showing where in the code the resource was allocated. This can help pinpoint the offending code.

Of course, the correct way to read a line from a file in Factor is to use a combinator which cleans up the stream for you. In the following example, the resource leak has been fixed:

To define a new disposable resource, simply create a tuple class that subclasses disposable, make sure to construct it with new-disposable, and override the dispose* method.

Here is an example that manages a limited pool of "X"s, of which there are 100 total:

SYMBOL: xs

100 >vector xs set-global

: get-x ( -- x ) xs get pop ;
: return-x ( x -- ) xs get push ;

TUPLE: my-disposable-resource < disposable x ;

: <my-disposable-resource> ( -- disposable )
    my-disposable-resource new-disposable get-x >>x ;

M: my-disposable-resource dispose* x>> return-x ;

The disposable resource machinery is built with very little code, and it is used throughout Factor already.

Status of the PowerPC port, and Snow Leopard's imminent release

2009-08-24T18:40:00.005-04:00

Factor has had a PowerPC port since some time in 2004, when I got it running on my old G3 iMac, and I continued working on it after I switched to a Power Mac G5 as my primary workstation. However, since then, Apple decided to go with Intel chips, and I sold my G5, so I no longer own any PowerPC gear. As a result, the Factor PowerPC port has been neglected for a while now. Right now, the code in the master branch of the git repository bootstraps on PowerPC and basic things seem to work, but there are stability issues (it doesn't manage to finish a full continuous integration run). While I'll probably fix this particular issue and ensure that up to date binaries get uploaded, I can't help but wonder, now that OS X 10.6 is around the corner (without PowerPC support), is it worth my time to keep the PowerPC port going?

In addition to stability issues, the PowerPC port lags behind a bit as far as code quality goes. It doesn't do instruction scheduling, nor does it make use of some unique PowerPC features that would help improve performance (multiple condition registers, etc). AltiVec isn't used at all.

I have a couple of questions for the community:

Does anyone still care about PowerPC at all? I might be out of the loop here; is it about as relevant nowadays as DEC Alpha, or PA-RISC? Other than the game consoles and IBM's big iron gear, who uses it?
Is there any interest at all in a Linux/PowerPC port of Factor?
I guess over time, people who still own older PowerPC-based Macs are going to switch to Linux, as Apple gradually ends issuing security updates and so on for PowerPC systems
Is anyone interested in taking over development of Factor's PowerPC support? It's only 1600 lines of code in basis/cpu/ppc, the assembler is simple to use and implemented declaratively, and the compiler's backend interface is well abstracted and consists of a few dozen small assembly templates. A lot of contributors have more than enough Factor experience to take this one on, I think. If you know some assembly language already, compiler backends are really not that complex in Factor, it just takes time to test them thoroughly.
Should I forget about PowerPC altogether, and spend the time that I would spend on it on reviving the Factor/ARM port instead? Last time I messed around with ARM (a few years ago) contemporary devices were pretty short on RAM; nowadays 256Mb RAM is starting to become common, and Factor would run much better.

Any comments on this matter are appreciated.

Global float unboxing and some other optimizations

2009-08-10T17:21:00.009-04:00

In compiler implementation, "global" optimizations are those that apply to an entire procedure at a time, in contrast to "local" optimizations, which operate on individual basic blocks only. After some work, float unboxing is the latest optimization which is now done globally in Factor.

Factor's float unboxing optimization used to be part of local value numbering. Originally I planned on implementing global value numbering and trying to do float unboxing there, but since then I discovered a better way. I also improved the SSA coalescing pass I talked about last time, and implemented some optimizations which help compile the code in the math.vectors vocabulary more efficiently.

Global float unboxing

Instead of modeling float unboxing as an algebraic simplification problem (where unbox(box(x)) can be rewritten as x) I now model it as a representation problem, ie, the optimizer makes a global decision, for every virtual register, whether to store it as a tagged pointer, or an unboxed float.

When the low-level IR is built, no boxing or unboxing operations are inserted, and the compiler assumes all floating point values will end up unboxed. The new compiler.cfg.representations pass is responsible for inserting just enough boxing and unboxing operations to make the resulting code valid. This pass consists of several step.

Representations and register classes

A representation is like a low-level data type associated to a virtual register. At this stage, possible repesentations are tagged pointers, single-precision floats, and double-precision floats. Note that fixnums (which are stored directly inside a pointer, rather than being heap allocated) are considered as tagged pointers, and that single-precision floats are only used by the FFI. In the future, I will also have a representation type for untagged integers (so that Factor code can perform arithmetic on 32 and 64-bit numbers without boxing them) and various SSE vector types.

A register class is a set of machine registers that instructions can operate on. Every representation has a register class, and values in this representation must be stored in registers of that class. Multiple representations can share a register class; for example, single and double precision floats all go into floating point registers. The register allocator deals with register classes.

When the low-level IR is built, virtual registers do not have representations assigned to them. Instead, this mapping is established later, by the compiler.cfg.representations pass.

First step: compute possible representations for each virtual register

The first step to deciding what representation to use for a virtual register is to take stock of the possibilities. The compiler.cfg.representations.preferred vocabulary defines words which output, for each instruction, the preferred representation of the input values, and the preferred representation of the output value, if any.

For example, the ##slot instruction, which accesses an object's slot, prefers that its inputs and outputs be tagged pointers. On the other hand, ##add-float prefers that its inputs and outputs are unboxed floats (for otherwise, boxing is required), and ##integer>float takes an integer but outputs an unboxed float.

This information is collected into a single mapping, from virtual registers to sequences of representations.

Second step: computing costs for different representations

The next step is to compute the cost of keeping each virtual register in every possible representation for that register. The compiler uses a simple cost heuristic. The cost of keeping a register in a given representation R is obtained by iterating over all instructions that use that register, but expect to receive the value in a different representation from R. For each such instruction, its loop nesting depth is added up. Finally, if the representation R differs from the output representation of the instruction that computed the register, the loop nesting is added to the tally. This gives an approximation of the overhead of boxing and unboxing the value.

To calculate the loop nesting depth of an instruction, I use the standard natural loop detection algorithm. This is implemented in compiler.cfg.loop-detection. The details can be found in any moderately advanced compiler textbook; for each basic block, it identifies a set of loops this basic block belongs to (this set may be empty). A loop consists of a header, a set of more or more end blocks, and a set of blocks making up this loop. Multiple loops can share a header, but each loop can only have a single header because all control flow graphs that the low-level optimizer constructs are reducible (at least I think so).

Third step: representation selection

Once costs have been computed, it is easy to assign to each virtual register the representation that has the least cost. There is one subtlety here though; if an instruction outputs a tagged pointer, no other representation may be used for that virtual register. For example, in this code, it would not be sound to pick an unboxed float representation for the input parameter, since in one branch, it is used as a fixnum, and trying to perform a float unboxing on a fixnum will just crash:

: silly-word ( x -- y )
    {
        { [ dup fixnum? ] [ 1 + ] }
        { [ dup float? ] [ 3 * ] }
    } cond ;

The problem here is that in low-level IR, the ##peek instruction which loads the value from the data stack outputs a tagged value, and a priori the compiler cannot assume its going to be a boxed float that can be safely unboxed -- only the output of a float-producing instruction can be unboxed. A more complicated unboxing algorithm based on control-dependence was suggested to me by Daniel Ehrenberg. However, because the low-level IR is single-assignment, the potential overhead from the current unboxing scheme is not so great, and so I'm not worried about it right now.

Fourth step: inserting boxing and unboxing instructions

Once the compiler has determined the representation to use for each virtual register, it must now iterate over all instructions again, this time, inserting conversions whenever a virtual register is used with a representation other than the one that was chosen for it. This pass introduces new temporaries, and renames virtual registers used and defined in instructions, in order to preserve single assignment. Other than that, it is relatively straightforward.

Live-range coalescing revisited

Last time I mentioned that I had implemented a rather complex algorithm for converting out of SSA form and doing copy coalescing at the same time. After having some problems getting the algorithm working in certain corner cases, I decided to scrap it and implement something simpler instead. My new SSA coalescing algorithm uses the classical interference graph approach, except it doesn't actually have to build the interference graph, since interference testing on SSA form can be done in O(1) time.

The register allocator used to do its own coalescing, to eliminate copies inserted by the two-operand conversion pass. The two-operand pass converts

x = y + z

into

x = y; x = x + z

(and similarly for all other arithmetic operations). This makes arithmetic operations fit the x86 instruction encoding scheme, where the destination register is also the first register. Implementing copy coalescing twice, in two different ways, seemed inelegant to me. A big breakthrough was when I was able to get my SSA coalescing algorithm working on a relaxed SSA form, where values can be reassigned more than once, but only within the same basic block where they are defined. This means that the two-operand conversion pass can run before SSA coalescing, and the register allocator does not need to perform coalescing at all.

The new coalescing algorithm was not noticably slower than the old one (it still benefits from not having to construct an interference graph), the code is much simpler, and the register allocator's copy coalescing code is gone. The compiler feels cleaner as a result.

Improved tuple unboxing

I implemented escape analysis for tuple unboxing last year and recently came up with a way to improve it. Whereas previously, only freshly-allocated tuples could be unboxed, I realized that if an input parameter to a word is known to be an instance of an immutable tuple class, and the input parameter does not escape (ie, not passed to a subroutine call, or returned) then it can be unboxed, too. Whereas unboxing a freshly-allocated tuple involves deleting the allocation call, and replacing slot access with references to the inputs to the allocation call, unboxing an input parameter is a bit trickier. Actual code has to be inserted at the beginning of the word, which unpacks the tuple. This optimization is only a win if the same slot is accessed more than once within a word; in particular, its a win if the slot access occurs inside a loop. This situation came up with specialized arrays; a specialized array is a tuple with two slots, a byte array, and a length. To access the nth element of a specialized array involves an indirection, because the byte array has to be retrieved. By unboxing the specialized array before a loop, a slot access is eliminated from the loop. This gives the high-level optimizer a form of loop-invariant code motion (real loop-invariant code motion might appear in the low-level optimizer at some point, too).

Vector operations on specialized arrays

I used to use hints to make the math.vectors vocabulary faster. While vector words could be used on any sequence type, hints would automatically compile a specialized version of each vector word for the double-array type. This gave a nice speedup on benchmarks which performed vector operations on arrays of double-precision floats, but it didn't help at all for vector operations on other specialized arrays, and there was still at least one runtime dispatch per vector operation, to determine if the generic or hinted version should be used.

While hints have their place, I don't use them for vector words anymore. Instead, I cooked up some special compiler extensions for them (easier than it sounds; the compiler is pretty extensible, at least the pass that I needed to extend for this). Now, every specialized array type compiles a specialized set of vector words, and if the input types of a vector word are known at compile time, the right specialized version is used instead. Of course there's no actual code duplication here, the code is generated at runtime.

Benchmark results

The above improvements, as well as the changes I outlined in my previous post, give a nice speedup since the last time I did some benchmarks.

Benchmark	May 31st	July 17	Aug 10
benchmark.backtrack	1.767561	1.330641	1.111011
benchmark.base64	1.997951	1.738677	1.536447
benchmark.beust1	2.765257	2.461088	2.360084
benchmark.beust2	3.584958	1.694427	1.691499
benchmark.binary-search	1.55002	1.574595	1.585475
benchmark.binary-trees	1.845798	1.733355	1.771849
benchmark.bootstrap1	10.860492	11.447687	9.962971
benchmark.dawes	0.229999	0.161726	0.104693
benchmark.dispatch1	2.015653	2.119268	2.252401
benchmark.dispatch2	1.817941	1.216618	1.629185
benchmark.dispatch3	2.568987	1.899128	2.692071
benchmark.dispatch4	2.319587	2.032182	2.073563
benchmark.dispatch5	2.346744	1.614045	1.369721
benchmark.empty-loop-0	0.146716	0.12589	0.12608
benchmark.empty-loop-1	0.430314	0.342426	0.351241
benchmark.empty-loop-2	0.429012	0.342097	0.350182
benchmark.euler150	16.901451	15.288867	13.046828
benchmark.euler186	8.805434999999999	7.920478	7.997483
benchmark.fannkuch	3.202698	2.964037	2.859117
benchmark.fasta	5.52608	4.934112	5.135706
benchmark.gc0	2.15066	1.993158	2.03638
benchmark.gc1	4.984841	4.961272	5.075487
benchmark.gc2	3.327706	3.265462	3.376618
benchmark.iteration	3.736756	3.30438	3.22603
benchmark.javascript	9.79904	9.164517	9.000165000000001
benchmark.knucleotide	0.282296	0.251879	0.231547
benchmark.mandel	0.125304	0.123945	0.123321
benchmark.md5	0.946516	0.85062	0.84516
benchmark.nbody	3.982774	3.349595	2.204085
benchmark.nested-empty-loop-1	0.116351	0.135936	0.053609
benchmark.nested-empty-loop-2	0.692668	0.438932	0.390032
benchmark.nsieve	0.714772	0.698262	0.694443
benchmark.nsieve-bits	1.451828	0.907247	0.727394
benchmark.nsieve-bytes	0.312481	0.300053	0.225218
benchmark.partial-sums	1.205072	1.221245	1.152942
benchmark.random	2.574773	2.706893	2.403702
benchmark.raytracer	3.481714	2.914116	2.428384
benchmark.recursive	5.964279	3.215277	3.178855
benchmark.regex-dna	0.132406	0.093095	0.08619400000000001
benchmark.reverse-complement	3.811822	3.257535	3.003156
benchmark.ring	1.756481	1.79823	1.696271
benchmark.sha1	2.267648	1.473887	1.43003
benchmark.sockets	8.794280000000001	8.783398	8.643011
benchmark.sort	0.421628	0.363383	0.367602
benchmark.spectral-norm	3.830249	4.036353	3.277558
benchmark.stack	2.086594	1.014408	0.91959
benchmark.sum-file	0.528061	0.422194	0.383183
benchmark.tuple-arrays	0.127335	0.103421	0.08908199999999999
benchmark.typecheck1	0.876559	0.6723440000000001	0.744205
benchmark.typecheck2	0.878561	0.671624	0.770056
benchmark.typecheck3	0.86596	0.670099	0.699071
benchmark.ui-panes	0.426701	0.372301	0.369152
benchmark.xml	2.351934	2.187999	1.630145

Dataflow analysis, computing dominance, and converting to and from SSA form

2009-07-30T03:24:00.007-04:00

As I mentioned in my previous post, I'm working on having the compiler backend take advantage of our fancy new register allocator by making better use of registers than we do now.

As with the previous post, there are lots of links to Factor code here. Also, since much of what I implemented comes from academic papers, I've linked to the relevant literature also.

Over the course of the last year, Factor went from a rudimentary scheme where some intermediate values are placed in registers, to local register allocation for all temporaries in a basic block, to the current system where registers can remain live between basic blocks and values are only stored on the data stack when absolutely necessary; subroutine calls, returns, and points in the procedure from where the value will not be used again.

Before I dive in to the technical details, here is a taste of what the new code generator can do. The following Factor word,

: counted-loop-test ( -- ) 1000000000 [ ] times ;

Compiles to the following x86-64 machine code:

000000010c73b2a0: 48bd0050d6dc01000000  mov rbp, 0x1dcd65000
000000010c73b2aa: 4831c0                xor rax, rax
000000010c73b2ad: 4983c610              add r14, 0x10
000000010c73b2b1: e904000000            jmp 0x10c73b2ba
000000010c73b2b6: 4883c008              add rax, 0x8
000000010c73b2ba: 4839e8                cmp rax, rbp
000000010c73b2bd: 0f8cf3ffffff          jl dword 0x10c73b2b6
000000010c73b2c3: 4983ee10              sub r14, 0x10
000000010c73b2c7: c3                    ret

General overview

The general structure of the low-level optimizer still remains, along with the optimizations it performs -- alias analysis, value numbering, dead code elimination, and so on. However, what has changed in a major way is how the low-level IR is constructed, and how it is gets converted out of SSA. There are also two new abstractions used by the compiler; a dataflow analysis framework, and a meta-programming utility for renaming words.

In the low-level IR, "peek" and "replace" instructions are used to read and write stack locations, making stack traffic explicit. Peek instructions output a virtual register, and replace instructions take a register as input. All other instructions operate on virtual registers, not stack locations.

When building the control flow graph, the compiler.cfg.builder vocabulary used to insert "peek" and "replace" instructions at every use of a stack location, and subsequent redundancy elimination passes would get rid of the ones that are deemed redundant -- where either the relevant stack location was in a register already (peek after peek or peek after replace), or because it would be overwritten before being read again (replace after replace).

Now, the CFG builder doesn't insert peeks and replaces at all, and simply associates with each basic block a set of stack locations that it reads, and a set of stack locations that it writes. For each stack location, there is a globally unique virtual register which is used for it; instructions which need a stack location simply refer to that fixed virtual register (or assign to it). The last step of the CFG builder runs a dataflow analysis and actually inserts peek and replace instructions on the right edges in the CFG, mostly to ensure the invariant that values are saved to the stack between subroutine calls, that all values that are needed from the stack get loaded at some point, and that everything it saved to the stack eventually before the procedure returns. The inserted peeks and replaces reference the stack location's global fixed virtual register.

However, one thing in the above construction is that the output of the CFG builder is no longer in SSA form, like it used to be. However, the problem of converting applicative languages into SSA form is well-known, and so now I have an explicit SSA construction pass which runs after the CFG builder, before any other optimizations which operate on values. After optimizations, SSA form is eliminated by converting phi instructions into copies, at which point the result is passed on to the machine register allocator.

Dataflow analysis

The wikipedia page on dataflow analysis gives a good overview of the topic. Simple dataflow analyses with a single direction of flow all look quite similar, and there are many ways to abstract out the duplication. Since my code to convert stack-based code into low-level IR requires four dataflow analysis passes, and register allocation and SSA construction perform liveness analysis, I needed to eliminate the 5x code duplication that would result from naive implementation.

I went with an object-oriented approach, where a set of generic words are defined, together with a top-level driver word which takes an instance supporting these generic words. The generic words compute local sets, implement the join operation, and determine the direction of flow. The code is defined in the compiler.cfg.dataflow-analysis vocabulary. In addition to the generic words, I also define a couple of parsing words which create a new instance of the dataflow analysis class, together with some supporting boilerplate for looking up basic block's in and out sets after analysis has run. The actual content of the sets propagated depends on the analysis itself; liveness deals with virtual registers, and stack analysis deals with stack locations.

Because of this framework, adding new analyses is very easy. Liveness analysis, implemented in the compiler.cfg.liveness vocabulary, is only a few lines of code.

The dataflow analysis framework does not take SSA phi instructions into account, because stack analysis operates on stack locations (which are not single assignment) and liveness analysis is performed in SSA construction, when no phi instructions have been added yet, as well as register allocation, after SSA destruction.

Renaming values

Multiple compiler passes -- SSA construction, copy propagation, SSA destruction, and register allocation -- need to traverse over instructions and rename values. The first three replace uses of virtual registers with virtual registers, and the latter replaces virtual registers with physical registers prior to machine code generation. To avoid duplicating code, I wrote a utility which takes a hashtable of value mappings, and renames all values used in an instruction. There was a generic word with a method for each instruction. However this approach was insufficient for SSA construction, where the renaming set cannot be precomputed and instead changes at every instruction. So a better abstraction would be one that takes a quotation to apply to each value. However, dynamically calling a quotation for every slot of every instruction would be expensive, and inlining the entire renaming combinator at every use would be impractical. Instead, I used Factor's "functors" feature to write a parsing word which generates renaming logic customized to a particular use. This is defined in the compiler.cfg.renaming.functor vocabulary, and one usage among many is in compiler.cfg.renaming, which implements the old behavior whereby a single hashtable of renamings was input. Here is how this utility is used in SSA construction for instance:

RENAMING: ssa-rename [ gen-name ] [ top-name ] [ ]

This defines words ssa-rename-defs, ssa-rename-uses and ssa-rename-temps (the latter being a no-op). The first two apply gen-name and top-name to each value to compute the new value.

The register allocator does something similar in compiler.cfg.linear-scan.assignment:

RENAMING: assign [ vreg>reg ] [ vreg>reg ] [ vreg>reg ]

Here, words named assign-defs, assign-uses and assign-temps are defined, and they all perform the same operation on each instructions' defined values, used values and temporary values, respectively, by looking up the physical register assigned to each virtual register. This and other optimizations to linear scan significantly improved compile time, to the point where it has almost gone down to what it was before I started adding these fancy new optimizations.

Computing the dominator tree

The dominator tree is a useful concept for optimizations which need to take global control flow into account. At this point, I'm using them for SSA construction and destruction, but there are many other optimizations which depend on dominance information. The classical approach for computing dominance uses iterative dataflow analysis, but a better approach is given in the paper A Simple, Fast Dominance Algorithm by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy. I implemented the dominator tree computation described by the paper in the compiler.cfg.dominance vocabulary. The dominator tree is a tree with basic blocks as nodes; the entry block of the CFG as its root.

There are three operations that need to be performed, and this influences the tree representation:

Getting a node's parent in the tree, often referred to as the immediate dominator (sometimes, a convention is used where the immediate dominator of the root node is the root node itself).
Getting a node's children.
Testing if one node is an ancestor of another node (in this case we say that the first node dominates the second).

The algorithm in the paper computes a mapping from basic blocks to basic blocks, which gives the immediate dominator of every basic block. This lets us solve #1 in constant time. Since many algorithms need to look up children, I invert the immediate dominator mapping and turn it into a multimap (which in Factor, we just represent as an assoc from keys to sequences of values; the push-at utility word is helpful for constructing these). This gives us #2. For #3, the obvious approach is to walk up the tree from the second node, checking if the node at each step is the first node. However, this takes time proportional to the height of the tree, and the worst case is straight-line code with little control flow, where the dominator tree becomes a linked list. Another approach is to compute a hashed set of dominators for each node, which gives us constant time dominance checks, but the space usage is quadratic in the worst case so that's not ideal either.

A much better trick can be found in the paper on the SSA destruction algorithm which I will talk about below. I believe this technique goes back to the 70's and it is widely-known, but I did not learn about it until now. First, you perform a depth-first traversal of the dominator tree, incrementing a counter at each step. The first time you visit a node (on the way down), you assign the current counter value to the node's preorder value. The second time you visit a node (on the way up), you assign the current counter value to the node's maxpreorder value. What this does is number the nodes in preorder, and the maxpreorder of each node is the maximum of the preorder numbers of its children. Once these numbers have been precomputed, dominance checking can be done in constant time using the identity:

A dominates B iff preorder(A) >= preorder(B) & preorder(A) <= maxpreorder(B)

Of course, this works for any tree, and if you plan on doing many repeated child-of tests, it is worth precomputing the pre/maxpre numbers for each node in this manner. This addresses #3 above.

Here is a control flow graph, with the numbers denoting reverse post order on basic blocks:

and here is the corresponding dominator tree:

These diagrams were generated using the Graphviz tool together with the compiler.cfg.graphviz vocabulary).

The paper also gives an efficient algorithm for computing dominance frontiers, but I do not need those, for reasons given in the next section.

SSA construction

The classical approach for constructing SSA form yields what is known as minimal SSA involves three steps:

Computing dominance frontiers for each basic block in the control flow graph
For every value, take the set of basic blocks which have a definition of the value, compute the iterated dominance frontier of this set, and insert a phi instruction (with dummy inputs) in each member of the set
Walk the dominator tree, renaming definitions and usages in order to enforce single static assignment, updating phi instruction inputs along the way.

This approach has two three problems:

Computing iterated dominance frontiers is expensive, and this is done for every value defined in more than one block
Too many phi instructions are inserted, and most end up being eliminated as dead code later
The renaming algorithm, as originally specified, requires too much work to be done on the walk back up the dominator tree, with each block's instructions being traversed both on the way down and on the way up

Nevertheless, the algorithm is simple and easy to understand. It is explained in the original paper on SSA form, Efficiently computing static single assignment form and the control dependence graph; straightforward pseudocode can be found in these lecture notes.

The so-called "pruned SSA form" addresses the issue of too many phi instructions being inserted. It is a minor modification of minimal SSA construction. Prior to inserting phi instructions, liveness information is computed for each block. Then, a phi instruction is only inserted for a value if the value is live into the block. Computing liveness is somewhat expensive, and the so-called "semi-pruned SSA form" uses a simple heuristic to approximate liveness; phi nodes are only inserted for values which are used in blocks other than those they are defined in.

An algorithm for computing iterated dominance frontiers which does not require dominance frontiers to be computed first was described in the paper A Practical and Fast Iterative Algorithm for Phi-Function Computation Using DJ Graphs by
Dibyendu Das and U. Ramakrishna.

Finally, the paper introducing semi-pruned SSA form, titled Practical Improvements to the Construction and Destruction of Static Single Assignment Form, proposes a slightly more efficient renaming algorithm.

So the SSA construction algorithm I implemented in the compiler.cfg.ssa.construction vocabulary is a combination of these three papers. First, I compute merge sets using the DJ-Graph algorithm, then, I use liveness information for placing phi instructions, and finally, I use the improved renaming algorithm.

SSA destruction

To get out of SSA form and back to imperative code which can be executed by a machine, phi instructions must be eliminated. The approach originally described by Cytron et al gives incorrect results in many cases; the correct algorithm is well-known now but it introduces many additional copy instructions. The classical approach for eliminating copies ("copy coalescing") is to do it as part of register allocation; if two values are related by a copy but do not otherwise interfere, they can be assigned to the same physical register, and the copy can be deleted from the program. This works for a graph-coloring approach, but with linear scan, you're limited in how much global knowledge you can have while performing register allocation, and accurate interference information is difficult to obtain.

Factor's register allocation performs some basic coalescing, mostly to eliminate copies arising from conversion to two-operand form on x86. However, phi nodes introduce copies with more complex interferences and my approach didn't work there, so even though stack analysis eliminated many memory to register and register to memory moves, the generated code had a large number of register to register moves, which is a bottleneck for instruction decoding, not to mention wastes valuable cache space.

Instead of attempting to coalesce copies arising from phi instructions in the register allocator, a more modern approach is to do this as part of SSA destruction -- instead of converting phi instructions to copies, the goal is to avoid inserting as many copies as possible in the first place.

A nice algorithm for SSA destruction with coalescing is detailed in the paper Fast copy coalescing and live-range identification, by Zoran Budimlic et al. The algorithm is very clever -- the two key results are a constant-time interference test between SSA values using dominance and live range information, and a linear-time interference test in a set of variables using "dominance forests", which are easy to construct and enable you to rule out most pairs of values for interference tests altogether.

This algorithm is implemented in LLVM (lib/CodeGen/StrongPHIElimination.cpp) and I essentially ported the C++ code to Factor. You can find the code in the compiler.cfg.ssa.destruction vocabulary.

I tweaked the algorithm a little -- instead of inserting sequential copies, I insert parallel copies, as detailed in the paper Revisiting Out-of-SSA Translation for Correctness, Code Quality and Efficiency by Benoit Boissinot et al. The parallel copy algorithm is implemented in compiler.cfg.parallel-copy. I used it not only in SSA destruction, but also to clean up some hackish approximations of the same problem in global stack analysis and the linear scan register allocator's resolve pass. I didn't implement the rest of the paper, because I found it hard to follow; it claims to provide a better algorithm than Budimlic et al, but the latter is good enough for now, and having a working implementation in the form of the LLVM pass was very valuable in implementing it in Factor.

This pass was very effective in eliminating copy instructions; it generates 75% of copies than the old phi elimination pass, which simply used the naive algorithm.

Loop head rotation

The last optimization I added eliminates an unconditional branch in some loops. Consider the following CFG:

A valid way to linearize the basic blocks is in reverse post order, that is 0, 1, 2, 3, 4, 5. However, with this linearization, block 3 has an unconditional branch back to block 2, and block 2 has a conditional which either falls through to 3 or jumps to 4. So on every loop iteration, two jumps are executed (the conditional jump at 2 and the unconditional jump at 3). If, instead, the CFG was linearized as 0, 1, 3, 2, 4, 5, then while 1 would have an unconditional jump to 2, 2 would have a conditional jump back to 3 and 3 would fall through to 2. So upon entry to the loop, an extra unconditional jump (from 1 to 3) executes, but on each iteration, there is just the single conditional backward jump at 2. This improves performance slightly and is easy to implement; the code is in the compiler.cfg.linearization.order vocabulary, and I borrowed the algorithm from SBCL's src/compiler/control.lisp.

Conclusion

There are some performance regressions I need to work out, because global stack analysis introduces too many partial redundancies for some types of code, and inline GC checks are currently disabled because of an unrelated issue I need to fix. It will take a few more days of tweaking to sort things out, and then I will post some benchmarks. Early results are already very promising on benchmarks with loops; not just the trivial counted loop example above.

Next steps are global float unboxing, unboxed 32-bit and 64-bit integer arithmetic, and SSE intrinsics. To help with the latter, Joe Groff was kind enough to add support for all SSE1/2/3/4 instructions to Factor's x86 assembler. Finally, thanks to Cameron Zwarich for pointing me at some of the papers I linked to above.

Improved value numbering, branch splitting, and faster overflow checks

2009-07-17T02:19:00.005-04:00

Hot on the heels on the improved register allocator, I've added some new optimizations to the low-level optimizer and made existing optimizations stronger.

Improved value numbering

Local value numbering now detects more congruences along values computed by low level IR instructions. All the changes were either in the rewrite or simplify steps.

Some additional arithmetic identities. For instance, the result of adding or subtracting 0 to a value is congruent to the value itself. The high-level optimizer implements the same optimization on Factor's generic arithmetic words, but sometimes low-level optimizations introduce additional redundancies.
A ##add instruction where one of the two operands is the result of a ##load-immediate is now converted into a ##add-imm, saving a register. A similar identity holds for other commutative operations, such as ##mul, ##and, ##or, ##xor, and ##compare with a condition code of cc=.
Constant folding. Arithmetic instructions where both operands are constants are replaced by a ##load-immediate containing the result. A special case is a subtraction where both operands are congruent; this is replaced by a load of 0. Again, the high-level optimizer performs constant folding also, but low-level optimizations sometimes introduce redundancies or expose opportunities for optimization which were not apparent in high-level IR.
Reassociation. If an ##add-imm instruction's first input is the result of another ##add-imm, then a new ##add-imm is made which computes the same result with a single addition. Algebraically, this corresponds to the identity (x + a) + b = x + (a + b), where a and b are known at compile-time. Similar transformations are made for other associative operations, such as ##sub, ##mul, ##and, ##or and ##xor.
Constant branch folding. If both inputs to a ##compare or ##compare-branch are constant, or if both are congruent to the same value, then the result of the comparison can be computed at compile-time, and one of the two successor blocks can be deleted.

While the high-level optimizer performs constant folding and unreachable code elimination as part of the SCCP pass, low-level optimizations which are done before value numbering can expose optimization opportunities which were invisible in high-level IR. For example, consider the following code:
[ { vector } declare [ length ] [ length ] bi < ]
Using the optimized. word, we can see what the high-level optimizer transforms this into:

[ dup >R 3 slot R> 3 slot fixnum< ]

The high-level optimizer only attempts to reason about immutable slots, but a vector's length is mutable since a vector may have elements added to it, and so the high-level optimizer cannot detect that the two inputs to fixnum< are equal. A conversion into low-level IR, the code becomes the following sequence of SSA instructions:

_label 0 f 
##prologue f 
_label 1 f 
##peek V int-regs 1 D 0 f 
##copy V int-regs 4 V int-regs 1 f 
##slot-imm V int-regs 5 V int-regs 4 3 7 f 
##copy V int-regs 8 V int-regs 1 f 
##slot-imm V int-regs 9 V int-regs 8 3 7 f 
##copy V int-regs 10 V int-regs 5 f 
##copy V int-regs 11 V int-regs 9 f 
##compare V int-regs 12 V int-regs 10 V int-regs 11 cc< V int-regs 13 f 
##replace V int-regs 12 D 0 f 
##epilogue f 
##return f 
_spill-counts f f

Now, the low-level alias analysis optimization is able to detect that the second ##slot-imm is redundant, and it transforms the code into the following:

_label 0 f 
##prologue f 
_label 1 f 
##peek V int-regs 1 D 0 f 
##copy V int-regs 4 V int-regs 1 f 
##slot-imm V int-regs 5 V int-regs 4 3 7 f 
##copy V int-regs 9 V int-regs 5 f 
##copy V int-regs 10 V int-regs 5 f 
##copy V int-regs 11 V int-regs 9 f 
##compare V int-regs 12 V int-regs 10 V int-regs 11 cc< V int-regs 13 f 
##replace V int-regs 12 D 0 f 
##epilogue f 
##return f 
_spill-counts f f

Now, notice that both inputs to the ##compare instruction (vreg #10 and vreg #11) are copies of the same value, vreg #5. Value numbering detects this congruence since copy propagation is just a special case of value numbering; it then simplifies the comparison down to a constant load of f, since for any integer x, we have x < x => false. After dead code elimination, the result is the following:

_label 0 f 
##prologue f 
_label 1 f 
##load-immediate V int-regs 12 5 f 
##replace V int-regs 12 D 0 f 
##epilogue f 
##return f 
_spill-counts f f

While no programmer would explicitly write such redundant code, it comes up after inlining. For example, the push word, which adds an element at the end of a sequence, is implemented as follows:

: push ( elt seq -- ) [ length ] [ set-nth ] bi ;

HINTS: push { vector } { sbuf } ;

The hints tell the compiler to compile specialized versions of this word for vectors and string buffers. While the generic versions work on any sequence, the hinted versions are used when the input types match, and the result can be better performance if generic words are inlined (in this case, length and set-nth). Now, after a bunch of code is inlined, a piece of code comes up which compares the insertion index against the vector's length; however, the insertion index is the length in this case, and so value numbering is now able to optimize out a conditional which could not be optimized out before. Of course I could have just written a specialized version of push for vectors (or even built it into the VM) but I'd rather implement general optimizations and write my code in a high-level style.

I'd like to thank Doug Coleman for implementing some of the above improvements.

Branch splitting

Roughly speaking, branch splitting is the following transform:

[ A [ B ] [ C ] if D ] => [ A [ B D ] [ C D ] if ]

It is only run if D is a small amount of code. Branch splitting runs before value numbering, so value numbering's constant branch folding can help simplify the resulting control flow. Branch splitting is implemented in the compiler.cfg.branch-splitting vocabulary.

For example, suppose we have the following code:

[ [ t ] [ f ] if [ 1 ] [ 2 ] if ]

The high-level optimizer is unable to simplify this further, since it does not work on a control flow graph. The low level optimizer builds a control flow graph with the following shape:

The basic block in the middle is a candidate for splitting since it has two predecessors, and it is short. After splitting, the result looks like so:

Now, at this point, the only thing that this has achieved is eliminating one unconditional jump at the expense of code size. However, after stack analysis and value numbering run, some redundant work is eliminated:

One example of real code that benefits from branch splitting includes code that calls the = word followed by a conditional. The = word is inlined, and it has a conditional inside of it; some branches of the conditional push constants t and f, and others call non-inline words. The result is that the branches which push a constant boolean can directly jump to the destination block without the overhead of storing and testing a boolean value.

Once again thanks to Doug Coleman for collaborating with me on the implementation of branch splitting.

Block joining

Block joining is a simple optimization which merges basic blocks connected by a single control flow edge. Various low-level optimizations leave the control flow graph with a large number of empty or very small blocks with no conditional control flow between them. Block joining helps improve effectiveness of local optimizations by creating larger basic blocks.

In the above example for branch splitting, block joining will eliminate the four empty basic blocks that remain after optimization.

Block joining is implemented in the compiler.cfg.block-joining vocabulary.

Faster overflowing integer arithmetic intrinsics

In the lucky cases where the compiler can eliminate overflow checks, the various math operations become single instructions in the low-level IR which eventually map directly to machine instructions. In the general case, however, an overflow check has to be generated. In the event of overflow, a bignum is allocated, which may in turn involve running the garbage collector, so it is quite an expensive operation compared to a single machine arithmetic operation.

Previously, the overflowing fixnum operations were represented in low-level IR as single, indivisible units, and just like subroutine calls and returns, they were "sync points" which meant that all values in registers had to be saved to the data and retain stacks before, and reloaded after. This is because of how these operations were implemented; they would perform the arithmetic, do an overflow check, and in the event of overflow, they would invoke a subroutine which handled the overflow. Keeping registers live across this operation was not sound in the event of overflow, since the subroutine call would clobber them.

No longer. Now, an overflowing fixnum operation breaks down into several nodes in the control flow graph, and the arithmetic part, the overflow check and the bignum allocation are represented separately. In particular, the code to save registers to the stack and reload them after is only generated in the overflow case, so in the event of no overflow, which happens much more frequently, execution can "fall through" and continue using the same registers as before.

The code that generates low-level instructions and control flow graph nodes for overflowing fixnum operations is defined in the compiler.cfg.intrinsics.fixnum vocabulary.

Faster integer shifts

This last optimization is a very minor one, but it made a difference on benchmarks. Previously shifts with a constant shift count and no overflow check would compile as a machine instruction, and all other forms of shifts would invoke subroutine calls. Now, machine instructions are generated in the case where the shift count is unknown, but the result is still known to be small enough not to require an overflow check.

Benchmark results

Here are the results of running Factor's benchmark suite on a build from 31st May 2009, before I started working on the current set of low-level optimizer improvements (which includes the register allocator I blogged about previously), and from today.

Benchmark	Before	After
benchmark.backtrack	1.767561	1.330641
benchmark.base64	1.997951	1.738677
benchmark.beust1	2.765257	2.461088
benchmark.beust2	3.584958	1.694427
benchmark.binary-search	1.55002	1.574595
benchmark.binary-trees	1.845798	1.733355
benchmark.bootstrap1	10.860492	11.447687
benchmark.dawes	0.229999	0.161726
benchmark.dispatch1	2.015653	2.119268
benchmark.dispatch2	1.817941	1.216618
benchmark.dispatch3	2.568987	1.899128
benchmark.dispatch4	2.319587	2.032182
benchmark.dispatch5	2.346744	1.614045
benchmark.empty-loop-0	0.146716	0.12589
benchmark.empty-loop-1	0.430314	0.342426
benchmark.empty-loop-2	0.429012	0.342097
benchmark.euler150	16.901451	15.288867
benchmark.euler186	8.805434999999999	7.920478
benchmark.fannkuch	3.202698	2.964037
benchmark.fasta	5.52608	4.934112
benchmark.gc0	2.15066	1.993158
benchmark.gc1	4.984841	4.961272
benchmark.gc2	3.327706	3.265462
benchmark.iteration	3.736756	3.30438
benchmark.javascript	9.79904	9.164517
benchmark.knucleotide	0.282296	0.251879
benchmark.mandel	0.125304	0.123945
benchmark.md5	0.946516	0.85062
benchmark.nbody	3.982774	3.349595
benchmark.nested-empty-loop-1	0.116351	0.135936
benchmark.nested-empty-loop-2	0.692668	0.438932
benchmark.nsieve	0.714772	0.698262
benchmark.nsieve-bits	1.451828	0.907247
benchmark.nsieve-bytes	0.312481	0.300053
benchmark.partial-sums	1.205072	1.221245
benchmark.pidigits	16.088346	16.159176
benchmark.random	2.574773	2.706893
benchmark.raytracer	3.481714	2.914116
benchmark.recursive	5.964279	3.215277
benchmark.regex-dna	0.132406	0.093095
benchmark.reverse-complement	3.811822	3.257535
benchmark.ring	1.756481	1.79823
benchmark.sha1	2.267648	1.473887
benchmark.sockets	8.794280000000001	8.783398
benchmark.sort	0.421628	0.363383
benchmark.spectral-norm	3.830249	4.036353
benchmark.stack	2.086594	1.014408
benchmark.sum-file	0.528061	0.422194
benchmark.tuple-arrays	0.127335	0.103421
benchmark.typecheck1	0.876559	0.6723440000000001
benchmark.typecheck2	0.878561	0.671624
benchmark.typecheck3	0.86596	0.670099
benchmark.ui-panes	0.426701	0.372301
benchmark.xml	2.351934	2.187999

There are a couple of regressions I need to look into but for the most part the results look pretty good. I also expect further gains to come with additional optimizations that I plan on implementing.

Next steps

I'm going to keep working on the code generator for another little while. First of all, compile time has increased so that needs to improve. Next, I'm going to implement better global optimization. At this point, values are stored in register between basic blocks, unlike with the old code generator. However, loop variables are still stored on the stack between iterations because the analysis does not handle back edges yet. Fixing this, and making float unboxing work globally, is my next step. After that, I plan on adding support for unboxed word-size integers (32 or 64-bits, depending on platform) and some intrinsics for SSE2 vector operations on Intel CPUs. Next, the register allocator needs improved coalescing logic, and it also needs to support fixed register assignments as found on some x86 instructions which take implicit operands. Finally, I have a few optimizations I want to add to the high level optimizer.

Improvements to Factor's register allocator

2009-07-09T19:49:00.007-04:00

For the last couple of months I've been working on some improvements to Factor's low-level optimizer and code generator. The major new change is that the control flow graph IR is now allowed to define registers that are used in more than one basic block. Previously, all values would be loaded from the data stack at the start of a basic block and stored to the stack at the end. Register allocation in this case is called local register allocation. Now the only time when values have to be saved to the stack is for subroutine calls. The part of the compiler most affected by this is of course the register allocator, because now it needs to do global register allocation.

I will describe the new optimizations in a future blog post and talk about global register allocation here. To help people who are learning Factor or are simply curious about what real Factor code looks like, I've inserted lots of links from this blog post to our online code repository browser.

Instead of rewriting the register allocator from scratch, I took a more incremental approach, gradually refactoring it to operate on the entire control flow graph instead of a basic block at a time. Generalizing the linear scan algorithm to do this is relatively straightforward, but there are some subtleties. Once again, I used Christian Wimmer's masters thesis as a guide, however this time around I implemented almost the entire algorithm described there, instead of the simplification to the local case.

First, recall some terminology: virtual registers are an abstraction of an ideal CPUs register file: there can be arbitrarily many of them, and each one is only ever assigned to once. The register allocator's job is to rewrite the program to use physical registers instead, possibly mapping a number of virtual registers to the same physical register, and inserting spills and reloads if there are insufficient physical registers to store all temporary values used by the program.

Linearization

A local register allocator operates on a basic block, which is a linear list of instructions. For the global case, linear scan still requires a linear list of instructions as input, so the first step is to traverse the CFG in reverse post order and number the instructions.

Building live intervals

Once a linear ordering among all instructions has been stablished, the second step in linear scan register allocation is building live intervals. In the local case, a virtual register is defined in the same basic block as all of its usages. Furthermore, if we assume single assignment, then there will be only a single definition, and it will precede all uses. So the set of instructions where the register is live is a single interval, which begins at the definition and ends at the last use.

In the global case, the situation is more complicated. First of all, because the linearization chosen is essentially arbitrary, and does not reflect the actual control flow in reality, instructions are not necessarily executed in order, so if a register is defined at position A and used at position B, it does not mean that the register is live at every position between A and B. Indeed, in the global case, the live "interval" of a register may consist of a number of disjoint ranges of instructions.

As an example, consider the following C program:

1: int x = ...;
2: if(...) {
3:     ... a bunch of code that does not use x
4: } else {
5:     int y = x + 1;
6:     ... code that doesn't use x
7: }
8: ... more code that doesn't use x

The value x is live at position 1, and also at position 5. The last usage of x is at line 5, so it is not live at any position after 5, but also, it is not live at position 3 either, since if the true branch is taken, then x is never used at all. We say that x has a lifetime hole at position 3.

Another case where lifetime holes come up is virtual registers with multiple definitions. The very last step in the low level optimizer, right before register allocation, is phi node elimination. Essentially, phi node elimination turns this,

if(informal) {
    x1 = "hi";
} else {
    x2 = "hello";
}
x = phi(x1,x2);

into the following:

if(informal) {
    x1 = "hi";
    x = x1;
} else {
    x2 = "hello";
    x = x2;
}

Now, the value x is not live at the line x2 = "hello";, because it hasn't been defined yet, and the previous definition is not available either. So the lifetime interval for x has a hole at this location.

To represent such complex live intervals, the live-interval data type now contains a list of live ranges. Since basic blocks cannot contain control flow or multiple definitions, there can be at most one live range per basic block per live interval. (The only time multiple definitions come up is as a result of Phi node elimination, and since the input is in SSA form this cannot introduce multiple assignments in the same block).

Information from liveness analysis is used to construct live ranges. A basic block's live range contains the first definition of the register as well as the last use. If the register is in the "live in" set of the basic block, then the range begins at the block's first instruction, and if the register is in the "live out" set then the range ends at the block's last instruction. Note that even if a basic block has no usages of a register, it may appear in both the live in and live out sets; for example, the register might be defined in a predecessor block, and used in a successor block.

Allocating physical registers to live intervals

Once live intervals have been built, the next step is to assign physical registers to them. During this process, live intervals may be split, with register to memory, memory to register and register to register moves inserted in between; a single virtual register may be in different physical registers and memory locations during its lifetime.

In the local case, the allocation algorithm maintains two pieces of state; the "unhandled set", which is a heap of intervals sorted by start position, and an "active set", which is a list of intervals currently assigned to physical registers. The main algorithm removes the smallest element from the unhandled set, and then removes anything from the active set which ends before the new interval begins. The next step depends on whether or not any physical registers are free. If all physical registers are taken up in the active set, then a decision is made to spill either the new interval, or a member of the active set. Spilling will free up at least one physical register. At this point, a physical register is now free and can be assigned to the new interval, which is then added to the active set. Spilling may split intervals into smaller pieces, and add new elements to the unhandled set, but since the new split intervals are strictly smaller than the original interval, the process eventually terminates. Once the unhandled set is empty, allocation is complete.

The global case is more complicated, primarily due to the presence of lifetime holes in live intervals. A third piece of state is maintained by the allocation pass. This new set, the "inactive set", contains live intervals which have not ended yet, but are currently in a lifetime hole. To illustrate, suppose we have two physical registers, R1 and R2, and three virtual registers, V1, V2, and V3, with the following live intervals:


    [Program start ....... Program end]
V1: <======>                <=========>
V2:         <==============>
V3:              <================>
                 ^
                 |
           Current position

Immediately before V3's live interval begins, the active set includes V2, and the inactive set contains V1, since V1 is not finished yet, but the current position is in a lifetime hole. Suppose that V1 was assigned to physical register R1, and V2 was assigned to physical register R2. In the local case, since the active set only includes one element, V1, we could conclude that R2 was free, and that V3 could be assigned to R2. However, this is invalid, since at a later point, V1 becomes active again, and V1 uses R2. Two overlapping live intervals cannot use the same physical register. So global linear scan also has to examine the inactive set in order to see if the new live interval can fit in an inactive interval's lifetime hole. In this case, it cannot, so we have to split V3, and insert a copy instruction in the middle:

      [Program start ....... Program end]
V1:   <======>                <=========>
V2:           <==============>
V3_1:              <=========>
V3_2:                         <====>
                   ^
                   |
             Current position

With V3 split into V3_1 and V3_2, a valid register assignment is possible, with V3_1 stored in R1 and V3_2 stored in R2.

In this case, a register assignment without any spilling is possible. However, sometimes, virtual registers have to be stored to memory. This is done by the spilling code which uses a similar algorithm to the local case. The main complication is that in order to free up a physical register for the entire lifetime of the new interval, more than one interval may need to be split; zero or one active intervals, and zero or more inactive intervals.

Assigning physical registers to instructions

After live intervals are split, and physical registers are assigned to live intervals, the assignment pass iterates over all instructions, storing a mapping from virtual registers to physical registers in each instruction. Recall that this cannot be a global mapping, since a virtual register may reside in several different physical registers at different locations in the program.

The algorithm here is essentially unchanged from the local case. Two additions are that at the start and end of each basic block, the assignment pass records which registers are live. This information is used by GC checks. GC checks are performed on basic block boundaries of blocks which allocate memory. Since a register may be defined in one basic block, and used in another, with a GC check in between, GC checks need to store registers which contain pointers to a special location in the call stack and pass a pointer to this location to the GC. Some language implementations use a conservative GC to get around having to do this, but I think recording accurate pointer root information is a superior approach. This liveness information is also used by the resolve pass, coming up next.

The resolve pass

Since linear scan does not take control flow into account, interval splitting will give incorrect results if implemented naively. Consider the following example program:

x = ...;

if(...) {
    ...
    y = x + 1;
    ... some code with high register pressure here
} else {
    z = x + 2;
}

If the live interval of x was spilled immediately after the line y = x + 1; then the register allocator would rewrite it as follows -- it would be spilled after the last usage before the spill point, and reloaded before the first usage after the spill point:

x = ...;

if(...) {
    ...
    y = x + 1;
    spill(x);
    ... some code with high register pressure here
} else {
    reload(x);
    z = x + 2;
}

In this case however, the spill and reload locations are in different control flow paths. However, linear scan does not take control flow into account during the main algorithm. Instead, a subsequent resolve pass. The resolve pass looks at every edge in the control flow graph, and compares the physical register and spill slot assignments of all virtual registers which are both live across the edge. If they differ, moves, spills and reloads are inserted on the edge. Conceptually, this pass is simple, but it feels hackish -- it seems that a more elegant register allocator would incorporate this into the previous stages of allocation. However, all formulations of linear scan I've seen so far work this way. The only tricky part about the resolve pass is that the moves have to be performed "in parallel"; for example, suppose we have two virtual registers V1 and V2, and two physical registers R1 and R2. Block A and block B are joined by an edge. At the end of block A, V1 is in R1, and V2 is in R2. At the start of block B, V1 is in R2 and V2 is in R1. Doing the moves in any order would give the wrong result; for correct behavior, the cycle has to be broken with a third temporary location. The logic for doing this in the general case is a bit complex; Doug Coleman helped me implement the mapping code.

General observations

While implementing the register allocator improvements, I relied heavily on unit testing as well as an informal "design by contract"; basically, making extensive use of runtime assertions in the code itself. The compiler.cfg.linear-scan vocabulary weighs in at 3828 lines of code; 2484 lines of this are unit tests. This is certainly a much higher test:code ratio than most other Factor code I've written, and some of the tests are not very useful or redundant. However, they represent a log of features and bugs I've implemented, and at the very least, minimize regressions.

When testing the register allocator, I first got it working on x86-64. Here, there are enough registers that spilling almost never occurs, so I could focus on getting the primary logic correct. Then, I hacked the x86-64 backend to only use 4 physical registers, and debugged spilling.

The whole project took a bit longer than I had hoped, but I managed to start implementing a number of additional optimizations in the meantime. When they are more complete I will blog about them.

Factor's implementation of polymorphic inline caching

2009-05-26T21:19:00.005-04:00

Polymorphic inline caching is a technique to speed up method dispatch by generating custom code at method call sites that checks the receiver against only those classes that have come up at that call site. If the receiver's class does not appear in the polymorphic inline cache (this case is known as a "cache miss"), then a new call stub is generated, which checks the receiver's class in addition to the classes already in the stub. This proceeds until the stub reaches a maximum size, after which point further cache misses rewrite the caller to call a general "megamorphic" stub which performs a full method dispatch. A full description can be found in the original paper on the topic.

I implemented polymorphic inline caching and megamorphic caching to replace Factor's previous method dispatch implementation.

Call sites

A generic word's call site is in one of three states:

Cold state - the call instruction points to a stub which looks at the class of the object being dispatched upon, generates a new PIC stub containing a single entry, updates the call site, and jumps to the right method.
Inline cache state - the call instruction points to a generated PIC stub which has one or more class checks, followed by a jump to a method if the checks succeed. If none of the checks succeed, it jumps to the inline cache miss routine. The miss routine does one of two things:
- If the PIC stub already has the maximum number of entries, it sets the call site to point to the generic word's megamorphic stub, shared by all megamorphic call sites.
- If the PIC stub has less than the maximum number of entries, a new PIC stub is generated, with the same set of entries as the last one, together with a new entry for the class being dispatched on.
Megamorphic state - the call instruction points to the generic word's megamorphic stub. Further dispatches do not modify the call instruction.

When code is loaded into the image, or a full garbage collection occurs, all call sites revert to the cold state. Loading code might define new methods or change class relationships, so caches have to be invalidated in that case to preserve correct language semantics. On a full GC, caches are reverted so that serially monomorphic code is optimized better; if a generic word is called in a long loop with one type, then in a long loop with another type, and so on, it will eventually become megamorphic. Resetting call sites once in a while (a full GC is a relatively rare event) ensures that inline caches better reflect what is going on with the code right now. After implementing PICs, I learned that the V8 JavaScript VM uses the same strategy to invalidate call sites once in a while, so it sounds like I did the right thing.

Direct class checks versus subclass checks

Factor supports various forms of subtyping. For example, tuple classes can inherit from other tuple classes, and also, a union class can be defined whose members are an arbitrary set of classes. When a method is defined on a class, it will apply to all subclasses as well, unless explicitly overriden. Checking if an object is an instance of a class X is a potentially expensive operation, because it is not enough to compare direct classes, superclasses and union members have to be inspected also. Polymorphic inline caching only deals with direct classes, because direct class checks are much quicker (for tuples, just compare the tuple layouts for pointer equality; for instances of built-in classes, compare tag numbers). So for example if a generic word has a single method for the sequence class, and a call site calls the generic with arrays and strings, then the inline cache generated there will have two checks, one for strings, and one for arrays, and both checks will point at the same method.

Inline cache stubs

Inline cache stubs are generated by the VM in the file inline_cache.cpp. This generates machine code, but I'll use C-like pseudocode for examples instead. An inline cache stub looks like this, where index is the parameter number being dispatched on (generic words defined with GENERIC: use 0, generic words defined with GENERIC# can dispatch on any parameter):


void *obj = datastack[index];
void *class = class_of(obj);
if(class == cached_class_1) cached_method_1();
else if(class == cached_class_2) cached_methd_2();
...
else cache_miss(call_site_address,index,class,generic);

Getting the direct class of an object (what I call class_of() in the pseudocode) is a relatively cheap operation. I briefly discussed pointer tagging, type headers and tuple layout headers in my C++ VM post. In the most general case, getting the direct class looks like this, again in vague C-like pseudocode:

if(tag(obj) == hi_tag) return obj.header;
else if(tag(obj) == tuple_layout) return obj.layout;
else return tag(obj);

However, if the cached classes consist only of tag classes (the 7 built-in types whose instances can be differentiated based on tag alone) then the generated stub doesn't need to do the other checks; it just compares the pointer tag against the cached classes. Similarly, if tag and tuple classes are in the cache but no hi-tag classes, one branch can be avoided. In total, the PIC generation code uses one of four stubs for getting the object's class, and the right stub to use is determined by looking at the cached classes (see the function determine_inline_cache_type() in inline_cache.cpp).

Once the stub has been generated, it is installed at the call site and invoked. This way, a PIC miss is transparent to the caller.

Patching call sites

The code for getting and setting jump targets from jump and call instructions is of course CPU-specific; see the get_call_target() and set_call_target() functions, and note that on PowerPC, the instruction cache needs to be flushed manually:

Recall that there are two situations in which the PIC miss code can be invoked:

For a cold call site, to generate the initial stub
For a polymorphic call site, to add a new entry to the PIC

If the call site is a non-tail call, then the return address will be pushed on the stack (x86) or stored in a link register (PowerPC). If the call site is a tail call, then Factor's code generator now moves the current instruction pointer into a register before performing the tail call. This code is generated even when tail-calling words that are not generic; it is a no-op in this case. This is only a single integer load, so other than increasing code size it really has no effect on performance, since on a modern out-of-order CPU the load and jump will execute concurrently. For example, here is how the code snippet beer get length compiles on x86:

0x000000010b8628c0: mov    $0x10b8628c0,%r8
0x000000010b8628ca: pushq  $0x20
0x000000010b8628cf: push   %r8
0x000000010b8628d1: sub    $0x8,%rsp
0x000000010b8628d5: add    $0x10,%r14
0x000000010b8628d9: mov    $0x10a6c8186,%rax
0x000000010b8628e3: mov    %rax,-0x8(%r14)
0x000000010b8628e7: mov    $0x100026c60,%rax
0x000000010b8628f1: mov    (%rax),%rcx
0x000000010b8628f4: mov    %rcx,(%r14)
0x000000010b8628f7: callq  0x10b1e0de0
0x000000010b8628fc: add    $0x18,%rsp
0x000000010b862900: mov    $0x10b86290f,%rbx
0x000000010b86290a: jmpq   0x10b70f4a0

The first few instructions set up a call stack frame, then the beer symbol is pushed on the stack, and the (inlined) definition of get follows. Finally, the address of the jump instruction is loaded into the rbx register and a jump is performed. Initially, the jump points at the PIC miss stub, so the first time this machine code executes, the jump instruction's target will be changed to a newly-generated PIC.

However, the inline_cache_miss() function in the VM takes the call site address as an input parameter, and after all, it is written in C++. Where does this input parameter actually come from? The answer is that there are short assembly stubs that sit between the actual call site and the PIC miss code in the VM. The stubs get the return address in a CPU-specific manner, and then call the VM. This code is in the primitive_inline_cache_miss procedure, which is again defined in several places:

Note that the functions have two entry points. The first entry point is taken for non-tail call sites, the second one is taken for tail call sites.

An optimization

Since allocation of PICs is something that happens rather frequently, it is good to optimize this operation. I implemented segregated free lists for the code heap. Allocating lots of small code heap blocks requires less work now. Also, since every PIC is referenced from at most one call site, when a call site's PIC is regenerated with a new set of cached classes, the only PIC can be returned to the free list immediately. This reduces the frequency of full garbage collections (when the code heap fills up, a full GC must be performed; there is no generational tenuring for code blocks).

Megamorphic caching

If a call site is called with more than a few distinct classes of instances (the default maximum PIC size is 3 entries) then it is patched to call the megamorphic dispatch stub for that generic word. Megamorphic stubs are again generated in the VM, in the dispatch.cpp source file. The machine code that is generated, were it to be expressed in pseudo-C, looks like this:

void *obj = datastack[index];
void *class = class_of(obj);
if(cache[class] == class) goto cache[class + 1];
else megamorphic_cache_miss(class,generic,cache);

Every generic word has a fixed-size megamorphic cache of 32-entries (this can be changed by bootstrapping a new image, but I'm not sure there's any point). It works like a hashtable, except if there is a collision, the old entry is simply evicted; there is no bucket chaining or probing strategy here. While less efficient than a polymorphic inline cache hit (which only entails a direct jump), megamorphic cache hits are still rather quick (some arithmetic and an indirect jump). There are no calls into the VM, it is all inline assembly. A megamorphic inline cache miss calls the mega_cache_miss primitive which computes the correct method and updates the cache.

Performance

I added some instrumentation code to the VM which counts the number of cache hits and misses. The majority of call sites are monomorphic or polymorphic, and megamorphic call sites are very rare. Megamorphic cache misses are rarer still.

The performance gain for benchmark runtimes was as I expected; a 5-10% gain. The old method dispatch system was already pretty efficient, and modern CPUs have branch prediction which helped a lot with it. For compile time, the gain was a lot more drastic, however, and definitely made the effort I put into implementing PICs pay off; bootstrap is now a full minute faster than before, clocking in at around 3 minutes, and the load-all word, which loads and compiles all the libraries in the distribution, used to take 25 minutes and now takes 11 minutes. All timings are from my MacBook Pro.

The compile-time gain is not a direct result of the inline caching, but rather stems from the fact that the compiler has to compile less code. With the old method dispatch implementation, every generic word was an ordinary word under the hood, with a huge, auto-generated body containing conditionals and jump tables. When a method was added or removed, the dispatcher code had to be re-generated and re-compiled, which takes a long time. With polymorphic inline caching, what happens is now the VM essentially lazily generates just those parts of the dispatch code which are actually used, and since it uses the VM's JIT code instead of the optimizing compiler, it can just glue bits of machine code together instead of building an IR and optimizing it; which yielded no benefits for the type of code that appeared in a generic word body anyway.

Improving compile time is one of my major goals for Factor 1.0, since it improves user experience when doing interactive development, and I'm very happy with the progress so far.

Live status display for Factor's build farm, and other improvements

2009-05-22T19:38:00.002-04:00

Lately I've made a few additional improvements to the build infrastructure. First, build reports sent to the Factor-builds mailing list are now formatted as HTML, which makes them a bit more readable. Second, there is a Twitter feed of binary uploads: @FactorBuilds. Finally, we now have a live status display for build machines. Previously if I wanted to know what a build machine was doing, I'd have to log in with ssh and poke around -- total waste of time. Now, just clicking on the OS/CPU combination on factorcode.org takes you to a status page. For example, here is the status page for Mac OS X/x86. At the time of this blog post, I see that this machine is running tests for a certain GIT revision. Each GIT revision is a link to the GitHub mirror of the Factor repository so you can see exactly what's going on. Finally, the latest build report can be viewed too; this has the build failures, if any, as well as benchmark timings.

Our continuous build system is called mason and adds up to a total of 1196 lines of code. Eduardo Cavazos wrote the first iteration, called builder. I forked it and added additional features.

It's been over a year since we started using continuous integration in the Factor project, and I can say its been an overwhelming success. The first iteration of the build system would load all libraries and run all unit tests, and send an email with the results. If everything succeeded, it would upload a binary package. Over the last year, more than 5000 binary packages were uploaded. Over time, we added more checks to the build farm. It now runs help lint checks which ensure that examples in documentation work and that there are no broken links, and checks for compiler errors.

I think the code quality has definitely gone up over the last year; having a dozen machines running tests all the time does a good job of triggering obscure bugs, and the automatic upload of binaries when tests pass saves us from the hassle of making manual releases.

I think pretty soon, we're going to start having releases again, in addition to continuous builds. I intend on making the release process semi-automatic; when I decide to do a release, I want to send some type of command to all the build machines to have them build a given GIT ID and upload the binaries to a special directory. The goal is to have regular releases until 1.0, starting from a few weeks from now. I'm not going to commit to a schedule for 1.0 yet, but having regular releases and published change logs is the first step of the process.

Unboxed tuple arrays in Factor

2009-05-21T20:25:00.006-04:00

One difference between high level languages and systems languages is that high level languages typically hide the notion of a pointer, and by extension, value versus reference semantics, from the programmer. Systems languages make this explicit, and the programmer can make a choice whether or not to pass an object by value or by reference.

In particular, this level of control can lead to significant space savings for large arrays of homogeneous data. If the elements of an array are themselves not shared by other structures, then storing values directly in the array will, at the very least, save on the space usage of a pointer, together with an object header.

I don't believe there is any reason for high-level languages to not offer more fine-grained control over heap storage. Factor is dynamically typed but it offers both arrays of unboxed numeric values, and arrays of tuples, which I will describe below. In some cases, using these special-purpose data types can offer significant performance and space gains over polymorphic arrays.

Consider a Factor tuple definition:

TUPLE: point x y ;

We can find out how much space points use in memory -- this is on a x86-64 machine:

( scratchpad ) point new size .
32

The x and y slots are as wide as a machine pointer, so together they use 16 bytes. This means that there is an additional 16-byte overhead for every instance. Indeed, Factor tuples store a header and a pointer to a layout object (shared by all instances of that class) in addition to the slot data itself. While this compares favorably to other dynamic languages (see this blog post for instance; Ruby in particular has really terrible object representation), it still adds up to a significant overhead when you have a large collection of points.

Suppose you have an array of N points. Each array element is a pointer (8 bytes) to a point object (32 bytes). Assuming the points are not referenced from any other collection, that's 40*N bytes for the entire collection. However, there is only 16*N bytes of real data, namely the x and y slots of every element, so we're wasting more than 50% of heap usage here, not to mention increasing GC overhead by allocating tons of small objects.

This overhead can be avoided, however, using Factor's tuple-arrays library. Tuple arrays implement the same sequence protocol as arrays, but the semantics differ. Instead of storing references to objects, they store object slots directly within the array. There are two main restrictions that result from this:

Tuple arrays are homogeneous; all elements are of the exact same type. This rules out setting some elements to f to represent missing data, or having elements which are instances of different subclasses of the same base class.
Tuple arrays implement value semantics. If you get an element out, and mutate it, you have to store it back into the array to update the original value in the array.

So how do tuple arrays work? The original implementation, by Daniel Ehrenberg defined a single tuple-array class where the constructor took a class word as a parameter, and reflection APIs were used to implement getting and setting elements. While this had all the space savings described above, constructing and deconstructing tuples via reflection is not the fastest thing in the world; even the most efficient possible implementation would require some indirection and type checking in order to work.

A better approach is to generate a new sequence type for each element type. This is what the current implementation does. Because all of Factor's sequence operations are written in terms of a sequence protocol, these generated classes are for the most part transparent to the programmer, and there is no added inconvenience over the previous approach. To use it, you invoke a parsing word with the element type class you want to use:

TUPLE-ARRAY: point

Assuming a class named point was previously defined, this generates a point-array class with associated methods.

Briefly, the implementation works as follows. The underlying storage of a tuple array is an ordinary array. If the tuple class has N slots, then every group of N elements in the underlying array is a single element in the tuple array. The nth and set-nth methods, which are generated once for every tuple array, read and write a group of N elements and package them into a tuple.

Now let's dive into the guts of the implementation. The parsing word is defined as follows:

SYNTAX: TUPLE-ARRAY: scan-word define-tuple-array ;

So it delegates all the hard work to a define-tuple-array word. This word is a functor, so tuple arrays work the same as specialized numeric arrays. Functors are similar to C++ templates in spirit, but really they are implemented entirely as a library, and it's all just syntax sugar for parsing word machinery (which is a lot more powerful than C++ templates). They're named "functors" to annoy category theory fanboys and language purists. A functor definition begins with FUNCTOR::

FUNCTOR: define-tuple-array ( CLASS -- )

A functor is essentially the same as a word defined with ::, but with additional syntax sugar. So CLASS here is a local variable available in the body of the functor. I use the convention of uppercase names for functor parameters. What follows FUNCTOR: is a list of clauses which create new words at parse time. The left hand side of each clause is a new local variable name that the generated word will be bound to, and the right hand side is an interpolate form describing what the new word should be named. The middle operator specifies whether or not the word should already exist (IS) or if it should be defined (DEFINED). So the definition of define-tuple-array proceeds as follows:

CLASS IS ${CLASS}

CLASS-array DEFINES-CLASS ${CLASS}-array
CLASS-array? IS ${CLASS-array}?

<CLASS-array> DEFINES <${CLASS}-array>
>CLASS-array DEFINES >${CLASS}-array

Next, a functor definition calls WHERE, which switches the parser to reading the functor body.

After that, what follows is a series of forms which look like word definitions, but really they parse as code which defines words at the time that the functor is executed. Both the word names and bodies may reference local variables defined in the first part of the functor:

WHERE

TUPLE: CLASS-array
{ seq array read-only }
{ n array-capacity read-only }
{ length array-capacity read-only } ;

: <CLASS-array> ( length -- tuple-array )
    [ \ CLASS [ tuple-prototype <repetition> concat ] [ tuple-arity ] bi ] keep
    \ CLASS-array boa ; inline

M: CLASS-array length length>> ;

M: CLASS-array nth-unsafe tuple-slice \ CLASS read-tuple ;

M: CLASS-array set-nth-unsafe tuple-slice \ CLASS write-tuple ;

M: CLASS-array new-sequence drop <CLASS-array> ;

: >CLASS-array ( seq -- tuple-array ) 0 <CLASS-array> clone-like ;

M: CLASS-array like drop dup CLASS-array? [ >CLASS-array ] unless ;

INSTANCE: CLASS-array sequence

So every time someone calls define-tuple-array (most likely with the TUPLE-ARRAY: parsing word) a new class is defined, together with a constructor word and some methods.

Finally, we end the functor with:

;FUNCTOR

To illustrate, this means that the following:

TUPLE-ARRAY: point

Is equivalent to the following:

TUPLE: point-array
{ seq array read-only }
{ n array-capacity read-only }
{ length array-capacity read-only } ;

: <point-array> ( length -- tuple-array )
    [ \ point [ tuple-prototype <repetition> concat ] [ tuple-arity ] bi ] keep
    \ point-array boa ; inline

M: point-array length length>> ;

M: point-array nth-unsafe tuple-slice \ point read-tuple ;

M: point-array set-nth-unsafe tuple-slice \ point write-tuple ;

M: point-array new-sequence drop <point-array> ;

: >point-array ( seq -- tuple-array ) 0 <point-array> clone-like ;

M: point-array like drop dup point-array? [ >point-array ] unless ;

INSTANCE: point-array sequence

Now imagine writing all of the above code out every time you want a specialized tuple array; that would amount to boilerplate. Of course, at this point, it still looks like runtime reflection is happening, because we're passing the point class word to the read-tuple and write-tuple words. However, what actually happens is that these words get inlined, then the fact that the class parameter is a constant triggers a series of macro expansions and constant folding optimizations that boil the code down to an efficient, specialized routine for packing and unpacking points from the array. If you're interested in the gory details, take a look at the tuple arrays source code.

So the space savings are clearly nice to have, but what about performance? Here is a program that uses polymorphic arrays:

TUPLE: point { x float } { y float } ;

: polymorphic-array-benchmark ( -- )
    5000 [ point new ] replicate
    1000 [
        [
            [ 1+ ] change-x
            [ 1- ] change-y
        ] map
    ] times drop ;

Here is the same program using tuple arrays:

TUPLE: point { x float } { y float } ;

TUPLE-ARRAY: point

: tuple-array-benchmark ( -- )
    5000 <point-array> 
    1000 [
        [
            [ 1+ ] change-x
            [ 1- ] change-y
        ] map
    ] times drop ;

On my MacBook Pro, the first version using polymorphic arrays runs in 0.39 seconds, the second version using tuple arrays runs in 0.91 seconds. Clearly, there is some overhead from copying the objects in and out of the array.

Now, let's try a slightly different program. Instead of mutating the elements of the array, let's instead extract the slots, modify them, and make a new tuple. Here is a version using polymorphic arrays:

TUPLE: point { x float read-only } { y float read-only } ;

: polymorphic-array-benchmark ( -- )
    5000 [ point new ] replicate
    1000 [
        [
            [ x>> 1+ ] [ y>> 1- ] bi <point>
        ] map
    ] times drop ;

This version runs in 0.94 seconds; the additional object allocation induces a 3x overhead over mutating the points in place. Now, let's try the same thing with tuple arrays:

TUPLE: point { x float read-only } { y float read-only } ;

TUPLE-ARRAY: point

: tuple-array-benchmark ( -- )
    5000 <point-array> 
    1000 [
        [
            [ x>> 1+ ] [ y>> 1- ] bi <point>
        ] map
    ] times drop ;

For this variant I'm getting runtimes of 0.59 seconds, which is faster than the same code with polymorphic arrays. The reason for the speed boost is that the Factor compiler's escape analysis pass kicks in, eliminating all tuple allocation from within the loop completely.

So to summarize, in order from fastest to slowest,

Polymorphic arrays with in-place mutation
Tuple arrays with read-only tuples
Polymorphic arrays with read-only tuples
Tuple arrays with in-place mutation

Finally, a note about benchmarking methodology. Because garbage collection can add an element of unpredictability to benchmarks, I force run the GC to run first:

( scratchpad ) gc [ tuple-array-benchmark ] time
== Running time ==

0.593989 seconds

The combination of a high-level language with efficient abstractions that the compiler knows how to optimize is very powerful. Factor occupies a middle ground between the dynamic languages and systems languages. I want Factor to be a language that you can write an entire application in, even the performance-critical parts. Often you hear that "performance doesn't matter", but outside of a few I/O-bound problem domains, this is false (and even there, you want to heavily optimize your I/O and text processing routines). Very often, people cite some variation of the "80/20 performance rule" (20% of your program runs 80% of the time; adjust percentages to suit your strawman). Of course, the idea is that you can write the 80% in a high level language, dropping down to C for the performance-critical 20%. I think this reasoning is flawed, for two reasons:

As my friend Cameron Zwarich likes to point out, very little justification is given for the 80/20 rule itself. For many programs, the performance profile is rather flat, and every indirection, every unnecessary runtime check, and every unnecessary runtime memory allocation adds up to a non-trivial amount of overhead. The "performance bottleneck" myth originated in a survey of Fortran programs which did numerical calculations. For numerics, it is indeed true that most of the runtime is spent in a handful of inner loops; whether or not this is true for ordinary programs is far less clear.
Even if runtime really is dominated by a small number of routines, chances are these routines are algorithmically complex, hard to write, and nice to experiment with interactively; precisely the domain where high-level languages with advanced abstractions shine.

I think it's about time dynamic language advocates stopped citing the same old myths to justify poor implementation techniques. Their energy would be better spent researching compiler optimizations and garbage collection techniques which they can apply in their favorite language implementations instead. Hats off to the V8, SquirrelFish, Unladen Swallow and SBCL projects for taking performance seriously.

Factor VM ported to C++

2009-05-08T14:06:00.008-04:00

Most of Factor is implemented in Factor (the parser, data structures, optimizing compiler, input/output, the UI toolkit, etc) however a few bits and pieces are not completely self hosting. This includes the garbage collector, non-optimizing compiler (used for bootstrap), and various runtime services. This code comprises what I call the "Factor VM". Even though it is not a Virtual Machine in the classical sense, since there's no interpreter or bytecode format, it serves a similar role to the VM of scripting languages.

Ever since Factor lost its JVM dependency in mid-2004, the VM has been written in C with some GNU extensions. Over time, I've noticed that a few things in the VM source code seem to be hard to express and error-prone in straight C. I've been thinking about switching to C++ for a long time, and now I've finally decided to bite the bullet and do it. I'm pleased with the result, and other than a longer compile time for the VM, I don't have any complaints so far.

I started off by first getting the existing C code to compile with the GNU C++ compiler. Since C++ is almost, but not quite, a super set of C, I had to make a few changes to the source:

Renaming a few identifiers (I had local variables named class, template and new in some places)
Fixing some type safety issues (C will implicitly cast void* to any other pointer type, whereas C++ will not)
Moving global variable declarations to source files, and changing the declarations in the headers to be extern
Making a few functions extern "C" since they are called from code generated by the Factor compiler

Once this was done and everything was working, I started the process of refactoring my C pain points using C++ language features and idioms. This process is far from complete; at the end of the blog post I will outline what remains to be done.

Miscellaneous improvements

While the Factor VM is pretty small, around 13,000 lines of code right now, being able to use C++ namespaces is still nice since I've had name clashes with system C headers in the past. Now everything is wrapped in a factor namespace, so this should occur less in the future. Also, I changed a bunch of #define to inline functions and constants.

Tagged pointers

Factor is dynamically typed. While the optimizing compiler infers types and eliminates type checks sometimes, this generates machine code directly and mostly sidesteps the VM entirely. As far as the VM is concerned, it must be possible to determine the type of a value from its runtime representation. There are many approaches to doing this; the one I've been using from the start is "tagged pointers".

Here is how it works: in the Factor VM, objects are always allocated on 8-byte boundaries in the data heap. This means every address is a multiple of 8, or equivalently, the least significant 3 bits of a raw address are zero. I take advantage of this to store some type information in these bits. A related trick that the Factor VM does is to reserve a tag for small integers that fit in a pointer; so a 29-bit integer (on 32-bit platforms) or a 61-bit integer (on 64-bit platforms) does not need to be heap-allocated.

With 3 tag bits, we get a total of 8 unique tags. Factor has more than 8 data types, though, and indeed the user can define their own data types too. So there are two tags used to denote that the data type is actually stored in the object's header. One of these is used for built-in VM types that don't have a unique tag number, another one is used for user-defined tuple class instances.

Since C and C++ do not have native support for tagged pointers, the VM needs a mechanism to convert tagged pointers to untagged pointers, and vice versa. When converting a tagged pointer to an untagged pointer, a type check is performed.

In the C VM, I had code like the following:

#define TAG_MASK 7
#define UNTAG(tagged) (tagged & ~TAG_MASK)

typedef struct { ... } F_ARRAY;

#define ARRAY_TYPE 2

F_ARRAY *untag_array(CELL tagged)
{
    type_check(ARRAY_TYPE,tagged);
    return (F_ARRAY *)UNTAG(tagged);
}

Here, CELL is typedef'd to an unsigned integer as wide as void*, and UNTAG is a macro which untags a pointer by masking off the low 3 bits (7 decimal is 111 binary).

To convert untagged pointers to tagged form, I used code like the following:

#define RETAG(untagged,tag) (((CELL)(untagged) & ~TAG_MASK) | (tag))

CELL tag_array(F_ARRAY *untagged)
{
    return RETAG(untagged,ARRAY_TYPE);
}

For hi-tag types, such as strings, I used a single tag_object() function:

CELL tag_object(void *untagged)
{
    return RETAG(untagged,OBJECT_TYPE);
}

The OBJECT_TYPE constant was misleadingly named, since everything in Factor is an object. However, in the VM it means "an object with type info in its header".

The old C code for tagging and untagging pointers was mostly adequate, however it suffered from a few issues. First, there was a lot of boilerplate; each tag type has an untag/tag function pair, and each hi-tag type had an untag function. Furthermore, every time I changed a hi-tag type into a tag type, I had to find usages of tag_object() and change them appropriately. Over time I developed several preprocessor macros to clean up this type of stuff but I was never happy with it.

In C++, the whole thing came out much cleaner. The UNTAG and RETAG macros are still around (although I may change them to inline functions at some point). However, for tagging and untagging pointers, I use a single set of template functions. To tag an untagged pointer:

template <typename T> cell tag(T *value)
{
 return RETAG(value,tag_for(T::type_number));
}

That's it; one function for all data types. It is used like so:

array *a = ...;
cell c = tag(a);

How does it work? The F_ARRAY struct is now the array class, and it has a static variable type_number:

struct array : public object
{
    static const cell type_number = 2;
    ...
}

How do hi-tag pointers get handled? Well, their type numbers are all greater than or equal to 8. The tag_for() function checks for this, and returns the object tag number of it is the case. Since it is an inline function, the computation is constant-folded at compile time, and the generated code is as efficient as the old C version, only more type-safe and with less boilerplate.

For untagging tagged pointers, I use a more complicated scheme. I have a templated "smart pointer" class representing a tagged pointer with an associated data type. Here is a simplified version of the class; this omits the type checking logic and a bunch of other utility methods; if you want the gory details, the full source is in tagged.hpp.

template <typename T>
struct tagged
{
    cell value_;
    T *untagged() const { return (T *)(UNTAG(value_)); }
    T *operator->() const { return untagged(); }
    explicit tagged(T *untagged) : value_(factor::tag(untagged)) { }
}

The overload of operator-> means that tagged pointers can be used like ordinary pointers on some cases without needing to be untagged first. Otherwise, a pointer stored in a cell can be untagged like so:

array *a = tagged(c).untagged()

I made a utility function to encapsulate this type of thing, for when I just want to untag a value once and not pass it around as a smart pointer:

template  T *untag(cell value)
{
 return tagged(value).untagged();
}

Now I can write

array *a = untag<array>(c)

This compiles down to the same machine code as the C version but it is more type-safe and less verbose.

Registration of local variables with the garbage collector

Any object allocation can trigger a GC, and the GC must be able to identify all live values at that point. For compiled Factor code, this is pretty easy. The GC needs to scan a few globals, the data and retain stacks, as well as the call stack; call frames for Factor code have a known format. The compiler does store objects in registers, but it moves them to the stack before calling into the GC.

However, the VM code itself uses the garbage collector to allocate its own internal state. This makes the VM code more robust since it doesn't need to worry about when to deallocate memory, but it presents a problem: if a C local variable points into the GC heap, how does the GC know that the value is live, and how does the GC know to update the pointer of the value got moved (Factor's GC is a generational semi-space collector so objects move around a lot). Between function calls, compiled C code saves pointers in the call frame. However, since I have no control over the machine code gcc generates, I cannot force call stack frames into a certain format that the GC can understand, like I do with compiled Factor code.

One solution is conservative garbage collection. The garbage collector can just pessimistically assume that any integer variable on the call stack might point into the GC heap. There are two problems with this approach. The first is if you have a bit pattern that happens to look like a pointer, but is really just a random number, you might keep a value live more than it is really needed. From what I've heard, this is mostly just a theoretical concern. A more pressing issue is that since you do not know what is a real pointer and what isn't, you cannot move objects that might be referenced from the call stack. This can lead to fragmentation and more expensive allocation routines.

The technique I've been using until now in the C VM code was to have a pair of macros, REGISTER_ROOT and UNREGISTER_ROOT. These push and pop the address of a local variable on a "GC root stack". So by traversing the GC root stack, the garbage collector knows which call stack locations refer to objects in the GC heap, and which are just integers. The disadvantage of this approach is that pairing root registration was verbose and error-prone, and forgetting to regsiter a root before calling a function which may potentially allocate memory would lead to hard-to-discover bugs that would be triggered rarely and result in memory corruption.

Using C++ language features, I instead implemented a "smart pointer" gc_root class. It subclasses the tagged smart pointer I described above, with the additional functionality in the constructor and destructor to register and unregister a pointer to the wrapped pointer as a GC root. Together with the overloaded operator-> this makes for much clearer and safer code. By updating existing code to use this new smart pointer I found a few places in the old C code where I had forgotten to register roots. No doubt one or two users saw Factor crash because of these. You can look at the source code for the GC root abstraction.

Object-oriented abstractions

Most functions in the VM are still top-level C-style functions, however in a few places I've found good reason to use methods and even inheritance. I've avoided virtual methods so far. One place where inheritance has really helped clean up some crufty old C code is in what I call the JIT. This is a simple native code generator that the VM uses to fill in the gaps for the optimizing compiler that's written in Factor. The JIT is used to generate machine code in the following situations:

The old design was built out of C macros and code duplication. Now there is a jit class with various methods to emit machine code. Subclasses of jit, such as quotation_jit and inline_cache_jit, add additional functionality. The constructor and destructor take care of registering and unregistering the objects used by the JIT with the GC.

Functionality moved out of the VM

Since I prefer programming in Factor over low-level languages such as C and C++, I try to keep the VM small. A couple of things were in the VM for historical reasons only. The complex number and rational number data types, for instance, were defined in the VM, even though operations on them were in Factor code. This is because the number tower predated user-defined tuple types by a year or so. Nowadays there is no reason not to use tuples to define these types, so I made the change, simplifying the VM. Another piece of functionality that no longer had a good reason to be in the VM was some vestigial code for converting Factor's Unicode string type to and from Latin-1 and UCS-2 encodings. Ever since Daniel Ehrenberg implemented the io.encodings library in Factor, most string encoding and decoding was done in library code, and a lot more encodings were implemented; UTF8, Shift-JIS, MacRoman, EBCDIC, etc. Only a couple of things still relied on the VM's broken built-in string encoding. They're now using the library just like everything else.

Code heap compaction

Factor allocates compiled machine code in their own heap, separate from the data heap. A mark/sweep/compact garbage collector manages the code heap. When performing a compaction, the code heap garbage collector needs to maintain an association from a code block's old address to its new address. Previously this would be stored in the code block's header, wasting 4 bytes (or 8 bytes on 64-bit platforms) per code block. Now I use std::tr1::unordered_map to do this. Of course I could've written a hashtable in C, or used an existing implementation, but using STL is more convenient.

Future improvements

I don't spend much time working on the Factor VM, since most of the action is in the compiler, library, and UI, which are all written in Factor and not C++. However, at some point I'm going to do more work on the garbage collector, and I will do some more cleanups at that time:

Eliminate usages of GNU C extensions. I want to be able to compile the Factor VM with other compilers, such as Microsoft's Visual Studio, and LLVM's Clang.
Eliminating global variables
Using new/delete instead of malloc() and free() for the small set of data that the VM allocates in unmanaged memory
Various other cleanups, such as making better use of method invocation and templates
There's some code duplication in the garbage collector I hope to address with C++ templates

Conclusion

A lot of these cleanups and improvements could have been achieved in C, with clever design and various preprocessor macro tricks. However, I think C++ offers a better set of abstractions for the problem domain that the Factor VM lives in, and since I only use the language features that have no runtime penalty (I'm not using C++ exceptions, virtual methods, or RTTI) there's no performance decrease either. I'm very happy with how the code cleanup turned out. Making the VM easier to understand and maintain will help with implementing more advanced garbage collection algorithms, among other things.

Recent UI improvements

2009-04-18T18:42:00.005-04:00

Over the last few months I've done a lot of work on Factor's UI toolkit, and the developer tools built on top. Here is an overview of what's changed.

Code cleanup

I've been working on the UI since 2005, and it has accumulated a lot of cruft since then. Language features have come and gone and not enough refactoring was done over time. Last year I rewrote the HTTP server and compiler using the latest language features and the result was very clean code. The UI is now written in the same style.

Improved font support

I've blogged about this:

All UI gadgets that render text now use the appropriate platform-specific mechanism for rendering text. The ui.text vocabulary provides the cross-platform abstraction layer. The fonts vocabulary defines data types for fonts and font metrics. This replaces ad-hoc loosely-typed "font specifiers" that the UI used formerly, where a font was just a triple; { "sans-serif" plain 12 } for instance. Font metrics are now supported in a cross-platform manner too. All relevant gadgets now do baseline alignment.

Image support

The UI now supports an easy API for displaying images. The ui.images vocabulary defines some words which can be called from your gadget's draw-gadget* method. The ui.gadgets.icons vocabulary defines a simple gadget that renders an image and nothing else. This is all built on top of the images vocabulary, which implements BMP and TIFF loaders in pure Factor. Hopefully we'll get PNG and JPEG at some point too.

Editor gadget improvements

The ui.gadgets.editors vocabulary supports some new features:

Undo and redo (Control-z, Control-Shift-z)
Join lines (Control-j)
Character and word navigation now uses unicode.breaks

Table gadget replaces list gadget

The ui.gadgets.tables vocabulary implements a new gadget which is a replacement for the old list gadget. It's functionality is a superset of what lists offered. Tables are used extensively by the new developer tools to display completion popups and such. Unlike lists, which would create a gadget for every row of data, tables do not have any children and render rows directly. This reduces memory consumption. Tables take the list of rows from an underlying model, and place the currently selected row in another model. The latter model can then be wrapped in an arrow model to compute a new list of rows, which can then be the model for another table. This way, multiple tables can be chained together for a 'drill down navigation'-style of interaction with very little code.

Scroller gadget improvements

Scroller gadgets, defined in the ui.gadgets.scrollers vocabulary, now provide a protocol that their children can implement. This protocol has two generic words:

viewport-pref-dim - this allows the child to specify the preferred dimensions of the scroller surrounding the gadget. Tables and editors implement this generic word, allowing you to set various slots, such as min-rows and max-rows, which control the size of the scroller surrounding the gadget in character units.
viewport-column-header - constructs a gadget which is displayed at the top of the scroller. This allows the table gadget to display column titles which are always visible, regardless of the vertical scroll position.

Frame layout improvements

The ui.gadgets.frames vocabulary is more flexible now. Instead of limiting frame layouts to a 3x3 grid with the center item stretched to fill available space, the grid can be of any size, and an arbitrary cell can be designated to take up available space.

Models API changes

The models vocabulary has undergone some cleanups. To avoid confusion with sequence functionality, filter models are now called arrow models. Compose models are now called product models, since really they represent a cartesian product of functions, not a composition of anything at all. The new models.arrow.smart vocabulary wrap an arrow around a product whose arity is the arity of the arrow's quotation.

Integration between event loop and I/O

Until Factor supports real native threads, any FFI call blocks all Factor threads until the call completes. I/O is done with non-blocking APIs on Unix (epoll, kqueue) and Windows (IO completion ports), so socket operations can proceed concurrently. However, until recently, the UI would have to poll for events because of this, because blocking calls to wait for events would prevent I/O and other Factor threads from running. This meant that even if you weren't doing anything in the Factor UI, it would use a little bit of CPU - 5% to 25%. This problem has been fixed. On Mac OS X, I use the CFFileDescriptor API to wait on a kqueue and GUI events at the same time; you can provide a callback which is invoked when file descriptors are ready for I/O, and call [NSApplication run] as usual. On X11, I use XConnectionNumber() to get a file descriptor out of a Display and call wait-for-fd to wait for events to arrive while also allowing other Factor threads to run. This solves the CPU usage problem and allows Factor threads to run concurrently with the event loop waiting for events.

Improvements to tooling

The main focus of my recent UI work, however, has been on improving UI developer tools. I plan on making a screencast to highlight the new improvements soon.

OpenGL textures and the power-of-two size restriction

2009-04-08T03:21:00.004-04:00

Prior to version 2.0, the OpenGL specification required that texture dimensions be powers of two. This simplifies the implementation of texture mapping, because converting floating point texture co-ordinates (which are in the range 0..1) to texel coordinates is trivial; multiplying a floating point number by a power of two is essentially just adding a number to the exponent. Eventually, more capable drivers and graphics cards came along, and introduced the ability to use non-power-of-two texture dimensions. To signal this capability to GL applications, they report supporting the GL_ARGB_texture_non_power_of_two extension. OpenGL 2.0 implementations are required to support this extension.

In practice, the only major OpenGL implementations which don't provide this extension are older X11 drivers, and the Microsoft Windows software renderer, which is a very bare-bones OpenGL 1.1 implementation.

There is a trick for padding textures up to a power of two for implementations which don't support this extension, however it doesn't seem to work everywhere either. Instead of manipulating the bitmap in software before passing it onto a call to glTexImage2D(), it is permissible as of OpenGL 1.1 to pass a bitmap pointer of NULL. This creates a texture with uninitialized content. The glTexSubImage2D() function is used to fill it portions of the new texture. In particular, glTexSubImage2D() places no restriction on the width and height, even if GL_ARGB_texture_non_power_of_two is not supported.

The above trick works with the Windows software renderer. On the other hand, previous-generation MacBooks with Intel graphics suffer from a driver bug which results in artifacts appearing when this feature is used to render scaled textures. However, all OpenGL implementations in recent Mac OS X releases support non-power-of-2 textures, so on this platform, the workaround can be avoided entirely anyway.

In Factor, the opengl.capabilities vocabulary provides some utility words to check for extensions. For example, a common operation is checking for either a specific OpenGL version, or an extension (new versions of the GL spec frequently absorb existing extensions):

"2.0" { "GL_ARB_texture_non_power_of_two" } has-gl-version-or-extensions?

The gl-extensions word outputs a sequence of all supported extensions. Here is the output from the Mesa software renderer on Linux.

I replaced my old code in opengl.textures which padded bitmap image objects out to powers of two using sequence manipulation words, with the new way using texture sub-images instead. If the extension is present, no padding is performed, ensuring correct behavior on Mac OS X. This means that any code using opengl.textures, such as the UI's text rendering and image support, should now spend less CPU time running Factor code.

Factor's OpenGL binding has been in development for 4 years and has seen contribution from 4 developers. For a demo of what it can do, try "spheres" run in the UI listener. You will need a video driver that supports OpenGL 2.0 or GL_ARB_shader_objects.

Rendering text on Windows via Uniscribe

2009-04-07T00:33:00.003-04:00

My original goal was to use Pango to render Unicode text in the Factor UI on Windows. This didn't pan out, for a number of reasons:

Pango, Cairo and all of their dependencies add up to around 7Mb of DLLs that we'd need to ship with every Factor binary, as well as every standalone app binary deployed from Factor. That's too much when a 'Hello world' compiles down to a 500kb image.
Pango has various bugs on 64-bit Windows.
Pango doesn't play well with Microsoft's ClearType, and anti-aliased text is clipped for some reason.

I'm sure these problems will get fixed eventually (except for the first one perhaps) and Pango is open source so I could always send a patch, but I'd rather spend my time working on interesting things instead, so I've decided to bypass Pango on Windows altogether and use Microsoft's native Uniscribe API instead. Uniscribe ships as a standard part of Windows XP (actually it's been around since IE 5.0) and so Factor can depend on it being installed. On X11, I continue to use Pango; most *nix systems have at least part of the GNOME platform installed, so Pango and Cairo will be there, and I haven't seen any rendering issues in Pango with X11 either.

I'm using the Uniscribe script string API, which is intended to be used for laying out and rendering a piece of text with a single font and color. It is directly analogous to CTLine in Core Text and PangoLayout in Pango.

The function to create a script string, ScriptStringAnalyze, takes a device context handle as a parameter. The device context must be provided if the string is going to be rendered or measured.

Before creating the string, the font and text color are set in the device content. To set the font, I look up a font handle with CreateFont, and pass it to the SelectObject() function. There's an important caveat with CreateFont(); if you want your font size to be specified in points (rather than pixels), you must pass a negative size. I noticed that 12-point font was rendered way too small; changing the 12 to a -12 fixed the problem, so now the Factor UI does this for you on Windows.

The text color is set by calling SetTextColor, and the background color (which is only rendered if a flag is passed to ScriptStringOut(); see below) with SetBkColor.

For both fonts and colors, the Uniscribe text rendering uses Factor's cross-platform font and color types.

Size measurement is done by calling ScriptString_pSize(). Unlike Core Text and Pango, Windows Uniscribe makes no distinction between metric and ink bounds. There is a provision for oversize glyphs, such as those in the Zapfino font (see my blog post on ink and metric bounds), where each glyph has an associated ABC metrics structure. I'll implement support for this later.

When rendering to an offscreen context that is intended to be used as an OpenGL texture, as in the Factor UI, a bit of a chicken-and-egg problem occurs, because we need to know the size of the resulting text before we can create a bitmap. Fortunately, Windows GDI separates the process of creating a memory (off-screen) DC and allocating the bitmap storage for it, into two functions, CreateCompatibleDC() and CreateDIBSection(). The trick is to create a DC, create a script string, get its size, then allocate the bitmap for the DC, and finally render the string.

Script strings can be rendered to their underlying DC with the ScriptStringOut function. This function takes a number of parameters. For instance, it can render the text selection for you.

Font metrics -- the ascent, descent, and leading -- can be obtained by calling GetTextMetrics() on the DC.

Once the text has been rendered into a memory DC, the underlying bitmap needs to be obtained and the graphics object handles freed. This is the third time I implement a similar-looking make-bitmap-image combinator, so by now I've developed some utilities that I've abstracted out into the images.memory vocabulary. The bitmap is cached as a texture in the same way on all platforms; I've discussed OpenGL texture caching before.

Converting between x co-ordinates and line offsets, and vice versa, can be done with ScriptStringXToCP() and ScriptStringCpToX(). Watch out for the fact that passing the length of the string to ScriptStringCpToX() is invalid; if you want the X-offset of the trailing edge of the last code point, you have to pass length-1 instead, with the fTrailing parameter TRUE.

Finally, script strings are freed by calling ScriptStringFree(). When binding to the API from another language, watch out for the type of the input parameter; it's a pointer to a SCRIPT_STRING_ANALYSIS type, which is itself a pointer type. So you're passing a pointer to a pointer to a struct! I got the type wrong in my FFI declaration the first time around and was getting segfaults when deallocating stuff. Very annoying.

The code implementing this is split between four vocabularies:

windows.offscreen - support code for creating GDI memory DCs. Originally written by Joe Groff for another purpose; I've generalized it and put it in a common location so that it can be used by both the Uniscribe code and offscreen gadget rendering.
windows.fonts - looking up GDI font handles from Factor font descriptions
windows.uniscribe - the bulk of the code; creating, rendering script strings, converting x co-ordinates to line offsets and vice versa
ui.text.uniscribe - a backend for the UI's cross-platform text rendering support. Just a thin shim over the preceding vocabularies.

Here is what it looks like when all is said and done:

Factor: a practical stack language

Factor 0.94 now available

Incompatible changes:

New libraries:

Improved libraries:

Compiler improvements:

Miscellaneous improvements:

An overview of Factor's I/O library

First example: converting a text file from MacRoman to UTF8

Converting a directory full of files from MacRoman to UTF8

An aside: generalizing the "current working directory"

Checking free disk space

Unix only: symbolic links

File system monitoring

Memory mapped files

Launching processes

Unix only: file ownership and permissions

Networking

Network servers

Under the hood

Making Factor's continuous build system more robust

Checking for disk space

Git repository corruption

Error e-mail throttling

More robust new code check

Build system dashboard

Conclusion

Two things every Unix developer should know

Interruptible system calls

Subprocesses inherit semi-random things from the parent process

Overhauling Factor's C library interface

The previous FFI implementation

Factoring FFI calls into simpler instructions

GC maps

Callback support improvements

Factor talk in Boston, July 26th

Comparing Factor's performance against V8, LuaJIT, SBCL, and CPython

Language implementations

Benchmark implementations

Running the benchmarks

Benchmark results

Benchmark analysis

Conclusions

A collection of small compiler improvements

Improvements to value numbering

Optimistic copy propagation

Representation selection improvements

Register allocator improvements

Compiler code cleanups

A bug fix for alias analysis

Instruction scheduling to reduce register pressure

Some benchmarks

Factor 0.93 now available

Incompatible changes:

New features:

Frame-based structured exception handling on Windows x86-64

Switching call stacks on different platforms

System APIs for switching call stacks

High-level libraries for switching call stacks

NetBSD/x86 limitation

Windows-specific concerns

The TIB

Structured exception handlers

Accessing the TIB

Sample code for updating Windows-specific structures

Incompatible change in Mach exception handler behavior on Mac OS X 10.6

Adding a recaptcha to the Factor pastebin

Final classes and platform-specific vocabularies

Final classes

Typed words can now be declared foldable and flushable

Platform-specific vocabularies

Factor 0.92 now available

Language improvements

Notable new libraries

Implementation improvements

Editor integration

Replacing GNU assembler with Factor code

Factor platform ABI

Replacing the c_to_factor() entry point

Replacing the throw_impl() entry point

Replacing the `c_to_factor()` entry point

Replacing the `throw_impl()` entry point

Replacing the `lazy_jit_compile_impl()` and `set_callstack()`entry points

Inline assembly with the `alien-assembly` combinator