Skip to content

Instantly share code, notes, and snippets.

@owensd

owensd/list.h Secret

Last active February 27, 2018 18:56
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save owensd/94490781a0ce1dce6737834876ff3a02 to your computer and use it in GitHub Desktop.
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))")
@owensd
Copy link
Author

owensd commented Sep 6, 2017

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment