The performance of linkdom.NodeShellSort

[Richard Webb]

The NodeShellSort function contains a 'gapseq' array that gets rebuilt on each call, and when making large numbers of calls to sort with collections of length 0 or 1 (for example, when there is a large number of nodes with one attribute each), i see a large performance gain when making the array 'static immutable' instead of const.

This is with DMD 2.058 on Windows. (which is itself a lot faster than 2.057 due to GC optimizations).

(fwiw the performance issue looks like hidden calls to __d_arrayliteralTX causing large amounts of GC traffic).

[Richard Webb (numpsy)]

As an example, it takes ~5 seconds to load the attached file with the current version, but i see that drop by over a second with that change (i was quite surprised by the size of the improvement).

[michaelrynn (michael-rynn-500)]

Thank you very much for the example file, and a smart idea in making it.
I made the change to sortMe, and NodeShellSort.
Made a bigload project, and did repeated tests on loading 5, 50, 500, 5000, and 50000 objects from cuts of your testgen.xml file.
Added timings and garbage collection statistics to static create and delete counters to various root objects, to see how garbage collector is doing its job, or not.
For large Documents, linkdom needs a garbage colleciton help.
ArrayDom and original slow std.xml better at this.

Added explode method, to demolish large Documents. Of course its optional, but current garbage collector gags out on larger data sets.

Added same to arraydom and std.xml1. New code is more susceptible to being missed by bad garbage collection.
explode gaurantees DOM cleanup, leaving the immutable strings for the garbage collector. Risk of dangles increases if used.