Monday, November 28, 2005

New hashtable implementation brings 400kb reduction in image size

I put Factoroids aside for now. I got it in a further state than shown in the screenshot, but I wanted to return to Factor hacking.

I reimplemented the hashtable to use open addressing instead of bucket chaining. With bucket chaining, the hashtable is backed by an array of buckets; keys are sorted by hashcode into buckets, where each bucket is an association list. With open addressing, the hashcode determines the starting index in the array; if the index is occupied by another key, the next index is searched, and so on.

On a 32-bit system, the old implementation, each key/value pair stored in a hashtable required two cons cells -- that's 16 bytes -- and each bucket required 4 bytes of storage. Since the number of buckets was kept at roughly the same as the number of key/value pairs, that is 20 bytes per hashtable entry. With the new implementation, a hashtable entry is just a pair of consecutive array elements -- 8 bytes. The underlying arrays are kept larger than before, so the end result is a savings of not quite 12 bytes per key/value pair, but enough to reduce the image size by 400Kb, and the time to do a full garbage collection by 10ms (on a 1.25 Ghz PowerPC G4).

There were some changes to the hashtable words as a result.

hash* ( key hash -- [[ key value ]] ) is now hash* ( key hash -- value ? ). Unlike hash ( key hash -- value ), this word can detect the difference between a value of f, and a key that is not present at all. However, the old stack effect was not only clumsy -- most callers would call cdr on it after checking if it is not f; but it makes no sense with the new implementation, and would require allocating a cons cell. So the new implementation returns the value, but also pushes a boolean that denotes if the key is in the hashtable.

Along similar lines, the hashtable combinators that would formely pass a cons holding a key/value pair to their quotation now pass the key and value separately on the stack:

Also, association lists are, for all intents and purposes, gone. An association list is a list of cons cells where the car is a key and the cdr is a value. They were used in a few places as "lighter weight" mappings than hashes. However, now there's no reason to use them anymore. This means the following words are now gone:

One final change is the literal syntax. Here is the new syntax:
{ "garlic bread" "appetizer" }
{ "steak" "main" }
{ "ice cream" "desert" }

The difference is that key/value pairs are entered with { ... } syntax, not [[ ... ]]. I always thought the old syntax looked kind of cluttered, and now the reason to use cons cells here is gone.

The other thing I've worked on lately is fixing some compiler bugs; one that was reported recently, and a handful of long-standing ones. All of them turned out to be related by a common thread: inlined recursive words. This is always tricky because the compiler must take care to note which values remain constant between recursive calls, and which do not. While the idea is simple there are a lot of tricky details, and we had a number of problems where values would be assumed to be literal when they were not, resulting in inappropriate optimizations being performed.

In other news, I now have an dual core AMD64 machine. I will begin porting Factor to this architecture very soon. I know a few people have been looking forward to running Factor on their AMD64 machines, and I hope to make them happy.

Tuesday, November 15, 2005

Working on a 3D game in Factor

I started work on Factor 0.80 in CVS, but decided to take a break from working on the Factor core, and instead, try writing a 3D game! I only did a few hours hacking on it so far, just fleshing out the bare necessities of a game engine. Here is what I have so far; you can move the player around the rather dull-looking world, and shoot projectiles which fly off into the distance:

Sunday, November 06, 2005

Factor 0.79 released

Factor 0.79 is now out after two months of development.
  • Incompatible changes:
    • The ifte combinator has been renamed to if.
    • Syntax changes:

      { 1 2 3 } ! arrays
      V{ 1 2 3 } ! vectors
      H{ [[ key value ]] ... } ! hashtables
      C{ 1.02 -7.44 } ! complex numbers
      T{ class slots ... } ! tuple
  • Compiler:
    • New basic block optimizer performs more aggressive dead load and store elimination.
    • Stack shuffles are compiled more efficiently.
    • Pushing literals on either side of a stack shuffle is now compiled more efficiently.
    • Fixed a problem with relocation of compiled code on PowerPC.
    • Fixed various FFI issues on Mac OS X.
  • User interface:
    • Graphics rendering is now done using OpenGL and text rendering is done via FreeType. SDL_gfx and SDL_ttf libraries are no longer required.
    • Added expandable outliners. Used by the inspector, .s, usage., uses., vocabs., and various other words.
    • Added word completion to the listener pane; press TAB.
    • Added word navigation shortcuts to the listener pane; press C+LEFT and C+RIGHT to move a word at a time, and C+BACKSPACE and C+DELETE to delete the previous and next word, respectively.
    • Added mouse-over help for presentations.
    • Previously-entered output is now clickable in the listener.
    • New, better-looking widget theme.
  • Collections:
    • Faster map, 2each and 2map.
    • Arrays are now better supported and should be used instead of vectors where resizing is not desired.
    • Some new sequence words that do not bounds check: nth-unsafe and set-nth-unsafe. These should only be used in special circumstances, such as inner loops (each, map and so on use them).
    • New replace-slice ( new from to seq -- seq ) word replaces a slice of a sequence with another sequence.
    • Hashtables did not obey the rule that equal objects must have equal hashcodes, so using hashtables as hashtable keys did not work.
    • New mismatch ( seq seq -- i ) word returns first index where two sequences differ, or -1 if they have equal elements.
    • New drop-prefix ( seq seq -- seq seq ) word returns a pair of sequences which have the same elements as the two input sequences, with the common prefix removed.
  • Everything else:
    • On Mac OS X, signal 11 errors caused by stack under/overflow no longer trigger the OS X crash reporter dialog.
    • Easier exception handling. The cleanup ( try cleanup -- ) word encapsulates the following idiom:

      [ A ] [ B rethrow ] catch
      [ A ] [ B ] cleanup
      The recover ( try recover -- ) word encapsulates the following idiom:

      [ A ] [ [ B ] when* ] catch
      [ A ] [ B ] recover
      The catch ( try -- error/f ) word no longer takes a quotation that receives the error caught; rather, it just pushes the error that was caught on the stack. That is, the old way:

      [ A ] [ B ] catch

      [ A ] catch B
      However, most uses of catch can be replaced by cleanup and recover.
    • The distinct t type is gone. Now, the t object is just a symbol.
    • A new with-server ( port ident quot -- ) combinator takes care of listening on a network socket, logging client connections, spawning client handler threads, and error handling. The quotation is called for each client, in a new scope with the client socket as the default stream.
    • New 1+, 1- words are a bit faster than 1 + and 1 - since there is one less generic dispatch involved.
    • On Windows, FFI errors would raise a signal 11 instead of reporting a nice message.
  • Contributed code:
    • The HTTP server and client has been moved from library/httpd/ to library/contrib/.
    • Intel 8080 CPU and Space Invaders emulator in contrib/space-invaders (Chris Double)
    • AOL Instant Messenger chat client library in contrib/aim (Doug Coleman)
    • Cairo graphics library binding in contrib/cairo. (Sampo Vuori)
    • Advanced math library with quaternions, matrices, polynomials, statistics and various functions in contrib/math/. (Doug Coleman)
    • Dimensioned units in contrib/units/. (Doug Coleman)
    • X11 binding in contrib/x11/ (Eduardo Cavazos)