Hi everyone!
I have a question about time complexity of vector indexing. Obviously, it should be constant, but if I do the following naive tests it looks linear. What do I do wrong?
Ivan
$ for i in 10000000 20000000 40000000 80000000 ; do cat vec_in_"$i".hs; ghc -fforce-recomp -O2 --make vec_in_"$i".hs && time ./vec_in_"$i"; done
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 10000000
[1 of 1] Compiling Main ( vec_in_10000000.hs, vec_in_10000000.o )
Linking vec_in_10000000 ...
10000001
real 0m0.033s
user 0m0.032s
sys 0m0.000s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 20000000
[1 of 1] Compiling Main ( vec_in_20000000.hs, vec_in_20000000.o )
Linking vec_in_20000000 ...
20000001
real 0m0.062s
user 0m0.060s
sys 0m0.000s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 40000000
[1 of 1] Compiling Main ( vec_in_40000000.hs, vec_in_40000000.o )
Linking vec_in_40000000 ...
40000001
real 0m0.125s
user 0m0.120s
sys 0m0.004s
import Data.Vector.Unboxed
main = do
let a = enumFromN 1 100000001 :: Vector Int
print $ a ! 80000000
[1 of 1] Compiling Main ( vec_in_80000000.hs, vec_in_80000000.o )
Linking vec_in_80000000 ...
80000001
real 0m0.244s
user 0m0.240s
sys 0m0.000s
