Þ   briarpig  » log  » sep07

redacted ¶

     After I write about myself, the next day I often redact, if any bad feeling lingers. Usually it's a piece about me. I almost killed a few recent pieces (eg quarterback). I let them live when I feel they have an interesting social point, or career focus theme.

tracking ¶

     I've almost written about "tracking" several times, where people are slotted in tracks limiting what is expected of them. It won't gel yet, though. However, if I write about tracking, I'll criticize an effect of blindness it causes in folks who heed them. I associate few (if any) positive effects with tracking.

sound check ¶

     This is one of those days I feel like not writing. At times I wonder why I write so much, as if someone is listening. I think I do it for myself; it supplies something otherwise missing. It seems to greatly amplify my rational thinking. I attend fewer useless trains of thought. I ignore things that used to bother me (quite the blessing).

     It's fun not knowing what I'll write about. I seldom follow the loose outline I'd imagined.

     So far I keep resisting an urge to write funny stories. I think of character dialogs I find hilarious, and I know I can write better than I once did. But despite being fun and creative, I don't think it's constructive. Better to stay focused.

assertions ¶

     Should you add code to software that does nothing but look for mistakes? Yes. That sounded short and simple, so let me amplify until you get sick of hearing more. You should add a lot of code to your software looking for errors. Paranoid code is good code. If you give bad data to your app, it should either crash or complain — preferrably both for data you swear on a stack of bibles is trusted. Just complain for untrusted data. But see bad data.

     Do I make mistakes? Absolutely. "Good at coding" doesn't mean never mistaken. You will err; even if code is first perfect, you or others will err later. Just find out as soon as possible. Aim to make and find mistakes faster. I find most of mine before I subject others to my code, thus never terrifying my peers.

     If quality engineers wax eloquent in your praise, then you're at least trying hard enough. If they speak of you in awe, then maybe you're starting to overdo it. But if you inspire awe, you'll get many free passes to make changes you want, even when folks are afraid. (But one day you'll blow it and your name will be mud for a day.)

     Someday I'll list a whole bunch of new Murphy's Laws (cf Murphy's_law) specific to programming. There must be hundreds of them. You can get any good coder to rattle of dozens of them in a few minutes. Just ask: what things can go wrong? Gee, isn't that funny? There's so many, and so ironically amusing. Your code should explicitly look for ones occurring to you when writing.

     Next sections explain you should look specifically for corruption and confusion. I like to rattle junior engineers and my managers by saying all systems become corrupt: it's just a matter of time. Your goal is to get mean time before failure longer than the next weakest link; maybe a nice fuse will blow first.

confusion ¶

     When many coders use assertions, they're looking for confusion. For example, suppose you want to move a page from the used list to the free list. The page is supposed to be in the used list, it says here, but what if it's not? Heh, that's why you assert the page is in the used list as expected. If you're wrong, it can be a nightmare. Better check all the time, continuously.

     Code flow often implies conditions that must be true, so you don't check them. That's wrong — you need to check them. What else is easy to check besides those conditions you know must be true? So check them and assert when they fail. It saves an enormous amount of time, right from the very start, because errors show immediately.

corruption ¶

     I'm often asked how to make memory allocation more safe. I say you must expect someone will get it wrong eventually. So you look for the effect of an error, and complain when you see it: preferrably by asserting in debug mode. Many permutations of error exist, from clobbering memory with overwrites to freeing and re-allocating space before other code notices.

     In the old days, when systems had less memory as RAM, such errors were more likely to cause SEGVs (crashes signalled by illegal memory bus errors). Crashing is wonderful because it gives such unambigous feedback: bad coder! Best to have your nose rubbed in it immediately. Once first cause is so old an evidence trail goes cold, bad news is much harder to use constructively.

     But today you might write a server using almost all of your address space on a 32-bit system. How are you going to be punished with unmapped memory addresses, when almost all addresses are mapped and valid? In a stochastic sense, probability of detecting bad addresses the classic way isn't good when you use all your memory.

     So you want to simulate the effect of SEGVs, and the easiest way to do this is with magic numbers embedded in structures, which should be equal to a known expected value when space involved is still good (unclobbered and still allocated in the same lifetime). If you check fields for expected values constantly, and assert when you see bad values, you get diagnostics like SEGVs.

     When junior folks ask how many structures should have fields containing magic numbers, I say all of them should. Well actually most of them; some formats are so small and tight, and numbering in the zillions, that you can't spare a byte. Okay, not in those structures. I feel guilty every time I create an object that doesn't have such a field.

     (Bugs that slip by me often would have been revealed by the use of a field containing a magic number. But I leave them out when I'm in a hurry, especially for very simple or very dumb objects.)

     Here's an example of my standard boilerplate. This example assumes an entire 32-bit integer as a magic number field is not too large. Suppose you have a class named Foo; the code below shows what you add specifically for the magic number. Obviously you should imagine Foo also does something useful that's not shown.

     When a class is prepared like this, you should check goodFoo() in every non-trivial method where time cost of another test condition is inconsequential.

modules ¶

     With a reader and writer done, I started a basic Lisp interpreter to evaluate sexps (s-expressions, aka symbolic expressions) and paused immediately to reconsider what I know about naming things (which is one of the two hard things in computer science according to Phil Karlton.)

     A single global code namespace is too little, and I already know I want my module namespace to be a tree corresponding to a file path. But before I commit myself to one or another coding path, I should explore lots of things people say about module systems, so I grasp how global values in Lathe modules become visible and interact with other languages.

     I expect I might start posting lots of links to specs and discussions on modules and how they get exposed (or should be exposed) in various languages. For example, there's the Squeak New Module page (where Spoon's Naiad is an interesting mention).

     Then from scheme-punks there's Dynamic Loading of ERR5RS Libraries, described as "the most important part of ERR5RS, and the easiest to get wrong." If I want to ensure I worked with err5rs later, I might want to think about how my module system plays in that context.

lathe ¶

     Here's a short note on codenames for languages I build atop þ (as described by λσπ): Lisp, Smalltalk, and Python layers — λþ, σþ, and πþ (aka lambda thorn, sigma thorn, and pi thorn) — will use consistent short names based on contracting the long names:

λþ	lambda thorn	lathe (tool)
σþ	sigma thorn	scythe (tool)
πþ	pi thorn	pith (essential part)

     All these words have etymologies (apparently) with Old English roots using the original þ glyph, making them most appropriate. (Note the use of y as a substitute for þ in the source code echoes alphabet history.)

     This means I've changed the name of the Scheme-like Lisp dialect from lithe to lathe: a much better reference to craftsmanship. The scythe name is suitably cutting, and pith is predictably obligatory (if I can't implement Python with Lathe, then it's done wrong).

     I expect I can never say Lathe is Scheme. At most I'll support some Scheme standards in Lathe. Lately I'm eagerly reading scheme-punks for specs on Will Clinger's emerging ERR5RS alternative to R6RS. (Yes, err5rs was deliberately a single letter substitution away from errors.)

     I plan to use Lathe as an internal Lisp layer with good C++ primitive support. Other languages will map to Lisp ASTs (abstract syntax trees) processed by Lathe modules for compilation and assembly, etc, so Lathe will provide a basic virtual machine used by Scythe and Pith.

python ¶

     What's my motivation to implement Python later? Libraries, inertia, and invested communities. There's a lot of value tied up in Python that can't be ignored. Why should I try? Support for multiple languages is part of what I seek: to emit code in whatever syntax needed for a deployment context.

     (Javascript is the canonical example for a target deployment syntax. Libraries I write in Lisp, Smalltalk, or Python must be able to generate code in Javascript when necessary, for Ajax style apps. Javascript is just another compilation target. Python, too.)

     I don't know Python well enough yet, and I need to stretch by learning again. I've found I learn languages best by implementing them. What would make a better lab for experiments than a way to translate to and from Python? Both directions are good, but Python to Lathe is most useful. Here's why:

     Python libs translated to Lathe would make good Lathe test beds. Lathe versions should act the same. It's difficult to test complex code systems without real applications to drive many possible conditions.

     Finally, there's intellectual commerce flowing through Python territory. It's a hub of traded code goods. To become a new trade merchant, you follow existing trade routes. Lathe as no chance without following.

ferris bueller ¶

     I had to point this out. It's a small but pleasing joke. Ben Stein wrote this in the NY Times, in The Great Inflation Mystery, Still Unsolved:

This famous equation, MV = PT, had long been thought to explain everything, and maybe it did. But why, then, if M rose and V and T showed only modest growth, if any, didn't P rise? (Anyone? Anyone? Bueller? Bueller?) No one knew.

     Ben Stein's done many things, including host his own game show called Win Ben Stein's Money. And he's also appeared in movies ... including Ferris Bueller's Day Off. In other words, Ben Stein played the original character who said, "Anyone? Anyone? Bueller? Bueller?" in that marvelously droning voice.

purism ¶

     I'm not a purist. For example, I think I have few hangups of the sort reported by JJ (Shannon Behrens) in Smart People Have Weird Hangups. For all practical purposes, I'll use anything a situation requires, even if there's a smell I don't like. Bad code smells are just part of the territory; I track them though.

     There isn't time to address anything except problems with highest priority. To focus and deliver on big stuff, you can't afford attention on little stuff. Every system has little problems I just ignore.

     Smell of inefficiency stinks most to me. It's partly cultivated: usually folks want me to make things go faster, so I'm encouraged to react negatively to anything I suspect might be too slow. Professionally, I must have good taste in ranking performance problems. The worst things make me itch to fix them. Less important things affect me little beyond taking note.

     Variety in code style affects me not at all as long as I see systematic thought in the coder's hand. Hmm, in fact, I think my high tolerance for variation makes it easier for me to change systems. Intermediate messy steps don't bother me. I'm actually comfortable with having more than one way to do anything. It allows me to compare one to another.

     That said, it makes me wince to read code with chaotic memory management. However, it's useful I notice it on sight, since it's usually on a hit list already: folks know it causes crashes, and want it gone. It goes on my todo list for rewrite in priority order. When I fix it, it's really fixed. Other folks sigh with relief.

     Anything you insist must be perfect, I write myself. I won't use existing code unless I see it's already close to perfect. It's easiest to write good code from scratch; you can plan a unit test at the same time, adding hooks for this as you go. Code's not perfect until unit tested (then field tested a long time after).

     You say close enough is good? I'm fine with it. You want incremental improvement? I'll incrementally rewrite it. Your wish is my priority list.

nail soup ¶

     The way I run my own personal projects might make me seem a purist, because I'm a heretic when it comes to prevalent nail soup (cf Stone_Soup) religion in open source software. In this model, you whip up something that barely works as a starter: the initial nail or stone, as it were. Then everyone else tosses in this and that, until it's soup.

     The "just toss things in" part bothers me. It presumes the average contributer is not making things worse. This presumption might be true if the goal all along was to make something barely edible. Nail soup works when you don't mind cleaving to the lowest common denominator. But bringing the quality up later is hard: there's enormous inertia against it.

     Well, the C runtime is something I'm specifically trying to replace — in large part — with my þ runtime library. Random code contributions done in "normal" C style would undermine my plan, which changes what you assume about memory allocation, for example. I want consistent guarantees at the bottom, so code is friendlier to servers and dynamic languages.

     Later I can take high level language contributions compiled to C and/or C++. That would work. In fact, that's one of the goals: to specify intentions at a high level, later converted to low level code with some guarantees ensured by compilation. Right now I'm bootstrapping code, and I trust no one else.

being right ¶

     I was right too often in high school, and it warped my world view. My memory was often photographic, and I understood my teachers completely, so I could predict what they wanted even when their lessons were incoherent. With respect to teacher's questions, I was an oracle.

     As a result, working with other students was always a losing strategy. Anyone who disagreed with me was wrong; it was easy to test by seeing which of our answers a teacher wanted. I was rarely wrong, and it gave other students the willies. I was very intimidating. I took class objectives too literally. I thought the goal was to be right.

     My math teacher thought I needed to learn I wasn't perfect. He kept searching for gray areas in my proofs and problems, until he could find an imperfection large enough to award a grade of 99% instead of 100%. This occurred many times in a row, which made me more careful. Either he gave up looking, or I stopped showing weakness, because my scores returned to 100%.

     I had perfect scores in all classes so often my satisfaction became perfunctory at best. My reaction to a perfect score? That's nice, I'd say. Another job well done. Obviously I wasn't learning the right lesson. The real world doesn't have tests with scores you can verify objectively. Instead, the real world has a lot of psychology: winning can make you lose.

     I remained an asshole for years.

teamwork ¶

     I learned the value of teamwork very slowly, because I was very self reliant. My high school experience taught me exactly the wrong lessons. Instead of learning to trust others, I learned to distrust them, because I always did a better job by myself. However, this only works given an absolute authority to say who's right — like teachers.

     In the real world, every problem definition is a group activity. You can't work on problems other folks can't or won't recognize. If you do, you seem to do nothing, and you can't afford to seem to do nothing. In practice, you can only afford to work on tasks mattering to others. It doesn't matter how important, if it's not recognized.

     Additionally, you can't threaten the self esteem of others by performing too well. It can look like you want to show them up. Guess what happens if folks think that? Darn right: then you're up shit creek. The result can be worse than screwing up. At work, you're paid to make folks satisfied you're there helping, not to make them feel bad.

     Looking harmless actually takes dedication. No one assumes your attitude is neutral. If you need to do something well, it's best to get someone to order you to do it first. Then they can take some credit, and it's not all about you. Describe consequences and tradeoffs present in all the options. Other folks can see the best choices too.

     Ideally, everything you do at work should occur after someone wants you to do it. You're in the business of delivering satisfaction. First you're asked to do X, then you do X well and quickly, then everyone is happy. Lather, rinse, repeat. You can't do it if they don't see it or want it.

     This is why communicating clearly matters so much. You must write or speak quickly and simply, so you're done within attention spans. What you want doesn't matter unless others want it too, with an obvious and timely value proposition. You can't make others think like you; that's your job.

     Honesty and integrity requires you always tell the truth, after adopting the value system of folks you inform: true from their perspective as well as yours. Obviousness is highly desirable in good choices. Simplicity is a good path to obviousness. Each story must unfold clearly.

bouyancy ¶

     Someone at lunch managed to get me to tell the old story of how I sank in high school. I think it was the phrase "everyone floats," said of swimming, that set me off. I was once member of that 1% of the population with negative bouyancy, and I did not float. So, what does it matter?

     Well, in Iowa at that time you didn't get a pass in swimming phys ed without passing a float test. So despite the fact I'd been on the swim team one year, I was a floating failure. So in college a couple years later they actually forced me to take a swimming class. I still didn't float then either; it was easy to demonstrate.

     If I inhaled just short of lungs bursting explosively, then curled into a ball, it took me less than ten seconds to hit the bottom of a fairly deep pool. This usually made gym teachers say "wow!" at the impressive drop rate. I sank as fast as you would with lungs emptied.

     Today with higher percentage body fat, I barely float. I miss being able to demo the drop.

physical fitness ¶

     I'm not especially fit these days. I'm not too shabby either, but lately I'm coding more and working out less. I should really walk more since I don't get enough aerobic exercise. I mostly lift weights; it's not as good for your heart. Looking buff is nearly pointless when you ignore flirts. I only work out to feel physically good, for good spirits.

     I asked myself: what could I cite as a statistic you'd recognize as a sign of fitness? Pushups, I said to myself. How many of those can I do? The last time I checked was four or five months ago. I did as many as I could with proper style (touching nose and chest to ground each time).

     So I did 38 pushups. Not too bad. There's a lot of guys who can do that many, right? But how many at 48 years old? How many weighing 210 pounds? I weighed 170 four years ago, at 11% body fat. Since then I put on 30 pounds of muscle, ten of fat. (All on my belly, dang it.)

     Now I seem to have hit a genetic set point for muscle. It didn't look like I'd stop getting stronger for years. Compared to when I started, I can lift four times as much weight for twice as many repetitions. I'm still getting a little stronger, but very slowly. I'm shaped like the high school football guys, but I'm 30 years older.

     In my youth it was clear muscle made others expect less intelligence. Jocks tried to exchange recognition signs. I signed back: total geek here, sorry. Something a bit like it still occurs; folks see sports nazi, age about 40. I don't care about professional sports at all. Each year I pass the Super Bowl not knowing names of contending teams.

quarterback ¶

     My high school's football team was short-handed, and they asked me to play, but I wasn't interested. I was subjected to a friendly but insistent campaign of persuasion. Please? Pretty please? I kept saying no: I don't know how to play. I'm afraid of getting hurt. I'm not interested. I never trained. Didn't the season already start? Why me?

     I did the 100 yard dash in 10.9 when I wasn't on the track team. I weighed 165 and benchpressed 285. And I was patently a very bright guy at my school. Apparently that was good for quarterbacks. Don't ask me why. Being smart would only help if you understood the game, right? And I didn't: case closed.

     The funniest thing happened in the weight room my junior year, where apparently I was the only person working out who wasn't an off season football jock. (Of course I wasn't teased: other guys were afraid of me. Imagine that.) I had amazing arms: about like now, but more powerful.

     Okay, here's the good part. The football coach entered the weight room, came over next to me and watched, thinking a couple minutes. I think he offered this cliché: "Look at the arms on this guy." Then the coach addressed the room: "Attention everyone, I have an announcement to make." When all eyes were on him, he pointed at me.

     "This guy," the coach proclaimed, "is going to be our new quarterback next year." Then he looked at me with a cheesy grin, and waited for my answering, um, whatever he expected — something big fit his expression. Like I should throw a fit and roll around in ecstacy, or something. High fives?

     I just looked at him without saying anything. A very long pregnant pause filled the room. I could hear the other guys thinking very loud thoughts. (They sounded like: "Sir, that's the geek. Big mistake.") A puzzled expression entered the coach's face, then slowly grew to a dawning look of horror. Finally, he decamped. We never spoke again.

     But the next fall, a daily campaign to get me to play ensued, lasting weeks. I was never unclear: I was not interested. So it fell off and became wheedling, with occasional new and strange strategies, like most popular jocks wanting to be my friend, and chat about football opportunities. It was kind of charming.

     Of course, I knew what it was about. In gym class, it was extremely hard to catch me, and my hand/eye coordination was phenomenal. I could throw wonderful bombs when I played football. I just didn't care, and I'd hated football since age 5, when it bored me to tears. All I cared about was going to college for engineering — to do tech stuff.

