Irate Nate's weblog

on boggle solver performance

Wed, 06 May 2009 21:05:00 CDT

The other day somebody wrote a blog post concerning the performance of Boggle solvers written in C and in Common Lisp. Humorously titled “I want to believe”, the article (predictably) made its way to reddit, where it was met with all manner of comments. The dominant theme was that the C implementation wasn't much to write home about, the Common Lisp code was possible worse, and it was likely that the performance of the Common Lisp version could be improved. Several people even outlined plausible ways in which this could be done. The author of the original article wrote a “yeah, the burden of proof is on you and you have nothing” response to the comments generated.

This post is the response the author has been looking for. I will say up front that my modifications were nearly exactly what the commenters on Reddit suggested, so I'm not bringing much new to the table, just showing that they were right all along.

So, the numbers. My machine is a 1.6 GHz Core Duo with 2GB of RAM, running 32-bit Ubuntu. My Common Lisp implementation is SBCL, version 1.0.28.7, compiled with Unicode support and without thread support; the C compiler is “gcc (Ubuntu 4.3.2-1ubuntu12) 4.3.2”. Timings for the C program, on my machine:

@bishop:~/boggle-master/src/c$ time ./boggle --test --dict ../../dict/english_270k.txt < \
../../output/sample-1000x1000.txt > w ; tail -n 40 w
*** stack smashing detected ***: ./boggle terminated
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6(__fortify_fail+0x48)[0xb7e7d6d8]
/lib/tls/i686/cmov/libc.so.6(__fortify_fail+0x0)[0xb7e7d690]
./boggle[0x804b117]
======= Memory map: ========
08048000-0804c000 r-xp 00000000 08:04 1922146    /home/froydnj/boggle-master/src/c/boggle
0804c000-0804d000 r--p 00003000 08:04 1922146    /home/froydnj/boggle-master/src/c/boggle
0804d000-0804e000 rw-p 00004000 08:04 1922146    /home/froydnj/boggle-master/src/c/boggle
08cfb000-1b137000 rw-p 08cfb000 00:00 0          [heap]
b6562000-b7503000 rw-p b7d55000 00:00 0
b7c8d000-b7d83000 rw-p b7c8d000 00:00 0
b7d83000-b7edb000 r-xp 00000000 08:04 903780     /lib/tls/i686/cmov/libc-2.8.90.so
b7edb000-b7edd000 r--p 00158000 08:04 903780     /lib/tls/i686/cmov/libc-2.8.90.so
b7edd000-b7ede000 rw-p 0015a000 08:04 903780     /lib/tls/i686/cmov/libc-2.8.90.so
b7ede000-b7ee1000 rw-p b7ede000 00:00 0
b7ee7000-b7ef4000 r-xp 00000000 08:04 128135     /lib/libgcc_s.so.1
b7ef4000-b7ef5000 r--p 0000c000 08:04 128135     /lib/libgcc_s.so.1
b7ef5000-b7ef6000 rw-p 0000d000 08:04 128135     /lib/libgcc_s.so.1
b7ef6000-b7efa000 rw-p b7ef6000 00:00 0
b7efa000-b7f14000 r-xp 00000000 08:04 189007     /lib/ld-2.8.90.so
b7f14000-b7f15000 r-xp b7f14000 00:00 0          [vdso]
b7f15000-b7f16000 r--p 0001a000 08:04 189007     /lib/ld-2.8.90.so
b7f16000-b7f17000 rw-p 0001b000 08:04 189007     /lib/ld-2.8.90.so
bfa02000-bfa17000 rw-p bffeb000 00:00 0          [stack]
Aborted

real    0m57.012s
user    0m54.023s
sys     0m2.916s

Yes, that's out of the box, no modifications to the C program. Lovely, eh? The performance of the original Lisp program:

@bishop:~/boggle-master$ ./solve-boards.sh < output/sample-1000x1000.txt > w; tail -n 40 w
[...lots of output scrubbed...]
Evaluation took:
  248.506 seconds of real time
  248.331519 seconds of total run time (240.755046 user, 7.576473 system)
  [ Run times consist of 10.492 seconds GC time, and 237.840 seconds non-GC time. ]
  99.93% CPU
  413,140,979,480 processor cycles
  534,709,752 bytes consed

The performance of my optimized version:

@bishop:~/boggle-master$ ./solve-boards.sh < output/sample-1000x1000.txt > w; tail -n 40 w
[...lots of output scrubbed...]
Evaluation took:
  68.062 seconds of real time
  68.000250 seconds of total run time (64.704044 user, 3.296206 system)
  [ Run times consist of 1.908 seconds GC time, and 66.093 seconds non-GC time. ]
  99.91% CPU
  113,153,248,150 processor cycles
  50,750,728 bytes consed

Not quite four times faster and around 10x less consing. Not bad. Common Lisp is within roughly 20% of the peformance of C for this particular program. I'm fairly certain that all my changes to the Common Lisp code are “non-algorithmic”, so modifying the C implementation is a moot point. I'm also a little leery of modifying a program that falls over in the first place; I have better things to do with my time than debug C programs. At least when the O'Caml or Haskell people come around with performance benchmarks, their test programs work perfectly the first time.

The patches against git version 02a0a24257260c825f13da764fa54bdbc01dd14a (the project does not have a publicly clone-able URL) are located at http://method-combination.net/lisp/files/boggle-solver-patches/, if you want to see how things work. I admit to having a large number of non-performance enhancing cleanup patches in there; rather difficult to code if you're constantly fighting some non-idiomatic coding style.

Performance notes to take away from this lesson:

