main.cpp for the perf tests

list.h

#pragma once

#include <memory>
#include <iostream>
#include <string>


template <typename value_t>
class linked_list {
public:
    /// Inserts the given value in the linked list in the correctly sorted order.
    /// @precondition the assumption is that the linked list is _already_ in sorted order.
    void insert_sorted(const value_t& Value) noexcept;
    
    /// Inserts the given value at the index specified. If the index is greater than the
    /// number of elements, then the value is appended to the end of the list.
    void insert_at(uint64_t Index, const value_t& Value) noexcept;

    /// Inserts the given value at the front of the linked list.
    void push(const value_t& Value) noexcept;

    /// Inserts the given value at the end of the linked list.
    void push_back(const value_t& Value) noexcept;
    
    /// Returns the given node value located at the index. If the index is out of the
    /// range of possible nodes, then `nullptr` is returned.
    ///
    /// NOTE: std::optional would be preferred, but clang doesn't support it yet.
    std::weak_ptr<value_t> value_at(uint64_t Index) noexcept;
    
    /// Outputs the values of the linked list to `stdout`.
    void print(std::ostream& OutputStream = std::cout, std::string Separator = ", ") noexcept;
    
private:
    struct ll_node {
        ll_node(value_t Value): Value(Value), Next(nullptr) {}
        
        value_t Value;
        std::shared_ptr<ll_node> Next;
    };

    std::shared_ptr<ll_node> Head;
};


/// ---- TEMPLATE IMPLEMENTATION ----

template <typename value_t>
void linked_list<value_t>::insert_sorted(const value_t& Value) noexcept {
    std::shared_ptr<linked_list<value_t>::ll_node> NewNode(new linked_list<value_t>::ll_node(Value));

    if (Head == nullptr || Value < Head->Value) {
        NewNode->Next = Head;
        Head = NewNode;
    }
    else {
        auto PlaceToInsert = Head;
        while (PlaceToInsert->Next != nullptr && PlaceToInsert->Next->Value < Value) {
            PlaceToInsert = PlaceToInsert->Next;
        }

        NewNode->Next = PlaceToInsert->Next;
        PlaceToInsert->Next = NewNode;
    }
}

template <typename value_t>
void linked_list<value_t>::insert_at(uint64_t Index, const value_t& Value) noexcept {
    std::shared_ptr<linked_list<value_t>::ll_node> NewNode(new linked_list<value_t>::ll_node(Value));
    
    if (Head == nullptr || Index == 0) {
        NewNode->Next = Head;
        Head = NewNode;
    }
    else {
        uint64_t CurrentIndex = 0;
        auto PlaceToInsert = Head;
        while (PlaceToInsert->Next != nullptr && CurrentIndex < Index) {
            PlaceToInsert = PlaceToInsert->Next;
            ++CurrentIndex;
        }
        
        NewNode->Next = PlaceToInsert->Next;
        PlaceToInsert->Next = NewNode;
    }
}
template <typename value_t>
void linked_list<value_t>::push(const value_t& Value) noexcept {
    std::shared_ptr<linked_list<value_t>::ll_node> NewNode(new linked_list<value_t>::ll_node(Value));
    NewNode->Next = Head;
    Head = NewNode;
}

template <typename value_t>
void linked_list<value_t>::push_back(const value_t& Value) noexcept {
    std::shared_ptr<linked_list<value_t>::ll_node> NewNode(new linked_list<value_t>::ll_node(Value));

    if (Head == nullptr) {
        Head = NewNode;
    }
    else {
        auto PlaceToInsert = Head;
        while (PlaceToInsert->Next != nullptr) {
            PlaceToInsert = PlaceToInsert->Next;
        }
        PlaceToInsert->Next = NewNode;
    }
}

template <typename value_t>
std::weak_ptr<value_t> linked_list<value_t>::value_at(uint64_t Index) noexcept {
    auto Node = Head;
    for (uint64_t CurrentIndex = 0; Node != nullptr && CurrentIndex < Index; ++CurrentIndex) {}

    if (Node) return Node->Value;
    return nullptr;
}

template <typename value_t>
void linked_list<value_t>::print(std::ostream& OutputStream, std::string Separator) noexcept {
    auto Node = Head;
    while (Node != nullptr) {
        OutputStream << Node->Value << Separator;
        Node = Node->Next;
    }
    OutputStream << std::endl;
}

main.cpp

