Searching for hash parameters

[burnsauce]

Here is the code I am using to search for suitable parameters to hash all dictionary words included with include test with no collisions.

Using the following code, the lowest multiplier I could find was 109 with a mod of 0 (which is handy for performance).

It would be nice to find a lower prime, even with a mod. The mod would be orders of magnitude less time than the multiplication time of higher primes.

edit: updated code

decimal
31 value hash-prime
0 value hash-mod

: hash ( caddr u - u )
  0 >r
  1- begin
    2dup + c@
    r> hash-prime m* rot
    m+ hash-mod ?dup if um/mod then
    drop
    >r
    ?dup while 1-
  repeat
  drop
  r> ;

: insert ( n hashtable -- flag )
  begin
    dup @ ?dup while ( n hashtable h[i] )
    2 pick = if 2drop -1 exit then
    2 +
  repeat
  ! 0 ;

' hash value hashfunc
800 constant hashtable-max
create hashtable hashtable-max 2* allot

: s<> ( caddr1 u1 caddr2 u2 -- flag )
  rot over <> if drop 2drop -1 exit then
  0 do
    2dup i + c@ swap i + c@
    <> if 2drop unloop -1 exit then
  loop
  2drop 0 ;

50 constant ignore-max
0 value ignore-size
create ignore ignore-max 2* allot

: new-hash
  hashtable hashtable-max 2* 0 fill ;

: new-ignore
  ignore ignore-max 2* 0 fill
  0 to ignore-size ;

: ignore-word ( nt -- )
  ignore-size ignore-max = abort" ignore overflow"
  ignore ignore-size 2* + !
  ignore-size 1+ to ignore-size ;

: is-ignored ( nt -- flag )
  name>string
  ignore-size if
    ignore-size 0 do
      2dup ignore i 2* + @ name>string
      s<> 0= if 2drop -1 unloop exit then
    loop
  then
  2drop 0 ;

variable collision
0 collision !

: hash-name \ dowords lambda
  dup name>string hashfunc execute hashtable insert
  if
    dup is-ignored if drop 1 exit then
    collision ! 0
  else drop 1 then ;

: hash-words
  ['] hash-name dowords ;

: name-hash \ dowords lambda
  dup name>string hashfunc execute 2 pick =
  if nip name>string 0 else drop 1 then ;

: find-hash
  ['] name-hash dowords ;

: test-hash
  new-ignore
  begin
    new-hash
    0 collision !
    hash-words
    collision @ ?dup if
      dup name>string 2dup
      hashfunc execute find-hash s<> if
        name>string 2dup type space
        hashfunc execute find-hash type
        -1 exit
      then
      ignore-word
    then
    collision @ while
  repeat
  0
  ." Hash collision-free." cr
;

\ looping stack
: stack: create here 0 , 0 , ; ( name -- u )
: s, , dup @ 1+ over ! ; ( u n -- u )
: ;stack ( u -- )
  dup @ swap 2+ !
  does>
  dup @ dup if
    1- over !
    dup @ 2* + 2+ 2+ @
  else
    swap dup 2+ @ swap !
  then ;

\ multipliers should be small primes
stack: rvalues
107 s, 103 s, 101 s,
97 s, 89 s, 80 s, 53 s,
49 s, 43 s, 41 s, 37 s,
;stack


\ divisors should be large primes
hex
stack: mvalues
5e27 s, 5f09 s, 5fd5 s, 60d9 s, 619d s, 6283 s,
6343 s, 6415 s, 64db s, 65a1 s, 6673 s, 6731 s,
6817 s, 68c5 s, 6983 s, 6a69 s, 6b57 s, 6c35 s,
6ccb s, 6da5 s, 6e89 s, 6f65 s, 6ff5 s, 70bb s,
7195 s, 7267 s, 7321 s, 7415 s, 74fb s, 75d1 s,
769f s, 7781 s, 7861 s, 792b s, 79d9 s, 7a9b s,
7b8b s, 7c69 s, 7d4d s, 7e29 s, 7eb9 s, 7f6d s,
;stack
decimal

: find-good-hash
  ['] hash to hashfunc
  cr
  begin
    rvalues to hash-prime
    hash-prime while
    begin
      mvalues to hash-mod
      cr
      ." R=" hash-prime u.
      ." M=" hash-mod u.
      test-hash
      hash-mod while
      0= if
        exit
      then
    repeat
  repeat
  cr ." No suitable parameters."
  cr ;

[burnsauce]

Ooooo just found R=41 M=30593. nope, didn't include test yet >.<

Watching how they fail is interesting, and makes me wonder how applicable this could be. I'm using a very large dictionary to compare against, but that's no guarantee against future collisions.

[burnsauce]

Search is running with some broadly-selected but well-limited set of primes, but I'm not entirely hopeful that a magic combination will appear that will be collision-free.

Perhaps the solution is picking some reasonably fast values and implement a collision response. Unless we're getting rid of words, we'll need to include strings anyway. The few collisions that occur could be a fairly small table of resolutions.

[burnsauce]

Hmmmm.... I know it's forth code and not assembly, but the hash function alone costs more than searching for pushya in the current dictionary.

: hash2 ( caddr u -- u )
  0 >r begin
    2dup + c@ r> 109 m* m+ drop >r
    ?dup while 1-
  repeat drop r> ;

Shows that there's a lot of work to be done to get anywhere near the performance of the current dictionary. Yikes!

[burnsauce]

Lowering the string length from 10 (why did I set it this long?) to 5 (system average is 4.7) shows a rough halfing in time, so it's not nearly as bad as I thought.