Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > gnu.bash.bug > #16184

Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up hash_search?)

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

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

Back to gnu.bash.bug | Previous | Next | Find similar

Thread

Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up hash_search?) Koichi Murase <myoga.murase@gmail.com> - 2020-04-20 18:48 +0900

csiph-web