I've ported a maze benchmark from Rust to Nim, here https://github.com/avahe-kellenberger/maze_bench_nim
Out of curiosity/for fun, how would you improve (i.e. speed up) the solution?
Didn't look at the algorithm at all, just applied some typical optimisation strategies (better compile flags, adding a main, inlining things, avoiding ref objects).
Times on my machine went from (range is min/max of three runs): Generation: 6.2 - 6.7 ms down to 3.4 - 3.5 ms Cold run: 9.9 - 10.4 ms down to 9.0 - 9.3 ms Warm run: 9.9 - 10.1 ms down to 8.7 9.0 ms
So about a 10% speedup, 50% in the case of the generation. I also tried to preallocate the path stack with newSeqOfCap[Point](3679) but that didn't seem to give any noticeable speedup.
My fixes can be found in this PR: https://github.com/avahe-kellenberger/maze_bench_nim/pull/1
I tried the BoolSeq from that post but it actually made the map generation about twice as slow - I merged PMunch's solution.
I am curious why a main function increases speed, I wouldn't think it'd make a difference
With this BoolSeq, i can get a speedup, at the cost of slower assignment
type
BoolSeq = object
data: seq[set[uint8]]
func newBoolSeq(length:int):BoolSeq =
result.data = newSeq[set[uint8]](length div 256 + 1)
func `[]`*(b:BoolSeq,idx:int):bool{.inline.} =
(idx mod 256).uint8 in b.data[idx div 256]
func `[]=`*(b:var BoolSeq,idx:int,val:bool){.inline.} =
let
x = idx div 256
y = uint8(idx mod 256)
if val:
b.data[x].incl y
else:
b.data[x].excl y
the other technique that helped a bit was not using a 2d coordinate system. all those multiplications ain't free.