Irate Nate's weblog

treehouse

Fri, 02 May 2008 21:07:00 CDT

John Derbyshire of National Review fame and some excellent mathematics histories (I guess that's what you'd call them) built a treehouse for his children, documenting the process in prose and photos. I always wanted a treehouse when I was little, but I never thought about how much work it'd be to actually put one together. Maybe if we plant a tree in our new house, my grandchildren can have a treehouse...

young programmers

Wed, 30 Apr 2008 14:52:00 CDT

Everybody in the family except myself seems to be somewhat sick lately, so I have been taking a chunk of time off each day this week to assist with care. Yesterday that involved playing Duplos with Becca while Tricia and Ally slept. We built a Duplo car that was roughly the size of a good-size U-Haul moving van...strapped onto the chassis of a Honda Civic. As part of its accoutrements, it featured a house in the back for one of the Duplo animals she owns (the lion, in this case).

Becca also decided that there needed to be a computer on the roof of the car. She sat down one of her little Duplo men in from of the computer, prompting the question from me, “What's the Duplo man doing, Becca?” Her response: “Oh, he's just writing...he's just writing GCC.” She is her father's daughter.

library thing meme

Tue, 29 Apr 2008 22:09:00 CDT

(via Zack Weinberg and bitbashing)

What we have here is the top 106 books most often marked as “unread” by LibraryThing's users. As in, they sit on the shelf to make you look smart or well-rounded. Bold the ones you've read, underline the ones you read for school, italicize the ones you started but didn't finish. Add (*) beside the ones you liked and would (or did) read again or recommend. Even if you read 'em for school in the first place.

Jonathan Strange & Mr Norrell
Anna Karenina
Crime and Punishment
Catch-22*
One Hundred Years of Solitude
Wuthering Heights
The Silmarillion
Life of Pi
The Name of the Rose*
Don Quixote
Moby Dick
Ulysses
Madame Bovary
The Odyssey
Pride and Prejudice
Jane Eyre
The Tale of Two Cities
The Brothers Karamazov
Guns, Germs, and Steel: the fates of human societies
War and Peace
Vanity Fair
The Time Traveler's Wife
The Iliad
Emma
The Blind Assassin
The Kite Runner
Mrs. Dalloway
Great Expectations
American Gods
A Heartbreaking Work of Staggering Genius
Atlas Shrugged
Reading Lolita in Tehran : a memoir in books
Memoirs of a Geisha
Middlesex
Quicksilver*
Wicked : the life and times of the wicked witch of the West
The Canterbury Tales
The Historian : a novel
A Portrait of the Artist as a Young Man
Love in the Time of Cholera
Brave New World
The Fountainhead
Foucault's Pendulum
Middlemarch
Frankenstein
The Count of Monte Cristo
Dracula
A Clockwork Orange
Anansi Boys
The Once and Future King
The Grapes of Wrath
The Poisonwood Bible : a novel
1984
Angels & Demons
The Inferno (and Purgatory and Paradise)
The Satanic Verses
Sense and Sensibility
The Picture of Dorian Gray
Mansfield Park
One Flew Over the Cuckoo's Nest*
To the Lighthouse
Tess of the D'Urbervilles
Oliver Twist
Gulliver's Travels
Les Miserables
The Corrections
The Amazing Adventures of Kavalier and Clay
The Curious Incident of the Dog in the Night-Time
Dune
The Prince
The Sound and the Fury
Angela's Ashes : a memoir
The God of Small Things
A People's History of the United States : 1492-present
Cryptonomicon*
Neverwhere
A Confederacy of Dunces
A Short History of Nearly Everything
Dubliners
The Unbearable Lightness of Being
Beloved
Slaughterhouse-five
The Scarlet Letter
Eats, Shoots & Leaves
The Mists of Avalon
Oryx and Crake : a novel
Collapse : how societies choose to fail or succeed
Cloud Atlas
The Confusion
Lolita
Persuasion*
Northanger Abbey
The Catcher in the Rye
On the Road
The Hunchback of Notre Dame
Freakonomics : a rogue economist explores the hidden side of everything
Zen and the Art of Motorcycle Maintenance : an inquiry into values*
The Aeneid
Watership Down
Gravity's Rainbow
The Hobbit*
In Cold Blood : a true account of a multiple murder and its consequences
White Teeth
Treasure Island
David Copperfield
The Three Musketeers

I'm too lazy to underline the ones I read for school. (Most of the not-published-the-last-fifty-years ones, though.) I need to work on my classic literature.

