Mergesort Investigation Summary

• Problem statement and some experimentation
• Explanation of the algorithm I came up with in 2021.
• Recursive merge sort algorithm to have something to compare
• Re-using linked lists while bench marking
• Effect of address-ordered linked lists
• Traversing linked lists does not exhibit weird performance drops at specific list lengths
• Effect of size of linked list nodes tests whether virtual memory is somehow involved. It is not.
• Bottom-up implementation with linked lists from Wikipedia, has the same performance drops as my July 2021 algorithm
• Memory access effects: incrementing .Data values, or arbitrarily changing .Next pointers does not cause the performance drops, and looking for other anomalies
• Effect of garbage collection before preparing a new, unsorted, linked list
• The memory access patterns of recursive and wikipedia bottom up algorithms are identical. The performance is not.
• I wrote an iterative, explicit stack frame variation of recursive mergesort to try to get the same abrupt performance drops as the wikipedia bottom up algorithm. No joy.

Learnings

• Recursive is faster than iterative in this case. Again.
• Memory location of a data structure matters.
• Go’s heap allocator gives back smaller allocations from 8192-byte chunks.
• Mergesort truly is O(n log n) in time complexity.
• Different machines really do have differences in performance, sometimes incomprehensibly so.
• Detecting anomalies, like abrupt performance drops, isn’t particularly objective
• Output files need to have their provenance in them. Don’t depend on file names.
• The pattern of memory accesses (read .Data and possibly update .Next pointer) isn’t the problem. Recursive mergesort doesn’t share performance anomalies, despite identical memory access patterns as Wikipedia’s bottom up with lists
• Sorting an already sorted list doesn’t show the performance anomalies.
• Sorting a reverse sorted list doesn’t show the performance anomalies.
• Two difference CPUs/ISA show the same performance anomalies
• There might be a small 2²¹ node increment performance anomaly
• Linked list node size doesn’t affect where the performance anomalies occur.
• Layout or order of linked lists nodes affects performance generally, does not change list lengths where anomalies occur
• Garbage collection after each benchmark iteration doesn’t affect were anomalies occur

Software Engineering Notes

Data Provenance

I found that keeping data in human-readable form is a vast benefit. You can look at the data with a text editor to verify that a graph is correct. You can embed comments in the data to keep track of what the data represents, and how it was generated.

What I put in the output changed. At first, it was simple, two columns, tab-separated, linked list length, and the mean of 10 repetitions of whatever sorting algorith. Then, I added a third column, the total time of all 10 repetitions, so I could get an idea of the overhead of preparing lengthy linked lists, possibly sorting the lengthy linked lists on their addresses, etc. I added fourth and fifth columns, the minimum and maximum time it took to sort a list. I started adding provenance, info like time-of-day the benchmarking started, beginning list length, increment and ending list length. I added more and more provenance. A timestamp when the entire run started, which machine it was running on, which mergesort algorithm, any linked list preparation before sorting. I believe the final provenance I added was a timestamp at the very end of the data noting when the run finished

Implicit Binary Tree

Recursive mergesorts have a binary tree implicit in the recursive function calls. The recursive function terminates on 1-node-long lists. Once the code has split a list into left and right hand parts, it calls itself on the left part, and the right part. The only thing that’s missing is a struct named “tree” with .Left and .Right fields.

Some Meditations on Big O

Complexity only shows up in very long lists, longer than anyone would do in practice.

Code Repo

Github repo

Supporting software

I feel like I need to give praise to the supporting software I used in this investigation.

• I wrote code for this in the Go programming language, because Go programs are easier to get right.
• I used Gnuplot to generate the graphs.
• I used GraphViz to make the nice linked list diagrams.