complex printing ¶

     It took considerably longer than ten more minutes to finish the pretty printer described two weeks ago. A weird interaction with shared structure printing emerged, slowly revealing a gross oversight on my part:

• shared state print progress is stateful
• pretty print metering changes state early

     My reader parsed the input expression above correctly. But then it wouldn't print as expected. Instead of looking exactly the same as above, it came out like this:

     The reason became clear: measuring expression length before printing made the printer believe the expression had already been printed in full once already. So every subsequent hit displayed as above.

     Deciding what to do about it took a couple days of scheming and plan revision, until finally I knew how to do the right thing; it was far more complex than I'd hoped.

     Here's the solution: all state changes caused by metering for length must be undone again, so the printer returns to exactly the state it was in before metering length. This way the first time a printer sees a pair, it really is the first time seen and not the second after metering. (It actually gets worse, and I'm simplifying.)

     To get a really clean solution, I finally decided the hashmaps involved needed a temporary copy-on-write (cow) layer while metering, which gets stripped away before printing is resumed. I put the hashmaps into a special class allowing me to layer for temporary cow, and later unlayer to revert to the original unchanged hashmaps.

     Is that tedious, or what? But I could test behavior independently from the printer. I printed the structure before, during, and after the cow layer, and verified the after state exactly matched before state, down to identical crc's for all hashmap pages involved. Alrighty then.

