Tail recursion limit not working

[t-paul]

sin = function(x) sin(); 
echo(sin(30)); 

[thehans]

I did some debugging and profiling and found that the limit counter is counting just fine, but its just slowing to a crawl before reaching the limit, because it spends ever increasing time in prepareTailCallArguments every time it recurs.

Problem is this->defaultArguments gets another duplicate x variable added to it for each recursion(Line 556)
Then all those get inserted into variables (Line 564).
Then the vast majority of runtime is spent updating the hashmap of tailCallContext setting x=undefined repeatedly (Lines 570-572).

openscad/src/expr.cc

Lines 554 to 572 in 2a943a5

	for (const auto &arg : definition_arguments) {
	if (this->resolvedArguments.find(arg.name) == this->resolvedArguments.end()) {
	this->defaultArguments.emplace_back(arg.name, arg.expr ? arg.expr->evaluate(context) : ValuePtr::undefined);
	}
	}
	}
	std::vector<std::pair<std::string, ValuePtr>> variables;
	variables.reserve(this->defaultArguments.size() + this->resolvedArguments.size());
	// Set default values for unspecified parameters
	variables.insert(variables.begin(), this->defaultArguments.begin(), this->defaultArguments.end());
	// Set the given parameters
	for (const auto &ass : this->resolvedArguments) {
	variables.emplace_back(ass.first, ass.second->evaluate(context));
	}
	// Apply to tailCallContext
	for (const auto &var : variables) {
	tailCallContext->set_variable(var.first, var.second);
	}

So the problem is clear, but I'm a little confused about the overall handling of contexts and variables here to know the proper fix.

[thehans]

@jschobben It looks like this regression is a result from some of your tail recursion changes in #3020. Any ideas how to best resolve this?

[jschobben]

Hmm, this looks like a silly bug. Line 549-559 is supposed to only execute once (sort of a lazy init or cache). Maybe with the function literals that now happens each time for this example. The "cache" is tied to a node in the AST, which probably works differently in this new use case.

A fix should probably be in restoring the "running once" of the if-block. Might be a bit tricky with the dynamic-ness of function literals.

Right now I'm not around my pc for a while, building openscad on my phone works but takes up to 2 hours :D
I'll look into this when back home, in about 2 weeks, if it's still open then.

[jschobben]

A temporary workaround might be to change defaultArguments from vector to map, which should fix the quadratic behavior but not the proper usage of the cache. Not sure about importance of argument order though, has to be checked.

[jschobben]

Or maybe the call to EvalContext->resolveArguments on line 552 just returns an empty map? That would also cause the if-block and line 556 to always execute. If so then maybe tracking the "not-filled-yet" status of resolvedArguments just needs to be improved (better than .empty()), or that for-loop in 554-558 needs an extra guard.

I need my debugger :D

[thehans]

Yes EvalContext::resolveArguments returns a AssignmentMap based on the number of parameters from the call site which in @t-paul's example is empty: sin().

I'm thinking that resolveArguments should be changed so that it returns a map with containing all of definition_arguments. So omitted arguments in a call will have their default expression(or undef if none) mapped to their name by resolveArguments.

Then on Line 549, instead of checking
if (resolveArguments.empty())
it could check
if (this->resolvedArguments.empty() && !definition_arguments.empty())
and I think we could get rid of this->defaultArguments entirely.

Since setting default arguments is currently dependent on whether the call site contains arguments, this means that it won't re-evaluate in the following case where default should get modified:

// resolvedArguments is NOT empty
$test = 0; 
sin = function(x=0,y=$test) let($test=$test+1, z=assert($test<=10) echo(x,y,$test)) sin(x);   
echo(sin(30));

Results:

ECHO: 30, 0, 1
ECHO: 30, 1, 2
ECHO: 30, 1, 3
ECHO: 30, 1, 4
ECHO: 30, 1, 5
ECHO: 30, 1, 6
ECHO: 30, 1, 7
ECHO: 30, 1, 8
ECHO: 30, 1, 9
ECHO: 30, 1, 10
ERROR: Assertion '($test <= 10)' failed in file issue3118.scad, line 3

But its inconsistent because when no arguments are passed, it does re-evaluate the defaults, which is more like what I would expect:

// resolvedArguments always empty
$test = 0; 
sin = function(x=0,y=$test) let($test=$test+1, z=assert($test<=10) echo(x,y,$test)) sin();   
echo(sin(30));

Results in:

ECHO: 30, 0, 1
ECHO: 0, 1, 2
ECHO: 0, 2, 3
ECHO: 0, 3, 4
ECHO: 0, 4, 5
ECHO: 0, 5, 6
ECHO: 0, 6, 7
ECHO: 0, 7, 8
ECHO: 0, 8, 9
ECHO: 0, 9, 10
ERROR: Assertion '($test <= 10)' failed in file issue3118.scad, line 3

