Re: maintenance of hash tables.


"Pascal J. Bourguignon" <pjb@xxxxxxxxxxxxxxxxx> wrote in message
news:87ws6qmcw1.fsf@xxxxxxxxxxxxxxxx
"cr88192" <cr88192@xxxxxxxxxxx> writes:

"Andrew Tomazos" <andrew@xxxxxxxxxxx> wrote in message
news:e2a2fff7-b993-4ddc-a955-1336961b10ed@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jun 30, 5:10 pm, "cr88192" <cr88...@xxxxxxxxxxx> wrote:
in practice, although divides or modulo operators are a bit more
expensive
than masks, typically they are not a significant portion of the overall
performance, so the cost is often reasonable.

<
If we use x86 as an example than a binary and (AND) is approximately
50-100 times faster than a modulus (IDIV). [*]

If the keys are easily hashed (such as numeric types) than a modulus
will be a significant cost associated with the hash function.
-Andrew.

[*] See Intel 64 and IA-32 Architectures Optimization Reference
Manual, Appendix C


ok...

well, this operation is weighted against:
hashing the string (if a string is used);
various other costs (checking if the spot is free, calculating the next
permutation, ...);
...

so, mod is slow, but in many cases, this can be glossed over some (which
is
why I said 'typically'...).

in some cases, there are "faster" ways to approximate division and
modulo,
but I am not sure of any that are particularly appropriate in this case.
I
may have to check compiler output, and see if it finds some way to
optimize
away the idiv...


but, yes, if speed is critical (and/or one is using a highly optimized
hash
table), then a power-of-2 size is better...

In lisp, the default for hash-table is to use the identity of the key
[:test (function eql)]. In this situation, there's no lengthy hash to
compute, just the modulo on the address (or object in case of fixnums
and characters). The way they're specified, it is intended that CL
hash-table do not use collision lists, but have always more slots in a
vector than entries in the hash, so collisions are handled by storing
the colliding entries in adjacent slots. This means that in the worse
case, there's a small number of additionnal EQL comparisons made. As
soon as the hash-table becomes too filled, the vector is extended to
render it sparse again.


<snip>

I am not sure how this is directly related, or what exactly is trying to be
argued here...

but, I guess it can be noted that LISP is its own set of issues...


but, I guess the core issue is that, yes, mod (and div) are a bit slower
than shifts or masks, but in many cases, it is not noticable (the weight of
everything else often compensates enough that there is not as much worry
over the number of clock cycles taken for particular instructions...).

of course, a mod is often slower than a conditional, which says something...
however, given a typical hash operation may involve several conditionals in
a row (is spot empty? is spot the wanted value? is the loop finished? ...),
the mod is no longer the big killer (especially if the value check is a
'strcmp'...).


but, alas, if we are looking up based on a pointer-address or integer (no
strcmp, ...), this mod may be significant, and it may well be worthwhile to
use a power-of 2 table...


of course, as a matter of practice I tend to keep all fixed-size tables as
powers of 2, as after all, it is not useful to waste time unnecessarily...

or such...




.

Relevant Pages

  • Re: Suggestions for double-hashing scheme
    ... >> managing the hash table is very low. ... > Irrelevant to the point about the relative costs of comparing, hashing, ... the cost of these sorts. ... > if 75% of the lookups hit on the first try. ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... >>> Once you sufficiently optimize a hash table, the big cost in hashing ... >>> by computing of the hash function). ... Irrelevant to the point about the relative costs of comparing, hashing, ...
    (comp.programming)
  • Re: maintenance of hash tables.
    ... typically they are not a significant portion of the overall ... will be a significant cost associated with the hash function. ... I observe a much smaller ratio between TRUNCATE and + ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... >> Once you sufficiently optimize a hash table, the big cost in hashing ... >> by computing of the hash function). ... any good hash function basically always has a minimal ... >> What you want is for each of these entries to have a different reprobe ...
    (comp.programming)
  • Re: 65816s
    ... The other reason is the cost of masks approaching $1M. ... These are funny projects if all the development costs are dwarfed by ...
    (comp.sys.apple2)