This week I learned...

• 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.

This week I learned...

• 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.

This week I learned...

• A chipotle is a jalapeño that has been smoked.

• 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.

This week I learned...

• 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!

Today's recommendations for me

Amazon thinks I might like the following items:

• György Ligeti Edition 2: A capella choral works
• Galois theory for beginners
• General topology
• Infinity and the mind
• Banana

Banana?

It turns out Amazon recommended Banana for me because I purchased Fried Egg. So that's all cleared up.

This week I learned...

• 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.

This week I learned...

• 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.

Black-Eyed Pea Dip

Heat and drain:

• 1 can Bush's black-eyed peas

You can just zap them in the microwave for 2 minutes.

Mash them, then mix in:

• 1 tsp. seasoned salt
• 2 tbsp. chopped onions
• 1 tbsp. jalapeños (or salsa or diced tomatoes)
• 1½ cup grated cheddar
• ¼ cup unsalted butter, softened
• 1 3-oz. can of deviled ham

Pour the mixture into a 9-inch baking dish. Sprinkle on top:

• 3 oz. grated mozzarella cheese

Bake at 350° for 25 minutes. Serve with corn chips.

This week I learned...

• Net-casting spiders spin small webs which they hold in their long, spindly legs and slap down on unsuspecting insects. Amazing.

• In OpenGL, textures are applied after lighting has already been applied to the colors of whatever material you're drawing. So once you get a material to look the way you want, if you then try to put a red spot on it, using a texture with some red parts and some transparent parts, the red parts aren't affected by lighting. It looks really dumb.

  I think the fix is to draw the polygon twice, applying the “decal” in a second pass. But to do that, you have to actually do things right—turn off depth-buffering and sort all your polygons. Blah.

• OpenGL contains a lot of stuff that now seems quaint, like stippling. And support for 8-bit graphics modes.

• Many CPUs (including, for example, PowerPC) don't have an instruction for the integer “modulo” operation, the one spelled % in C and Java. (This is mentioned in the HotpathVM paper; I must have skimmed past it the first time I read it.)

• To decode g++ mangled names, pipe them to c++filt! Actually, Waldo told me about this last week. It helped me figure out some puzzling linker errors (you know the sort— “undefined symbol ??XZ13Frz__F21Z6K9__”).

• A good merge sort is faster than quicksort for real-world data. You can easily take advantage of certain kinds of pre-existing order in the array. Timsort is a merge sort implementation that takes that idea and, er, runs with it.

• Python's list.sort() is strangely wasteful when you use the key= named parameter. It allocates a separate, reference-counted temporary object for each item in the list. (It should allocate a single temporary array.)

• Maintaining a Mercurial queue containing large patches to a project is about as hard as maintaining a fork.

And a bunch of stuff about compilers that isn't really interesting.

According to a coloring book we bought for the kids, the black spots on a strawberry are not seeds but tiny fruits that contain the seeds. Wikipedia does say that “from a technical standpoint, the seeds are the actual fruits of the plant, and the flesh of the strawberry is modified receptacle tissue.” Appetizing! But I still say if your strawberry has black spots on it, don't eat it.

This week I learned... (Toronto edition)

It was a good week, because I was stuck in a room with Benjamin Smedberg and Taras Glek for a couple days.

• Virtual method calls are branch-predicted these days. What is the world coming to?

• When you fly from Canada to the U.S., you go through customs in Canada.