[thehans]

I started looking at changing resolveArguments but I realized yet another thing which gave me pause.

Its not very clear how positional vs named arguments are supposed to behave in some situations, so I wrote this test script to help see: arg-permutations.scad.txt

It basically defines the following function, and calls it with all combinations (I decided its too many to quote the whole script directly) of named and un-named parameters in all possible positions:

function f(a="a", b="b", c="c") = [a,b,c];

Here is the output, which I've filtered to show only lines which I consider problematic:

ECHO: "f(a=1,2)", [2, "b", "c"] 
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 12
ECHO: "f(2,a=1)", [1, "b", "c"]
ECHO: "f(a=1,2,3)", [2, 3, "c"] 
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 14
ECHO: "f(2,a=1,3)", [1, 3, "c"]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 15
ECHO: "f(2,3,a=1)", [1, 3, "c"]
ECHO: "f(b=2,1,3)", [1, 3, "c"]
ECHO: "f(1,b=2,3)", [1, 3, "c"]
WARNING: argument b supplied more then once, in file arg-permutations.scad, line 22
ECHO: "f(1,3,b=2)", [1, 2, "c"]
ECHO: "f(a=1,b=2,3)", [3, 2, "c"]
ECHO: "f(a=1,3,b=2)", [3, 2, "c"]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 35
ECHO: "f(3,a=1,b=2)", [1, 2, "c"]
ECHO: "f(b=2,a=1,3)", [3, 2, "c"]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 37
ECHO: "f(b=2,3,a=1)", [1, 2, "c"]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 38
ECHO: "f(3,b=2,a=1)", [1, 2, "c"]
ECHO: "f(a=1,c=3,2)", [2, "b", 3]
ECHO: "f(a=1,2,c=3)", [2, "b", 3]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 44
ECHO: "f(2,a=1,c=3)", [1, "b", 3]
ECHO: "f(c=3,a=1,2)", [2, "b", 3]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 46
ECHO: "f(c=3,2,a=1)", [1, "b", 3]
WARNING: argument a supplied more then once, in file arg-permutations.scad, line 47

I'm not sure the best way to handle all these, but I think they would be covered if we followed the way Python seems to handle such situations:

1. It does not allowed unnamed args to come after named args
   SyntaxError: non-keyword arg after keyword arg
2. If a named arg is set after an unnamed arg in its defined position, this results in an error
   TypeError: f() got multiple values for keyword argument 'a'

[thehans]

Alternatively we could process all named args first, and fill in positional gaps with any other args, which I think would also allow for all those test cases to function in a somewhat reasonable manner without any warnings or errors.

But that would be a little trickier to implement, and maybe that encourages sloppy, harder to decipher scripts.

[MichaelAtOz]

Wouldn't changing that probably break a whole bunch of existing code?

[thehans]

@MichaelAtOz you mean the second suggestion I made of processing named args and filling the gaps? I think it would only change behavior of code that wasn't really working in the first place, which is to say some parameters were already being overridden/ignored (and without warning in some cases).

If we would rather keep behavior as is and simply warn whenever parameter values are being overridden then we could do that without breaking anything at all. So ignoring the ones that already emit warnings leaves 9 cases from the above example which silently override named or positional arguments:

1) ECHO: "f(2,a=1)", [1, "b", "c"]
2) ECHO: "f(2,3,a=1)", [1, 3, "c"]
3) ECHO: "f(b=2,1,3)", [1, 3, "c"]
4) ECHO: "f(1,3,b=2)", [1, 2, "c"]
5) ECHO: "f(a=1,b=2,3)", [3, 2, "c"]
6) ECHO: "f(3,a=1,b=2)", [1, 2, "c"]
7) ECHO: "f(3,b=2,a=1)", [1, 2, "c"]
8) ECHO: "f(a=1,c=3,2)", [2, "b", 3]
9) ECHO: "f(2,a=1,c=3)", [1, "b", 3]

Adding a warning based on the second "Python rule" I wrote above would address cases 1,2,4,6,7,9 from that remaining set.

Then there's 3 left:

3) ECHO: "f(b=2,1,3)", [1, 3, "c"]
5) ECHO: "f(a=1,b=2,3)", [3, 2, "c"]
8) ECHO: "f(a=1,c=3,2)", [2, "b", 3]

These could be covered by the first Python rule above, but that feels heavy handed and would create warnings where there's not necessarily a problem
eg. ECHO: "f(c=3,b=2,1)", [1, 2, 3] would create a new warning even though its fine IMO.
So to avoid superfluous warnings, we might want something more specific like
"WARNING: positional argument overrides named argument X ...".

But regardless of the decided solution I think this test case is important to add so we can know for sure whether or not changes to resolveArguments are affecting behavior.

[thehans]

I've just opened a PR with the fix for original issue, plus added warnings as discussed above.

