+++ title = "Fixing GNU bash associative array insert speed" author = ["George M Jones"] publishDate = 2020-04-18T00:00:00-04:00 lastmod = 2023-12-06T05:45:13-05:00 tags = ["geek", "programming", "gnu", "linux"] categories = ["blog"] draft = false +++
Bash uses linear search to insert values in to associative arrays. This is all well and good for small numbers of keys. I was adding millions[^fn:1]. I went poking around the bash source code today (2020-04-18) to confirm my suspicion and gauge the difficulty of adding an option to do something more sensible.
In less than a day after I reported it, there is a patch https://lists.gnu.org/archive/html/bug-bash/2020-04/msg00114.html My timing code and pre and post patch timings are here: https://github.com/eludom/snippits/tree/master/bash/tests
Here the steps I took and where I might go if I get serious about fixing the problem:
find the homepage : A quick bit of googling lead to the homepage http://savannah.gnu.org/projects/bash/
use git : For a minute it looked like GNU was still stuck in the bad old
days of having to download a tarball and then apply a series
of patches, but fortunately, it there is a git repo <http://savannah.gnu.org/git/?group=bash>
git clone https://git.savannah.gnu.org/git/bash.git
Bash follows a time honored build convention
./configure
make
hashlib.c
/* Create an entry for STRING, in TABLE. If the entry already
exists, then return it (unless the HASH_NOSRCH flag is set). */
BUCKET_CONTENTS *
hash_insert (string, table, flags)
char *string;
HASH_TABLE *table;
int flags;
{
BUCKET_CONTENTS *item;
int bucket;
unsigned int hv;
if (table == 0)
table = hash_create (0);
item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL
: hash_search (string, table, 0);
hash_search()
/* Return a pointer to the hashed item. If the HASH_CREATE flag is passed,
create a new hash table entry for STRING, otherwise return NULL. */
BUCKET_CONTENTS *
hash_search (string, table, flags)
const char *string;
HASH_TABLE *table;
int flags;
{
BUCKET_CONTENTS *list;
int bucket;
unsigned int hv;
if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0))
return (BUCKET_CONTENTS *)NULL;
bucket = HASH_BUCKET (string, table, hv);
for (list = table->bucket_array ? table->bucket_array[bucket] : 0; list; list = list->next)
{
/* This is the comparison function */
if (hv == list->khash && STREQ (list->key, string))
{
list->times_found++;
return (list);
}
}
see if they would even entertain the idea of a patch
See https://lists.gnu.org/archive/html/bug-bash/2020-04/msg00114.html
[^fn:1]: yes, there are many better tools for this job, but not in the constrained environment where this had to run.