21 December 2007

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!

20 December 2007

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


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

14 December 2007

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.

07 December 2007

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.

02 December 2007

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.