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.