Hooks and recursion depth

[d-torrance]

The recursion depth seems to jump by a pretty large chunk when using hooks:

i1 : fact1 = method();

i2 : addHook((fact1, ZZ), n -> 1);

i3 : addHook((fact1, ZZ), n -> if n > 0 then n * fact1(n - 1));

i4 : fact1 ZZ := n -> (print recursionDepth(); runHooks((fact1, ZZ), n));

i5 : fact1 10
2
14
26
38
50
62
74
86
98
110
122

o5 = 3628800

Compare to:

i6 : fact2 = method();

i7 : fact2 ZZ := n -> (print recursionDepth(); if n > 0 then n * fact2(n - 1) else 1);

i8 : fact2 10
2
3
4
5
6
7
8
9
10
11
12

o8 = 3628800

Why is this? It makes it pretty easy to hit the recursion limit when using hooks.

[mahrud]

That's not quite a fair comparison because runHooks is a method with Options => true, and the implementation of MultipleArgsWithOptions is pretty inefficient. Compare with this:

i1 : fact2 = method(Options => true);

i2 : fact2 ZZ := true >> o -> n -> if n > 0 then n * fact3(n - 1) else 1;

i3 : fact3 = method();

i4 : fact3 ZZ := n -> (print recursionDepth(); fact2(n));

i5 : fact3 10
2
7
12
17
22
27
32
37
42
47
52

o5 = 3628800

If I similarly simplify runHooks, I get the precise same result:

i1 : fact1 = method();

i2 : rH0 = MutableHashTable#(runHooks, MutableHashTable, Thing, Thing);

i3 : addHook(ZZ, symbol fact1hook, n -> if n > 0 then n * fact1(n - 1) else 1);

i4 : fact1 ZZ := n -> (print recursionDepth(); rH0(ZZ, symbol fact1hook, n, Strategy => 0));

i5 : fact1 10
2
7
12
17
22
27
32
37
42
47
52

o5 = 3628800

If I optimize runHooks further then I can get it down to this:

i1 : rH0 = MutableHashTable#(runHooks, MutableHashTable, Thing, Thing);

i2 : rH = (frames rH0)#0#1 new OptionTable from { Strategy => "hooks" };

i3 : addHook(ZZ, symbol fact1, Strategy => "hooks", n -> (print recursionDepth(); if n > 0 then n * rH(ZZ, symbol fact1, n - 1) else 1));

i4 : rH(ZZ, symbol fact1, 10)
4
7
10
13
16
19
22
25
28
31
34

o4 = 3628800

which actually shows that the options handling and debug info printing behind the scenes are actually pretty optimized.

I'd be happily surprised if you can get any lower without sacrificing features, but I suspect your best bet is optimizing MultipleArgsWithOptions.

[d-torrance]

Ok, thanks for the explanation!

Is the TODO comment here related?

https://github.com/Macaulay2/M2/blob/729dcedb9437682f631c99e1473e47732dc06d1f/M2/Macaulay2/m2/methods.m2#L151-L163

[mahrud]

Yes!

[mahrud]

@DanGrayson closed #2591, but this issue would also greatly benefit from him going through and optimizing the code for evaluating method calls. I've done what I could at the top level, but the relevant code in the interpreter seems impenetrable to me.

Even going through evaluate.d, actors5.d and commenting what each of the functions do would already be very helpful, especially since a lot of the existing comments are incorrect (e.g. reference features that don't exist anymore).