29 February 2008

This week I learned...

I spent most of this week sick in bed, but I did discover that:

  • According to the Jameel Poverty Action Lab at MIT, the cheapest way to improve attendance in Kenyan schools is mass deworming.

  • There's a guy removing Garfield from Garfield comic strips. The result: “an even better comic about schizophrenia, bipolar disorder, and the empty desperation of modern life”.

  • Guy Steele wrote The TELNET Song. Before webcomics, if hackers wanted to laugh without leaving the net, they had to make their own humor.

Also, I like this poem: “The Trash Can”.

23 February 2008

This week I learned...

  • A shibboleth is language that sends cultural signals beyond its plain meaning. The word comes from a fairly amazing Bible story.

    Now I want a word for language invented to annoy, like “Democrat Party”.

  • Aristotle believed slavery to be “expedient and right”. All the best arguments by learned apologists for slavery in the U.S. South were from his writings, particularly in the Politics.

  • Incidentally, Aristotle thought democracy was a crummy form of government. And, in his ideal society, homeschooling would be banned.

  • There are expressions of the Golden Rule in the scriptures of many religions.

  • I don't understand what this means, exactly, but the x86 instruction set contains an FNOP instruction. The manual describes it as a floating-point no-operation instruction. How this might be different from a regular NOP I don't know.

  • So there's a widely known interview question: write a function to count the number of bits of a 32-bit int that are set to 1. This function is called the population count—that link describes a surprising use for it.

    The last time I tested this, summing 4 queries into a 256-value lookup table is fastest for 32-bit integers, faster than the awesomely clever bit-twiddling solution. I shouldn't have been surprised. The lookup table fits easily into cache. The bit-twiddling solution has a lot of dependencies; the CPU can't find any instruction-level parallelism there.

    Anyway, what I learned a week or two ago is that future Intel chips will have an SSE instruction, POPCNT, that does this, in parallel, for several words at a time. (Someone I mentioned this to commented that he doesn't want to be fired for pronouncing that.)

  • Often when I write these blog entries, I'm still unsure of the significance of some of the things I've just learned. For example, I learned something about Java monitors (or pthreads condition variables, which are the same thing). When thread 1 notifies, waking thread 2 on a separate CPU, the lock associated with the monitor ensures that CPU 1's writes are flushed to main memory and CPU 2 sees them before thread 2 starts running. There's no need for write-barrier magic in Object.notify itself.

  • Apple's Shark profiler has a feature that lets you compare two profiles. But the result is calculated by comparing percentages, not comparing the absolute number of samples. So, for my purposes, useless.

  • The .mshark files produced by Shark are gzipped binary property lists, but the actual samples are stored in there as raw binary data which I haven't tried to decipher.

08 February 2008

This week I learned...

Special double issue! Two weeks' worth of trivia, including a week spent in Mountain View.

  • Most Japanese streets do not have names.

  • With GNU Radio, you can buy some cheap hardware, plug it in, and your computer becomes a GPS receiver, a garage door opener, an HDTV tuner, an AM/FM radio, a cell phone. This is subversive technology. Hollywood wants regulations that would ban such nonsense.

  • Radio waves bounce off meteor trails. This is actually usable as an alternative to satellite communications, depending on the application. For example, the USDA has a network of solar-powered snow depth sensors that use meteor trails to phone home.

  • On the Mac, Alt+[ types a left double-quote mark and Alt+{ types the right one. Much better than typing “.

  • GCC generates a floating-point instruction for isnan(x); it amounts to x != x (NaNs are not equal to themselves). Intel engineers claim integer instructions can be much faster, on x86 at least, due to floating-point exception nastiness.

  • Xavier Leroy has written a provably correct “lightly-optimizing” back-end that compiles a subset of C to PowerPC machine code. Sandrine Blazy and Zaynah Dargaye have hooked it up to a provably correct front-end.

    A little background here. A compiler works by lowering code step by step from relatively high-level internal representations, like parse trees, to successively lower-level representations, until it gets down to machine code. At each level it can apply optimizations: some optimizations, like common subexpression elimination, work at a very high level, and some work at the machine-code level. Stack up enough lowering passes and optimizations, and you've got yourself a compiler. There's considerable interest these days in using formal methods to prove the correctness of program transformations. First you define mathematically what it means for two programs to be equivalent. Then you prove that a given transformation always produces a result that's equivalent to the original. Stack up enough provable lowering passes and optimizations, and you've got yourself a provably correct compiler.

    This kind of work has been done for subsets of Java, but C's pointers and undefined behavior present some nasty problems. Leroy's work is hedged in with disclaimers, but it's still pretty amazing stuff, and an interesting read. For example, he proposes the following sneaky technique. Write your compiler pass however you want, and don't bother proving it correct. Then just verify the correctness of the transformation afterwards (for the particular program being transformed). It's apparently much easier to prove a verifier correct than the transformation code itself. Plus, you can then tweak the transformation without redoing any proof work. The only risk is that your transformation is incorrect, in which case your compiler flunks out with an internal error at compile time.

  • The PDP-11 had probably the nicest of all the widely used CISC instruction sets.

  • emacsclient is my new EDITOR. It connects to my existing Emacs process, if any (I had to put (server-start) in my .emacs file) and loads the file there.

  • Speaking of emacs: M-/ is the autocomplete key. It's moderately smart. You also want to know C-x r SPACE x (save current cursor position in x) and C-x r j x (jump to the position saved in x).

  • When you run a configure script, it generates a config.status file in the build directory. That file is helpful when debugging stupid build problems.

  • In the late-1990s, there were two computer science research projects called Dynamo, both involving dynamic optimization: one at Indiana University and of course the awesome one, at HP Laboratories.