main.cpp for the perf tests
#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; | |
} | |
/* | |
* 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; | |
} |
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))") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
The
arc4random_uniform(255)
in the Swift timing loops has an insignificant overhead, so I didn't bother updating it.