If you want to write fast Common Lisp code, you absolutely need to understand how array types work in Common Lisp. If you aren't declaring things as simple-array or simple-vector, you're probably doing something wrong. And that goes doubly so if you are doing anything involving strings on an implementation that supports Unicode (where base-char and character are probably different). You also need to have some idea of what upgraded-array-element-type does and why saying something is of type (VECTOR (VECTOR STRING *) *) is probably not going to perform the type-checking/inference that you think it might.
Likewise for declaring numeric types. If you have variables that you aren't declaring as fixnum (or subtypes thereof), single-float, double-float, or complex variants of the float types, then you're probably doing something wrong. That is, declaring things as integer, or worse, number is Not Helpful for performance.
Listen to the compiler. The compiler tells you a lot of helpful stuff. The original code of the benchmark had some #+sbcl bits scattered about protecting slightly stricter type declarations than their #+ccl counterparts. A comment like “ccl doesn't barf on null pointers” usually lurked close by. First of all, “null pointer” is a category error in Common Lisp. Second of all, SBCL complaining about things (whether in the compiler or a runtime with (SAFETY 0))...was correct. (I've had the same sort of experience with Lispworks.) If the compiler complains at you, fix the problem. Only turn things off or tune them out if you're absolutely sure you understand why the compiler is whinging at you and if there's nothing you can do about it.
format ~A is useful, but expensive. One of the biggest wins was converting the printing of the words to use write-string. Do use FORMAT for your everyday printing needs, but if you need some performance, look at Common Lisp's other IO functions, too.
Sprinkle optimization declarations judiciously. The original code contained a global (declaim (optimize (speed 3) (space 0) (safety 0) (debug 0) (compilation-speed 0))). But most of the runtime (95% in the final optimized version) was spent in two functions. Putting the declarations in just those functions would have achieved the same effect. As an added bonus, the compiler will probably just tell you about ways those particular functions can be improved, rather than pointing out the hundred different ways some utility function you barely use can be improved.
Don't compile with (SAFETY 0). Just don't. You can get surprisingly far, performance-wise, with type-checking and array bounds checking turned on. If you feel like you must live dangerously, make absolutely sure that everything works and that you are not lying to the compiler about types (see above note about listening to the compiler) before flipping the switch.
Make your code runnable from the REPL. Life is too short to spend constantly waiting for your shell script to compile and/or load all your files before it gets to the business of running your program. You should be able to invoke your benchmark with a single form typed in at the REPL.
If you are translating code from C, converting #defines to defparameters is generally not what you want. You want defconstant instead.
Don't needlessly allocate things inside loops. This should go without saying.

