in reply to Re^5: Heap structure for lookup?
in thread Heap structure for lookup?
What I've come up with is a very simple & compact hash implementation:
The insertion rate of 150e6 (into a fixed-size array of just over 200e6) is less that 1/4 microsecond per; or 37 second for them all; which is fine.
If I push the number of inserts to 190e6, you can visibly see -- watching the trace of every 1e6th insertion -- the insertion rate slow down; but still the insertion rate is less than 1/2 a microsecond per.
The lookups, currently done manually by feeding some of the values traced out back in to check they are found, and a few off-the-top-of-my-head other numbers to check they aren't, and the lookup time is around 20 microseconds per, including the perl->XS->perl transitions and conversions. Which is also very acceptable:
C:\test>lookup64 -N=150e6 16536075677023473182 @ 171436696 ... 6917323807836132563 @ 155785214 4887574662696880337 @ 47194064 9190776599876911997 @ 197069741 5378457539553008893 @ 15322593 6479208648984222734 @ 29944101 7965142717433510515 @ 185179020 1980553766129900057 @ 1573360 4821546746934524968 @ 179443020 Inserting 150e6 U64s took 38.428204060 seconds 4821546746934524968 4821546746934524968 @ 179443020 in 0.000000000 s 1980553766129900057 1980553766129900057 @ 1573360 in 0.000020027 s 6479208648984222734 6479208648984222734 @ 29944101 in 0.000023127 s 4887574662696880337 4887574662696880337 @ 47194064 in 0.000015020 s 1 1 @ 0 in 0.000015974 s 5 5 @ 0 in 0.000000000 s 12345 12345 @ 0 in 0.000018120 s 1234567890987654321 1234567890987654321 @ 0 in 0.000018835 s 16536075677023473182 16536075677023473182 @ 171436696 in 0.000000000 s
All together, I'm really surprised that such a simple hash implementation should work quite so well; even allowing for a 25% to 10% headroom in the array.
|
---|