main.cpp for the perf tests
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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
The
arc4random_uniform(255)
in the Swift timing loops has an insignificant overhead, so I didn't bother updating it.