Generate algorithm visualizations from parsed logs

[adamconkey]

The core idea was initially described here: #15 (comment)

Currently the convex hull algorithm visualizations rely on ConvexHullTracer struct to separately track low-level steps in the algorithm. This was simple to implement but has the downside that you need to muddy the core algorithm code with tracing logic that isn't even relevant unless you are actively running the algorithm visualization. To me it's a distraction in the code. I have additionally added trace-level logging (#75 and #81) so now there are effectively two sources of tracing which is redundant.

The idea here is to remove the tracing-specific code, have only trace-level logs, and create a log parser that can reconstruct the information needed to generate visualizations directly from the logs.

One cool feature of this that I think would be possible is to support different fidelity visualizations, so if you enable say debug-level logs, it will show the high-level steps in the algorithm which might be most suitable for understanding and debugging the main steps in the algorithm. But if you enable trace level, then it would show truly every step that was done and could also show what's the state of the data structures and such, which would be helpful for debugging the finer details and for digging deep on understanding the code.

Need to figure out how to create parse-able versions of the logs, I assume there's a cool way to aggregate them into a code-readable form but worst case scenario I bet you could redirect to a file and just parse the file.

[adamconkey]

I think my best bet for getting this going quickly is to try to just write logs to a file and create a parser for the file. flexi_logger looks like a nice starting point: https://docs.rs/flexi_logger/latest/flexi_logger/code_examples/index.html

[adamconkey]

Have a basic version of this working for Incremental convex hull algorithm and am currently working on porting GrahamScan. I did indeed use the flexi_logger crate and have the file parsing working. Went back and forth on the correct way to serialize and deserialize. I tried using kv (key-value) logging but that made log parsing more difficult, as I wanted to be able to leverage serde (de)serialization as much as possible so that I didn't truly have to write my own deserialization logic.

The best way I could come up with is to create step structs, e.g. IncrementalStep that stores the exact attributes of any given algorithm step needed to reconstruct the visualization on the other end. This is then similar to what I had before with ConvexHullTracerStep, but instead of having one super step for all convex hull algorithms, I'll have separate more minimal steps for each algorithm. There's some opportunity to abstract out the commonalities between them (e.g. index and hull ids) but I'll leave that for later.

There is one quirk I don't love but is perhaps a short-term necessity, is I'm having to implement the Display trait for them so that it correctly writes the optional values in the logs, i.e. if there's an Optional value than it will not write it, instead of writing None which would happen with default serialization. And it won't write Some(value) which is what also happens by default. Then I can readily use serve_hjson to easily deserialize (together with a regex that is reasonably simple to define). Ideally I wouldn't have to write Display and could just rely on an inherited serialization, but I couldn't quickly find a crate that did exactly what I wanted.

Currently I don't think I've saved myself much code from what I had with the tracer code, but I still like this idea better that I can have zero-overhead tracing by having log statements and parsing those to generate visualizations. I also think I will ultimately save a bit in the code once I add some custom macros. For example, currently I have a block that looks like this:

debug!(
    "{}",
    GrahamScanStep {
         idx: idx + 1,
         new_id: Some(new_v.id),
         hull_ids: stack.clone(),
    }
);

I think I can write a custom macro that will handle all that, and all you have to do is pass the values to it, e.g.

log_graham!(idx + 1, new_v.id, stack.clone())

Very compact! 🤩

[adamconkey]

I have a workable port from the initial trace infrastructure so I will go forward with merging that. I'm going to create a separate ticket for the macro mentioned in my previous comment. I'm also sure I will do some minor refactors to cut down on some boilerplate at the outset of the visualization algorithms. One thing I'm considering is to have a tighter coupling of the algorithms to the step type, but I'm not yet sure what is the best way to achieve that quite yet.

[adamconkey]

Created these follow-up tickets to address a couple smaller things:

• Create macros for algorithm tracing steps #85
• Add logs to algorithm visualization in rerun #87