home safety announcement

Sat, 26 Apr 2008 12:25:00 CDT

Pro tip: when attempting to determine if a burner on the stove was previously being using for cooking, do not lay your hand flat on the burner to test its temperature. Instead, hover your hand slightly above the burner to check for radiant heat. It's amazing how even a small number of pain points on the inside of your fingers can make doing simple tasks uncomfortable.

shadow and claw

Wed, 23 Apr 2008 23:33:00 CDT

Mom and Dad D bought me Gene Wolfe's The Book of the New Sun quadrilogy for my birthday this year. I read the first three by checking them out from the library last year, but was cruelly stymied from reading the conclusion because the library didn't have it. (They had virtually every other Gene Wolfe book...except The Citadel of the Autarch...go figure.) I'm rereading it right now, enjoying it just as much, but not perceiving the depth I've heard other people attribute to the series. I must say, though, that the stories Severian reads from Thecla's books are worth the price of admission just by themselves.

mortgage payments

Wed, 23 Apr 2008 23:31:00 CDT

One down. Three hundred and fifty-nine to go. (Well, really more like two hundred and seventy-five if we can accelerate our payment schedule a bit, as our lawyer never tired of reminding us.)

hugs from ally

Tue, 08 Apr 2008 00:40:00 CDT

We drove to see my grandmother this past Saturday. While we know she loves to see us, doing so makes for a long day--about eight hours on the road. Sometimes the girls sleep in the car, sometimes they don't. Today was one of the days where they--especially Ally--choose not to, and it made for a bit of a long day. Tricia did a great job entertaining the girls in the backseat of the car today: singing with them, reading with them, reasoning with a tired 2.5-year old about singing songs and not playing with her sister's sunshade while her sister was sleeping for ever-so-briefly, etc.

Saturdays are bath nights in the Froyd household. Despite getting home late and thinking it would not be a good time to attempt a bath, Tricia suggested filling up the tub for Becca just a little bit and letting her splash around before going to bed. I did this and Becca climbed in and began cheerfully pouring water back and forth between containers. Tricia went to get Ally ready for bed and I stepped out to get a glass of water.

When I came back into the bathroom, Tricia was standing there with Ally in her PJs. Before I explain what happened next, y'all ought to know that I am not Ally's favorite parent. Tricia insists that this is only because I don't have breasts and therefore don't provide the “mommy milk,” but I sometimes suspect it goes deeper than that. Every once in a while, however, Ally does something that indicates she does appreciate having her father around. Tonight provided just such an occasion.

I walked up to Tricia and began talking to Ally a little bit. Ally unwrapped herself from Tricia and leaned forward: this is her way of indicating that she's willing to be passed off. Usually I need to hold my hands out to her before she will lean forward. But hey, I'll take whatever daughter adoration I can get, so I held out my hands and held her upright against me with one arm.

Ally then laid her head down on my shoulder, which is out of character for her, especially when Mommy is around. She usually has this “up-periscope” sort of posture that is focused on ascertaining Mommy's location and distance to Mommy. If she is within range and it does not appear that Mommy is making a move in her direction, she activates her Mommy Proximity Alarm (MPA) to indicate her displeasure with this state of affairs. Again, I'll take whatever daughter adoration I can get.

What happened next, though, totally surprised me. She popped up, looked at me, and reached her hand up to stroke the side of my face. She then leaned in and gave me a kiss right on my mouth! She has “given kisses” before, but that involved her leaning her head forward until her forehead made contact with some part of your face; this was much different. It didn't seem accidental, but very deliberate, especially because we think the head-on-shoulder bit was “hugging” me and we talking about Becca and Daddy giving Mommy and Ally hugs and kisses before Ally gets put down for bed each night.

Tricia and I started laughing and I had a few tears sliding down my check from this unexpected outpouring of affection from my daughter. I think we must have freaked Ally out somehow, because she was ready--not upset, just ready--to go back to the safety of Mommy shortly thereafter. And she refused to do any sort of repeat performance before Tricia had to put her to bed. Hopefully we didn't indicate that this was undesired behavior. Her little gestures totally made my day.

something substantial

Wed, 19 Mar 2008 21:18:00 CDT

In which several things are combined to make them appear more substantial:

Tiona Marco: Creating fine art with Crayola crayons.

I read Persuasion by Jane Austen last Saturday morning while lying sick in bed. Recommended. One cannot help but feel a sense of disgust when the story moves Anne back to her family at Bath.

