Profiling in Klink

Profiling in Klink

Klink is now at the stage where it makes some sense to profile it. The C part can just be profiled as C. That makes sense for the C parts, but tells me nothing about the Kernel parts. (Some of Klink is in a Kernel prolog that is loaded first) As far as the C profiler knows, that's merely _klink_cycle being called many times.

What I need to know is how much each combiner of interest causes _klink_cycle to be called. ISTM I won't need to track C-to-C calls even when they are "the same" as Kernel code. The C profiler will do a far better job of profiling C-to-C calls.

Profiling in Guile

Profiling Scheme is not like profiling C. There's no single relevant call-stack. A call might apply continuations, force promises, or cause dynamic guards to be called. It might even be returned to multiple times. There's not neccessarily much relation between the stack below a call and the amount of evaluation that that call caused.

So I looked at how other Schemes do profiling, specifically Guile. Surprise, Guile's statprof just does it the C way! It just walks up "the" stack. Exactly what I didn't want to do.

What I'm doing instead

The stack in Klink is a spaghetti stack (as usual for Scheme). It's also heterogeneous. While call frames are the "main" thing, and they are what is popped when one combiner is evaluated, the stack includes:

• call frames
• guards
• dynamic variables

So to that list I added profile structures. They contain:

• Pointer to the combiner in question
• Count of eval-cycles so far.

That much I've already written. For profiling, each _klink_cycle will push the combiner it is using. That's unless the same combiner is already being profiled in this frame, which happens when a combiner recurses as a tail call.

That's because _klink_cycle stores the profiling node above the original frame (ie, one place further away from the leaves of the stack). It has to, because it pops the frame that made that combiner launch. If it stored tail calls too, recursive functions could accumulate many profiling frames. In particular, the REPL loop would have a ton of them, because it's implemented as a recursive combiner.

I may make profiling count distinct tail calls, but for now I'm just treating tail calls as continuances of the original call.

This design will not show calls that never terminate. It's not clear that they could be meaningfully profiled. This specifically includes calls that never continue normally.

This design also doesn't try to handle re-entered continuations. The second time a continuation is used, the elapsed number of _klink_cycle counts bears no relation to how much evaluation the call caused. Again, it's not clear that this situation can be meaningfully profiled. I will probably just ignore returns other than the first time.

It's also not clear what this should do when a call's continuation is stored (say in user environment), and later is used for the first time. It would be misleading to count every _klink_cycle between the two times. So this design is far from perfect too.

Slightly different topic: Plans for the stack

Make it a list of Kernel objects

At the moment, the stack nodes are a different set of types than Klink objects. But it nags at me that they partly overlap and have an extra layer of indirection that was inherited from Tinyscheme. For instance, a combiner on the stack is very nearly a Kernel combiner object. But it also contains an environment, and it has to have a second tag to type it on the stack.

In the future I am hoping to make the stack just a list of Kernel objects. One tag would disambiguate these objects both type-wise and stack-wise.

That would let a number of "hot" stack-handling functions be simpler. But it would also eject the static environment object from stack frames. However, the static environment is mostly re-used every frame. We only need to restore environment occasionally:

• When continuing abnormally
• When popping (continuing normally out of) a vau
• When popping an eval
• In certain special contexts such as evaluating guards or promises

In some of those contexts I already have to manage environment explicitly. So I may simply move an environment argument into the continuation object, and treat an environment object on stack as meaning "restore this static environment".

Args on stack

At the moment, arglists in Klink are literally lists. There is no attempt to vectorize them, nor keep track of previous type-checks on them.

If the stack directly stored objects, it would be tempting to also use it to store an argvector when that is applicable, and to store intermediate variables on it, and even vectors of environments that we know won't be captured.

However, such objects must be categorically distinguished from all other stack objects. Combiner objects at least risk being falsely recognized as frames. All that might be required is a type that means "The next N slots are reserved, pop past them when popping frame".

COW spaghetti stacks

Months ago I blogged about a design I call COW spaghetti stacks. Basically spaghetti stacks that try to be vectors for sub-portions that allow that. The above changes would make it tempting to implement them in Klink.