@jschobben Since you've worked on this most recently, I'd appreciate a review of my changes if you have time.

I changed the local stack handling because context keeps a shared_ptr to its parent which I think should be enough.

There was one other thing that caused me some headache, where I thought I could evaluate and set the variables in-order with a single loop in prepareTailCallContext:

openscad/src/expr.cc

Lines 555 to 562 in fb5fe91

	/*
	for (const auto &arg :this->resolvedArguments) {
	tailCallContext->set_variable(arg.second.name,
	arg.second.expr ?
	(arg.first ? arg.second.expr->evaluate(context->getParent()) : arg.second.expr->evaluate(context)) :
	ValuePtr::undefined);
	}
	//*/

Until I finally realized that its a problem because c_next is actually a parent of c_local. That seems backwards, but I couldn't figure out a way to rearrange contexts and make it all work.
It caused issues when a var is evaluated and set, then a second variables expression includes that first var, but the lookup gets the newly set value when it needed the previous one.

[jschobben]

That is a decently-sized PR, hope you don't mind if it takes me a while 🙂 Guess it was still more complicated than fixing the resolvedArguments.empty() guard then.

Just to be clear, is most of it to enable the fix, or does the warnings part also cover a lot of code (beside test cases/expected output)?

I'll try my best at a phone-based review.

One other question: there aren't real KPI tests yet, but how does this impact performance? As that was the reason to introduce the flawed caching.
Say, as a poor-man's KPI test by running time openscad ... from the shell on something like: function speed(n=1000000) = n == 0 ? 42 : speed(n-1);, compared to master?

[jschobben]

About c_local/c_next: I suppose those could have benefitted from some more comments, indeed, and c_next should maybe be called c_entry or something.
c_local is the context of the current code path through the function, or the top of its stack really.
c_next is updated in-place just before the tail call "happens", with the relevant parts (definition arguments) of c_local. It then forms the unfortunately-named parent of the fresh c_local stack in that tail call. So most of the time, it represents the context at function entry of the current call.

[thehans]

That is a decently-sized PR, hope you don't mind if it takes me a while Guess it was still more complicated than fixing the resolvedArguments.empty() guard then.

Just to be clear, is most of it to enable the fix, or does the warnings part also cover a lot of code (beside test cases/expected output)?

Well, 12 of the 18 files changed are test related. I fix a small spelling in the warnings "then" -> "than", and added quotes around named variables, so that affected a few more than the one test I added..

I did end up getting a little carried away and doing some whitespace refactoring in expr.cc which is where a lot of the line changes are. I probably should have left that to a separate commit, since it clutters the changes a bit. Sorry about that, but hopefully easy enough to identify and just scroll past those in review.

The biggest actual code change was re-writing resolveArguments to detect the different types of variable override situations (and changing its return type to a vector instead of map).

One other question: there aren't real KPI tests yet, but how does this impact performance? As that was the reason to introduce the flawed caching.
Say, as a poor-man's KPI test by running time openscad ... from the shell on something like: function speed(n=1000000) = n == 0 ? 42 : speed(n-1);, compared to master?

I tried your performance test suggestion, and added a loop to give it a bit more to chew on:

function speed(n=1000000) = n == 0 ? 42 : speed(n-1);
for(i=[0:20]) echo(speed());
//  time ./openscad -o test.echo ~/Desktop/OpenSCAD\ Perf/speed_test.scad

Results are averaged over 5 consecutive runs per build:

master 
  real 9.700s
  user 9.692s
  sys  0.006s

PR
  real 8.909s
  user 8.905s
  sys  0.003s

So its consistently a bit faster than before.

Let me know if you have any other test ideas to try.

[thehans]

Oh and I did a small unrelated refactoring in primitives.cc (limiting lookup of $fn,$fs,$a to only the primitives which use them) which was just something that caught my eye while I was debugging the context setting changes I made.

[thehans]

@jschobben Just to summarize, I was mainly hoping for some input or thoughts about the changes in expr.cc:prepareTailCallContext and expr.cc:evaluate_function, if you think those still make sense. I also just added a comment to the PR diff for one specific part that was bothering me.

The tests pass at least, which is a good sign, but I don't know if we are thoroughly testing all the possibilities that function literals introduce.

[jschobben]

@thehans unfortunately I barely had time the past week, sorry about that. At first sight the changes look good, and improving performance is of course excellent 🙂

To be honest I felt the whole prepareTailCallContext method and its caching was a bit dirty, so this PR looks like a good improvement already.

In 2 days I'll be back home, then I can do a proper review.

[jschobben]

Finally found some time to look, after enjoying 2 flight cancellations 😅
Looks like another PR has been made and merged already, great!
If you need help to rebase the original PR and maybe split it into commits, I am happy to assist.

[kintel]

Fixed by #3181