We received notice at work this week that after four years, we get a month to do anything we want that is “loosely related” to the mission of the company. It's not Google's 20% time, but it's a nice perk. I am already plotting what to do when my time rolls around in early 2011...

Thought on discourse: one often labels a critique as “devastating” not because it possesses such a destructive force, but merely because it happens to align with the opinion of the labeler and assures the labeler than he will not need to interact with the critiqued. It works in the opposite direction too: one labels a blunder or misstep of one's opponent “devastating” in hopes the opponent will be marginalized or go away altogether.

new trees release

Wed, 19 Mar 2008 20:44:00 CDT

Long ago, when I was still tweaking my blog software, I decided I wanted to eschew databases. Instead, I wrote a simple binary tree package for an in-memory database of sorts (my blog was getting to large to deal with linear lists and I wanted things sorted by date at the very least). It worked for me and didn't seem to erase my hard drive, so I released it to the world as TREES. I marveled at my contribution to Lisp software.

However, over the years, bug reports came trickling in, mostly saying, “Hey, I tried AVL trees and deleting elements from AVL trees goes into an infinite loop.” Like a negligent maintainer, I paid little attention to the reports, as I used red-black trees and they Worked For Me (tm). Not the greatest contribution to Lisp, eh?

I recently decided that life is too short to have buggy software with one's name floating around. Over the past month or so, I have been rewriting TREES and released version 0.10 yesterday, with improved interfaces, more efficient code, and a real testsuite. I thought I'd share a few lessons from my grand rewrite:

Follow established Common Lisp conventions. Erik Naggum wrote a post about this sort of thing a while back, and I have tried to follow his suggestions. But I also applied existing conventions in other ways too: the lambda list for making a binary tree prior to the rewrite was something ugly like (tree-kind &key compfun eqfun keyfun). After thinking about established convention and how binary trees really work, it's now (tree-kind pred &key key test), which seems more obvious to my mind, as well as saying, “an ordering for binary trees is not an optional feature.”
Also, if you're going to write DO-style macros, make sure the body is surrounded by tagbody. I learned about this nifty feature recently--that one can place go tags in the body of such macros and use them to implement things like C's continue. Very handy.
Randomized testing is a good thing. I built several million random trees of varying sizes while testing the whole thing and doing so quickly ferreted out bugs in my initial implementations. In later stages, I'd leave my computer churning away overnight to ensure I hadn't broken anything.
As a corollary, make sure you have some way of replaying the building of a randomized thing so you can debug your code when things go pear-shaped.
I discovered a practical use for non-standard method combinations: I implemented a VALIDATE-TREE function that checks invariants for different kinds of binary trees. But when checking, say, the invariants applying to an AVL tree, one should also check the invariants applying to basic binary trees, preferably without code duplication. Solution? An AND method combination: both the basic- and AVL-specific methods get run and their return values are combined for you.
Profile your test suite. The faster your test suite goes, the more testing you can do--especially when doing randomized testing. I sped my tests (at an early stage) up by a factor of 30 after profiling. A quirk in how SBCL implements type declarations for WITH clauses in loop inspired me to rewrite how I kept track of some things in my testing, leading to a ~20x speedup. And using (lambda (x y) (< x y)) is faster than (function <) when you know you're going to be dealing with fixnum data; that SBCL-specific tweak lead to another factor of ~1.5x.
In the same vein: structures are faster than classes. Really. I knew this already, but I didn't have a good feel for how much those accesses-as-function calls cost me. Tests sped up by ~20% when I reimplemented the tree nodes as structures rather than classes. I'm still on the fence whether to reimplement the tree objects themselves as structures.
Functional programming can be a great substitute for generic programming. The previous version of TREES tried to be too clever, handling insertion into an empty tree as a special case and delegating a good chunk of work to a method called TREE-INSERT-NONEMPTY or somesuch, which handled rebalancing. A similar tack was done for deletion. I didn't understand my intentions for TREE-INSERT-NONEMPTY after coming back to the code, so I started cutting and pasting, hoping idioms would jump out at me after I had done two or three binary tree variants.
And they did. What emerged was having generic code handle insertion and deletion and then called a passed-in function to handle rebalancing. It's quite a bit cleaner and more understandable than doing things with methods, in my opinion.

I still have things to fix; I took out DO-TREE-RANGE and WITH-TREE-ITERATOR because my code didn't need them, but they should probably go back in--especially WITH-TREE-ITERATOR. But I wanted to get the code out the door; two years between releases is long enough!

name of the rose

