On 14/03/2010, at 5:48 AM, Gene_Gaunt@xxxxxxxxxxxxxxx wrote:
QPROCT hashes the 8-letter MI opcodes into 563 linked lists. All
those
x'FFFF's you observes in the QPROCT space are linked list tombstones.
Thanks. I don't know how long it would have taken me to work that out.
And this begs the question:
Why 563?
Knuth. Volume 3. Page 516.
The implemented algorithm does a good job of dispersing similar keys
but has a surprising (to me anyway) number (149 in 468) of collisions.
MATUP, MODQSAT, INSDSEN, ACTBPGM, CPYBREP all hash to 377.
There are another 5 groups of 4 op-codes that hash to the same values.
There are a further 27 groups of 3 op-codes that hash to the same
values. Finally, 74 groups of 2 op-codes that has to the same value.
Probably not as bad as first seems: 68.2% of entries (319) will be
found on the first access. 23% (108) will take two access. 7.2% (34)
will require 3 accesses. 1.3% (6) will need 4 accesses and 1
instruction will consume 5 accesses. That seems not too bad for a
hashing algorithm. A simple tweak to the XOR operation can reduce the
total collisions to 143 but still has the same number of 4 and 5 link
chains.
Interesting exercise ... now back to trying to determine what those
remaining two flag bytes mean.
Regards,
Simon Coulter.
--------------------------------------------------------------------
FlyByNight Software OS/400, i5/OS Technical Specialists
http://www.flybynight.com.au/
Phone: +61 2 6657 8251 Mobile: +61 0411 091 400 /"\
Fax: +61 2 6657 8251 \ /
X
ASCII Ribbon campaign against HTML E-Mail / \
--------------------------------------------------------------------
midrange.com
