Search code examples
arraysbashperformanceiterationdirection

Bash array iteration direction and performance

Could someone explain what is the cause of the severe slowdown when iterating bash arrays backwards?

Example:

time bash -c 'arr=();for i in {1..100000}; do arr+=( $i );done; echo "Straight"; i=0;while (( $i < 100000 )); do current_element=${arr[$i]}; ((i++));done'

Straight

real    0m0.270s
user    0m0.269s
sys 0m0.002s

time bash -c 'arr=();for i in {1..100000}; do arr+=( $i );done; echo "Reverse"; i=99999;while (( $i > 0 )); do current_element=${arr[$i]}; ((i--));done'

Reverse

real    0m25.569s
user    0m25.589s
sys 0m0.008s

Also 

${arr[i-1]} + ${arr[i]}

is much faster than 

${arr[i]} + ${arr[i-1]}

Thanks for your time.

Edit:

bash --version

GNU bash, version 4.3.42(1)-release (x86_64-redhat-linux-gnu)

Solution

  • Found some info on the matter.

    According to http://www.tldp.org/LDP/abs/html/arrays.html

    Arrays in Bash are (circularly) linked lists of type string (char *).

    I guess this means that the passed elements are sought from the beginning of the array each time, hence the slowdown. (eg: if we are at i, in order to get to i-1, we should start looking from 0)

    Also found a related post with some more info on the matter: http://spencertipping.com/posts/2013.0814.bash-is-irrecoverably-broken.html