Fri, 14 Mar 2008 06:49:00 CDT

I finished Umberto Eco's The Name of the Rose last weekend. The book is one of the best justifications for learning Latin that exists. (While the book is perfectly readable without knowing Latin, I think it would have illuminated the story at a few points if I actually did.) It's also one heck of a story, too.

wheat chex

Thu, 06 Mar 2008 12:25:00 CDT

Does anybody purchase Wheat Chex for anything besides including them in Chex Mix?

christian academics

Wed, 27 Feb 2008 14:02:00 CDT

What does faithfully executing your work as a Christian mean? At least in the academic world, it looks something like this:

Oddly, the most objective History of Philosophy I've ever read, and it's a big one, is Frederick Copleston's. It's a nine volume thing, about 4,000 pages in all, but it's also a blast. Plus, there was lots of remedial stuff that, even after I got by B.A. in Philosophy, I really didn't have a handle on, and I feel that Copleston is really great refresher training as well. Ironically, for Russell, Copleston was an Orthodox Catholic, almost personally a Fundamentalist, and so it is odd, even bizarre that such a source, which would seemingly be the most unobjective, really does a wondrous job.
And on people Copleston disagrees with, he does so with a phenominal fairness. In fact, the people he disagrees with, you can tell he made an extra effort to be very careful to represent those views as the people putting them forward really intended.
So, although I am a die-hard Agnostic who believes that Copleston's Catholic Orthodoxy is pure silliness, amazingly, I must say that his ability to portray other philosophers in a way that is true to those philosphers in question, is almost uncanny, really sheer genius. That being said, probably Russell had a higher I.Q., and that may have gotten in his way with his particular History project...

The shot at the end is quite unnecessary, however. The sheer bewilderment of this reviewer that this Orthodox Catholic could improve upon Betrand Russell is a response worth striving for.

gossie

Sun, 24 Feb 2008 16:48:00 CDT

We picked up Gossie at the bookstore last weekend. which is a truly delightful children's book. How much do we like it? I went online looking for prints of some of the pages--pages in which joy leaps directly from page to eyeballs to neurons--the same night we bought it. We also immediately added every other book by the same author to our Froyd family wishlist on Amazon. And we have read the book at least 20 or 30 times since purchasing it, so much so that Becca has both it and the sequel--given to her Thursday evening by her grandparents and read numerous times since--memorized, as evidenced by her reciting them to her sister for entertainment this morning. Highly recommended.

In the book, there are two facing pages talking about what Gossie likes to do: “She walks backwards.” and “She walks forwards.” The pictures depict her walking to the left and walking to the right, respectively. And that made me wonder: would translations of Gossie in right-to-left languages like Hebrew flip the illustrations so she would be walking to the right for backwards and to the left for forwards?

calvin's prayers

Sun, 24 Feb 2008 16:38:00 CDT

I have been taking a break from WoW this Lenten season and using that time I would normally be slaying pixelated monsters to read. One of the things I have been reading is Calvin's commentaries on the Old Testament, specifically the minor prophets. I have enjoyed Calvin, especially the realization that Calvin did deal with historical and textual issues; his commentaries are not simply florid prose. But I have enjoyed at least as much the prayers that punctuate sections of the commentaries. Consider this one:

Grant, Almighty God, that, since to a perverse, and in every way a rebellious people, thou didst formerly show so much grace, as to exhort them continually to repentance, and to stretch forth thy hand to them by thy Prophets,--O grant, that the same word may sound in our ears; and when we do not immediately profit by thy teaching, O cast us not away, but, by thy Spirit, so subdue all our thoughts and affections, that we, being humbled, may give glory to thy majesty, such as is due to thee, and that, being allured by thy paternal favour, we may submit ourselves to thee, and, at the same time, embrace that mercy which thou offerest and presentest to us in Christ, that we may not doubt but thou wilt be a Father to us, until we shall at length enjoy that eternal inheritance, which has been obtained for us by the blood of thine only-begotten Son. Amen.

Or this one:

Grant, Almighty God, that since we cannot otherwise really profit by thy word, than by having all our thoughts and affections subjected to thee, and offered to thee as a sacrifice,--O grant, that we may suffer thee, by the sound of thy word, so topierce through every thing within us, that being dead in ourselves, we may live to thee, and never suffere flatteries to become our ruin, but that we may, on the contrary, patiently endure reproofs, however bitter they may be, only let them serve to us as medicine, by whcih our inward vices may be cleansed, until at length being thoroughly cleansed and formed into new creatures, we may, by a pious and holy life, really glorify thy name, and be received into that celestial glory, which has been purchased for us by the blood of thy only-begotten Son, our Lord Jesus Christ.

