4 ms·
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
by 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
```