• I learned a little about why Mozilla's security code is the way it is. I hate the wrapper model, but the model I prefer, which depends on examining the stack to find unauthorized callers, has problems too.

  BS claims stack-checking might be even more fragile, because it depends on the stack information being correct. For example, sometimes C++ code calls methods in order to block something evil that a content script is trying to do. If that C++ code neglects to say "Simon says", the blocking doesn't happen. Apparently a bug like this actually happened at one point (story embedded in document). I still think the wrapper model is horrible and not to be taken seriously, unless it's enforced with static analysis.

  I will say this: stack checking would have to be optimized for Mozilla. Performance is a problem. Compare Mozilla's sandbox to the Java applet sandbox. Applets are an easy case. The security checks don't normally trigger at all—if they do hit, it's either a bug or the applet is malicious. Mozilla, by contrast, has to do an access check each time a script does anything to the DOM. It's easy to optimize those checks away using wrappers; not so easy with stack checking (but I don't know much about it).

• I'm told the line numbers in Unix debugging symbols are limited to 16 bits. Source files with over 64K lines of code can confuse your debugger. Haven't tested this.

• Vmgen is a tool for auto-generating fast interpreters. (Paper, PDF, 30 pages.)

• I learned why an interpreter that uses while (1) switch (*bytecode++) {...} might be slower than one that uses an explicit computed goto at the end of each case to jump directly to the case for the next bytecode. It has to do with how CPUs do branch prediction. The CPU keeps a table of branch instructions and where they usually end up branching to. This allows it to predict (guess) where each branch is going to most of the time, keeping pipeline full. If your interpreter uses a computed goto at the end of each case, the CPU makes a separate entry in this table for each of those. So the CPU can do a good job of predicting what the next opcode is, and it'll automatically tune this intelligence to the specific bytecode the interpreter is executing! By contrast, the single indirect branch in switch (*bytecode++) { ... } is impossible to predict using this simple historical table. The pipeline is often derailed, which kills performance.

• Tracepoints are breakpoints that don't stop long. When a tracepoint hits, the program runs a little code that logs the contents of certain pieces of memory, then continues the program. By design, the tracepoint can't modify the program state. It treats the process as read-only. This feature was invented to help debug critical software while it's live. (!)

  But there are two even crazier applications. If you know what you're interested in, tracepoints can be used to implement a debugger that can step back and forward in time, with much less overhead than the usual approach of logging every memory write. GDB only supports tracepoints in remote debugging, but it's been proof-of-concepted for debugging the Linux kernel from a user-mode debugger (arrrgh, too cool!).

This week I learned...

• Chicken cacciatore isn't at all what I thought it was. Sure is tasty though. The recipe in The Joy of Cooking is recommended; here's a similar recipe (video).

• Searching YouTube for recipes is an awfully delicious time sink. My mouth is watering.

• Color Schemer exists—and does a pretty darn good job. Very helpful for the color-impaired like me.

• Dot (PDF) is a very simple little language for describing graphs. graphviz turns dot files into professional-quality 2D images in various formats. You just describe the nodes and arrows, with as much or as little style info as you want; graphviz does the layout and draws the lines. The Mac version won an Apple Design Award.

• LLVM is a VM for low-level languages like C and C++. Too much supercool stuff going on here for me to even begin to describe.

  (Benjamin Smedberg is interested in maybe using LLVM in Mozilla 2, as the mechanism for JavaScript-C++ interop. And—heh—maybe a lot more.)

• Dijkstra wrote about Why numbering should start at zero. The usability note about MESA is especially interesting. Ruby has built-in operators M .. N and M ... N that create ranges M ≤ i < N and M ≤ i ≤ N, respectively—or is it the other way round?

• Finalizers are scary! It's unpredictable when they'll be called, and this lays more traps than I had realized. Say a finalizer removes an entry from some data structure. The system could fire off that finalizer just about any time. It might happen to call it while you're in the middle of modifying that data structure. Or some other thread is. Uh oh.

  You might think, “Oh, you can work around that using locking.” But that has scary consequences of its own. If the system uses a stop-the-world garbage collector, and one of the threads it stops is holding the necessary lock, you immediately get deadlock. If your thread is holding the lock at the time the finalizer decides to execute on the same thread (something Java doesn't do, but Python could), you have another kind of problem. If you used a non-reentrant lock, you'll deadlock (yes, with finalizers, you can deadlock even if your program is single-threaded). Otherwise, your critical section will be reentered anyway, as if you didn't have a locking scheme in place at all!

  I've heard some JVMs avoid potential deadlocks by running finalizers concurrently with ordinary code, in a separate thread. But that seems even scarier. It means non-threadsafe code can be called at unpredictable times from a magical system thread that most programmers don't even know about. Yikes!

This week I learned...

• To view the wiki-source of any MediaWiki page, add ?action=raw to the URL. (Good for scripting.)

• Unix has system calls like mlock, mincore, mprotect, and madvise that interact with the virtual memory manager. (Some are more standard than others.) I only knew about the venerable mmap.

• There's a fast, easy way to avoid the agonizing worst-case fragmentation you can get when you use a simple size-class/freelist implementation of malloc: per-page freelists.

• You can implement a copying collector in 100 lines of easy-to-read C that won't blow the stack!

• The Encyclopædia Brittanica is about 33,000 pages long, and I'm not the only one to raise an eyebrow at the volume titled “Menage - Ottowa”.

I also keep learning about good decisions the JVM designers made, but they're even less exciting than the above.

This week I learned...

• How to find the median of n items in O(n) comparisons. The easiest algorithm is merely O(n) expected time. Can you figure out how it works? Hints in the comments.

• You can sort items with string keys in O(kn) time, where k is the average length of the strings. But it requires, say, 5n words of extra table space. This is amusing because in JavaScript, Array.prototype.sort() sorts objects by their toString(), so it is always sorting strings. (A comparison sort in this case can be as bad as O(kn log n), since comparisons are worst-case O(k).)

• The memory model that processors present to multithreaded programs running on multiprocessor machines is frighteningly subtle: A Taxonomy of Multiprocessor Memory-Ordering Models (44 slides, PDF). The presentation cheerfully explains about 13 different ways CPUs can (by design) shuffle the order of memory accesses, causing more or less confusion on other CPUs. The reason they have to do this is per-CPU caches, which are a major speed win; the techniques multiprocessors use to maintain a modicum of sanity are called cache coherency protocols.

• That's why atomic operations are so costly. Not only do they flush the cache line of the memory being atomically accessed. In order to maintain cache consistency and coherency, the CPU has to flush, potentially, its entire cache.

• You can implement a copying collector in 100 lines of easy-to-read C, if you're not too worried about blowing the stack.

  T.S. brought me a book, Garbage Collection by Jones and Lins (read a review). It was written in 1996, which in the GC field is a long time ago; but I don't think the basics have changed. Still, it's odd to see Fortran and Modula-2 used as examples, rather than various JVMs, the CLR, Python, JavaScript, and Ruby.

  Working for Mozilla is like going back to school, except I'm motivated.

• Suppose I want to create a set of C/C++ macros that application code can use that allows me to swap out different kinds of memory management systems, switching between reference counting, mark-and-sweep, copying GC, and so on, as a compile-time option. In C/C++ this is actually practically impossible, because the range of operations you want to hook, and the amount of detail the GC might need to know about them, is so great. To do a good job, each memory management scheme will want to optimize away a lot of work, which you can't do without still more cooperation from the compiler or the programmer.

  Java doesn't have this problem. The JVM can hook whatever it wants because the bytecode it loads and executes is really only partly-compiled. With Jikes RVM, you can in fact choose from a huge array of garbage collectors at the time you compile your VM.

This week I learned...

• bug.gd is a web site dedicated to finding explanations and workarounds for every cryptic error message your computer can generate (with a little help from you).

• The Canadian Standards Association charges Canadian citizens hundreds of dollars for (copy-protected) CD-ROMs containing the detailed regulations they're required to follow to do their work.

• Mississippi medical examiner Stephen Hayne claims he performs 1500-1800 autopsies each year. According to the article, “People who have visited Hayne’s practice during an autopsy session have described seeing as many as 15 bodies opened at once, with Hayne and his assistants smoking cigars, sometimes even eating sandwiches, as they go from one body to the next.” It's not just gross. Hayne performs about 80% of the state's forensic autopsies. He tells prosecutors what they want to hear. He testifies in court. People go to jail. I couldn't put this article down. Must read.

• The Jikes Research Virtual Machine is a JVM written in Java. (The garbage collector is written in Java, too. In fact the garbage collector is pluggable, which makes Jikes RVM a nice testbed for experimental new GC strategies.)

• An “on-the-fly” garbage collector is one that is neither “stop-the-world” nor “fully concurrent”— that is, it neither stops all application threads at any point while it collects, nor works entirely in a separate background thread. Instead, it asks each application thread to pause periodically, at their convenience, to do some GC work.

• Xiao-Feng Li, a developer on the Apache Harmony JVM project, has a blog on programming language runtime implementation techniques. The posts often focus on GC.

• In C++, static_cast<B2 *>(d), where d is of type D * and B2 is the second base class of D, does not compile to a simple addition operation, even though the offset of the B2 within D is a constant known to the compiler. The catch is that if d is null, the result must be null. So the compiled result includes a conditional branch, essentially (d == NULL ? NULL : (intptr) d + some bytes).

The principle of explosion

Pop quiz:

1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + ... = ?

It's obviously 0, right? Or maybe it's 1. In the 17th and 18th centuries, everyone apparently thought the correct answer was ½ (and it wasn't because they were stupid back then: this includes people like Leibniz and Euler).

Eh, so math is inconsistent. So what?

It is important to point out that it is not enough to consider at the same time two conflicting statements in order to develop in pupils' minds the awareness of an inconsistency and the necessity of second thoughts (Schoenfeld, 1985): the perception of some mutually conflicting elements does not always imply the perception of the situation as a problematic one (Tirosh, 1990).

Infinite series: from history to mathematics education (PDF), Giorgio T. Bagni.

Huh.

Now, maybe this is because math doesn't make a whole lot of sense to most kids to begin with. But I think the main cause is that kids, like the rest of us, are used to things being inconsistent sometimes. And they live with it. I mean, what are you going to do?

Well, let me tell you something. In math, you can't live with a contradiction.

The principle of explosion is built into the fundamental rules of logic, rules that both mathematicians and ordinary people use to reason with. Ex falso sequitur quodlibet: from a contradiction, anything follows. Or as an old friend of mine used to say, after you swallow the first pill, the rest go down real easy.

In math, if you accept a single contradiction, the entire system comes crashing down around you.

(Now there's such a thing as paraconsistent logic, in which inconsistencies are not so destructive. But it's quite different from ordinary logic, and not many people are familiar with it.)

In the above case, mathematicians eventually discovered a formal notion of “convergence” and found that the sum 1 - 1 + 1 - 1 + ... does not converge. That is, there's no answer, just as there's no answer for the sum 1 + 2 + 3 + 4 + ..., and for the same reason: you can go on for as long as you like, and your numbers are never going to converge on some specific value.

Is this a cop-out? It's a hard fact of life that some mathematical problems just don't have answers. The ancients considered 2 - 7 to be undefined, because the answer would be less than nothing, which was clearly nonsense. Today we have negative numbers, but other things, like division by zero, are still undefined. Given all that, maybe it's not so surprising if expressions that end in the innocent-looking “+ ...”, as if to say “oh don't mind me, I'm just a little infinite series, tra la”, sometimes fall into this category.