new ironclad release

Sun, 24 Feb 2008 16:30:00 CDT

Ironclad 0.25 is out and available from the usual place. There are a few optimizations suggested by Attila Lendvai, and corrections for two thinkos: CRC32 was bugged and the testsuite wasn't included (it works perfectly, I promise...). Thanks to Todd Sabin and Peter Graves, respectively, for pointing out those flaws.

Also, somebody suggested a long time ago that it would be nice if Ironclad included a “dummy” cipher that did nothing. (It might have been a simple XOR cipher, actually; I do not remember.) I thought that seemed like a silly idea at the time, but have since come to think that having such a cipher would be useful in real-world cases. So Ironclad now includes the NULL block cipher, which--at least in ECB mode--copies its input to its output unmodified. Enjoy!

linkage

Mon, 18 Feb 2008 21:06:00 CDT

Boy, there are some times I miss watching TV.

Stuff White People Like. Like assists:

White people love to pass, it's no secret.
In basketball, it's kind of a must so that white guys can carve out a niche and guarantee acceptance on a team. Trying to be a white guy who dunks and stuff is like trying to be a white rapper - yeah, there are a few, but you have to work twice as hard for half the results.

Or gifted children:

But wait, aren't there white people who aren't doctors or lawyers, or even all that smart?
Well, here is another one of those awesome white person win-win situations.
Because if a white kid gets crappy grades and can't seem to ever do anything right in school, they are still gifted! How you ask? They are just TOO smart for school. They are too creative, too advanced to care about the trivial minutiae of the day to day operations of school...
This is important if you ever find yourself needing to gain white person acceptance. If you see their kid playing peacefully, you say “oh, he/she seems very focused, are they in a gifted program?” at which point the parent will say “yes.” Or if the kid is lighting a dog on fire while screaming at their mother, you say “my he/she is a creative one. Is he/she gifted?” To which the parent will reply “oh, yes, he's too creative and smart for school. We just don't know what to do.” Either situation will put a white person in a better mood and make them like you more.

Or not having a TV:

The number one reason why white people like not having a TV is so that they can tell you that they don't have a TV.
On those lonely nights when white people wish they could be watching American Idol, Lost, or Grey;s Anatomy, they comfort themselves by thinking of how when people talk about the show tomorrow they can say “I didn't see it, I don't have a TV. That stuff rots your brain.”
It is effective in making other white people feel bad, and making themselves feel good about their life and life choices.

Note that I said not watching TV earlier, so I am totally exempt from any potential irony...

new lisp software releases

Sat, 09 Feb 2008 14:45:00 CDT

I've released new versions of Ironclad, Chipz, and Archive. They are available in the usual places. These are mostly bugfix releases. Some problems with the Whirlpool cipher have been fixed in Ironclad and things should work much better on OpenMCL. Due to the nature of the changes, you will want to compile this release in a fresh Lisp invocation if possible. Jeremy English alerted me to a problem in Chipz--DECOMPRESS did not always handle :INPUT-END properly--which is fixed in this release. Finally, Archive includes some long overdue patches from Matthew Kennedy which make Archive work better with Win32 SBCL and BSD tar variants. This release also corrects a thinko with the Lispworks/Win32 support contributed by Sean Ross a while back; due to a packaging bug, the necessary bits were not being included.

The last bit is because I drive the packaging of my releases from Lisp. I wrote some code that grabs the names of all the files from an ASDF system, bundles them up with Archive, and signs it with Ironclad. Unfortunately, the packaging process is only as smart as its first step; the system definition had some #+lispworks goo in it and since I do all my work from within SBCL, that bit--which guarded whether a file was included in the system or not--was skipped. The packaging process, then, didn't know about the file and didn't include it. However, the cries from the Lispworks/Win32 community were not overwhelming, so I didn't notice for a long time. (I did get a bug report about it, and then failed to act for even longer. Sorry about that...)

vm tricks

Fri, 01 Feb 2008 10:28:00 CDT

I'd like to share two nifty language implementation tricks I've come across recently. The first is about doing allocation safely and quickly. It's helpful to have read Atomic heap transactions and fine-grain interrupts as background, but the first paragraph of the abstract sets out the issues, so I'll quote it here:

