Parsing performance of large YAML files

[PJB3005]

We're using YAML as a data format in our game, from data definitions to map files. We have a modestly sized map files now (that is at the time of writing, ~700 KiB uncompressed/38k lines).

I should note that we're not using deserialization features, JUST the AST (YamlMappingNode etc directly).

The parsing performance is really starting the hurt (currently taking about 10% of debug server startup time just spent inside YamlDotNet parsing the main map file) and, the kicker, 90% of that time is spent inside various collection ops like Array.Copy, List.Insert and List.RemoveAt.

Some profiling results

Could this be optimized? I tried saving the map files in flow style instead (since from my looking at the code the reason there's so many list butchering is because of parsing issues with block style?) but it did not seem to help perf. In fact it seems slightly worse with flow style.

[aaubry]

There's probably room for improvement. I would be interested in exploring this but I can't dedicate much time to performance right now because I already have another development in progress. I can probably provide some help if you guide this process, though.

I've looked at InsertionQueue, which appears in your screenshot, and I can see that there's a big TODO:

// TODO: Use a more efficient data structure

Looking at the Dequeue method, it is clear that it is really inefficient since it always removes the first item from a List, meaning that every other element needs to be shifted. We could start by changing this implementation to use a more efficient algorithm.

[aaubry]

Would you be able to provide an example of such a large YAML file ?

[PJB3005]

Would you be able to provide an example of such a large YAML file ?

From our repo

[aaubry]

Hello!
I've changed the implementation of InsertionQueue and LookAheadBuffer in an experimental branch. Would you be able to test your code against this build to see if there is any improvement ?

[PJB3005]

Pretty good improvement!

Before:

After:

[aaubry]

Nice! I'll merge this change then.
Of course this was just a low-hanging fruit. I'm sure there are many more optimizations that can be performed. If you can identify more bottlenecks, I can see what we can do.

[EdwardCooke]

Since there was a fix for this merged in, I'm going to close this issue. If you need more assistance, let me know.