Re: QPROCT and QPRODT
Simon Coulter <shc-Q/[email protected]> Mon, 15 Mar 2010 09:08:09 +1100
| Newsgroups | gmane.comp.lang.as400.mi |
|---|---|
| Message-ID | <[email protected]> |
On 14/03/2010, at 5:48 AM, Gene_Gaunt-GDFlLPZ4eRKEK/[email protected] 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 / \ -------------------------------------------------------------------- _______________________________________________ This is the MI Programming on the AS400 / iSeries (MI400) mailing list To post a message email: MI400-Zwy7GipZuJhWk0Htik3J/[email protected] To subscribe, unsubscribe, or change list options, visit: http://lists.midrange.com/mailman/listinfo/mi400 or email: MI400-request-Zwy7GipZuJhWk0Htik3J/[email protected] Before posting, please take a moment to review the archives at http://archive.midrange.com/mi400.