/*
 * This is a sample project to illustrate a common misconception in computer science: Big-O notation
 * can lead us astray if we concerned about the whole scenario. The other: our intuition needs to be
 * switched from the context in which something might be faster for a human to do vs. what is faster
 * for a machine to do.
 *
 * This example specifically looks at linked lists vs. arrays for random insertions to validate the
 * common assumption that linked lists are vastly superior for insertions since it's just a simple
 * pointer swap vs. an array re-allocation.
 *
 * We'll also look at the insertion times of a standard linked list vs. the vector at the beginning
 * and the end.
 *
 * Copyright owensd.io (2017).
 */

#include <cstdio>
#include <vector>
#include <list>
#include <memory>
#include <stdlib.h>
#include <mach/mach_time.h>
#include <locale.h>
#include <CoreServices/CoreServices.h>

#include "list.h"

const auto NumberOfSamples = 10;

/// Measures the amount of time, in nanoseconds, that the `Worker` function takes.
uint64_t measure(std::function<void(void)> Worker) {
    auto StartTime = mach_absolute_time();
    Worker();
    return mach_absolute_time() - StartTime;
}

// The purpose of this structure is to provide a variable sized data-chunk for testing
// the performance of operations as the underling data structure size changes.
template <uint64_t structure_size>
struct test_data {
    char Data[structure_size];
};

// Generates a set of data to use with random data filled in to ensure that is no magical
// zero-copy optimizations going on.
template <uint64_t structure_size>
auto create_data(uint64_t NumberOfElements) {
    std::vector<test_data<structure_size>> Data;
    for (uint64_t Count = 0; Count < NumberOfElements; ++Count) {
        test_data<structure_size> Item;
        for (uint64_t Index = 0; Index < structure_size; ++Index) {
            Item.Data[Index] = arc4random_uniform(sizeof(char));
        }
        Data.push_back(Item);
    }
    
    return Data;
}

template <uint64_t structure_size>
struct test_entry {
    typedef test_data<structure_size> data_t;
    std::string Description;
    
    std::function<void(linked_list<data_t>&, const data_t&, const uint64_t Index)> InsertIntoLinkedList;
    std::function<void(std::vector<data_t>&, const data_t&, const uint64_t Index)> InsertIntoVector;
    std::function<void(std::list<data_t>&, const data_t&, const uint64_t Index)> InsertIntoList;
};

template <uint64_t structure_size>
std::vector<test_entry<structure_size>> create_test_entries() {
    typedef test_data<structure_size> data_t;
    
    return {
        {
            "Insert element in front",
            [](linked_list<data_t>& LinkedList, const data_t& Value, const uint64_t) { LinkedList.push(Value); },
            [](std::vector<data_t>& Vector, const data_t& Value, const uint64_t) { Vector.insert(Vector.begin(), Value); },
            [](std::list<data_t>& List, const data_t& Value, const uint64_t) { List.insert(List.begin(), Value); }
        },
        {
            "Insert element in back",
            [](linked_list<data_t>& LinkedList, const data_t& Value, const uint64_t) { LinkedList.push_back(Value); },
            [](std::vector<data_t>& Vector, const data_t& Value, const uint64_t) { Vector.insert(Vector.end(), Value); },
            [](std::list<data_t>& List, const data_t& Value, const uint64_t) { List.insert(List.end(), Value); }
        },
        {
            "Insert element in middle",
            [](linked_list<data_t>& LinkedList, const data_t& Value, const uint64_t Index) { LinkedList.insert_at(Index, Value); },
            [](std::vector<data_t>& Vector, const data_t& Value, const uint64_t Index) { Vector.insert(Vector.begin() + Index, Value); },
            [](std::list<data_t>& List, const data_t& Value, const uint64_t Index) {
                auto Iter = List.begin();
                for (auto Count = 0; Count < Index; ++Count, ++Iter) {}
                List.insert(Iter, Value);
            }
        }
    };
}

