Hi Folks -
[Cross-posted to VM-dev where this topic really belongs]
As others have noted, it's Really Hard (tm) to add a new immediate type. However, having said that, I would like to outline an approach that I've contemplated in the past (up to the point of actually implementing a major part of it). The main issue with tag bits is that they are for obvious reasons few and far inbetween so it's hard to get the maximum value out of changing the VM for a single new immediate type. In addition there is a major issue with the range of bits for SmallIntegers - each tag bit takes away from the number of bits available for small integers and that's not good since many algorithms are designed to fit into 32 bits and the more often you have to fall back to general large int arithmethic, the worse it gets.
Today, we use a single tag bit which differentiates small integers from "regular" pointer objects. (Not so) incidentally, this is bit zero so that pointer objects (which are always aligned to 32bits) have a "natural" LSB of zero for addressing. However, since pointer objects are 32bit aligned, there is an UNUSED(!) bit pattern even if we leave small integers alone:
xxxxxxxx00 -> object pointer (tag bit not set; divisible by four) xxxxxxxx10 -> Unused (tag bit not set; but not a valid pointer) xxxxxxxx01 -> SmallInteger (tag bit set) xxxxxxxx11 -> SmallInteger (tag bit set)
So what one could do is to use that formerly unused bit pattern for "something different". But wait! Unfortunately, the bit pattern is not-so-unused after all; the garbage collector makes use of it (see the definition of HeaderTypeGC in ObjectMemory) to flag objects that are currently being marked. This needs to be fixed before the bit pattern can be used and I'll leave that as an exercise for the interested reader because it's a strict prerequisite for anything that follows below and can be done independently (HINT: A cheap way out -and yes, there are others- is to relocate that bit; most people are likely just as happy with half of the addressable memory).
Once the GC usage of that flag is fixed we can decide what to do with the pattern. But given that we only have a single bit it's probably worthwhile to get a little bit more out of it than just one type. So instead of declaring "yet another immediate", I say let's use another 6bit to index into an array(!) of immediate classes (very much like compact classes) and use the 24 remaining bits to represent the actual value (and note that you can obviously adjust that number for different trade offs of number of immediate class vs. bits of accuracy). Then you need primitives that convert back and forth between a small integer and one of those immediates but that's about it.
IIRC (it's been a while since I looked at it) those are the issues that you'd have to deal with. There are some more nice things about this particular scheme beside preserving small int bit range btw; for example, class lookup can test the low order two bits and if non-zero index into a 256 element array (with the odd slots filled with SmallInteger) so that there is no additional overhead for fetching the class of an object. Whether 24 bits are useful is another good question though; there are certainly some places that could use them since you can also split 24 bits into 2x12 (immediate points) and 3x8 (immediate colors) or 4x6 (dunno what you'd use that for though ;-)
So the bottom line is that, yes, while it is hard to add new immediate types, it is far from impossible - it's a goodly amount of work and (the way I look at it) not worth doing it for just a *single* new immediate type; but being able to have up to 64 immediate types just *may* be worth it.
In any case, I think that if anyone is interested in this issue the best way to go about it is to fix the usage of that xx10 bit pattern in the garbage collector and take it from there. Good Luck!
Cheers, - Andreas
Joerg Beekmann wrote:
Can anyone comment on how much work would be involved in
- Adding a new 32bit field to the object header
- Adding a new immediate type like integer, presumable by adding
another tag bit.
I'm just looking for a very rough estimate. Do these tasks involve tracking down a bunch of constants and then rebuilding everything, tedious but a with a known path to follow. Or will this involve much more.
regards Joerg