Languages such as Java, ML, Scheme, and Haskell provide automatic storage management, that is, garbage collection. The two fundamental operations performed on a garbage-collected heap are “allocate” and “collect.” Because the heap is in an inconsistent state during these operations, they must be performed atomically. Otherwise, a heap client might access the heap during a time when its fundamental invariants do not hold, corrupting the heap.

When the paper talks about “atomic” operations, they aren't talking about the usual atomic memory references accomplished by low-level CPU instructions. They're talking about atomic-ness with regard to interrupts and such--if you're in the middle of an allocation sequence, and you receive an interrupt and attempt to run a handler that wants to do some allocation of its own, you're going to be in trouble. So you have to find some way to make the first allocation uninterruptible. (C chooses to punt on this; you're simply expected to not call certain functions--such as malloc--while you're in signal handlers. I think having conventions like that can be appropriate in other contexts, but asking people to avoid allocation in a high-level GC'd language is a bit harder.)

One way to do this is the way SBCL does it. A bit is set prior to beginning an allocation; call this the pseudo-atomic bit. The allocation then takes place in the usual pointer-bumping manner. After the allocation has been performed, GC'ing if necessary, and the object has been properly initialized, the pseudo-atomic bit is cleared and another bit, the pseudo-atomic interrupted bit is checked. This bit is set by the C runtime if a signal comes in while the pseudo-atomic bit is set; information about the signal is then saved for later use.

If the pseudo-atomic interrupted bit is set at the end of the allocation sequence, then we need to handle all the pending signals that have accumulated while we were doing the allocation. You can see this come up if you use SB-SPROF; a good number of samples will probably point at the instruction at the end of a pseudo-atomic sequence, because that's when the profiling signal finally got handled.

Code is helpful here. A typical allocation for a cons cell on x86 SBCL looks like:

; 0ACCD727:       800DB403100104   OR BYTE PTR [#x11003B4], 4
;       2E:       B808000000       MOV EAX, 8
;       33:       030544AB0708     ADD EAX, [#x807AB44]       ; boxed_region
;       39:       3B0548AB0708     CMP EAX, [#x807AB48]
;       3F:       7607             JBE L0
;       41:       E8563F39FD       CALL #x806169C             ; alloc_overflow_eax
;       46:       EB09             JMP L1
;       48: L0:   890544AB0708     MOV [#x807AB44], EAX       ; boxed_region
;       4E:       83E808           SUB EAX, 8
;       51: L1:   8D4003           LEA EAX, [EAX+3]
;       54:       8035B403100104   XOR BYTE PTR [#x11003B4], 4
;       5B:       7402             JEQ L2
;       5D:       CC09             BREAK 9                    ; pending interrupt trap
;       5F: L2:

Let's step through this:

; 0ACCD727:       800DB403100104   OR BYTE PTR [#x11003B4], 4

We first set the pseudo-atomic bit.

;       2E:       B808000000       MOV EAX, 8
;       33:       030544AB0708     ADD EAX, [#x807AB44]       ; boxed_region

We need to allocate 8 bytes for a cons cell, so we load up 8 and add it to some memory address. This memory address corresponds to the C symbol boxed_region, which is a structure that describes an allocation region inside SBCL. The first member is the allocation pointer and the second member is the end of the allocation region. EAX now holds the address of the end of the object, which must not lie outside of the nursery...

;       39:       3B0548AB0708     CMP EAX, [#x807AB48]
;       3F:       7607             JBE L0
;       41:       E8563F39FD       CALL #x806169C             ; alloc_overflow_eax
;       46:       EB09             JMP L1

...which is precisely what these instructions handle. We compare EAX to the end of the allocation region and call into the garbage collector if necessary. After the garbage collector has been called, the runtime will ensure that 8 bytes are allocated to EAX, which means that we can skip over the next bit of code:

;       4E:       83E808           SUB EAX, 8
;       51: L1:   8D4003           LEA EAX, [EAX+3]

Remember, EAX held the address of the end of the object, so we have to subtract off 8 bytes to get back to the beginning of the object. It'd be nice if we could combine the SUB and the LEA, but that's not possible, since the LEA is a jump target. What's the LEA doing, anyway? It's tagging the pointer in EAX as a cons cell; discussing tags in SBCL is outside the scope of this blog entry.

;       54:       8035B403100104   XOR BYTE PTR [#x11003B4], 4
;       5B:       7402             JEQ L2
;       5D:       CC09             BREAK 9                    ; pending interrupt trap
;       5F: L2:

Finally, the XOR clears the pseudo-atomic bit and checks via flags whether the pseudo-atomic interrupted bit was set. If it was, then we need to trap and handle pending signals; otherwise, we can proceed with normal execution.

If you've read about how fast allocation can be in garbage collected languages, you may be thinking that this looks pretty slow (although it's still shorter than the fast path through malloc, I'd imagine). You've got multiple memory reads and writes, a couple conditional jumps...it looks pretty ugly. The situation is better on register-rich architectures where the allocation pointer is held in a register, but there's quite a bit of overhead.

However, there are two advantages of this scheme: signals can be handled at more-or-less arbitrary points in the program, so there's no checking for safepoints and the latency for handling signals is minimized. The latter property comes in particularly handy for dealing with native threads; stopping the world for garbage collection is handled entirely with signals. I'm not entirely sure if this is the right way to go about things--the signal handling code in the runtime is fairly complicated and allocations are slower than they could be--but that's the way the system is.

A different way of doing it is shown by the OCaml runtime. Its allocation sequence on x86 for 8 bytes is much shorter. From asmrun/i386.S in the OCaml source tree:

G(caml_alloc1):
        PROFILE_CAML
        movl    G(caml_young_ptr), %eax
        subl    $8, %eax
        movl    %eax, G(caml_young_ptr)
        cmpl    G(caml_young_limit), %eax
        jb      LBL(100)
        ret

This is quite a bit shorter! This is your basic pointer bumping algorithm; caml_young_ptr is the allocation pointer and caml_young_limit serves as the end of the nursery. If we overflow the nursery, we jump to LBL(100), which calls into the garbage collector and then retries the allocation But there are two tricks that contribute to making this shorter than SBCL's allocation sequence.

The first trick employed here is that OCaml organizes the nursery slightly differently. SBCL's nursery grows from low to high addresses, which requires some extra legwork to determine whether an allocation overflows the nursery or not. OCaml's, on the other hand, grows from high to low addresses and requires less fiddling. (This is similar to why you want to try to write loops that count down towards 0, rather than count up towards N.)

But our experiences with SBCL and signals should have us asking: what about atomicness? What happens with signals here? And this leads us to our second trick: when a signal arrives, OCaml records whatever information it needs to handle the signal and then sets caml_young_ptr to caml_young_limit. So the next allocation that comes along will find that there is no space left in the nursery and call into the garbage collector, which also handles processing any deferred signals.

It is left as an exercise for the reader to verify that signals occurring during the allocation sequence do not corrupt the heap.

According to the terminology of the paper, OCaml uses safepoints; the end of every allocation is a safepoint. Allocations don't have to worry about pseudo-atomic, cutting instructions, and since OCaml is a mostly-functional language, allocations should occur fairly often, thus delivering reasonable latency on handling signals. The disadvantage is that signals are going to be delayed, so tricks like interrupt-driven profiling need to be baked into the runtime, rather than being written directly in OCaml.

Obviously, the authors of OCaml and the authors of SBCL (and CMUCL) envisioned their systems being used for very different things. CMUCL was probably designed to do all sorts of grotty systems programming directly and therefore required a system that could handle interrupts at virtually any instruction with minimal latency. OCaml's designers probably expected it to be used less for systems programming and more for application development, so they optimized their runtime along those lines instead.

It is left as an exercise for the reader to convert SBCL to use OCaml's system. Doing OCaml's first trick of organizing the nursery differently should be straightforward; doing the second trick of removing pseudo-atomic somewhat less so. I pointed out above that SBCL's thread support relies heavily on signals. Since signals could be delayed indefinitely with the OCaml scheme (more likely in Common Lisp than in OCaml), something needs to be done to ensure that all threads rendezvous for garbage collection in a timely manner.

This observation leads us to the second implementation trick.

I mentioned that OCaml uses safepoints. These are sometimes called yieldpoints, most notably in the Jikes RVM (nee Jalapeno) system. The idea is similar, but instead of waiting for the next allocation, which could be delayed indefinitely, put a check at every backward branch and function return to see if a signal has arrived. We will always hit one of these fairly quickly--even in a non-allocating loop. The heap's state is also guaranteed to be consistent at the point and we can safely run the garbage collector, signal handlers, etc.

Reading about this several years ago, I thought, “You're going to add an extra memory read and a conditional jump to every backwards branch? This is going to kill performance!” But many language implementers think this is a reasonable strategy. (The compiler, could, of course, choose to elide the yieldpoint checks in speed-critical code.) A number of native code JVMs use this strategy. I believe SML/NJ used to use this system, although for a different reason: at backwards branches, it recorded which registers contained pointer data to assist the garbage collector in discovering roots.

I discovered that the HotSpot Java compiler uses yieldpoints today, while reading an excellent blog post. But HotSpot applies a small optimization; a yieldpoint at the end of an infinite loop looks like (on x86-64):

28C26E6   test         dword ptr [160000h],eax
28C26EC   jmp          28C2690

Wait, wait, where's the comparison to see if we need to go handle signals? I'll let the aforementioned post explain:

This seemingly useless test is part of a mechanism used by the VM to suspend the thread at this instruction (a safepoint). When the VM wants to suspend all threads (for a GC) it unmaps the safepoint polling memory page (in this case at 0x160000) and waits for all threads to suspend. Each thread running compiled Java code will eventually run this instruction and cause a page fault, inside the page fault handler it is detected that a safepoint thread suspend is requested and the thread calls the VM to suspend itself.

What initially looked to be a test and branch (and possibly more code to properly jump into the signal dispatcher) added to every backwards branch has been reduced to a single test through the wonder of virtual memory and page protection. Very cute.

persistent smells

Sun, 27 Jan 2008 14:53:00 CDT

We went to my parents' house post-Christmas and my sister was excited about having Becca play with the play food that was hers when she was little. So we hauled out this box of plastic Fisher-Price food--bread and a coffee pot, a wedding cake and cupcakes, baby food and a small mixer, the whole nine yards. Becca enjoyed every bit of it, as predicted. I do want to note, however, that the icing for the cupcakes and the chocolate chip cookies still retained their fragrances; I'm not sure whether to be impressed or worried about this phenomenon.

lessons in customer service

Tue, 22 Jan 2008 19:09:00 CDT

Two lessons in how not to serve your customers.

Example the first: due to our recent almost-but-not-quite house purchase, we needed to go month-to-month on our apartment lease. Doing this carries a small price premium (~15%) over a long-term lease. Since we are now in negotiations to purchase a house that we will not actually live in until July or so, we thought it would be a good idea to try to negotiate a short lease that would save us a bit of money.

The apartment complex office was perfectly willing to do a six-month lease. However, they cautioned us that they needed to check with management: the managing company has this funny policy that only a certain number of leases can expire in a single month. If you were to be the N+1'th person for a particular month, you would need to negotiate a longer or shorter lease as necessary.

This policy makes perfect sense for the managing company: they want to ensure a steady income from their properties. But it's a slap in the face to their customers. If, like us, you cannot do a longer lease, then you must do a shorter one and then pay a month-to-month fee for the extra time--which, in our case was only a month. Still, that's extra money that we should not have had to pay. It's not my problem to ensure that you have a steady cash-flow from month to month. Dumb.

The second example comes from one of those wonderful credit card companies that sends special offers in the mail. In my case, the company in question is Chase, parternering with Continental Airlines, who has sent me the exact same credit card offer at the rate of once every week and a half for about four months. I don't need another credit card, thanks, and so I wind up throwing these applications away.

Upon receiving yet another one today, I was peeved enough that I called the application number in hopes of getting myself off whatever crazy mailing list they have. My call was taken, very kindly and professionally: what's the ID number on the offer, name, address, that sort of thing. I was rather pleased with how easy the call was.

Until the end of call, at least. The customer service person informed me that my request was in the system and that I might continue to receive offers for up to 90 (!) days past this point. My brain wanted to lambast the guy for taking so long, but I politely thanked him for his time and courtesy instead.

C'mon guys! We can order things from Amazon and get them delivered anywhere in the world in less than two weeks. Cisco (and probably other companies, too--Cisco was just the first) can close their quarterly financial books in a day or less. What on earth can possibly be holding up my request such that it could take three months to process it?

I can think of two reasons: number one is that Chase really is such a lumbering company that that ninety day figure is accurate. Maybe they have to communicate with all sorts of partners and send my request all over the place. Again, not exactly customer focused. Number two is that the number is a worst-case scenario; they know that if they were to say, “hey, it'll take two weeks.” and something screws up along the way, there will be a customer who receives a new card offer a month after the initial request. And that customer will be peeved and will call Chase to give them an earful. Still not customer focused: Chase should have a better hold on its internal processes and/or tighter rein over its partners' operations (think Wal-Mart or Dell here).

I should note that both experiences contained their pleasant points--getting such a short lease from the apartment complex and a painless “take me off your list.&dquo; process. But nestled in the middle of both are these two sour notes that do little for my good opinion.