Mergesort Investigation 5 - address ordered linked lists

Based on the effects of linked list re-use, I checked if using a linked list with in-memory-address-order made a difference.

The code to create a linked list whose nodes’ .Next pointers always contain a higher address than the nodes own addresses looks like this:

    head := &Node{} 
    head.Data = uint(uintptr(unsafe.Pointer(head)))
    tail := head

    for i := 1; i < n; i++ {
        nn := &Node{}
        nn.Data = uint(uintptr(unsafe.Pointer(nn)))
        tail.Next = nn
        tail = tail.Next
    }

    head = recursiveMergeSort(head)
    return rerandomizeList(head)

This creates a list whose .Data values have the address of the node in them, sorts the list small-to-large treating those addresses as numbers, then makes the list unsorted by putting a randomly-chosen integer into the .Data field of each node.

This made only a little difference.

Starting with an address-ordered linked list made no difference relative to an “idiomatic” memory layout linked list for the Macbook, and only a little for the Dell R530. The Qotom sorted lists faster when starting with a list laid out from low to high memory. All machines exhibit the abrupt performance loss that’s the cause of this investigation no matter how the linked lists are initially laid out.