Finally, this post by Juho Snellman sums up benchmarking efforts for Common Lisp (or most any other high-level language, I'd imagine) quite well.

michael abrash on larrabee

Sat, 02 May 2009 23:11:00 CDT

Michael Abrash is writing some extremely informative articles over at Dr. Dobb's about Intel's new graphics chip, Larrabee. The first article covers the new instructions and general capabilities of the chip. The second article discusses how to do rasterization on Larrabee--specifically, rasterization that takes advantages of the parallel processing power Larrabee brings to the table. (The techniques he discusses in the second article remind me of the adaptive mesh refinement techniques I looked at in grad school.) He's promised to write at least one more, dealing with writing shaders for Larrabee.

worm beauty

Thu, 30 Apr 2009 18:21:00 CDT

Great lines in children's literature, from Diary of a Worm by Doreen Cronin:

My older sister thinks she's so pretty. I told her that no matter how much time she spends looking in the mirror, her face will always look just like her rear end.

python coroutines

Fri, 24 Apr 2009 23:10:00 CDT

Good evening, class! Your assignment tonight is to read David Beazley's slides on Python coroutines from PyCon 2009. As the gurus say, contemplating the lessons found therein produces expansion of consciousness without abuse of substance.

scrod

Wed, 15 Apr 2009 20:32:00 CDT

My children have a book called Lightship. As you might imagine, it is about lightships (Wikipedia is slightly too pedantic on this one, I think). The book has lovely drawings and is just repetitive enough to drive the points home for the kiddos while having enough variety to make you enjoy reading the book. We have a hardback edition; the back cover has a sailor on the ship reading 99 Ways to Cook Scrod.

I would not have known what scrod was, except for a raid in Serpentshrine Cavern. I think we were standing on the platform just after Lurker and had a bit of time to kill. Our guild leader, who hails from Boston, began telling scrod jokes. Perhaps it was a tradition in the guild prior to my arrival, but scrod jokes were a regular feature of guild chat for the next four instances.

I have been WoW-free for six months today (or nearly so; I forget the exact date I last signed on). I think of my guild and raiding every time I read Lightship to the girls. I miss WoW.

tab cleanup

Tue, 14 Apr 2009 12:38:00 CDT

When I find things that I might want to blog about, I leave a tab open in my web browser to remind me. Cleaning time has come.

A really, really really long post about gay marriage that does not, in the end, support one side or the other. Worth reading in its entirety. To quote from near the end of the article:
Three laws. Three well-meaning reformers who were genuinely, sincerely incapable of imagining that their changes would wreak such institutional havoc. Three sets of utterly logical and convincing, and wrong arguments about how people would behave after a major change.
So what does this mean? That we shouldn't enact gay marriage because of some sort of social Precautionary Principle
No. I have no such grand advice.
My only request is that people try to be a leeetle more humble about their ability to imagine the subtle results of big policy changes. The argument that gay marriage will not change the institution of marriage because you can't imagine it changing your personal reaction is pretty arrogant. It imagines, first of all, that your behavior is a guide for the behavior of everyone else in society, when in fact, as you may have noticed, all sorts of different people react to all sorts of different things in all sorts of different ways, which is why we have to have elections and stuff. And second, the unwavering belief that the only reason that marriage, always and everywhere, is a male-female institution (I exclude rare ritual behaviors), is just some sort of bizarre historical coincidence, and that you know better, needs examining. If you think you know why marriage is male-female, and why that's either outdated because of all the ways in which reproduction has lately changed, or was a bad reason to start with, then you are in a good place to advocate reform. If you think that marriage is just that way because our ancestors were all a bunch of repressed bastards with dark Freudian complexes that made them homophobic bigots, I'm a little leery of letting you muck around with it.
The Antikytheea Mechanism Research Project. From the project overview:
More than a hundred years ago an extraordinary mechanism was found by sponge divers at the bottom of the sea near the island of Antikythera. It astonished the whole international community of experts on the ancient world. Was it an astrolabe? Was it an orrery or an astronomical clock? Or something else? For decades, scientific investigation failed to yield much light and relied more on imagination than the facts. However research over the last half century has begun to reveal its secrets. It dates from around the 1st century B.C. and is the most sophisticated mechanism known from the ancient world. Nothing as complex is known for the next thousand years. The Antikythera Mechanism is now understood to be dedicated to astronomical phenomena and operates as a complex mechanical “computer” which tracks the cycles of the Solar System.
David Noble's Battle to Defend the Sacred Space of the Classroom.
Since the splash made by his first distance-education essay, Mr. Noble has published three online sequels expanding the argument. In the latest, published late last year, he provides a history of correspondence schools in the late 1800's and early 1900's. In the essay, which Mr. Noble hopes to expand into a book, he traces several parallels between such efforts and today's distance-education ventures.
Early education-by-mail efforts, he says, were marketed with the same enthusiasm as today's Internet courses. “The chief selling point of education by means of correspondence, the firms maintained, was personalized instruction for busy people,” he writes.
By 1926, Mr. Noble writes, more than 300 private correspondence schools had sprung up. Around the same time, about 73 traditional colleges and universities were running correspondence programs, too.
But, Mr. Noble argues, such individualized instruction turned out to be more expensive than the institutions had anticipated. To cut costs, he says, institutions soon lowered standards for correspondence teachers and expanded their workloads, diminishing the quality of instruction and prompting many students to drop out. The number of such programs eventually fell.
I recently read David Noble's The Religion of Technology, having been prompted by this article to look into his works. The book was quite good and deserves a separate post.
OpenSecrets.org goes OpenData. Should be interesting to see what people come up with as far as visualizations.
GTD Guru David Allen and His Cult of Hyperefficiency. The title is slightly provocative, but worth reading for a deeper look at the man behind GTD. “Allen is remaking the self-help tradition for the information age.” is one of the best bits of the article.
Papers to read for unladen-swallow. unladen-swallow aims to be a compiled, faster implementation of Python (get it?). The list is pretty good, although it could definitely be quite a bit longer.
Deleted from Wikipedia. Not sure if it's been updated recently, but interesting nonetheless.
It's time to kill the idea that newspaper are essential for democracy. Yes, please.

on rss

Mon, 30 Mar 2009 13:49:00 CDT

I twittered about giving up Google Reader recently. I had a short exchange with Ryan in which I think he feared that I was burying my head in the sand. Herb blogged some thoughts about my decision and I was DM'd about my decision as well. So herewith is the larger context of my decision.

I am not burying my head in the sand; I am still following a moderately large list of feeds, but I'm doing it with Venus instead of letting Google automate my life. I still have my Gmail account. I purchased a G1, knowing full well that it would want to autosync a good chunk of my data to Google's servers. However, I have sync turned off and the account for my phone is a different one than the account I normally use for email. Paranoid? Maybe.

With Venus, I get to decide when I read my feeds. I realize that I have this choice with Reader. Having Reader open 24-7, however, changes the decision process--it's always there, it won't hurt if I check. It's like having a second email account. With Venus, it's consciously deciding, “Hey, I'm going to go tap commands into my terminal and wait for a while while it checks everything for me.” The psychology behind the decision is quite different. Now, if only I could make the same sort of psychological barriers in place for checking email...

Granted, I had to put in some elbow grease to make Venus work. Venus uses html5lib for some form of HTML normalization. I'm sure that it does wonderful normalization according to the HTML5 specification, but browsers today don't really handle HTML5. (Hint: <b></b> is not the same as <b/> to a modern browser.) So I had to write some cleanup scripts to make rendering work right. I also had to chase down some strange bugs with the Genshi templating bits that made the first parts of feeds come out duplicated. Which wasn't so bad, except for getting a double dose of every Bunny comic. (I find it humorous that's the first hit on Google for “bunny”.) And even that was not always unpleasant. But just knowing that there was a bug compelled me to fix the bug.

