AST Walker: Loop vs Visitor Design Pattern

Help & Support
1

I was looking through Crystal’s semantic analyzer which unsurprisingly uses Visitor design pattern and it made me wonder how fast I could get an AST walker that uses loop instead. So I decided to benchmark a loop walker against a visitor walker on a simple AST.

The loop version is roughly 50x slower which is not entirely surprising because of the dynamic arrays, but I couldn’t wrap my head around why the visitor version uses ~50x more memory.

Does anyone know why this is the case? Also I’d like to know how to reduce memory usage for the visitor version or how to make the loop version faster.

VISITOR WALKER 116.34M (  8.60ns) (± 2.64%)  0.0B/op        fastest
   LOOP WALKER   1.99M (503.74ns) (± 4.25%)  864B/op  58.61× slower

The code is here. Needs to be run with the --release flag.

1 Like
2

I wish benchmark would show what is what in each column. For reference:

name           iters/s     s/iter            memory   relative
VISITOR WALKER 116.34M (  8.60ns) (± 2.64%)  0.0B/op        fastest
   LOOP WALKER   1.99M (503.74ns) (± 4.25%)  864B/op  58.61× slower

Note that the first number is iterations per second. The B/op is the memory consumed. Visitor doesn’t consume memory. Your loop does when you do return [@name, @params, @body], that’s an array allocation right there. This is definitely going to be slower than visitor. Also visitor has no reason to be slow.

2 Likes
3

Sorry if the above sounded harsh, I was in a hurry and didn’t have time to write it in a better way.

2 Likes
4

Thanks a lot. Your explanation makes sense.

5

I didn’t know there was another mainstream way to build and AST. This was interesting to read. I know this probably would not matter but you are using a rather old version of Crystal and a really old version of LLVM.

6

I only used repl.it to share the code. I have latest Crystal release on my machine.