3 ms·
FTA: The loop example iterates 1 billion times, utilizing a nested loop: u = ARGV[0].to_i r = rand(10_000) a = Array.new
by Someone 2y ago
FTA: The loop example iterates 1 billion times, utilizing a nested loop:
u = ARGV[0].to_i
r = rand(10_000)
a = Array.new(10_000, 0)
(0...10_000).each do |i|
(0...100_000).each do |j|
a[i] += j % u
end
a[i] += r
end
puts a[r]
Weird benchmark. Hand-optimized, I guess this benchmark will spend over 99% of its time in the first two lines.
If you do liveliness analysis on array elements you’ll discover that it is possible to remove the entire outer loop, turning the program into:
u = ARGV[0].to_i
r = rand(10_000)
(0...100_000).each do |j|
a += j % u
end
a += r
puts a
Are there compilers that do this kind of analysis?
Even though u isn’t known at compile time, that inner loop can be replaced by a few instructions, too, but that’s a more standard optimization that, I suspect, the likes of clang may be close to making.
- IshKebab 2y agoCompilers don't do liveness analysis on individual array elements. It's too much data to keep track of and would probably only be useful in incorrect code like this. I used to work on an AI compiler where liveness analysis of individual tensor elements actually would have been useful. We still didn't do it because the compilation time/memory requirements would be insane.
- hatthew 2y agoClosed form that works for most cases: result = ((u * (u - 1)) / 2 * (100000/u)) + (100000%u * (100000%u - 1) / 2) + r)