But besides the psychological aspect, the “share” button was way too tempting. It was tempting to share an article discussing some philosophy or policy or whatever and know that said article would show up in the “inbox” of a person who did not share that philosophy or policy or whatever. It was the internet equivalent of cluster bombing. I'm fairly sure sharing the articles I did didn't change the minds of the intended readers, much less were the articles read in the first place. (Don't worry, dear reader, you were not the intended target.) I don't have a “share” button with Venus and I think that's a good thing. Furthermore, reading what other people thought were interesting articles...meh. I haven't missed them.

I read my feeds once, maybe twice a day now. Minus a couple of hours of ranting at Venus for being braindead prior to fixing the issues cited above, I'm enjoying my choice. And if I can't access my feeds because I don't have my computer with me, I don't think that's a particularly bad thing.

ironclad 0.27

Sat, 28 Mar 2009 11:08:00 CDT

Ironclad 0.27 has been released and uploaded to the usual place. There are a few fixes for Allegro 8.1, a fix for LispWorks 5.1, and a fix for when the user has set *print-case*. HMAC has been made somewhat more efficient and now supports reinitialize-instance. 64-bit variants of SHA have been added along with SHA-224. Finally, several kinds of Gray streams subclasses now support write-sequence.

bad samaritans

Fri, 27 Mar 2009 19:49:00 CDT

I love simply browsing through the stacks at libraries--I find some of the most interesting books to check out on the spot or to file away for later reading. One such book I found recently was Bad Samaritans: The Myth of Free Trade and the Secret History of Capitalism by Ha-Joon Chang. I enjoy reading a contrarian book now and then, although the subtitle of this one sounded a little over-the-top. The giant-sized endorsement on the back from Noam Chomsky also made me pause. But I checked it out anyway, figuring it didn't cost me anything and I could always stop if it got to be too weird.

I read the entire book. At no point was it too weird, and it made a lot of points that made a lot of sense.

Chang's basic point is this: the rich countries in the world go about promoting free trade and capitalism (“neo-liberalism”) as the cure to all ills for smaller, less developed countries. The story is that such tactics have worked to propel these rich nations into their current positions and will work the same sort of improvements in living standards and personal incomes in the smaller countries. However, if you look at history, the numbers tell a different story:

This story misrepresents the process of globalization among the rich countries during this period. These countries did significantly lower their tariff barriers between the 1950s and the 1970s. But during this period, they also used many other nationalistic policies to promote their own economic development -- subsidies (espeically for research and development, or R&D), state-owned enterprises, government direction of banking credits, capital controls, and so on. When they started implementing neo-liberal programmes, their growth decelerated. In the 1960s and the 1970s, per capita income in the rich countries grew by 3.2% a year, but its growth rate fell substantially to 2.1% in the next two decades.

Examples are given throughout the book of particular industries from particular countries who have benefitted from the protectionist policies of their governments: Toyota, Samsung, Nokia. The examples are not limited to the 20th century, either; he discusses how Britian's protectionist policies towards its textile industry helped propel Britian to the position of global influence it enjoyed in the 18th and 19th centuries. And that when Britain abandoned its protectionist policies, it was largely became it was no longer the dominant force that it once was, mostly because of the growing influence of the United States--which derived in part from its own protectionist policies.

(Interesting tidbit about Adam Smith's The Wealth of Nations: Smith did indeed campaign for the lifting of various protections for British industries--but only because they were mature industries and no longer needed the state to prop them up. It was time to grow up, to remove the protections, and subject the companies to actual market forces--not unlike kicking a college graduate out of the basement. (Indeed, Chang later likens the care and education of his six year old son to the protection that should be afforded to infant industries.) The father of free trade praised the Navigation Acts, which severly restricted the ability of British colonies to produce particular goods. History is sometimes a wee bit more complicated than the history books tell you...)

During the 1960s and the 1970s, when they were purusing the `wrong' policies of pretectionism and state intervention, per capita income in the developing countries grew by 3.0% annually. As my esteemed colleague Professor Ajit Singh once pointed out, this was the period of `Industrial Revolution in the Third World'. This growth rate is a huge improvement over what they achieved under free trade during the `age of imperialism' (see above) and compares favourably with the 1-1.5% achieved by the rich countries during the Industrial Revolution in the 19th century. It also remains the best that they have ever recorded. Since the 1980s, after the implemented neo-liberal policies, they grew at only about half the speed seen in the 1960s and the 1970s (1.7%). Growth slowed down in the rich countries too, but the slowdown was less marked (from 3.2% to 2.1%), not least because they did not introduce neo-liberal policies to the same extent as the developing countries did.

The same pattern is cited numerous times throughout the book: countries do not necessarily grow--and often wither instead--when adopting neo-liberal policies and countries do not necessarily wither--and often thrive instead--when they use “bad” policies.

The main criticism of the book falls upon the backs of the “rich countries” who, having achieved wealth, forbid other countries from utilizing those same strategies (“kicking away the ladder”). The rich countries, through the demands of the IMF, World Bank, and WTO, impose neo-liberal policies on countries that would benefit far more were they allowed more latitude in choosing their economic policies. Through tight monetary policy, draconian intellectual property laws, and the imposition of low trade barriers (which benefit the rich countries more by giving them access to cheaper goods), the developing countries are held back from actually growing those industries that will bring them sustained growth in the future.

(As an aside, I finished Postwar by Tony Judt recently. I only skimmed the last several chapters covering modern Europe, but I was amused at the economic posturing coming out of the EU. The EU has tigh restrictions on what sort of monetary policy entering countries must have: limits on government debt incurred on a per year basis, limits on total government debt, that sort of thing. Turns out that a couple of years ago, Germany and France (the two largest members of the EU) deliberately flouted these rules in an effort to stimulate the economies of their countries. When cries of protest were raised from other member nations (particularly nations only recently admitted who had contorted their economies to fit EU rules), Germany and France essentially said, “We are not beholden to your rules.”)

The above arguments comprise the core of the first three chapters of the book. The later chapters work out particular parts of the argument, discussing foreign investment, public vs. private enterprises, intellectual property laws, financial policy, and dealing with corrupt and/or undemocratic countries. The book is well-written and well-researched. I particularly appreciated the wide range of examples that Professor Chang gives: he doesn't just beat the drum and say, “This policy didn't work for country X, that policy didn't work for country X, free trade and capitalism are broken!” Instead, it's, “This policy didn't work for countries M-Z, that policy didn't work for countries I-R, these policies didn't work for countries A-N...why don't we acknowledge that there are problems here?” I also appreciated the discussion of key economic theorems about free trade...and the reminder that those theorems came with conditions that are often glossed over and/or unrealistic. If those conditions are not present, then the conclusions of the theorems are not valid, and arguments based on those theorems fall apart.

I do remember taking an economics class in college where the textbook was Paul Krugman's International Economics and the drum of free trade was pounded particular heavily. And during my time in that course or shortly thereafter, I do remember making myself persona non grata at a friend's house, if only for a short time, by incessently repeating the mantras of that course. If nothing else, Professor Chang's book has shown me--again--that the story in the real world is somehwat more complicated than the charts and graphs of an economics textbook suggests.

on remembering history

Thu, 26 Mar 2009 22:40:00 CDT

Those who cannot remember the past are condemned to repeat it.
--George Santayana

The above is a quote I found fairly early in life. I thought of it upon reading some of the comments in the LWN article Better than POSIX?:

In a previous life, I worked on memory ordering models in CPUs and chipsets. During this recent ext4 hubbub, it dawned on me that the issues with ordering and atomicity in high-performance filesystem design may be isomorphic to memory ordering. Even if that's not strictly true, there's probably a lot to be learned by filesystem designers and API writers from modern CPU memory ordering models, in any case, because memory ordering is a well-explored space by this point in the history of computer engineering; and I don't just mean the technical semantics, either, but the whole social aspect, too, i.e., how to balance good performance with software complexity, how much of that complexity to expose to application programmers, who often have neither the time nor the background to understand all of the tradeoffs, let alone dot all the “i”s and cross all the “t”s, etc. Anyway, changing rename's semantics as you suggest would be the equivalent of a “release store” in memory ordering terms, and seems to be exactly the right kind of tradeoff in this situation.

I'm guessing few people have made the connection because memory ordering is something that you start caring about when you're doing concurrent (shared-memory) programming and such programming hasn't been terribly widespread. And because all the world's an x86 machine and few people have been exposed to something like PowerPC or worse, Itanium. (And lest my comments be interpreted as coming from an expert on memory ordering, I am far from it. My own experience with atomic instructions and memory ordering comes from reading through the code for locking primitives in Linux and trying to understand papers on the Java memory model.)

Thanks for that comment --- it's amazing how much knowledge we're rediscovering in computing. It's almost as if we're coming out of some kind of dark age.
One thing that struck me was a comment on a Slashdot story about a “breakthrough” in data center energy optimization. The comment showed that the problem of deciding when to boot up additional servers to meet demand was isomorphic to the problem of steam boiler management --- right down to the start-up and constant energy costs --- and that the problem had already been thoroughly addressed in literature from the turn of the last century. (Emphasis in the original.)

Heh. That comment reminded me of a blurb I read about a week ago and cannot remember the location of it. The essential message was: Need a thesis topic? Go back 10 years in the computing literature and find an idea that can be dressed up with modern terminology and jargon. Nobody will notice.

And that reminds me of a comment I once read about hot new web technologies and discovering the next one. (I think it was related by Paul Graham, but I cannot find it on his site.) The essence was that today's hot web technology is simply a Unix service dressed up for the modern era. ICQ? talk. Blogs? .plan files. Web forums? Usenet. I suppose Twitter is finger. So if you want to invent the next hot web property, figure out what service Unix provided that hasn't be translated for a generation that's never seen a terminal.

status update

Thu, 12 Mar 2009 20:24:00 CDT

Wow, I haven't posted on here in over a month. Shame on me. A brief update on various activities and interesting sites, not necessarily in any sort of order, is in order. I'd prefer to split it up into nice, easily digestable, one-topic blog entries. Like one should have in a properly managed version control system. But you know those commits into version control that are just a torrent of unrelated stuff? This is the blogospheric equivalent.

I took a business trip to Texas to visit one of our partners. My flight through Chicago was delayed by several hours due to weather; I didn't get to the hotel until about 2:15AM. I had an 8AM meeting the next morning and an hour of travel time. The flight and lack of sleep notwithstanding, the trip went extremely well: the meetings were extremely productive and face-to-face time is always worth the investment.

I bought a T-Mobile G1 and SIM-unlocked it so I could use it with my current AT&T plan. I admit to being partially inspired to do this by a Twitter status talking about reading code at meals. I thought, “Why couldn't I take source code on my phone to read in various places?” In the same vein, I can read Project Gutenberg works on my phone. It's a little silly because I don't use any of the GPS, Bluetooth, or 3G/EDGE bits on the phone--it only gets used as a phone and a miniature computer with a Wi-Fi connection. One might think that I should have gotten a netbook instead, but a phone is more fun, easier to carry everywhere, and more socially acceptable for some value of acceptable. I'm waiting for the ARM netbooks to come out, personally.

I haven't really used the phone in its intended capacity yet because I haven't completed writing the viewer app for such files yet. (I thought about installing Debian on my phone and using vi/less/emacs, but I haven't worked up the courage to root my phone yet.) Writing the app means Java and GUI development, both of which make me feel like a complete newbie when programming. Eclipse is the preferred development environment for Android (the operating system on the phone) and is nice enough, I suppose. The code completion is somewhat weak, buffer management is horrible, and the navigation leaves something to be desired, though.

I went to a bachelor party in Chicago last weekend. We played Whirlyball and went to dinner at 437 Rush. Excellent establishments, both of them. I had the tastiest Alaskan King Crab, enhanced by Mojo's recommendation of brown butter. I also discovered a blend of alcohol that I am willing to drink: the B-52 shot. Yum. (I only had one, if you must know.) After dinner, instead of going out to a bar, I went back to the hotel with Mojo, Dave, and Jerry, and we played Dominion until the wee hours of the morning. A quality weekend.

I read Watchmen on the way home from Chicago. As a literary work, I think it's very well done: the “watch” theme is cleverly woven throughout, the multiple stories being told dovetail cleanly, and the basic storyline holds up well over 20 years later. That being said, I found it depressing: Good is going to get outflanked by Evil and that's just the way things are. After reading a bit about the 'net, though, I think you can argue thusly from the final page of the comic: either Good and the story Good has to tell about things is merely a crank story (still depressing), or Good really does Win, although you don't know for sure (potentially less depressing). And of course Good as represented by the final page and elsewhere is not exactly a shining moral example, which plays into the literary quality of the work. Anyway, I've thought about the book off-and-on after reading it, which I can't say for many books recently.

I checked out two books on the library recently: one about Peter Drucker, Inside Drucker's Brain, and a “best of” compilation, The Essential Drucker. Reading Drucker--at least in the edited compilation, the originals may not be quite as lucid--is exactly like reading your favorite business author of the current day. Christensen, Collins, Allen, Kotter, take your pick. Except that Drucker was writing it all decades ago. Fabulous stuff.

Akoha looks interesting, although it suggests that Charlie Stross was not too far off the mark when he wrote about SPOOKS in Halting State. Papers in Computer Science looks like a promising blog; I am tempted to flood him with suggestions from compilers, but will refrain for the time being. Cool Tools looks like a somewhat less pretentious and significantly more useful Gizmodo, of a sort. Das Netz looks like an interesting documentary, although I'm not sure if one needs to view the film after reading the extensive review. And if you want to figure out why Volkswagen's stock price looked so crazy in October 2008, you'll definitely want to read about Porsche hacking the financial system.

stem cells

Sun, 08 Feb 2009 13:49:00 CDT

I read Stem Cells: A Political History a couple weeks ago and made a note to post about it on my blog. I'm going to quote liberally from it, but you should go read the whole thing:

And on November 20, 2007, two independent teams published papers--one in the journal Cell, and the other in the journal Science--about the production of pluripotent human stem cells without using embryos or eggs or cloning. And with a silent thump, the topic suddenly fell off the front pages of the nation's newspapers...Basically, however, the breakthroughs in the fall of 2007 meant that the issue of stem cells was off the political table: If scientists can make pluripotent stem cells without creating or destroying embryos, then the pro-life community will no longer resist the research; and if the pro-lifers don't resist it, then their opponents will no longer use the topic to attack them. The news reporting--in the New York Times, particularly--has undergone an astonishing change over the last year: Where once they hyped stem cells as the looming cure for everything from Alzheimer's to diabetes, they now routinely explain how far scientists are from curing anything with stem cells...
In November 2005, the work of the Korean superstar Hwang Woo Suk was revealed as a fraud. For all the major scientific journals, embryonic research had become what Robert P. George and Eric Cohen would call “a litmus test for being pro-science and the central front in the alleged war of scientific reason against religious barbarians.” Science magazine had fast-tracked Hwang's work to let America know the cost of President Bush's refusal to fund embryonic stem-cell research. Scientific American published a mea culpa for all scientific journals, and it is, George and Cohen pointed out, “remarkable for both its honesty and remorse: `Hwang is guilty of raising false expectations, but too many of us held the ladder for him.'”
Not that the revelations of the Korean fraud changed much. Nature Biotechnology carried a report in April 2006 which declared that “the fear that United States researchers might lose ground to their international counterparts in human embryonic stem-cell research now appears to have become a fact.” The Washington Post began its news report on the study by telling its readers that “American scientists are falling behind researchers elsewhere in stem-cell discoveries because of U.S. limits on the use of federal funding.”
In fact, according to one survey, 46 percent of the scientific papers on stem cells were published in the United States. As Eric Cohen noted, the report in Nature Biotechnology actually demonstrates that “more than 85 percent of all the published embryonic stem-cell research in the world has used the lines approved for funding under the Bush policy. . . . It is clear that a great deal of the work done abroad has also involved these lines, even though most of it could not have been funded by the NIH. The lines are used, in other words, because they are useful, not only because they are eligible for federal support.”...
The history of the stem-cell debate is a study of what happens when politics and science reach out to each other. The politicians were guilty, but the scientists were more guilty, for they allowed--no, they encouraged--politicians to make stem-cell research a tool in the public fights over abortion, public religion, and high finance.
In the small demagogueries of a political season, the science of stem-cell research became susceptible to the easy lie and the useful exaggeration. A little shading of truth, a little twisting of facts--yes, the politics corrupted the science, but the scientists willingly aided the corruption. And with this history in mind, who will believe America's scientists the next time they tell us something that bears on an election? We have learned something over these years: When science looks like politics, that's because it is.

(Yes, I would like to grouse that the article doesn't actually provide citations for the research articles/surveys/etc. that support its position.)

But then just this past week, I read Has change come to biology? Stem cell research under Obama, which plays a significantly different tune:

President Obama's promise to restore science to its rightful place has raised the hopes of biologists that there will be swift action on what many view as a serious hindrance to biology: restrictions on the use of human embryonic stem cells (hESCs). Federal funding of hESC research has been limited to lines created before August 9th, 2001--nearly nine years ago--and most of the acceptable lines have since been found to be inappropriate for clinical research; ethical issues involving informed consent affect the remaining handful. On Tuesday, the New York Stem Cell foundation hosted a panel that discussed how a lifting of the Bush-era restrictions on hESC research is likely to change hESC research.

So who's telling the truth here? If you read the First Things article, one comes away with the impression that embryonic stem cell research is (nearly) dead in the water and that there are much more promising avenues for research. Reading the Ars Technica article, one might think that interesting biological research on stem cells was all but halted during the Bush administration years and that we are finally opening our gates to Progress. There are other, smaller conflicts: a hint of conflict between the numbers cited by Eric Cohen (85% of the embryonic stem cell research in the world has been done with Bush-approved stem cell lines) and the Ars Technica claim that “most the acceptable lines have since been found to be inapproprite for clinical research.” Is that 85% figure just because research has found the lines are not useful and therefore Cohen (and First Things) is shading the truth, or is Ars just blowing smoke?

I do not believe that First Things would willingly lead its readers astray, but I also note that the authors of the article in question were not actually scientists, whereas John Timmer (author of the Ars Technica piece) was writing from a scientist-populated panel hosted by The New York Stem Cell Foundation--which obviously does have a dog in this fight.

So...who do you believe?

halting state critique

Sun, 08 Feb 2009 13:30:00 CDT

Courtesy of Crooked Timber, a variety of essays on Charles Stross's work have been posted. I only read the review of Halting State and I thought it was quite good. I imagine the others are of similar quality and do an equally good job of expanding on the themes on which Stross builds his books.

git code snippet

Sun, 08 Feb 2009 13:24:00 CDT

I ran across this little snippet while reading through Git source code the other night:

	cnt = (len < 4) ? len : 4;
	len -= cnt;
	do {
		acc = (acc << 8) | (acc >> 24);
		*dst++ = acc;
	} while (--cnt);

What does the code do? It deposts a value consisting of CNT bytes, left justified in ACC, into the byte buffer DST in big-endian format. Clever, huh?

unconvincing australian

Wed, 28 Jan 2009 20:38:00 CDT

Funny bit from a recent post at the TF2 Official Blog:

Why is the Sniper such a fake Australian? Aren't several members of the TF2 team Australian?
Yes, it's true, the Sniper is a fairly unconvincing Australian. Most of his lines make him sound more English than Australian, and the voice actor is clearly an English actor faking an Australian accent. As for why we didn't fight to make him more authentic, we though it was appropriate that he was about as convincing an Australian as the Demoman is a Scotsman, or the Medic a German.

Touché.

building on culture

Sun, 25 Jan 2009 14:32:00 CDT

Given my recent read of a biography of Jackson Pollock, I thought this bit, from Culture Making by Andy Crouch, was spot-on:

[Pierre] Boulez and [John] Cage each explored the possibility of culture without culture, culture that tried to escape the culture that preceded it. Yet culture has a way of sneaking in even when it is not wanted. The modern painter Jackson Pollock, who tried to completely eradicate the difference between culture and nature, artist and gravity, produced paintings that have an insistent figural quality to them. As abstract expressionist Makoto Fujimura writes of Pollock, when art students try to imitate Pollock's seemingly grade-schoolish splatters and drips, their work does not begin to compare: Pollock's work is imbued with a tradition of painting, no matter how insistently the artist tries to overthrow that tradition. It would not be great painting without the tradition in which Pollock was trained and shaped.

Culture Making is one of the best books I've read all year, both this literal calendar year and the logical last year. I suspect it will wind up high on the list at the end of the calendar year, as well.

common lisp and javascript

Sat, 24 Jan 2009 21:29:00 CDT

I haven't done a lot of Lisp hacking lately. I've done a little bit of experimentation with assembly routines in Ironclad and a little hacking for GNU tar extensions and pax headers in ARCHIVE. The bulk of the twiddling with Lisp lately has been experimenting with a visualization tool for our home finances.

I record all our finance bits (well, at least what we spend on a day-to-day basis; nothing like tracking my 401(k) or anything like that) in Ledger. Ledger is great as far as it goes, but is somewhat lacking in being able to make pretty pictures--which is fine. But my wife would like to get a picture of where the money goes in our household, so I sat down to try to put something together for her.

Version 0.1 was about ten minutes of thinking about creating hand-drawn graphs with something like CL-GD. That sounded like a lot of tedious work, and it wouldn't necessarily be more accessible to my wife than teaching her the various invocations of Ledger at the command line, which was right out. So I quickly moved onto version 1.0.

Version 1.0 was an exercise in having Ledger generate XML output, parsed by CXML, which was then turned into web pages served by Hunchentoot, screen-scraped by MochiKit, and then be turned into snazzy plots by PlotKit. This actually worked pretty well; programming in JavaScript is fairly painless, MochiKit is pleasant to use, and PlotKit is straightforward enough. Even better was that I could just stick the whole thing on a server in our house and my wife could view the ins and outs of our budget with no difficulty. But scraping these tables was tedious and it seemed like there ought to be a better way.

Version 2.0 came about when I realized that I could expose the XML that Ledger generated as JSON URIs, and virtually all of the page layout and so forth could be driven by JavaScript. So I grabbed YASON for generating the JSON, scrapped a good bit of the JavaScript I had written, and went off to the races. This worked much better and I was able to learn how to use the nifty asynchronous bits of MochiKit to boot.

One bit about using YASON: the approved way of turning Lisp bits into JavaScript objects is to send a hashtable through YASON. This is uncontroversial, but I found myself wanting to pass a dictionary to JavaScript to fake keyword arguments. Common Lisp's hashtables are not really suited for such one-off bits (no literal syntax)--using an alist or a plist is much easier for this sort of thing. (Yes, I could use custom Lisp-side objects, but that's almost more heavyweight than hashtables.) YASON didn't support this sort of usage, so I tweaked it accordingly:

(defmethod json:encode ((list list) &optional (stream *standard-output*))
  (labels ((json-alist-p (list)
             (or (null list)
                 (and (consp (first list))
                      (json-alist-p (rest list)))))
           (json-plist-p (list)
             (or (null list)
                 (and (keywordp (first list))
                      (consp (rest list))
                      (json-plist-p (cddr list)))))
           (encode-key/value (key value)
             (let ((string (symbol-name key)))
               (json:encode-object-element string value)))
           (json-encode-alist (alist)
             (json:with-output (stream)
               (json:with-object ()
                 (loop for (key . value) in alist
                    do (encode-key/value key value)))))
           (json-encode-plist (plist)
             (json:with-output (stream)
               (json:with-object ()
                 (loop for (key value . rest) on plist by #'cddr
                    do (encode-key/value key value))))))
    (cond
      ((json-alist-p list) (json-encode-alist list))
      ((json-plist-p list) (json-encode-plist list))
      (t
       (write-char #[ stream)
       (let (printed)
         (dolist (value list)
           (if printed
               (write-char #, stream)
               (setf printed t))
           (json:encode value stream)))
       (write-char #] stream)))
    list))

Much better. I considered string-downcase'ing the symbols used for keys, but while that would be easier for simple cases (no need to || symbols), it prevents you from actually having capital letters in your object properties.

The result so far is that I have about 400 lines of Common Lisp and about 150 lines of JavaScript; that gets several useful views onto the data: a yearly summary, a breakdown of each spending category by month, and a breakdown of each month by category. The next steps are to add some links between them, an easy way to get information on individual transactions in the latter two views, and some information on how we're doing versus the budget that we've decided on. Ironclad and ARCHIVE can wait, for the moment; I'm having too much fun with this.

return addresses

Wed, 21 Jan 2009 22:48:00 CDT

I was writing bills tonight and had to write my address several times in the return address area. Theoretically, this shouldn't be needed: those nicely typed addresses showing through the clear plastic should always be there, are always right, and will always get the bill to the correct destination. But I am slightly paranoid about what happens if the return stub gets jostled a bit and the address no longer shows through (especially for some bills that are significantly smaller than the envelope, like the water bill)...so I write my address on every single envelope.

Now, I've already seen a solution to this, one that doesn't require the wastage of address labels: our previous health insurance company used to print their own address as the return address on the envelopes. So the bill was virtually guaranteed to get to the right place. (IIRC, it wasn't the corporate address, either; it was the actual P.O. box or whatever billing address they were using at the time.) Why can't more companies do this?

childhood tokens

Tue, 20 Jan 2009 22:40:00 CDT

Quoth What Girls Want, an extended review of the Twilight phenomenon:

One of the signal differences between adolescent girls and boys is that while a boy quickly puts away childish things in his race to initiate a sexual life for himself, a girl will continue to cherish, almost to fetishize, the tokens of her little-girlhood. She wants to be both places at once--in the safety of girl land, with the pandas and jump ropes, and in the arms of a lover, whose sole desire is to take her completely. And most of all, as girls work all of this out with considerable anguish, they want to be in their rooms, with the doors closed and the declarations posted. The biggest problem for parents of teenage girls is that they never know who is going to come barreling out of that sacred space: the adorable little girl who wants to cuddle, or the hard-eyed young woman who has left it all behind.

I would like to believe that raising adolescent daughters will not involve these wildly moodish females, that somehow the foundation Tricia and I are laying in these years will bear fruit a decade hence. But that's not what I quoted the above passage for. I quoted it for the opening sentence.

The opening sentence rings true in my life, in discussions with my wife about what to keep and what to throw away. I had a protracted discussion over Thanksgiving with my wife, who was horrified that I would so casually consign my high school yearbooks to the trash. My reasoning was that I haven't looked at them in a decade or so...and I don't imagine I'll look at them again anytime soon. Why bother? She maintained that my current and potential future children will get a charge out of a window into their father's former life. After much pleading and enlisting the help of my mother to find a suitable “hiding place”, Tricia saved the weighty tomes of pictures from the scrap heap. Sigh.

However, after going through my few remaining things at my parents' house, I did save a few tokens of childhood, or at least days gone past:

A Lego Technic F1 race car (along with all my other Legos; the race car was still assembled, though);
C.S. Lewis's Space Trilogy;
New Worlds: In Search of the Planets, which I hope my daughters will enjoy perusing in later years for the photos and (gasp!) information, despite being somewhat out of date by then;
A nearly complete collection of Tom Swift, Jr. books 1-30 in decent condition. I think these will probably get sold on Ebay or to Half-Price Books;
A couple of books by Samuel Delany and A.E. van Vogt (I think);
A picture of a friend and I from high school (Tricia: “who's this, hmmm?” me: “we were not romantically involved”);
The coup de grace, although not from my childhood: The Bell System Technical Journal, Vol. 57, No. 6, Part 2, July-August 1978. Topic? The Unix Time-Sharing System. Win.

Hey, my wife keeps her old baby teeth, yearbooks, and hand-written journals from elementary and middle school, I keep old sci-fi books and technical journals. Seems fair enough to me. (We no longer have the baby teeth, however.)

3d fractals

Sun, 18 Jan 2009 23:16:00 CDT

40 Amazing 3D Fractals Using Apophysis is full of win. I particularly like Ulliroyal's splash, the interwoven light sticks by Babymilk, the budding flower by MyNameIsShailo, Spiralum by AmyL, and the underwater mushroom city by RedHotCold. Props to 50ft and Ted for the link.