Yeah, I can definitely see how that would be a more performant approach.
I suppose I wasn't so interested in figuring out how to make this algorithm as fast as possible as much I was interested in diving into why this particular implementation was slower.
I'm not totally convinced that this difference is down to the string being parsed over and over, though
> doing the UTF-8 decoding up-front is exacerbating the performance difference in the allocator
This seems to suggest that allocation might be dominating here. WDYT? Either way, I've added a disclaimer to the post.
I think this is where the GP's first suggestion comes into play. If one were writing this code _and_ cared about performance, then you'd usually find a way to reuse allocations. I submitted a PR to demonstrate this: https://github.com/christianscott/levenshtein-distance-bench...