constant time ¶

     My main recipe for scaling servers is constant time operations: everything must occur in O(1) time (pronounced order one time), especially when populations are large. This results in systems that are said to scale linearly because constant time operations don't become more expensive with scale. When you increase resources by a factor of N, you use all the new resources productively without wasting them.

     If you screw this up, profiling shows a lot of cycles feeding bureaucracy of your data structures which are slower than constant time. Here's a hint: only use lists in ways where you can arrange O(1) operations. Never allow linear list operations. Never sort large populations.

     You normally can't use off the shelf software like STL classes in C++, because doing so loses options for constant time operations everywhere. When an object belongs in multiple collections, you usually need intrinsic rather than extrinsic links. Given any object, you need constant time access to fields allowing you to change containers in constant time.

     You can prototype with STL, but you can't keep it. Not if you want to scale linearly with more resources.

sampled profiling ¶

     One of my new colleagues has a profiling specialty with his own homebrew profile tools on Linux. We profiled a longish run of the server running in memory only mode and gratifying results were also interesting: the vast majority of cycles were consumed by only 1300 different processor instructions. All of them were in the methods where I touch memory in bulk.

     It was gratifying I'd done all constant time data structures — nothing shows in profiles. All runtime costs show where linear memory operations are unavoidable: copying, searching, comparing, hashing, etc. which are linear in length of bytes involved. The really interesting part: this confirms my theory about performance in a dynamic language. I could write the same server in Lisp, and it would have about the same performance, as long all costs are where they appear now: in necessary C++ routines touching memory buffers.

     In other words, all the complex thinking done by the server takes nearly unmeasurable, small amounts of time compared to bulk data costs. In the future I can use a runtime with garbage collection, and I can expect this will have no impact on performance, as long as I don't incur gc costs rivaling my other bulk data costs. (This is the basic idea behind λσπ: I might get the same performance in much less code time and effort.)

     Because server cycles are eaten by a small number of methods, we can optimize performance by tuning very few lines of code. One of my methods (already carefully tuned C++) had a twelve instruction loop eating 15% of CPU. My colleague got this down to nine assembler instructions with fewer pipeline stalls.