template <uint64_t structure_size>
void perform_test() {
    typedef test_data<structure_size> data_t;

    const auto NumberOfElementsPerIteration = { 10, 100, 1000, 10000 };
    auto TestEntries = create_test_entries<structure_size>();
    
    // This will generate a simple CSV structured output that can be brought into any spreadsheet tool
    // for proper analysis of the timings.
    
    printf("Data Structure, Description, Size of Structure, Number of Elements, Timing (ns)\n");
    for (auto& TestEntry : TestEntries) {
        for (auto NumberOfElements : NumberOfElementsPerIteration) {
            // To minimize the variance, all tests will use the same set of random values.
            auto Values = create_data<structure_size>(NumberOfElements);

            for (auto SampleNumber = 0; SampleNumber < NumberOfSamples; ++SampleNumber) {
                linked_list<data_t> LinkedList;
                auto LinkedListCreationTime = measure([&TestEntry, &LinkedList, &Values, NumberOfElements] {
                    for (int Count = 0; Count < NumberOfElements; ++Count) {
                        TestEntry.InsertIntoLinkedList(LinkedList, Values[Count], Count / 2);
                    }
                });
                printf("%s, %s, %lu, %d, %lld\n", "LinkedList", TestEntry.Description.c_str(), sizeof(data_t), NumberOfElements, LinkedListCreationTime);

                std::vector<data_t> Vector;
                auto VectorCreationTime = measure([&TestEntry, &Vector, &Values, NumberOfElements] {
                    for (int Count = 0; Count < NumberOfElements; ++Count) {
                        TestEntry.InsertIntoVector(Vector, Values[Count], Count / 2);
                    }
                });
                printf("%s, %s, %lu, %d, %lld\n", "Vector", TestEntry.Description.c_str(), sizeof(data_t), NumberOfElements, VectorCreationTime);

                std::list<data_t> List;
                auto ListCreationTime = measure([&TestEntry, &List, &Values, NumberOfElements] {
                    for (int Count = 0; Count < NumberOfElements; ++Count) {
                        TestEntry.InsertIntoList(List, Values[Count], Count / 2);
                    }
                });
                printf("%s, %s, %lu, %d, %lld\n", "List", TestEntry.Description.c_str(), sizeof(data_t), NumberOfElements, ListCreationTime);
            }
        }
    }
}

int main() {
    perform_test<1>();
    perform_test<2>();
    perform_test<4>();
    perform_test<8>();
    perform_test<16>();
    perform_test<32>();
    perform_test<64>();
    perform_test<128>();
    perform_test<256>();

    return 0;
}

main.swift

import Foundation

class LinkedListNode {
    init(_ value: Int32) {
        self.value = value
        self.next = nil
    }
    
    var value: Int32 = 0
    var next: LinkedListNode? = nil
}

class LinkedList {
    var head: LinkedListNode? = nil
    
    func insert(at index: UInt64, value: Int32) {
        let newNode = LinkedListNode(value)
        
        if index == 0 || head == nil {
            newNode.next = head
            head = newNode
        }
        else {
            var currentIndex: UInt64 = 0
            var placeToInsert = head!
            while (placeToInsert.next != nil && currentIndex < index) {
                placeToInsert = placeToInsert.next!
                currentIndex += 1
            }
            
            newNode.next = placeToInsert.next
            placeToInsert.next = newNode
        }
    }
    
    func print() {
        var node = head
        while node != nil {
            Swift.print("\(node!.value)", terminator: ", ")
            node = node?.next
        }
        Swift.print()
    }
}


let maximumNumberOfElements = 10000
let maximumNumberOfSamples = 10

var linkedListTotalTime: UInt64 = 0
var arrayTotalTime: UInt64 = 0
var contiguousArrayTotalTime: UInt64 = 0

for _ in 0..<maximumNumberOfSamples {
    let list = LinkedList()
    var array = [Int32]()
    var contiguousArray = ContiguousArray<Int32>()

    let value = Int32(arc4random_uniform(255))
    let linkedListStartTime = mach_absolute_time()
    for n in 0..<maximumNumberOfElements {
        list.insert(at: UInt64(n / 2), value: value)
    }
    linkedListTotalTime += mach_absolute_time() - linkedListStartTime

    let arrayStartTime = mach_absolute_time()
    for n in 0..<maximumNumberOfElements {
        array.insert(value, at: n / 2)
    }
    arrayTotalTime += mach_absolute_time() - arrayStartTime

    let contiguousArrayStartTime = mach_absolute_time()
    for n in 0..<maximumNumberOfElements {
        contiguousArray.insert(value, at: n / 2)
    }
    contiguousArrayTotalTime += mach_absolute_time() - contiguousArrayStartTime
}

print("average time for list: \(linkedListTotalTime / UInt64(maximumNumberOfSamples))")
print("average time for array: \(arrayTotalTime / UInt64(maximumNumberOfSamples))")
print("average time for contiguous array: \(contiguousArrayTotalTime / UInt64(maximumNumberOfSamples))")

The arc4random_uniform(255) in the Swift timing loops has an insignificant overhead, so I didn't bother updating it.