Porting micro-Max to a small teaching language

[octogonz]

Thanks! This patch seems to be based on version 4.8 of your algorithm, whereas my Hybrix language port is working from version 3.2 on your website. (As mentioned, for a tutorial version 3.2 has good docs and a simpler algorithm.) Version 3.2 uses the multi-probe scan:

Code: Select all

                                               /* lookup pos. in hash table*/
 j=(k*E^J)&U-9;                                /* try 8 consec. locations  */
 W((h=A[++j].K)&&h-Z&&--i);                    /* first empty or match     */
 a+=i?j:0;                                     /* dummy A[0] if miss & full*/

So I can't drop the two-slot code in directly, as the table geometry differs. But the idea can be ported: re-add real replacement intelligence that the big-table versions could afford to drop.

For a small saturated table, would you still prefer the paired shallowest-of-two with undercut aging, or does a short linear probe (say 8 slots) with shallowest-of-N replacement buy anything over the pair? On Chombit I'm counting instructions per node rather than cache misses, so the probe width tradeoff is different from a PC.

(The full Hybrix language source code will take me a few weeks to finish. I'll post it here for review when it's ready.)

[hgm]

Shallowest-of-4 is hardly better than shallowest-of-2, and when I tested shallowest-of-7 it was even worse. The best way I found was 'equi-distributed draft', but the complexity might not be worth it: it would keep a histogram of the depth distribution in the table, and would replace the entry in the depth-preferred slot when the depth of the latter is present in the table more than the lowest depth is present in the table. Otherwise it would defer to the always-replace slot. This automatically takes care of aging. There still would be the option to have several depth=preferred slots defer to the same always-replace slot.