dumb compilers ¶

     At the moment our C++ compiler is older and dumber than we expected, doing a lousy job of reordering instructions to avoid memory stalls. I sighed at this because I stopped manually re-ordering my code to avoid memory stalls years ago, because compilers had gotten so good. But not good enough apparently.

     Code is clearest when you access a slot right before you use the value read. But this is slower than reading a value a little earlier to let memory latency occur before use. Compilers written in recent years should do this for you, but apparently they sometimes don't. So you should write code accordingly without assumptions: try to read slots earlier before places you use them.

home synonyms ¶

     My sons and I watched several episodes of House Rules in a marathon Saturday, featuring a brilliant but strikingly edgy, cantankerous medical diagnostician in a hospital. We found the fast-paced, intelligent writing extremely entertaining; it gave us a lot to talk about. (I told them I'd never wanted to be a doctor since I'd believed they worked far too hard, making my younger son laugh and say I hadn't done much better. To which I should have said touché.)

     We watched Dr. House go home at the end of the last episode; when the camera panned past his street address, which was conspicuously 221, I laughed and explained it must be a reference to Sherlock Holmes, who lived at 221B Baker Street, who Arthur Conan Doyle had modeled upon a brilliant doctor (named Dr. Joseph Bell) of his day. Number one son rhetorically asked me what words were synonyms for home, and I took his point immediately that Holmes and House were obviously related.

geek squad ¶

     The last section reminds me of my brilliant coworker Alan Liu from Taligent, who earned his MD before choosing to write software. (I did ask him why he decided not to practice as a physician, and while the answer's interesting, he never gave me permission to repeat it: so get used to disappointment.) Alan was good at thinking.

     Alan also had a sense of humor: his job title was fun, and cleverly alluded to his background. In those days, Apple was famous for letting engineers choose anything they liked as job titles — strange and interesting was considered good, encouraging creativity — the whole "think different" business, you know, even before Jobs returned.

     Anyway, Alan's business card said Anatomically Correct, which never failed to bring smiles. My own business card held a reference to Roger Zelazny's Amber series. Since I had admired characters at the flexible and dynamic end of the spectrum, and was forever trying to escape pigeonholes assigned to me, I was Chaos Shapeshifter, which only confused folks.

     At Netscape all engineers had the same title: Member of the Technical Staff which was basically indistinguishable from a more colorful title I now wish they'd used instead, which was Morlock; end users are Eloi, of course. I don't care what my title is any more. Today if I had an accurate title, it'd be too long and useless; but Plumbing Techie comes close and lacks pretension.

drawing pictures ¶

     I draw whiteboard pictures continuously while describing systems. This has a much stronger impact on folks than any writing style I've ever used. The effective bit rate I achieve here (writing these words) is very small compared to what I get while talking and drawing. It would be painfully hard to create word pictures equivalent to what I draw.

     I think visually much more than verbally, so drawing pictures is my native mode. My drawings seem even more effective when someone sees me draw while I speak, because I draw what I'm saying at the same time, so lines are effectively high bandwidth gestures. Also, I change what I'm drawing and saying in response to questions I field at the same time, so I illustrate exactly what someone needs to know based on what they don't yet understand.

     (For a few years after I worked on OpenDoc at Apple, it was always during a particular ten minute interval of time that interviewers made up their minds they wanted me. This was when I described my database and drew pictures of transaction handling while answering questions exactly tuned to what an interviewer was parsing. Everyone wanted their systems to do what I drew, or something similar; it was obvious I'd have no problem.)

staying put ¶

     I decided to keep working where I do today, with a future planned coding task as a deciding factor in making me stay. My current near term task list includes a new async i/o system based on efficient, scaling, threadsafe, async event queues. So for example, I'll be able to do preadv() with my new threaded page cache, using my new async queue system underneath. Then threads would be optional in those layers (but a bottom layer still needs a thread pool without Linux async i/o).

     I've been meaning to write a first class async event system for years, and I'll need a simple version of such a thing in future projects, so it's most convenient to work out design kinks in a version someone else needs. The first time you do a bullet proof enterprise class systems tool, it costs some time, even when you already have the basic design in mind, because you have to keep asking what could go wrong now? over and over, until finally your mind replies nothing, anymore.

     The end result is simple, almost trivial. The expensive part is rejecting bad choices with rough edges you're tempted to work around. Best choices have nothing to work around and are hard to corrupt, because they care little about things you can screw up. The final version will look just like a picture I already have in my mind, but the C++ and C apis and plumbing won't have the boners that offer themselves in passing, if I'm choosy.

send & receive ¶

     In 80's college operating systems 101 I learned basic thread synchronization mechanisms have several equivalent duals that can be turned into one another. Of them all I found send and receive primitives most elegant and pregnant with possibilities in application. I used them to implement a simulation system in college, when a professor asked whether I could replace a Fortran based event simulation system. Did I use C++? Seems like I did; I was an early C++ adopter.

     (Why was I asked to do this instead of someone else? If you guessed I was the best student at operating systems there, you'd be correct. I'd not have been best with great peers at a high end CS school, though.)

     My implementation was logically pretty interesting, but no great shakes in performance because the way I did context switches was too expensive with longjmp() and stack copies. A few years later I discussed event implementation with a guy who'd written real, heavy duty event simulators for hardware. It had been his speciality, which informed the runtime we created. So I went over all that again, but I still liked a kind of mailbox style send & receive with queues for async events. I designed that in Mithril circa 1999-2000 but never coded it.

     I've been planning to use this same design in þ for Erlang style messaging. (Mithril's lightweight process messaging was indistinguishable from Erlang's, but I didn't know Erlang then.) So writing one or more async event queuing systems is already on my todo list. Clearly I'll find it very useful to write one in a highly threaded enterprise server, where I can see what happens when my design is subjected to that context. Seeing what actually survives and performs is great data.

     Anyway, threadsafe queues are trivial in complexity, and I already use them to manage thread pools, for example. So the interesting stuff is representing continuations as event sequences, with backtraces to permit debugging "stacks" in event flows. The most quirky part might be how a story of async control flow goes, so it doesn't confuse other devs. Docs may need more debugging than code. My guess is collecting stats for diagnosis will be most difficult and irritating.

citing examples ¶

     I wanted to show a good example entry from my resume, but items of most interest to others (eg mentioned in books) too clearly identify me. So instead I chose one I enjoyed doing the most. You can find very interesting comments on gzip and etags in it. Several years ago, after I asked questions about gzip online, I never reported the final resolution of my research, which was that zlib almost already did what I wanted.

     In summer 2004 when I interviewed at Fineground (acquired by Cisco in 2005), I was told my "etags" trick was one of their main features for web optimization. It was how they made browsers stop asking about changes until version numbers in URLs changed. I ended up saying no to Fineground since I couldn't afford the commute (and I doubted the offer of a four day work week).

resume excerpt ¶

     (This section excerpts one job from my new resume, which resembles style in this blog, as mentioned three days ago. It's one of the most interesting, and covers a two year period from Nov00 to Oct02. When folks ask me what I like doing, I say I enjoyed this job most. The product described is still sold; I removed the current name of the server, and who gave it this name, since it would tell you too much about me.)

     I joined startup Pivia as senior developer to write from scratch a Linux server for caching HTTP traffic in C++ with a few other developers. Our server's focus was dynamic caching and was structured as a reverse proxy with customers giving us DNS control of their domains, so we could cache proxied content from origin web sites.

     We aimed to address a market segment Akamai ignored: sites with web pages containing variable content even when the URL was exactly the same, when other parts of a header request (like cookies or user agents) also affected final page content. Akamai's and Squid's model considered such things cache busters that could not be cached. Pivia cached such pages anyway as templates compiled in virtual machine representation substituting correct values dynamically for HTTP responses.

     I designed all parts of the server I implemented myself, which was most of the runtime and content handling logic in the server, including all the memory managment, app binding, file i/o, streaming, header parsing, page parsing, esi parsing, compiling, disassembling, compression, logging, caching, invalidation, server markup, and debugging tools. I wrote all the docs defining how the server behaved, because I invented all the logic and rationale for how content was processed. First I defined discrete math for rules of behavior, then I wrote the plumbing to move bytes around. I did all the lock and thread design for the cache under pthreads.

     One developer did comms between boxes in our server farm; another did socket i/o and HTTP protocol management while using my zero copy APIs to stream files into memory. All content in our server's memory lived in threadsafe data structures I wrote, designed specifically for our usage patterns. I ported tens of thousands of lines of utils from my public domain IronDoc & Mithril libs, written before and after my Netscape years (sanctioned by Netscape & AOL). My compiler's infrastructure was cloned from my Mithril and Yb tools.

     First I wrote a module system to bind request URLs to "apps" in sub millisecond time to get page parsing rules specific to a URL path at variance from defaults, as specified by users via the web gui. The module system at runtime was built by compiling received app descriptions into graphs interpreted at runtime in app binding. Apps were refcounted and immutable (except for invalidations) and hot swappable at runtime between one request and the next when republished.

     Each newly received browser request was bound to an app containing rules to edit an entire request header into a uid (unique id) replacing the URL's function by adding missing keys and removing ignored keys from the URL. For example, if a cookie affected content, this went into the uid. Or if the values of some query parameter fell into a few distinct equivalence classes specified by pattern, that value got replaced by the pattern itself (causing fewer cache entries).

     This uid keyed a huge threaded cache of all the server knew, encoded as pivlets pairing OWS (origin web server) responses with virtual machine instructions and pre-compressed gzip templates, both generated by my HTML compiler. If the cache held an unexpired copy of a desired response template — not invalidated by queued patterns — it was executed by the VM to build a page emitted on the wire. (I defined and designed the VM and its instruction set.) When edge side includes were involved, this could involve additional requests for OWS page fragments.

     Each request logged to an accumulator aggregating duplicates by count in a hashmap before writing to a gzip compression shim before streaming to log files used by customers for traffic billing purposes. I gave each request a per-request log generating debug info and statisics if enabled, to be returned from the server on demand instead of original requested pages. When enabled, a generated debug page showed everything about processing a specific request for a page, including disassembled VM instructions.

     On cache misses we proxied original requests to the OWS, and ran each response through my web page compiler, operating at five megabytes per second when processing both HTML and embedded esi markup from the esi spec. My hand-crafted HTML and URI parser tracked byte perfect offsets for all parts of path and parameters for matching against rules for automated substitution. Variable references to future request header parameters were generated for both explicit esi variables and implicit app rule matches.

     I researched zlib's format for gzip and found gzip's format has a fallback mechanism to emit cleartext when compression fails, so the format explicitly supports embedded cleartext understood by all zlib clients (like browsers). By adding a very small extension to zlib's public api, I found I could emit content in cleartext in gzip on demand, letting me later patch those cleartext parts without impairing compression. Doing this only needs regeneration of a trailer's crc32, with very high speed (6ms/MB) compared to slow compression latency. As a result, I could pre-compress compiled web pages in gzip format as a template, with variables for substitution written in cleartext. The VM for my compiler was able to emit byte perfect dynamic transformations of new gzip streams from the templates with request variable values substituted.

     I designed and wrote all the threadsafe LRU and hashmap features for the cache, with refcounted compiled template pages replaceable on the fly with new OWS samples, without ceasing service of HTTP requests.

     I wrote all the disk i/o, file path processing, format versioning, and file formats of compiled web pages. I specialized my stream apis several ways to select subsets of other streams as i/o sources so (eg) the VM could read from a span of bytes in the template the same way from gzip and cleartext versions.

     I implemented cache invalidations per the esi spec with an added degree of difficulty: because many requests mapped to one template page, we could not tell which responses might be invalidated by any given request pattern rule until just before processing a request. So I had to apply invalidations as quickly as possible, even when as many as 50 thousand rules might be queued on a single app instance. So I compiled and sorted queued rules in a form that permitted fastest possible rejection of a rule against any given incoming request. Hashmaps were used in part of filtering, so rules could only be considered when targeted parameters were present.

     One of my last optimizations at Pivia added a server feature supporting both etags in the HTTP protocol and a related trick to stop browsers from even asking whether old content had changed. This was motivated by an observation that pages referencing many (say 70 or 80) images in a shopping site had a high latency to finish display even when individual objects were served with (typically) four of five millisecond latency. The problem: the end user's browser would ask whether each image had changed, incurring round trip latency per image. I invented a way to stop this using etag style version numbers:

     My HTML parser was already locating and parsing embedded page URLs with byte perfect positioning, so it was trivial to add dynamic URL mods when a path matching rule said a given URL was one needing an etag style transformation. Each server maintained a local hashmap of objects of this sort, each annotated with a current hash used as etag version number. So I looked for such URLs in this etag hashmap; on a hit, I had a version number I could append as suffix on original URLs. When a browser asked for such URLs (recognizable by distinctive suffix), I did two things:

1. removed the distinctive suffix from the URL
2. told the browser to cache the object forever

     This algorithm had the following effects: 1) a browser never asked for the same image twice when the etag version number was the same, and 2) when the image actually did change, so did its etag version number, and the new etag suffix was written for subsequent embedded URLs, causing a browser to ask for any changed image since its URL was new to the browser.

over articulation ¶

     For some reason, I'm often most proud of my older son's sense of humor when it reminds me of my own. Tonight he imitated the lead penguin's voice from Madagascar (Skipper aka Joe, cf Penguins_Madagascar): a voice actually done by director Tom McGrath (I see now on wikipedia). First my son quoted a part of dvd extras where McGrath says, "All I have to do is overarticulate everything I say."

     Then he started singing along with the radio in Joe's voice, turning Nickleback's lyrics into a zinging parody, "This is how you remind me of what I really am." Then in Joe's voice he explained how he loved karaoke, demanding the boys put on another of his favorite songs. It's like he completely gets the idea of hammering a silly premise into the ground, in pursuit of anything it might imply.

decisions ¶

     I've been making a really tough job decision this week. I never had to figure out anything this hard before. Depending on the line of reasoning I take, I can come up with good reasons to choose either way. It's comparing lines of reasoning that's hard, since they often have nothing to do with each other. Flipping a coin sounds dumb. But in the absence of enough information, it might be the same thing. Both choices have things I can't ground in evidence, so I can't predict my experience in six months and I'd rather I could.

     (So far I'm still where I've been for the last 13 months, which hasn't been disclosed here, and won't be. I no longer talk about employers. In fact, I don't really want you to know who I am, either, without a little effort.)

resume style ¶

     I rewrote my resume a couple weeks ago, and I used a completely different style. I used the way I write this blog as a template for a new conversational approach. It seemed a little risky, but I didn't see how it could do any harm. When it was done, I thought it was very effective. Some parts seem so good I want to repost sections here. Somehow it was exactly the right way to explain complex details. Among other things, it is unusually honest, straight forward, and clear. It's quite a long resume, now with more than just bullet points.

     But since it's a resume, it's quite sparse and fast moving, with little more than blitz side references to things I'd normally expand a lot. Curiously, this reads well. Roughly speaking, each job was a small story: why I joined, what was expected of me, what did I do, how changes relate to one another, etc.

parallelism ¶

     In the long run, code I show here will use native threads to get more things done in parallel with multiple processors, and to avoid waiting on system calls that block. For example, I'm likely to do all file system i/o from a different thread than the main thread, starting very early in development.

     But I'll aim for a runtime needing less synchronization for threads, with less mutable state visible in multiple threads. I expect I'll even try Erlang style lightweight processes which simply don't share mutable state, thus needing no synchronization. (Without mutable state, a process cannot test whether it shares address space with another proces, and one heavy weight process can safely host many lightweight processes.)

     Even so, multiple threads will be necessary for more performance, to use available processors and avoid blocking. Generally it's best to have at least one thread per processor and more threads than the number of concurrent blocking operations. However, even though details are interesting, for my own peace of mind I expect to write little about threads on this site.

     I find it easy to write safe and effective threaded code, but explaining how and why it works to others is far more effort than writing correctly threaded code. More than ten times as hard: let's guess 25 times as hard. What's the reason for this? It's like discussing the number of angels that can dance on the head of a pin: it's never grounded in empirical data, or in easily seen demos showing precise issues. Proving you're right is hard, encouraging long and stupid arguments with folks of persistent mien.

     In short, you have to pay me. Or I have to owe you the answer for good will reasons. :-)

     Of course my readers are generally very smart. But this doesn't mean unwilling to be difficult. In fact, usually the reverse: many smart folk get invested in butting heads with others as a professional stance. (If you object to any imprecise statement I make on threads, find someone else to harangue who likes it.)

thread lore ¶

     Today I'll write a bit about threads for a friend, from a C++ perspective. I might not ever write about use of threads in my þ runtime library, as it is now and how it evolves later. My day jobs in recent few years show me threads are the most complex thing I discuss with other engineers. That means I can't afford to discuss threads for free in software I write as open source: it would draw questions I haven't time to answer.

     But here's an idea for visualization when thinking about threads: imagine both code and data are written on transparent sheets of film, like acetate for an overhead projector. You need at least one copy on a separate sheet per (hyper?) processor in the system, and another copy for each thread to maximize chance of conflict.

     Now imagine sliding all the transparent sheets around to maximize possible overlaps in access to read and/or write. Play devil's advocate, and try to cause worst conflict allowed by synchronization and memory barriers. It's essential you imagine all code is running multiple times at once with worst case patterns of synchrony and lack of it, with worst case schedule changes like context switches in places maximizing conflict.

memory hierarchy ¶

     Modern processors have multiple truly irritating ways to make scenarios worse than you imagine, even when you use a many-acetate-sheet analogy from above. Both time (instruction ordering) and space (processor caches) can be fuzzed into Heisenberg-ish uncertainty compared to your nice discrete mental images. As result, neither when something happens nor when it's visible to another processor are well defined, and can vary.

     This means unsafe scenarios lurk in code that looks simple, when you try to test whether another thread has done something by looking at bytes changed in memory. Processors can perform changes in parallel, and visibility to another processor can be nondeterministic.

     When you have a choice and it's feasible to arrange, it's better (safer and less complex) to communicate with data that's immutable when visible to more than one thread. You can sometimes arrange this is true in special cases; for example, a refcounted object visible to multiple threads is actually visible to exactly one thread when the refcount hits zero, if you've done refcounts correctly. (And thus your destruction code need not be threadsafe since it runs in one thread.) But above zero, refcount changes must be carefully atomic — multithread safe.

pthread mutex ¶

     My sample code assumes you're using pthread mutexes for mutual exclusion, and that you have a C++ wrapper for using pthread mutexes, so naked C apis for pthreads are unnecessary. I make this assumption to avoid focus on the api, which is mostly irrelevent. I'll show you my own C++ wrapper for this later, in an update. What you use in Java for this has the same net effect.

     This code assumes your C++ wrapper for pthread mutex is named Mutex and that you have an RAII (resource acquisition is initialization, cf RAII) convenience class named MutexLocker locking a mutex in the constructor then unlocking in the destructor. So the pseudo code above would lock g_my_mutex for the remaining scope of foo() before unlocking again.

     (Note this is not guaranteed to work if foo() is called at static init time from another compilation unit, because then g_my_mutex's constructor might not have run yet, so the mutex doesn't work before the constructor's call to ::pthread_mutex_init(). You must never assume it's okay to call code to initialize objects at static init time, unless the code was designed for use at static init time. You can make a mutex wrapper lazy init on first use, but this is just as confusing as the presentation below.)

memory barriers ¶

     I'm working up to a short piece on double checked locking (cf Double-checked_locking), in which I'll casually claim it's possible to avoid the worst of "Heisenberg" uncertainty in processor behavior, by using a function imposing enough barrier in both time and space to ensure sufficient instruction ordering and processor cache consistency in the calling code.

     But it's hard to make it always work in a processor independent way, both portably and safely. First let's look at a simple C++ function approximating the idea I want to elaborate more. At some point I'll ask you to use some imagination to apply in your specific case. I won't spell out every detail.

     If you put identity() in its own compilation unit, the compiler will have a hard time proving that the original input param is always returned, so the call to identity() cannot be optimized away. Maybe some code somewhere changes the value of global g_dummy_pointer; the compiler needs to run all the code in identity() because it can't figure out how to remove it.

     The main reason I used the mutex here was to insert a memory barrier (cf Memory_barrier) to sync processor caches in the calling code. I could also have used a platform specific bit of assembler to lock the bus when (say) incrementing an atomic integer. But that would have been non portable. Locking a pthread mutex ought to have the same effect portably. (Typically atomic int code for any given platform is easily found in the pthread mutex implementation.)

     The identity() function itself stops compiler reordering of instructions in calling code, if subsequent code depends on identity()'s return value, which is our reason to use it. We don't care how fast this code runs since we expect to call it rarely. You only need it to be paranoid about foiling compiler and processor instruction reordering. (I'm not usually this paranoid. I ship on an appliance where it's feasible to check I'm getting desired results unportably.)

     You might ask yourself: why all this fuss? Because threads were not built into C++ directly with native support; instead threads were added as a library, with subtle pitfalls. To write C++ code you hope is truly portable and safe from interesting thread races at the compiler and processor levels, you might need something bizarre like this.

     The presentation here might be more clear if I used another type besides void* for the parameter. But let's look at an example of use to see my intentions.

     From this perspective, the implementation of identity() might replace the input param with a different instance: say one cached earlier. The returned after value might depend on the total initial state of param before, so a correct compiler must completely finish constructing before, and only then call identity(). So this usage should be able to force after to point at a complete and valid instance of Foo that's ready to use.

     In the presence of instruction re-ordering, the Foo::Foo() constructor need not have been called by the time identity() runs, unless the compiler sees a dependency forcing the constructor to run first. Compare the code above to the following unsafe code:

     What's unsafe about that? Instruction re-ordering can assign the newly allocated memory block address to variable g_global_foo before the constructor has been called. If another thread tests whether g_global_foo is non-nil as a sign it's safe to use, this assumption will be false if the constructor has not run.

     Even if you add more intermediary variables, nothing forces the constructor to run before assignment to g_global_foo except explicit dependency like the call to identity(), which might need constructed state.

     I imagine this section helps show why I don't like to discuss threading with other engineers, except in a professional work context. I can guarantee what I said so far is grounds to argue for someone.

double checked locking ¶

     Okay, here's the way I usually write double-checked locking code in C++ when I need to make a shared global resource on first use, when this might occur under contention from multiple threads. (Obviously this usage tends to correspond to a singleton design pattern, but the singleton pattern in no way clarifies the problem.)

     The main idea in double-checked locking is speed after first use. Once a singleton is created, it should no longer be necessary to bother with mutex. We only want to provide mutex for the first thread or threads that actually try to create the singleton on first use.

     When the first test condition fails, we lock a mutex (here assuming the pthread mutex wrapper I mentioned earlier) and check the very same test a second time, because multiple threads can the mutex and second test. We want only one thread to test false twice.

     I use s_ref==&s_done as the boolean showing init is done out of habit from my Netscape days, when my code had to work on all platforms. Globals on Windows notoriously contained 0xefefefef and static init never occurred. So I picked another way to see what I wanted that didn't require initialized global state. (I still use the same tactic today for code that can be called at static init time when order of init is not defined.)

     Using s_ref==&s_done as the test condition also has the advantage of still working if s_ref is only partially updated before a context switch, on platforms that can manage to reveal part of a pointer updated to another processor. Then I try to avoid putting the address of s_done into s_ref until after g_single_foo is updated with the pointer laundered by identity(), which aims for force a memory barrier requiring the constructor to run.

     If you're feeling really paranoid, you can ask whether it's possible for s_ref==&s_done to become visible in another processor's cache before g_single_foo appears changed. You could always add one more memory break after assigning g_single_foo, like this:

     In the real world I don't use the identity() function unless a coworker knows enough to start discussion, because its existence is hard to defend.

simpler locking ¶

     Here's a rewrite of last section's code to better organize semantics with two functions instead of one. We assume inner_foo() returns only after Foo::Foo() is called. It's a reasonable assumption, isn't it? Can C++ let you instantiate objects that never get constructed before returned as values? Wouldn't that surprise you? But let's assert the obvious, just in case.

     This rewrite avoids bizarre use of identity() at the cost of using two methods where one seems enough. What are odds some maintainer rewrites this to merge the two? What if someone adds keyword static before the definition of inner_foo(), encouraging the compiler to inline inner_foo()? What if a compiler inlines inner_foo() anyway? Well, the assert remains.

     In principle, this version shouldn't be very different from the original. But I feel a lot better about this one, in terms of it looking less goofy, and in terms of expecting inner_foo() always constructs g_inner_foo before returning. You need only worry whether updating pointer g_outer_foo is atomic. (On Intel, yes.)

versioning ¶

     Content versioning keeps coming up lately. Or maybe I'm just sensitive to it: I've written code to version things for many years, from database content streams to refcounted memory blocks. Today I touch a couple ideas related by versioning — some immutable and some not. Mutability is orthogonal, but often closely tied by intent, if not necessity.

     But the focus is usually safety. Version numbers let you see change that might otherwise trip you up. Versioning content in immutable networks lets you "change" graphs by swapping new nodes for old ones without actually mutating old ones. (See copy-on-write — aka cow — for an intro to simulating mutation by substituting new copies.)

     Copy-on-write is an ancient technique, in tech years. But folks keep trying to patent use of cow in new domains, even when the only novelty is using cow, because it's one of the primary classic means of optimization. And patent clerks seem happy to encourage optimization in new domains, like file systems. The patents sound like the dumb internet patents (I'm doing xyz... but on the internet). I'm doing to build file systems out of trees (duh) and I'm going to version them with cow (duh). Um, did you see other file systems and databases published years before? Did you notice they use cow? Didn't think so.

generation numbers ¶

     You can see and respond to changes in data by counting changes. You can poll changes to invalidate, to lazy notify, or to drive synchronization tricks. Change counts are called generation numbers — that's the term I use most in my day job. I've also used the term seed for numbers changing when other content changes. I first heard Deb Orton at Taligent use seed to mean this, around 1990. Seed, life, change, generation, version: same thing with slightly different spin.

     About a week ago I told someone my approach to bullet proofing refcount systems, and described how I do it lately in þ. (I know: I should accompany this post with code. I would, but it's already late. Maybe I'll add a code update later.)

     When you use a base class for refcounted objects, at least one byte should be a generation or version number assigned on first creation and remaining immutable for the object's lifetime. Your destructor should alter it (say one's complement), and new generation numbers must be kinda random: I like to use a byte from a pseudo random number generator.

     Then, when you acquire a ref to any refcounted object, you also copy its version number and keep it together with the ref. (My smart ref templates copy version numbers from a refcounted object into the smartref.) The version number tells you the ref is still good. If it's ever wrong, you should assert. It's the same as a SEGV: your memory integrity is toast.

     In distributed systems you can't assert() when version numbers are wrong, if they come from outside your process. (Otherwise anyone could send you a die now message just by sending you bad generation numbers.) But it's a good idea to make message refs self validating with version numbers.

     (Hash-based etags are just version numbers; same idea.)

     I keep thinking of new ways to use version numbers to invalidate indexes, but it's all variations of one idea. In scaling servers, this kind of invalidation lets you avoid cost bursts, so scrubbing is a pay-as-you-go operation in high granularity. (You never want to spend 100% of cpu for linear invalidation, since your traffic might bounce and back off.)

     But it always sounds clever to someone who hasn't used it before. Maybe it's partly my fault when my explanation sounds so crisp: I'm told, hey, you should patent that. And I'm thinking, yeah sure, I'm going to patent version numbers. (Of course if we add the words "on the internet" maybe it will fly.)

     My most frequent use of version numbers is in iterators which can't tolerate changes in an underlying collection. I need only count problematic physical changes in the collection, and keep a copy of this count in an iterator. Unexpected change is conflict with another thread mutating data (bad news). It's not supposed to happen, and that's exactly why you look for it.

