#5886 Reimplement Scheme_hash_table using linear probing.

[Han-Wen Nienhuys]

Add a unit-test and micro-benchmark, called from
input/regression/scheme-unit-test.ly

The GUILE hash table implementation uses conflict resolution by
chaining. This means that hash lookups involve walking linked lists,
which is both relatively slow (the CPU cannot prefetch the next list
item), and takes up a lot of space (each {key, value} pair needs an
extra cons to form the linked list.

The micro-benchmark for lookup shows a 2x speedup compared to GUILE's
hashtables.

https://codereview.appspot.com/559790043

[Han-Wen Nienhuys]

dak comments

https://codereview.appspot.com/559790043

[Anonymous]

This fails make check but it is not obvious why. The logs shows just this

Forking into jobs:  (18395 18394 18393 18392 18391)


job 4 terminated with signal: 6
fatal error: Children (4) exited with errors.

I cannot find any specific log or ly file that this refers to as I cannot pinpoint what job the PID refers to.

[Han-Wen Nienhuys]

fixes

https://codereview.appspot.com/559790043

[Anonymous]

Passes make, make check and a full make doc. Reg test diff attacghed

[Jonas Hahnfeld]

On 2020/04/12 11:05:14, hanwenn wrote:

this should probably not be merged, given the inability to demonstrate speed
savings. But I'm uploading the latest version to not leave bugs in the public
record.