Mergesort Investigation 10 - garbage collection

Previously, in July 2021, I had tried to remove garbage collection from the possible variables affecting my iterative mergesort. I transliterated the Go code to a plain C version that could not have any garbage collection. The C code benchmarked very similarly to the Go code.

During the current investigation I’ve discovered hat the layout of the initial, unsorted, linked list in memory can have a drastic effect on how long sorting or even merely traversing, the linked lists can have.

I added code to my benchmarking that loses any reference to the linked list, then runs garbage collection after sorting iteration. None of the mergesort algorithms generate any garbage while sorting, but creating a new linked list immediately after sorting one might cause some non-locality-of-reference in the new linked list. Garbage collection is mysterious enough that it’s worth investigating.

Above, benchmarks run on my Qotom fanless server, July 2021 algorithm, and Wikipedia’s bottom up with lists algorithm, with and without garbage collection after sorting, but before constructing a new list.

The purple line (“Qotom, July 2021 algorithm”) and the golden line (“Qotom bottom up algorithm”) on this graph are the same as the blue line and the gold line respectively on this graph,

With and without garbage collection, as executed by a Macbook with an M2 ARM CPU.

The purple and green lines are rendered from the same data as the yellow and dark blue lines respectively on this graph,

Conclusions

Collecting garbage after sorting a list, but before constructing a new list, made absolutely no difference. Benchmark data was nearly identical. Performance drops occurred at the same list lengths.

I hypothesize that the linked lists are so large, consuming so much memory, that there was already effective reuse of the previous iteration’s linked list memory, even though an explicit runime.GC() did not exist in my benchmarking code.

I’m only including this because I did the work, and I want to document everything.