cow patents ¶

     I ran across David Hitz's blog in passing, and one of his headlines caught me eye: NetApp Sues Sun for ZFS Patent Infringement, which was of great interest to me since the patent would also affect my IronDoc database from the mid 90's for the exactly the same reason Hitz says ZFS infringes: I used copy-on-write in IronDoc, too, which was modeled as a file system in a file. (So the model resembled that of ZFS.)

     Here's a leading quote from the abstract of patent 5,819,292 (added emphasis is mine):

A method is disclosed for maintaining consistent states of a file system. The file system progresses from one self-consistent state to another self-consistent state. The set of self-consistent blocks on disk that is rooted by a root inode is referred to as a consistency point. The root inode is stored in a file system information structure. To implement consistency points, new data is written to unallocated blocks on disk. A new consistency point occurs when the file system information structure is updated by writing a new root inode into it. Thus, as long as the root inode is not updated, the state of the file system represented on disk does not change.

     In other words (if you permit me to simplify), Hitz wants to patent use of cow in the context of file systems. Um, have you ever heard of monads? The use of tree snaphots with immutable data pre-dates filing of this patent, so the patent is invalid. My design for structured storage at Apple for OpenDoc sounds a lot like this patent, but I did it just a few months after the May 1995 filing date, so my work alone doesn't invalidate the patent. But let's look at something that probably does:

     Circa 1996 at Apple I helped review Kala: a database proposed for use as MacOS's file system: The Kala Basket (pdf). The following material was published in 1991. One third page section is entitled 4. Brief Kala Overview and begins with this paragraph (all emphasis is original):

