Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up
From:
Koichi Murase
Subject:
Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up hash_search?)
Date:
Mon, 20 Apr 2020 18:48:44 +0900
2020-04-20 10:00 George Jones <fooologist@gmail.com>:
> Thank you. Patch applied and (performance) tested with come tests
> I was working on
>https://github.com/eludom/snippits/tree/master/bash/tests
> .... bottom line:
Thank you for the measurements.
Also, I am sorry that I disturbed your plan for contributing to Bash.
I actually initially doubted that the insertion with the current
implementation is O(N), so I created the test first and then found
that it is an easy fix rather than reimplementing it by B-tree or
other data structures. I couldn't stop my interest in how much it is
improved by the easy fix.
Nevertheless, I have not tuned the parameters of rehashing. Actually
it is a tradeoff between the memory consumption and the computational
time, so it is a matter of preference to some extent. I attach an
updated patch which exposes some parameters. If you have an interest,
you can play by changing the value of the parameters
`HASH_REHASH_MULTIPLIER' and `HASH_MAX_LOADFACTOR' defined in
`hashlib.h'.
--
Koichi