Monday, November 26, 2007

Cross-platform Factor Install Script

Recently, I wrote an installer/updater bash script that downloads the git repository, compiles, and bootstraps Factor. On Linux, it compiles Factor for console-only if any of the libraries required for the graphical interface are missing (freetype, GL, GLU, X11).

To install Factor to a directory: ./factor.sh install
To update your Factor repository: ./misc/factor.sh update

The script source code is available for browsing or for download.

Tested on Windows XP/Vista in Cygwin, Debian and Ubuntu Linux, and Mac OS X.

Please send bug reports and improvements. Thanks!

Sunday, November 18, 2007

Where's my Raptor!??

My Macbook's dock displayed the default icon instead of a raptor. The fix was to move the move the .app directory to another name, then to move it back. Now I have a raptor!

Does 10.4 do some caching? It probably had it cached wrong since we got the new icon.

Wednesday, November 07, 2007

Doubly-linked Lists, Queues, and Heaps

Doubly-linked Lists and Queues


Factor has had doubly-linked lists for years now, but they were not well-documented or polished. Now, they're documented and have replaced the queues library.

An example of a dlist usage:
<dlist> "red" over push-front "blue" over push-front dup pop-back .
"red"


You can add/remove nodes of a dlist with push-front, push-back, pop-front, pop-back, delete-node, and search with dlist-find, dlist-contains?.

Finding the length of a dlist is O(1) since it stores the length as dlist-length, a tuple slot.

Heaps


Heaps have been updated to allow for <min-heap> and <max-heap> data structures. Adding elements to a heap is achieved with heap-push ( value key heap -- ), while popping elements is heap-pop ( heap -- value key ).

Factor's green threads implementation had been using a hack for the sleep-queue: each time a new entry was added it would modify a non-growable array, which would then be sorted by the smallest timeout. Adding a sequence of sleep continuations would take O(n^2 log n) time! Running 10000 [ [ 100 sleep ] in-thread ] times should spawn 10000 threads and sleep for 100 ms in each one, and with the old sleep-queue implementation it takes over a minute on my Macbook. Now it's just O(n log n), which takes a second or two.