Kala's data model is simple and largely untyped. Kala manages data elements of arbitrary size consisting of bits and embedded references. These data elements are termed monads. Monad references are essentially pointers into other monads. The salient feature here is that monads are immutable. Once created, a monad can never be deleted or modified. It may become inaccessible⁵ (if it does Kala will recover its physically allocated resources), but the monad's identity is never discarded.

     While Kala's terminology is a little aggressively non-standard, the result is semantically equivalent to a file system composed of log-structured immutable content. And the obviousness of this is emphasized by the fact Apple's ATG (advanced technolgy group) was considering use of Kala as a file system replacement. There's a body of research on the topic of log-structured file systems, like Kala, that probably also invalidate patent in question.

     Anyway, my purpose here isn't to treat this material thoroughly. (I didn't even search for other Kala references that might explain the whole cow treatment of trees more explicitly.) And I don't want to participate in further discussion about the patent. Nor do I want to talk about my own database work in this context. I just wanted to bring Kala to the attention of folks interested in comparing patent claims to materials published about Kala pre-dating the WAFL patent.

     (My own database design work merely applied standard block shadowing techniques and standard copy-on-write technique to dict and blob btrees. I also mapped free space with bitmaps that avoided changes to old content. And yet these are essentially the interesting parts of the WAFL patent. I knew myself there was no novelty in what I was doing. I could point at existing literature on log-structured file systems as precursors of IronDoc.)

