Where should the type information be: in tags and descriptors 413
Where should the type information be: in tags and descriptors 414
Typical implementations require a single memory bit for a fixed number of memory bytes to indicate whether an item is "special" (Usualy...
When you really need the speed, there's nothing wrong with this concept, except that I showed in a conference presentation ("Optimizing algorithms for modern CPUs") two years ago that it is no longer the fastest way to solve most problems.
I used to have state machine code that consisted of several (16 or 32) templates, which at runtime was replicated at every 128-byte offset within a 64kB aligned memory block.
This allowed direct chaining from one state to the next, based on loading the next input byte into the high half of a 16-bit index, with the low half containing a single mode bit which selected the code snippets at offset 0 or 128 in each 256-byte block.
When this blew up (performance-wise) due to icache trashing (all offsets being identical modulo 128), I also used an approach where each snippet was simplified to the point where it would fit in 16 bytes, so that the total runtime code array would fit in L1 icache.
However, since the Pentium-PentiumPro-Alpha-PPC timeframe the fastest codes I've been able to come up with all use register-only state machines, with effectively zero branches inside the (big) unrolled loop.
Where should the type information be: in tags and descriptors 415
That is almost entirely sheer incompetence - and it is not just SPARC, but almost every RISC designer and most others...
Terje -- "almost all programming can be viewed as an exercise in caching"
Alt Folklore Computers Newsgroups