As some of you may know, I've been reading Doug Gregor's series on introducing Swift to people coming from C++; I don't know if I'm exactly the kind of C++ programmer targeted here: my professional practice is in the embedded space, where the standards are rather more conservative than the C++17+ features taken as reference there, but I learned a few nuggets nevertheless.
But what most interested me was this one: withoutActuallyEscaping(_:do:). For you see, one of the difficulties with my algorithm is that I need to keep a reference to variables in active frames so lower frames can use them in case they are ever needed (for printing a solution when it is found, mostly). Thankfully, these variables can be captured immutably, so the references in question are easy to handle (e.g. they are trivially sendable) nevertheless these captures need to happen often, need to be passed around even more often, and are invoked very rarely. But I also need to expose these references uniformly with other previously captured references, in practice here by stuffing the closure (which has a reference to the capture) in a data structure, and you know what that means: it becomes escaping, even though it won't actually escape; but I can't prove that to the compiler!
This is not just a problem in Swift, the Rust port of the algorithm has the exact same issue; the penalty might be lessened in a garbage-collected language that scans memory (I haven't tried), but it would still be there. I don't think I could expose the demonstration that the capture doesn't escape to anything short of a dedicated proof-writing language like Coq (or my fellow humans, of course), so I resigned myself to the penalty of escaping closures and their heap allocation as the price to pay for operating in a memory-safe language.
So let's try and see whether withoutActuallyEscaping improves the situation! Addition of this functionality was straightforward, except I needed to add it to a second place in order to avoid the dreaded Passing a non-escaping function parameter 'action' to a call to a non-escaping function parameter can allow re-entrant modification of a variable diagnostic… and, oh, yeah, I also needed to further distinguish the async parts from the non-async ones, as the captures made in the async part (the main wagon) may actually escape, since the trainees may cause them to be kept alive while the main wagon has already backtracked from that branch of the bifurcation (but remember CPU utilization of the main wagon is a rounding error).
Let's look at the results:
N| T | factor
1|100 | ref
2| 75.0|x1.33
3| 67.1|x1.49
4| 64.5|x1.55
5| 51.9|x1.93
6| 45.1|x2.22
7| 42.8|x2.33
8| 39.3|x2.54
9| 39.3|x2.54
10| 39.8|x2.52
11| 39.4|x2.54
12| 39.1|x2.56
…ouch. That hurt. It's fortunate I did not spend too much time on this, because we are back at the scalability of the naive Swift version. Looks like the runtime checking of withoutActuallyEscaping is having an impact, though I can't tell anything besides that: the changes in code have caused quite a shift in the captured stacks, resulting in the flame graphs (not shown here) being hard to compare. Suffice to say I did not see any obvious inefficiency to remove, or any way to salvage the effort.
In the end, I reverted the change.
To be continued…