3 ms·

2013 - is this still the case 10 years on?

• louisbuchbinder 3y ago
  Yes or at least something similar. TLDR array lookups are not constant time in bash. I tested on my M1 Mac which came with bash3.2 installed and on ubuntu:22.04 with bash5.1. Interestingly bash5.1 seems to be able to traverse in reverse order based on bench65536. ```benchmark.sh #!/bin/bash xs=($(seq 65536)) function bench0() { local x=${xs[0]} y=${xs[0]} } function bench16384() { local x=${xs[16384]} y=${xs[0]} } function bench65536() { local x=${xs[65536]} y=${xs[0]} } function bench() { for n in $(seq 65536); do $1 done } echo bash version: $BASH_VERSION printf '\n%s:' 'bench0: local x=${xs[0]} y=${xs[0]}' time bench bench0 printf '\n%s' 'bench16384: local x=${xs[16384]} y=${xs[0]}' time bench bench16384 printf '\n%s' 'bench65536: local x=${xs[65536]} y=${xs[0]}' time bench bench65536 ``` ```m1mac.txt bash version: 3.2.57(1)-release bench0: local x=${xs[0]} y=${xs[0]}: real 0m0.366s user 0m0.346s sys 0m0.020s bench16384: local x=${xs[16384]} y=${xs[0]} real 0m1.704s user 0m1.676s sys 0m0.028s bench65536: local x=${xs[65536]} y=${xs[0]} real 0m5.443s user 0m5.393s sys 0m0.050s ``` ```docker_ubuntu2204.txt bash version: 5.1.16(1)-release bench0: local x=${xs[0]} y=${xs[0]}: real 0m0.348s user 0m0.345s sys 0m0.005s bench16384: local x=${xs[16384]} y=${xs[0]} real 0m2.394s user 0m2.390s sys 0m0.005s bench65536: local x=${xs[65536]} y=${xs[0]} real 0m0.348s user 0m0.345s sys 0m0.005s ```