My coworkers presented a silly programming interview style question to me the other day: given a list of words, find the largest set of words from that list that all have the same hash value. Everyone was playing around with a different language, and someone made the claim that it couldn't be done efficiently in bash. Rising to the challenge, I rolled up my sleeves and started playing around.

The first trick was to figure out how to write the hash function in bash. bash has functions, but they can only return an exit status in the range 0-255. There are a couple of different ways to do that, but I opted to return the value in a global variable. We also want to iterate through the letters of the word and want to take great care not invoke another process while doing so (so while read letter; do math; done <(grep -o <<<$word) is out of the question). Instead, we will use a for loop with bash expansions to iterate of each character. Finally, we will use bash 4.0 associative arrays map a letter to its corresponding index (for computing hash values).

# We will return into this variable.
declare -i HASH_RESULT
function kr1  {
    local word=$1
    HASH_RESULT=0
    for (( i = 0; i <${#word}; i++)); do
        local letter=${word:$i:1}
        (( HASH_RESULT += letter_value[$letter] ))
    done
}

Full program source below¹. With the hash function implemented, it is fairly straightforward to finish the rest of the program:

while read word; do
    kr1 $word

    (( hash_to_count[$HASH_RESULT]++ ))
    hash_to_words[$HASH_RESULT]+=" $word"

    if (( hash_to_count[$HASH_RESULT] > max_count )); then
        max_count=${hash_to_count[$HASH_RESULT]}
        max_hash=$HASH_RESULT
    fi
done <word.lst
echo ${hash_to_words[$max_hash]}

At this point it became interesting. My bash solution outperformed all the other bash solutions by a fair margin, but I wanted to see if I could do better. I ran it under a profiler and saw that it was spending all its time in many nested layers of execute_command.

This gave me the idea to try inlining the function call. Quickly prototyping a variation using an inlined function call, I run some trials (and collect statistics with my favorite tool, histogram.py²):

for variation in hash.bash hash.bash.inlined; do
  echo $variation
  for trial in {1..30}; do
    start=$EPOCHREALTIME
    bash $variation > /dev/null
    echo $((EPOCHREALTIME - start))
  done | histogram.py --confidence=.90 | head -n 2
  echo
done
hash.bash
# NumSamples = 30; Min = 3.43; Max = 3.99
# Mean = 3.529906 (+/- 0.028584); Variance = 0.009060; SD = 0.095184; Median 3.509426

hash.bash.inlined
# NumSamples = 30; Min = 2.84; Max = 3.16
# Mean = 2.932449 (+/- 0.016860); Variance = 0.003152; SD = 0.056141; Median 2.917874

As you can see, there is a greater than 15% improvement gain from inlining the function! We take this approach further, removing the local variable letter and making our code compact:

for (( i = 0; i <${#word}; i++)); do
    (( HASH_RESULT += letter_value[${word:$i:1}] ))
done

Running with this variation, we see yet another significant improvement:

hash.bash.inline_nolocals
# NumSamples = 30; Min = 2.69; Max = 2.84
# Mean = 2.749286 (+/- 0.010406); Variance = 0.001201; SD = 0.034651; Median 2.746643

At this point we run again under a profiler and notice something interesting: the first time the runtime of an execute_command call isn't dominated by another recursive call to execute_command, the function eval_arith_for_expr consumes a large portion of the time.

Furthermore, we see that a large portion of the rest of the time is eventually spent in expand_word_list_internal:

These observations lead us to another technique - we will use only one character variable names to try to optimize for these two functions. Running again with all of these optimizations, we get a huge performance improvement:

hash.bash.one_char_names
# NumSamples = 30; Min = 2.33; Max = 2.44
# Mean = 2.371499 (+/- 0.008031); Variance = 0.000715; SD = 0.026743; Median 2.363547

We can take this further, but I think I'm going to quit here for now - I improved performance by almost 50% by using a profiler and some bash-foo. Final program below³. One final note - for the love of all that is holy, don't write performant programs in bash!