poor (scheme hash-table) performance

[buhman]

Description:

The following program is a naive implementation of AOC 2019 day 3, that finds (axis-aligned) line intersections using hash table keys as a bitmap:

https://gist.github.com/buhman/7e93f3b9e545dabbd00a67978d51b5b0#file-day3-r7rs-red-scm

Generating this bitmap as written requires ~283,968 (hash-table-set!) calls.

Expected:

gxi/gxc writes (303 . 0) to stdout and terminates after ~<60 seconds.

Actual:

gxi/gxc writes (303 . 0) to stdout and terminates after 75m35s wall clock time.

For comparison, chicken's csi/csc writes (303 . 0) to stdout and terminates after 2.1s wall clock time.

Both tests done on a i7-8705G @ 1.5GHz

SRFI-125:

(hash-table-set! hash-table arg ...) [...] Must execute in expected amortized constant time per key

[buhman]

SRFI-113 doesn't require it, but I think it would be nice if (set-adjoin!) were implemented to execute in amortized constant time as well.

[fare]

Do you know where it's spending its time? Compile-time or runtime? In which library? gxprof might help.

[buhman]

Not sure if I quite understand what's going on, but I'm https://github.com/gambit/gambit/blob/master/lib/_system.scm#L2400 is almost certainly where the linear lookups happen (though I could have easily misread).

Changing:

(make-hash-table (make-pair-comparator (make-eq-comparator) (make-eq-comparator)))

to:

(make-hash-table equal?)

With the latter, gxi terminates after 1.4s

Making the same change, chibi had a similar speedup from >3h to 44s.

I'm a bit of a noob; is this issue actually just me not using SRFI-128 correctly? Prior to reading chibi's hash-table tests, it wasn't clear to me equal? was a valid argument value for (make-hash-table).

[fare]

Aha, it somehow makes sense: the implementation cannot infer a safe hashing function for an arbitrary comparison function, except everything-in-the-same-bucket, which transforms your hash-table into an alist.

[vyzo]

Yeah, srfi hash tables are not well tuned; the native hash tables perform pretty well. You can also try presizing the hash table, by passing the size: N option to the constructor. That should speed things up a bit more, as you won't be constantly resizing the hash table.

[vyzo]

Note that the comparator abstraction itself is pretty bad; it might be the source of the malice.