pretty printing ¶

     If I wasn't writing this I'd finish pretty printing cyclic objects and shared structure tonight. I started Sunday after tweaking my pretty print format to generate just what I wanted to see. Below is an example of output when echoing a just read s-expression containing special cases of interest. Here I aimed for a max line width of 64, but the writer allows small overshoots when the fit is better.

brackets ¶

     You can see a couple uses of square brackets instead of parentheses. Some Scheme dialects take parens or brackets interchangeably; I want to read such syntax without tweaking, so I accept brackets as alternatives for parens. The reader only requires they balance properly. When a pair begins with a bracket, this sets a bit in the pair's tag that means, "Write list enclosed with brackets when I'm first pair." So the pretty printer echoes brackets where so read.

quoting ¶

     You can also see examples of quotation by quote, quasiquote, unquote, and unquote-splicing, which print in the same form as the read macros.

line limits ¶

     Not shown is gnarly code to measure how long an expression will print before printing, to see if we want linebreak and indent. I wrote complex code to make that efficient: once I pass a line length threshold I give up measuring more if a line gets "too long."

     I didn't want to write a parallel series of measuring methods to gauge length in parallel to printing methods, so I just print everything twice: but only up to a current line limit. In the first printing pass to measure, I use a special stream subclass throwing away all bytes written, retaining length only. It folds streams into length.

