Opening a large yaml file is very slow

[dlang-community]

Opening a large yaml file is very slow

Interestingly, PYYAML, which inspired D-YAML can load the document twice faster.

$ git clone https://github.com/yaml/pyyaml
$ cd pyyaml
$ sudo python setup.py --without-libyaml install
$ python
Python 2.7.14 (default, Feb 17 2018, 10:42:17) 
[GCC 7.3.1 20180130 (Red Hat 7.3.1-2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>stream = file('typeIDs.yaml', 'r')
>>>yaml.load(stream)

The bottleneck is actually a complexity problem, here

void merge(ref Appender!(Node.Pair[]) pairs, ref Node.Pair toMerge) @trusted
{
    foreach(ref pair; pairs.data)
    {
        if(pair.key == toMerge.key){return;}
    }
    pairs.put(toMerge);
}

checking for equality has a terrible complexity. remove the check and the test case finishes in 6 secs (although being certainly wrong in regard of the content). This function is called in

Composer.Node composeMappingNode(const uint pairAppenderLevel, const uint nodeAppenderLevel)

If anyone want to fight against this issue you have the yaml file here

I've profiled with callgrind (3 hours to complete 😅 ).
Results are here: https://gist.github.com/BBasile/d8b9da00100a25ab411c89a8a0710582, and are much better than those from the built-in profiler. Use KCacheGrind to visualize.

[Erikvv]

Thanks for putting in the work.