Re: maintenance of hash tables.

"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.

So we are comparing: SHIFT + MOD + s AREF + s EQL + CONS + 3 STORE + ADD
vs. DIV + s AREF + s EQL + CONS + 3 STORE + ADD
Basically, all the operations but the firsts are sum up to 5+2s

The default rehash threshold is
#+clisp (hash-table-rehash-threshold (make-hash-table)) -> 0.75s0
so in clisp, s = 4

s = ceiling( 1 + ( rehash-threshold / ( 1 - rehash-threshold ) ) )

so we get 13 steps for them, and we would be comparing 15 steps
vs. 113 steps, about an order of magnitude, for the most used hash
tables.



Unfortunately (or happily), doing Q&D benchmarks on sbcl and clisp on
ix86 dual core, I observe a much smaller ratio between TRUNCATE and +
on fixnums... (about 1.3 in sbcl, and 17 in clisp).

(let ((a (random most-positive-fixnum))
(b (random most-positive-fixnum))
(r 10000000))
(macrolet ((test (expression)
`(funcall (compile nil (lambda ()
(print ',expression)
#+clisp (ext:gc) #+sbcl (SB-EXT:GC)
(time (loop repeat r do ,expression)))))))
(list
(test (progn))
(test (truncate a b))
(test (+ a b)))))

--
__Pascal Bourguignon__
.

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.
    ... than masks, typically they are not a significant portion of the overall ... will be a significant cost associated with the hash function. ... various other costs (checking if the spot is free, ...
    (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: maintenance of hash tables.
    ... typically they are not a significant portion of the overall ... will be a significant cost associated with the hash function. ... You can choose pretty much any constant modulus you want and still get ... the remainder quickly by multiplying by the appropriately scaled ...
    (comp.programming)