safe cycles ¶

     Since I like pretty printers safe by default, I'll do cyclic object and shared structure detection unless otherwise requested. You should be able to print anything without fear ugly things could happen. So in particular, directly and indirectly cyclic structures must not only avoid infinite loops, they must print themselves nicely so a reader can recreate original structure sharing and cycles.

     To do this, my first pass over the structure to be printed populates one hashmap Hp with containers (like pairs) I've seen before, and another hashmap Hp2i with address-to-integer mappings for each container I see more than once. Obviously the first hashmap stops me from revisiting pairs I've seen before, preventing cyclic visits.

     The second pass prints everything on first visits, using the recleared first hashmap Hp again to track visited pairs known by the second Hp2i (which maps the set of known repeats). But any object known by the Hp2i map is prefixed by a reference of the form #n= on first visit, where n is the integer associated with the container's address.

     When containers known by Hp2i are seen a second time, they are replaced completely with a gloss reference of form #n# where the n is the same number printed earlier when first encountered. This shows duplication in a structure and replaces self cycles with labeled references.

     For example, #1=(pig . #1#) is a cyclic list whose first member is symbol pig, followed by the list itself again: an infinite list of pig if you don't look for loops. I'm about ten minutes short of finishing the above. But then I need to finish my reader's building of such structures.

branding ¶

     This evening I started poking through images I found when I created this site; I ran across one (see below) oddly appropriate for my own themes. I never expected to post it, but so far I've done little to play up the site name — not enough branding.

     So all content below is just an excuse to post Briar Patch from a game I once played heavily. The card's color is the one I played most: green. I had a huge collection of green cards; I kept trying to make a winning deck with green.

magic cards ¶

     I think it was the summer of 1994 I started playing a collectible card game named Magic The Gathering. By the fall of 1994 I played at Stanford every weekend with folks who knew how to play — like 1994 world champian Zak Dolan. (Just now I found Zak's online championships diary, evoking memories.)

     Over many weeks I played a few dozen games with Zak at Stanford with the other hard core magic players. My specialty was "speed decks" which launch a horde of tiny violent creatures. I played a lot of angles later showing up in well known tournament decks. (I had one nearly the same as Vice Age.)

     I played multi color, favoring green slightly. Everyone learned to kill my Birds of Paradise as soon as they appeared. Even more amusingly, folks learned to counter all kinds of cards normally thought a benefit to the other player as well, like Howling Mines: my deck was so fast and destructive it was suicide to let me get more cards. So denial decks usually had to counter my mines.

     Folks designing tournament decks wanted to play their designs against me, to see if I could finish them before their new concept worked. If my opponent didn't defend early, my deck won on the 4th, 5th, or 6th turns — usually the 5th. Zak was one of my customers, since I was the only one with really scary horde decks. My green and multi color decks were best. The result of playing Timetwister was always spectacular. My white decks were tops, but not as fun to play.

trading ¶

     I spent at least as much time trading cards as playing. I was willing to buy cards at market price, and since I knew current value very precisely, I added a lot of liquidity to the local card market. I was happy to buy or sell as part of a large and complex trade, so cards had dollar value almost as hard as cash. During the summer and fall of 1994, card prices soared by 10% every two weeks like clockwork. (That summer I worked at a company making software for trading financial instruments, like derivatives — coincidence?)

     I was a local expert at three way trades. I learned how to solve resistance in moving cards, to get what I wanted. Once I learned everyone's wish list (I asked everyone what they sought) I could think of a sequence of trades making everyone happy on terms better than they expected. I had a head for visualizing transactions optimizing what folks weighted as value. I lost sleep over trading cards. I dreamed about trading cards. I didn't get over it until I left the finance software company and returned to Apple in 1995.

     Somewhere in the middle I learned something about people I hadn't known before, at least in practical terms: everyone wants something slightly different, but you can still make equitable trades for value — provided each side has goals defined. (I was unable to trade with folks who wanted nothing, or who could not quantify wants enough to enable trades.)

     The same sorts of market effects often make sense in software too, when trading space for speed or speed for scale. The next thing I designed at Apple featured trades between memory and secondary storage, always with the aim of getting a result valued more than state preceding a trade. So my database work was transactional in more than one sense.