Firefox 3 is nearing release. Check out what's new, especially the Awesomebar, which has changed my life.
(Awesomebar itself is the work of superhacker Ed Lee, but it relies on Places, the new bookmarks and history system, 2+ years in the making.)
If you're interested in security, especially the difficulty of giving users correct, actionable security-related info at a glance, read about Firefox's new site identification and malicious site detection features.
In the children's section of the Nashville public library, the mother lode of folk tales is in the nonfiction section. Aha!
There's a whole family of egg-eating snakes that swallow eggs bigger than their heads, squeeze out the insides, and spit out the shell.
According to this blog post, native speakers of Chinese are gradually forgetting how to write.
According to Jared Diamond, out of 148 species of large, wild, terrestrial herbivorous mammals, only 14 have ever been successfully domesticated. (Guns, Germs, and Steel.)
Every time I go to the Nashville library, I leave feeling like I've just picked somebody's pocket. It's a wonderful library. (I don't know that it's particularly unusual in this regard.)
The past three or four weeks are a bit of a blur, but:
Just before he died, Beethoven claimed to be working on a Tenth Symphony. Fragments of this were discovered among Beethoven's sketchbooks in the 1980s (!), and musicologist/composer Barry Cooper stitched together a highly speculative, but performable, first movement.
I knew that John Harrison invented the first clock that could keep time on a ship and that such clocks cracked the longstanding problem of determining longitude at sea, leading to the first accurate maps. (H1 was his first attempt; his masterpiece, H4, was a 5-inch watch with a diamond-studded movement.) I didn't know that Harrison faced competition from an astronomical method relying on careful on-ship measurements of lunar occlusions of certain stars, huge tables of laboriously pre-calculated data, and maybe four hours of additional calculations to be done on the ship. It was a usability disaster, as one might expect. But at the time, the idea of making a clock run reliably on a pitching, rolling ship apparently seemed even crazier.
Bill McCloskey's memoize is a replacement for make in a few lines of Python. The complete source code fits on my screen. This is the coolest hack I've seen all year.
The word goodbye comes from the saying “God be with you”. According to the American Heritage dictionary's etymology note, “A letter of 1573 written by Gabriel Harvey contains the first recorded use of goodbye: ‘To requite your gallonde [gallon] of godbwyes, I regive you a pottle of howdyes,’ recalling another contraction that is still used.”
According to Wikipedia, the lungfish has the largest genome of any vertebrate. But as of today, Wikipedia does not say anything about the lungfish's lungs! (I usually try to contribute in cases like this, but here I haven't a clue.)
On the Mac, if ls -l output has an @ symbol here:
-rw-r--r--@ 1 jason jason 54838 Sep 27 2007 #tamarin 9-25-07.colloquyTranscript
then the file has extended attributes. These are used, for example, to mark files as “saved from the web”, triggering a warning if a user tries to open the file.
I guess there's no point denying that J, my four-year-old, has a bit of an aggressive streak. Paraphrased from memory:
J: I'm going to try and splash him into that swimming pool. He's a bad guy. (The “bad guy” is a toy car.)
If he misses, he's going to be shot out of a cannon that will shoot him so hard, he will crash into the sun, and then he will blow up and his car will blow up.
(J. rolls the car off the table at a mixing bowl; it falls in.)
Me: Hey, you got him into the swimming pool.
J: (casually) Yeah, there's sharks in there.
I'm just glad he has it in for the bad guys.
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”.
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,
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.
Special double issue! Two weeks' worth of trivia, including a week spent in Mountain View.
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.
NestedVM can take any program that GCC can compile and run it in a Java VM. It does this by compiling the program to a MIPS executable and then translating the MIPS machine code to Java bytecode. Now, there isn't any high-level type information in a MIPS binary, so there isn't any in the bytecode. Instead each instruction is translated to something that bangs on some large int arrays that represent virtual memory. (The sbrk system call is implemented using new int[].)
The paper has sentences like, “The NestedVM runtime fills the role typically assumed by an OS kernel.” :)
I think the point of this, aside from being cool, is to make C++ code run anywhere Java does. I don't know how many platforms have JVMs but not gcc back-ends, though. (GCC actually has a back end for Java, but it can't handle C++.)
So if you know C, you know that && has short-circuit behavior: if the left-hand side is false, the right-hand side doesn't get evaluated. This week I learned that if the right-hand side of && is simple enough and has no side effects, as in x > 0 && x < N, a good compiler emits code that evaluates it anyway, essentially treating the && as &. A conditional branch is slower than a few redundant instructions.
Objective C exceptions on Mac are implemented using setjmp/longjmp. They don't cooperate with C++; if you throw an Objective C exception across a frame containing C++ objects, the destructors don't get called. This triggered some bugs in Mozilla, which apparently has Cocoa GUI code or something. (Sorry, I don't pay much atttention to that stuff. :))
If you compile with gcc -g3, then gdb can print expressions that use macros! I knew Jim Blandy had implemented this but I never actually went and dug up the magic to make it work. This will make my life a lot easier, at least for a year or two.
The gcc compiler itself uses a garbage collector. I'm told the GC is autogenerated from the source; so the gcc source distribution actually includes a bunch of autogenerated code.
gcc -S prints Intel assembly code with the operands reversed. I don't remember if I ever knew this or not. What a pain.
And some more about GCC internals, from here.
The Phaistos Disc is a mysterious clay disc, about 3400-3850 years old, discovered in the basement of a Minoan palace. It is imprinted with hieroglyphic symbols. It is the earliest known instance of movable-type printing, which would not be seen again until woodblock printing appeared in China some 1600+ years later.
Poseidon was believed to have created the horse. (I didn't even know that Pandora was a Greek legend. In my brain she was curiously detached from any specific culture.)
For some reason, Wikipedia's pages on Greek mythology are very often vandalized.
And I learned more about SpiderMonkey split objects than any human being should know. But I still don't understand them very well, as that page (which I wrote) indicates.
I've been learning (and documenting) a lot about SpiderMonkey and its API, which may be why the pickings are so slim otherwise.
Before desktop computers were widely used in China, telegraph operators there had to memorize every Chinese character's GB 2312 character code.
Moleskin is made from cotton, not moles. (In other news, guacamole is made from avacados.)
Garbage collection in Erlang is per-process. This seems weird—are messages copied from process to process?—but as that article explains, there are advantages, too.
The Haskell standard library contains over 100 operators— that is, functions whose names consist of ASCII symbols, like .| and |. and @?= and @=?. Someone must stop these madmen.
I learned a few very basic odds and ends of category theory.
The book I'm reading (by Benjamin Pierce) offers “injective functions are monic in Set; surjective functions are epic” as a mnemonic, you know, to help you remember monic and epic. This has to be the worst mnemonic of all time. I just don't see anything helpful about it. Sur- means “under”. Epi- mean “on top of”. I can never remember the difference between injective and surjective to begin with.
There are lots of ways to tile a regular dodecagon with sides of length s using only rhombi with sides of length s. My favorite so far:
I speculate all such tilings use exactly this many rhombi of each shape—six skinny diamonds, six fat ones, and three squares. It would be really cool if I were wrong. Calculate the area of each shape to see why I think this.
(Pictured: Melissa & Doug pattern blocks. Great toy.)
Basic stuff about the Erlang programming language. If you set aside the concurrency features for a second, Erlang looks like ML without static typing or refs. In a word, yuck.
Haskell has concurrency libraries that I should look at (while I'm learning about language-level approaches to concurrent programming).
Incidentally, if you're a Haskell programmer, see if you can spot the unintentional self-parody in that blog post. Hint: it's in the sentence “So let's do something useful with this, how about a little program that computes primes and fibonacci numbers?”
This week I started looking for elementary school curriculum materials. My son is four years old. We will probably homeschool him, and I want a head start on this one. Not a lot of luck searching so far. There are a lot of individual lesson plans; for example, PBS has some science lessons. On the other end of the spectrum, I found the What your nth-grader needs to know books and ordered one. We'll see. I really want a variety of textbooks and workbooks.
A five-step checklist saved about 1,500 lives in Michigan intensive care units in 18 months. It lists the five steps a physician should take, when putting a tube into a patient, to prevent infection.
Simple array lookups like arr[i], where i is an int, are troublesome for x64 compilers. This is because int is a 32-bit type, while arr is 64 bits. To generate the fastest possible code, the compiler must prove that the high 32 bits of the register containing i are all zeroes.
OpenGL is horrible for 2D graphics because 2D graphics are usually plainer and stay on the screen statically for a lot longer than 3D graphics. So a little imprecision is a very bad thing, especially for text. 3D cards don't have a whole lot of DWIM in them; if your use of an API is the slightest bit off, you can get bizarrely ugly results, and it's very hard to debug.
This is an instance of a principle that I think works against efforts like bug.gd: the most perplexing things computers do don't come with error messages. Instead it just behaves funny, and gives no indication that it even knows it's doing it.
An interference graph is a way of thinking about scheduling constraints. For example, many compilers use an interference graph to assign variables to CPU registers. The vertices of the graph are the variables. Each edge connecting two vertices indicates that those two variables cannot live in the same register—their lifetimes overlap; they would interfere. The problem of register allocation is just a graph coloring problem on the interference graph.
Graph coloring is NP-hard, though. Some JIT compilers do a linear scan instead, plopping each variable into the next available register. This may not get every variable into a register, even in cases where graph-coloring would. But it's fast.
Phone interviews are educational. :)
Merry Christmas!
Amazon thinks I might like the following items:
Banana?
It turns out Amazon recommended Banana for me because I purchased Fried Egg. So that's all cleared up.
This T-shirt claims that “Under extreme stress, an octopus will eat its own arms.” According to Wikipedia, this is a “common belief”, though I'd never heard of it. I'm suspicious.
Thanks to johnath, I now know that self-actualization tops Maslow's hierarchy of needs.
The Internet, incidentally, is all about self-actualization. Depending on my mood, this strikes me as either dumb or moderately profound.
Good Lisp compilers, I'm told, do fancy escape analysis on closures, so they can detect when the upward funarg problem doesn't occur and in those cases stack-allocate the captured variables. Nice one. In Python, by contrast, all captured variables become heap-allocated “cells”. I hear SpiderMonkey still keeps the whole activation record alive. I had thought that practice was long dead; I know I've seen it characterized on Lambda the Ultimate as “stupid”.
I knew this was there somewhere. In gdb, the commands command lets you specify debugger commands that run when a breakpoint hits. For example, you can have gdb print some variables and continue. Useful.
Also in gdb: set scheduler-locking on prevents other threads from running while you're stepping in a thread. Not available on all platforms, apparently; but this is the only sane way to debug a multithreaded program.
Also in gdb: thread apply all runs a debugger command on every thread in the process you're debugging. I have yet to use it without crashing gdb, though.
Even in a very simple 3D model, physics is very hard to get right. I think faking it using an easing function would get better results. Kind of sad.
...and more about static single assignment form, but I have much more to read there.
Remember when I linked ColorSchemer Online? Fun toy, huh? Well, forget about it. What you want is the ColorSchemer Gallery. Three thousand color schemes created by actual graphic designers or sampled from art and nature.
How does a really good garbage collector compare to explicit memory management (malloc/free)? According to a 2005 paper (PDF) by Matthew Hertz and Emery D. Berger, the two strategies are pretty competitive, and GC can even be faster than malloc, as long as memory is plentiful. To remain on par with malloc, a GC program needs about 4 times as much heap memory!
This may matter to me pretty soon, as we're working on replacing Mozilla's reference counting with a conservative tracing GC.
I had never even heard of static single assignment form before around June, but now that I know a little about it, it's everywhere. GCC uses it. Java JITs use it. LLVM code is in SSA form by construction. The key insight behind the HotpathVM tracing JIT, where I first ran across SSA, is that a lot of the well-known SSA optimization algorithms become trivially easy when you run them on a single basic block at a time.
Last week, apropos of nothing, someone described VHDL to me as “SSA-like”. And you know... that's a pretty good way of explaining it.
Having just the most basic understanding of SSA has greatly changed my expectations of what optimizations a compiler will perform. Not that they're necessarily any more accurate now; just changed.
I learned a couple things from the examples in this paper: Threads cannot be implemented as a library by Hans Boehm. I finally got around to actually reading (most of) those Intel slides on CPU memory models I posted over a month ago, and learned a lot there. To say that this stuff is not widely understood by people who write real-world multithreaded code is an understatement.
I learned how an OpenGL program knows what you just clicked on. It's clever. First it applies a transform that maps that pixel of your view to the unit cube. Then it does a new pass over all the polygons in the whole scene, just as it does when rendering the scene—only this time it's not drawing anything. It's just interested in knowing which polygons intersect the unit cube, a fairly simple calculation.
