2011-08-31
An interesting debugging experience (another tale from long ago)
This is programming war story.
Once, a long time ago, I worked on an Amiga program. The program had a bug. Well, it had many bugs, but it had one particularly frustrating one where the program had erratic crashes that we couldn't reproduce or track down. One day we were starting to give an internal demonstration of the program and bang, it crashed. We tried again, and it crashed again. I immediately said 'don't touch anything' and we sat down with this specific machine and build of the program to finally get to the bottom of the problem. (So much for the demo, but we'd gotten really frustrated with the bug and it was a small company run by a programmer, so the boss understood.)
At least back in those days, the Amiga had no virtual memory or other memory protection (CPUs with those capabilities were far too expensive for personal computers). It was also a preemptive multi-tasking system, with multiple processes (which were more like threads, since they all ran in the same address space with no protection from each other). Now, of course, each process needed its own stack, and without memory protection they were fixed size and not expandable. There was a system setting for how big a stack each new process should get.
You can see where this is going. All of the programmers had Amigas with relatively large amounts of memory and did complex things with them and we'd vaguely heard that some programs needed bigger stack sizes to be reliable, so we'd increased our stack sizes well above the default. Meanwhile, the default stack size had been designed so that an Amiga with the minimum amount of memory could still work and run enough processes and so was rather small.
(This was a long time ago and RAM sizes were much smaller back then. My memory is that the default stack size was 4K and we had generally turned it up to 16K.)
And, of course, one of the programmers had written a function with a relatively large amount of local variables (my memory is that he'd put a decent sized array on the stack), enough that the program easily exceeded the default stack size when this function was called. Run on our machines with their enlarged stack sizes, this function worked fine (or at least usually worked fine). Run on an Amiga with the default setup, it would blow past the end of the stack and overwrite whatever was in memory there. Sometimes you got away with this; sometimes you overwrote something important and crashed.
The demo machine crashed all the time because it had the default small stack size, what we were doing in the demo wound up calling the function with too many local variables, and what else was (or wasn't) on the demo machine meant that the stack overwrite reliably hit something important.
(In order to crash, you had to be doing something that called the function, on a machine with a small stack, in a situation where you overwrote something important. No wonder it was hard to reproduce, especially in an environment where most people had lots of memory and reflexively raised the stack size.)
One of the lessons I've taken from this experience is the obvious one; always test your programs on a stock configuration machine. These days I expect that it's standard testing practice, but we were younger and stupider back then (and machines were more precious and expensive).
2011-08-22
V8's neat encoding trick for type tracking
Courtesy of v8: a tale of two compilers I ran across a neat trick in how Google's V8 JavaScript compiler encodes types during runtime type tracking. Today I feel like writing it down to make sure that I really understand it.
One of the ways that a runtime compiler speeds up a dynamic language is by generating specialized code that operates only on specific types of objects using more and more native values and code; if your loop is actually only dealing with integers, the compiler wants to compile it down to integer math operations on native integers. To do this the compiler has to track what types of actual objects your code handles as it runs; this is generally called type feedback.
As part of doing this, V8 has a hierarchy of types that it tracks, or really a hierarchy of type distinctions (presumably based on specializations it can make in the generated code). The distinctions are: non-primitive types versus primitive types, then strings versus numbers, doubles versus integers, and finally full-sized integers or small integers. If your code always handles values that have the same type you'll stay at the appropriate spot in the hierarchy, but if the types of the values change V8 must combine your old type information with the new type to determine your new spot in the hierarchy.
To store this information compactly and do this combining operation very
efficiently, V8 has come up with a neat encoding trick. Mechanically,
V8 represents this type information as an 8-bit bitmap and it combines
new type information into the bitmap by and'ing the new type into the
current type information.
Well, sort of. What it really is doing is using and to selectively
remove bits from the type information as the types involved become less
and less specific. Let me show you the actual encodings, written as bits
(looking at these is how I came to understand what was going on and how
it worked):
| uninitialized | 1111111 |
| non-primitive | 1000000 |
| string | 0110000 |
| double | 0011001 |
| small integer | 0010111 |
| integer | 0010011 |
| number | 0010001 |
| primitive | 0010000 |
| unknown | 0000000 |
(Taken from V8's type-info.h.)
We start out with all bits set in the uninitialized state. As we move further and further up the hierarchy and thus know less and less about the specific types involved, the encoding knocks more and more bits out; eventually, we arrive at an encoding with no bits set (when a particular spot of code deals with both primitive types and non-primitive types). Written this way you can see the cascade of removed bits as things get less and less specific (and how related types in the hierarchy share bits), and how the bit patterns are carefully chosen to make this work.
(There are a lot of specific variations possible on this encoding, obviously, since the important thing is how many common bits you have between each type, not exactly where in the bitmap they occur. I assume that Google chose this specific one because it was convenient in some way.)
We can work this in reverse to deduce how many bits a particular sort of type information has set based on how far down the hierarchy it is. Primitive and non-primitive are one step down, so they each have one bit set. Strings and numbers are two steps down, so they have two bits set (one bit from Primitive and one extra bit to tell them apart). And so on down until you get to the furthest step away, small integers, with four bits set. This doesn't necessarily help in understanding V8, but may help if you want to use the same trick in some other context and thus need to come up with your own encoding.
(I believe but have not proved that you need as many total bits as you have steps in your type hierarchy; here V8 has seven steps (not counting either 'uninitialized' or 'unknown') and uses seven bits.)