bug-bash
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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 <address@hidden>:
> 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

Attachment: 0001-hashlib-Implement-rehash.v2.patch
Description: Binary data


reply via email to

[Prev in Thread] Current Thread [Next in Thread]