dag-snapshot-large_a.cpp

// dag-snapshot-large_a.cpp (C++11)
// AUTHOR: xixas | DATE: 2022.01.20 | LICENSE: WTFPL/PDM/CC0... your choice
// DESCRIPTION: Gaming: World-state snapshot example for non-interrupting saves.
//                      Repeated directed acyclic graph vertex replacement.
//                      NO LOCKS.
//                      Larger data set test.
// BUILD: g++ --std=c++11 -O3 -lpthread -o dag-snapshot-large_a dag-snapshot-large_a.cpp


#include <atomic>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <initializer_list>
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <thread>
#include <time.h>
#include <unordered_set>
#include <vector>


// ---------------------------------------------------------------------------
// Atomics used for test synchronization
// ---------------------------------------------------------------------------

std::atomic<bool> willSave(false);
std::atomic<bool> isSaving(false);
std::atomic<bool> saveComplete(false);
std::atomic<bool> endGame(false);

// ---------------------------------------------------------------------------
// Updateable object registration
// ---------------------------------------------------------------------------

class Updateable;
std::unordered_set<Updateable*> updateables_beforesave;
std::unordered_set<Updateable*> updateables_aftersave;
struct Updateable {
    Updateable() { updateables_aftersave.insert(this); }
    Updateable(bool onsave):Updateable() { if (onsave) updateables_beforesave.insert(this); }
    virtual ~Updateable(){};
    virtual void update() = 0;
};
void update_beforesave() { for (auto u : updateables_beforesave) u->update(); }
void update_aftersave() { for (auto u : updateables_aftersave) u->update(); }

// ---------------------------------------------------------------------------
// Generic snapshot template class
// ---------------------------------------------------------------------------

size_t saveableWrites = 0;
template <typename T> class Saveable : public virtual Updateable {
    T snap, live;
public:
    Saveable() { snap = live = T(); }
    Saveable(const T& t) { snap = live = t; }
    Saveable(const Saveable<T>& o) { snap = o.snap; live = o.live; }
    ~Saveable() {}

    Saveable<T>& operator=(const Saveable<T>& t) { setValue(t.live); return *this; }
    Saveable<T>& operator=(const T& t) { setValue(t); return *this; }
    operator T&() { return live; }
    operator const T&() const { return live; }
    T& operator *() { return live; }
    const T& operator *() const { return live; }
    T& operator +() { return snap; }
    const T& operator +() const { return snap; }

    void update() override { snap = live; }

    void setValue(const T& t) { /*saveableWrites++;*/ live = t; if (!isSaving) snap = t; }
    T& getValue() { return live; }
    const T& getValue() const { return live; }
    T& getSaveValue() { return snap; }
    const T& getSaveValue() const { return snap; }
};
template <typename T> inline bool operator <(const Saveable<T>& lhs, const Saveable<T>& rhs) { return *lhs < *rhs; }
template <typename T> inline bool operator ==(const Saveable<T>& lhs, const Saveable<T>& rhs) { return *lhs == *rhs; }
template <typename T> inline std::ostream& operator <<(std::ostream& os, const Saveable<T>& t) { os << *t; return os; }

// ---------------------------------------------------------------------------
// Vertex with saveable values
// All values are stored twice when a save is not in progress
// Automatically freezes a snapshot when isSaving is true
// ---------------------------------------------------------------------------

class Vertex {
    Saveable<std::vector<Vertex*>> _owns;
public:
    Saveable<std::string> name;
    Saveable<int> value;
    const Saveable<std::vector<Vertex*>>& owns = _owns;

    Vertex():name(),value(),_owns(){}
    Vertex(const std::string& name, const int& value):name(name),value(value),_owns(){}
    Vertex(const std::string& name, const int& value, const std::vector<Vertex*>& owns):name(name),value(value),_owns(owns){}
    Vertex(const Vertex& o):name(o.name),value(o.value),_owns(o._owns){}

    Vertex& operator=(const Vertex& o) { if (this != &o) { name = o.name; value = o.value; _owns = o._owns; } return *this; }

    void own(const std::vector<Vertex*>& owns) { _owns = owns; }

    std::string str() const {
        std::ostringstream os;
        os << "(\"" << name << "/" << value << "\")";
        return os.str();
    }
    std::string saveableStr() const {
        std::ostringstream os;
        os << "(\"" << +name << "/" << +value << "\")";
        return os.str();
    }
};
inline bool operator<(const Vertex& lhs, const Vertex& rhs) {
    return lhs.name < rhs.name;
}

// ---------------------------------------------------------------------------
// Edge (Vertex pair)
// Plain struct without any built-in snapshot ability
// ---------------------------------------------------------------------------

struct Edge {
    Vertex *a, *b;

    Edge(Vertex* a, Vertex* b):a(a),b(b){}
    Edge(Vertex& a, Vertex& b):a(&a),b(&b){}
    Edge(const Edge& o):a(o.a),b(o.b){}

    Edge& operator=(const Edge& o) { if (this != &o) { a = o.a; b = o.b; } return *this; }

    std::string str() const {
        std::ostringstream os;
        os << "{" << a->str() << ", " << b->str() << "}";
        return os.str();
    }
    std::string saveableStr() const {
        std::ostringstream os;
        os << "{" << a->saveableStr() << ", " << b->saveableStr() << "}";
        return os.str();
    }
};
inline bool operator<(const Edge& lhs, const Edge& rhs) {
    return lhs.a->name < rhs.a->name || (lhs.a->name == rhs.a->name && lhs.b->name < rhs.b->name);
}

// ---------------------------------------------------------------------------
// Graph (ordered set of Edges)
// No snapshot overhead on updates
// A snapshot must be manually requested when ready to save
// ---------------------------------------------------------------------------

class Graph : public virtual Updateable {
    Saveable<std::set<Edge>> _edges;
public:
    const Saveable<std::set<Edge>>& edges = _edges; 

    Graph():Updateable(true){}
    Graph(std::initializer_list<Edge> edges):Updateable(true),_edges(edges){}
    Graph(const Graph& o):Updateable(true),_edges(o._edges){}

    Graph& operator=(const Graph& o) { if (this != &o) { _edges = o._edges; (*_edges) = _edges; } return *this; }

    void update() override { _edges.update(); }

    size_t size() { return (*edges).size(); }
    std::set<Vertex*> vertices() {
        std::set<Vertex*> vertices;
        for (auto it = (*_edges).begin(); it != (*_edges).end(); ++it) {
            vertices.insert(it->a);
            vertices.insert(it->b);
        }
        return vertices;
    }
    const Edge* edge_at(size_t index) {
        if (index < (*_edges).size()) {
            auto it = (*_edges).cbegin();
            std::advance(it, index);
            return &*it;
        } else {
            return nullptr;
        }
    }
    Vertex* vertex_at(size_t edgeIndex, size_t vertexIndex) {
        if (edgeIndex < (*_edges).size() && vertexIndex < 2) {
            auto it = (*_edges).begin();
            std::advance(it, edgeIndex);
            return vertexIndex ? it->b : it->a;
        } else {
            return nullptr;
        }
    }


    void add_edge(const Edge& edge) {
        (*_edges).insert(edge);
    }
    void emplace_edge(Vertex* const a, Vertex* const b) {
        (*_edges).emplace(a, b);
    }
    void remove_edge(const Edge& edge) {
        for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
            if (it->a->name == edge.a->name && it->b->name == edge.b->name) it = (*_edges).erase(it);
            else ++it;
        }
    }
    void remove_vertex(const Vertex& vertex) {
        for (auto it = (*vertex.owns).cbegin(); it != (*vertex.owns).cend(); it++) {
            remove_vertex(**it);
        }
        for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
            if (it->a->name == vertex.name || it->b->name == vertex.name) it = (*_edges).erase(it);
            else ++it;
        }
    }
    void replace_vertex(const Vertex& a, Vertex& b) {
        std::vector<Edge> newEdges;
        for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
            if (it->a->name == a.name) {
                newEdges.push_back(Edge{&b, it->b});
                it = (*_edges).erase(it);
            } else if (it->b->name == a.name) {
                newEdges.push_back({it->a, &b});
                it = (*_edges).erase(it);
            } else {
                ++it;
            }
        }
        for (auto it = newEdges.cbegin(); it != newEdges.cend(); ++it) {
            (*_edges).insert(std::move(*it));
        }
    }
    void replace_vertices(const std::vector<Vertex*> a, const std::vector<Vertex*> b) {
        auto begin1 = a.cbegin(), end1 = a.cend();
        auto begin2 = b.cbegin(), end2 = b.cend();
        for (auto it1 = begin1, it2 = begin2; it1 != end1 && it2 != end2;)
        {
            replace_vertex(**it1, **it2);
            ++it1; ++it2;
        }
    }

    std::string str() const {
        std::ostringstream os;
        os << "[";
        for (auto it = (*edges).cbegin(); it != (*edges).cend();) {
            os << it->str();
            ++it;
            if (it != (*edges).cend()) os << ", ";
        }
        os << "]";
        return os.str();
    }
    std::string saveableStr() const {
        std::ostringstream os;
        os << "[";
        for (auto it = (+edges).cbegin(); it != (+edges).cend();) {
            os << it->saveableStr();
            ++it;
            if (it != (+edges).cend()) os << ", ";
        }
        os << "]";
        return os.str();
    }
};

// ---------------------------------------------------------------------------
// Timing Functions
// ---------------------------------------------------------------------------

std::chrono::time_point<std::chrono::system_clock> markedTime;
inline void markTime() { markedTime = std::chrono::system_clock::now(); }
inline std::chrono::duration<double> checkTime() { return std::chrono::system_clock::now() - markedTime; }

// ===========================================================================
// Tests
// ===========================================================================

int main() {
    using std::cout;
    using std::endl;

    std::srand(time(nullptr));

    size_t nVertices = 1000000;
    size_t minEdges = 1;
    size_t maxEdges = 4;

    Graph graph;
    std::vector<Vertex> vertices;
    std::chrono::duration<double> duration;

    auto swapVertex = [&]() {
        static Vertex extraVertex = {"0x0", 0};
        static Vertex* outVertex = &extraVertex;
        static size_t vertIndex = 1; // which vertex to choose from edge - 0 or 1

//        cout << "               " << graph.str() << endl;
        // swap random vertex
        size_t edgeIndex = rand() % graph.size();
        Vertex* pIn = graph.vertex_at(edgeIndex, vertIndex = (vertIndex + 1) % 2);
        Vertex* pOut = outVertex;
        outVertex = pIn;
        graph.replace_vertex(*pIn, *pOut);
        // zero all edge counts
        for (auto v : graph.vertices()) { v->value = 0; }
        // count all edges
        for (auto it = (*graph.edges).begin(); it != (*graph.edges).end(); ++it) {
            auto a = it->a, b = it->b; 
            a->value = a->value + 1;
            b->value = b->value + 1;
        }
//        cout << "(" << pIn->name << ") -> (" << pOut->name << ") " << graph.str() << endl;
    };


    cout << "========== GENERATE VERTICES ==========" << endl
         << "Vertex Count: " << nVertices << endl;
    {
        const char* idFormat = "0x%zx";
        char idBuf[9];

        markTime();
        vertices.reserve(nVertices);
        for (size_t i = 1; i <= nVertices; ++i) {
            sprintf(idBuf, idFormat, i);
            vertices.emplace_back(idBuf, 0);
        }
        duration = checkTime();
    }
//    for (auto it = vertices.cbegin(); it != vertices.cend(); ++it) {
//        std::cout << it->str() << std::endl;
//    }
    cout << "Time: " << (duration.count() * 1000) << " ms" << endl;


    cout << "========== GENERATE GRAPH ==========" << endl;
    {
        size_t i, j, idx, idxRange, edgeCount;
        size_t edgeRange = maxEdges - minEdges + 1;

        markTime();
        for (i = 0; i < nVertices - 1; ++i) {
            edgeCount = (rand() % edgeRange) + minEdges;
//            cout << "edgeCount: " << edgeCount << endl;
            idxRange = nVertices - i - 1;
            for (j = 0; j < edgeCount; ++j) {
                idx = (rand() % idxRange) + 1 + i;
                graph.emplace_edge(&vertices[i], &vertices[idx]);
            }
        }
        duration = checkTime();
    }
    cout << "Edge Count: " << graph.size() << endl;
    cout << "Time: " << duration.count() * 1000 << " ms" << endl;


    cout << "========== PERFORMANCE TEST ==========" << endl;
    auto performanceTest = [&]() {
        size_t loopCount = 1;
        saveableWrites = 6000000;
        {
            markTime();
            for (size_t i = 0; i < loopCount; ++i) { swapVertex(); update_beforesave(); }
            duration = checkTime();
        }
        cout << "Test Time:                  " << duration.count() << " s" << std::endl
             << "Average Iteration:          " << duration.count() / loopCount * 1000 << " ms" << std::endl
             << "Iterations per Second:      " << loopCount / duration.count() << std::endl
             << "Saveable Writes:            " << saveableWrites << endl
             << "Saveable Writes per Second: " << (int)(saveableWrites / duration.count()) << endl;
    };
    cout << endl << "-[ isSaving: false ]-----" << endl;
    isSaving.store(false);
    performanceTest();
//    std::this_thread::sleep_for(std::chrono::milliseconds(5000));
    cout << endl << "-[ isSaving: true ]-----" << endl;
    isSaving.store(true);
    performanceTest();
//    std::this_thread::sleep_for(std::chrono::milliseconds(5000));

    return 0;
}

dag-snapshot-large_b.cpp

// dag-snapshot-large_b.cpp (C++11)
// AUTHOR: xixas | DATE: 2022.01.20 | LICENSE: WTFPL/PDM/CC0... your choice
// DESCRIPTION: Gaming: World-state snapshot example for non-interrupting saves.
//                      Repeated directed acyclic graph vertex replacement.
//                      NO LOCKS.
//                      Larger data set test.
// BUILD: g++ --std=c++11 -O3 -lpthread -o dag-snapshot-large_b dag-snapshot-large_b.cpp



#include <atomic>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <initializer_list>
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <thread>
#include <time.h>
#include <unordered_set>
#include <vector>


// ---------------------------------------------------------------------------
// Atomics used for test synchronization
// ---------------------------------------------------------------------------

std::atomic<bool> willSave(false);
std::atomic<bool> isSaving(false);
std::atomic<bool> saveComplete(false);
std::atomic<bool> endGame(false);

// ---------------------------------------------------------------------------
// Updateable object registration
// ---------------------------------------------------------------------------

class Updateable;
std::unordered_set<Updateable*> updateables_beforesave;
std::unordered_set<Updateable*> updateables_aftersave;
struct Updateable {
    Updateable() { updateables_aftersave.insert(this); }
    Updateable(bool onsave):Updateable() { if (onsave) updateables_beforesave.insert(this); }
    virtual ~Updateable(){};
    virtual void update() = 0;
};
void update_beforesave() { for (auto u : updateables_beforesave) u->update(); }
void update_aftersave() { for (auto u : updateables_aftersave) u->update(); }

// ---------------------------------------------------------------------------
// Generic snapshot template class
// ---------------------------------------------------------------------------

size_t saveableWrites = 0;
template <typename T> class Saveable : public virtual Updateable {
    T *snap, *live;
public:
    Saveable() { snap = live = new T; }
    Saveable(const T& t):Saveable() { *live = t; }
    Saveable(const Saveable<T>& o):Saveable() { *live = *(o.live); if (o.snap != o.live) { snap = new T; *snap = *(o.live); }}
    ~Saveable() { if (snap != live) delete snap; delete live; }

    Saveable<T>& operator=(const Saveable<T>& t) { setValue(*(t.live)); return *this; }
    Saveable<T>& operator=(const T& t) { setValue(t); return *this; }
    operator T&() { return *live; }
    operator const T&() const { return *live; }
    T& operator *() { return *live; }
    const T& operator *() const { return *live; }
    T& operator +() { return *snap; }
    const T& operator +() const { return *snap; }

    void update() override { if (snap != live) { delete snap; snap = live; }}

    void setValue(const T& t) { /*saveableWrites++;*/ if (isSaving && snap == live) live = new T; *live = t; }
    T& getValue() { return *live; }
    const T& getValue() const { return *live; }
    T& getSaveValue() { return *snap; }
    const T& getSaveValue() const { return *snap; }
};
template <typename T> inline bool operator <(const Saveable<T>& lhs, const Saveable<T>& rhs) { return *lhs < *rhs; }
template <typename T> inline bool operator ==(const Saveable<T>& lhs, const Saveable<T>& rhs) { return *lhs == *rhs; }
template <typename T> inline std::ostream& operator <<(std::ostream& os, const Saveable<T>& t) { os << *t; return os; }

// ---------------------------------------------------------------------------
// Vertex with saveable values
// All values are stored twice when a save is not in progress
// Automatically freezes a snapshot when isSaving is true
// ---------------------------------------------------------------------------

class Vertex {
    Saveable<std::vector<Vertex*>> _owns;
public:
    Saveable<std::string> name;
    Saveable<int> value;
    const Saveable<std::vector<Vertex*>>& owns = _owns;

    Vertex():name(),value(),_owns(){}
    Vertex(const std::string& name, const int& value):name(name),value(value),_owns(){}
    Vertex(const std::string& name, const int& value, const std::vector<Vertex*>& owns):name(name),value(value),_owns(owns){}
    Vertex(const Vertex& o):name(o.name),value(o.value),_owns(o._owns){}

    Vertex& operator=(const Vertex& o) { if (this != &o) { name = o.name; value = o.value; _owns = o._owns; } return *this; }

    void own(const std::vector<Vertex*>& owns) { _owns = owns; }

    std::string str() const {
        std::ostringstream os;
        os << "(\"" << name << "/" << value << "\")";
        return os.str();
    }
    std::string saveableStr() const {
        std::ostringstream os;
        os << "(\"" << +name << "/" << +value << "\")";
        return os.str();
    }
};
inline bool operator<(const Vertex& lhs, const Vertex& rhs) {
    return lhs.name < rhs.name;
}

// ---------------------------------------------------------------------------
// Edge (Vertex pair)
// Plain struct without any built-in snapshot ability
// ---------------------------------------------------------------------------

struct Edge {
    Vertex *a, *b;

    Edge(Vertex* a, Vertex* b):a(a),b(b){}
    Edge(Vertex& a, Vertex& b):a(&a),b(&b){}
    Edge(const Edge& o):a(o.a),b(o.b){}

    Edge& operator=(const Edge& o) { if (this != &o) { a = o.a; b = o.b; } return *this; }

    std::string str() const {
        std::ostringstream os;
        os << "{" << a->str() << ", " << b->str() << "}";
        return os.str();
    }
    std::string saveableStr() const {
        std::ostringstream os;
        os << "{" << a->saveableStr() << ", " << b->saveableStr() << "}";
        return os.str();
    }
};
inline bool operator<(const Edge& lhs, const Edge& rhs) {
    return lhs.a->name < rhs.a->name || (lhs.a->name == rhs.a->name && lhs.b->name < rhs.b->name);
}

// ---------------------------------------------------------------------------
// Graph (ordered set of Edges)
// No snapshot overhead on updates
// A snapshot must be manually requested when ready to save
// ---------------------------------------------------------------------------

class Graph : public virtual Updateable {
    Saveable<std::set<Edge>> _edges;
public:
    const Saveable<std::set<Edge>>& edges = _edges; 

    Graph():Updateable(true){}
    Graph(std::initializer_list<Edge> edges):Updateable(true),_edges(edges){}
    Graph(const Graph& o):Updateable(true),_edges(o._edges){}

    Graph& operator=(const Graph& o) { if (this != &o) { _edges = o._edges; (*_edges) = _edges; } return *this; }

    void update() override { _edges.update(); }

    size_t size() { return (*edges).size(); }
    std::set<Vertex*> vertices() {
        std::set<Vertex*> vertices;
        for (auto it = (*_edges).begin(); it != (*_edges).end(); ++it) {
            vertices.insert(it->a);
            vertices.insert(it->b);
        }
        return vertices;
    }
    const Edge* edge_at(size_t index) {
        if (index < (*_edges).size()) {
            auto it = (*_edges).cbegin();
            std::advance(it, index);
            return &*it;
        } else {
            return nullptr;
        }
    }
    Vertex* vertex_at(size_t edgeIndex, size_t vertexIndex) {
        if (edgeIndex < (*_edges).size() && vertexIndex < 2) {
            auto it = (*_edges).begin();
            std::advance(it, edgeIndex);
            return vertexIndex ? it->b : it->a;
        } else {
            return nullptr;
        }
    }


    void add_edge(const Edge& edge) {
        (*_edges).insert(edge);
    }
    void emplace_edge(Vertex* const a, Vertex* const b) {
        (*_edges).emplace(a, b);
    }
    void remove_edge(const Edge& edge) {
        for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
            if (it->a->name == edge.a->name && it->b->name == edge.b->name) it = (*_edges).erase(it);
            else ++it;
        }
    }
    void remove_vertex(const Vertex& vertex) {
        for (auto it = (*vertex.owns).cbegin(); it != (*vertex.owns).cend(); it++) {
            remove_vertex(**it);
        }
        for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
            if (it->a->name == vertex.name || it->b->name == vertex.name) it = (*_edges).erase(it);
            else ++it;
        }
    }
    void replace_vertex(const Vertex& a, Vertex& b) {
        std::vector<Edge> newEdges;
        for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
            if (it->a->name == a.name) {
                newEdges.push_back(Edge{&b, it->b});
                it = (*_edges).erase(it);
            } else if (it->b->name == a.name) {
                newEdges.push_back({it->a, &b});
                it = (*_edges).erase(it);
            } else {
                ++it;
            }
        }
        for (auto it = newEdges.cbegin(); it != newEdges.cend(); ++it) {
            (*_edges).insert(std::move(*it));
        }
    }
    void replace_vertices(const std::vector<Vertex*> a, const std::vector<Vertex*> b) {
        auto begin1 = a.cbegin(), end1 = a.cend();
        auto begin2 = b.cbegin(), end2 = b.cend();
        for (auto it1 = begin1, it2 = begin2; it1 != end1 && it2 != end2;)
        {
            replace_vertex(**it1, **it2);
            ++it1; ++it2;
        }
    }

    std::string str() const {
        std::ostringstream os;
        os << "[";
        for (auto it = (*edges).cbegin(); it != (*edges).cend();) {
            os << it->str();
            ++it;
            if (it != (*edges).cend()) os << ", ";
        }
        os << "]";
        return os.str();
    }
    std::string saveableStr() const {
        std::ostringstream os;
        os << "[";
        for (auto it = (+edges).cbegin(); it != (+edges).cend();) {
            os << it->saveableStr();
            ++it;
            if (it != (+edges).cend()) os << ", ";
        }
        os << "]";
        return os.str();
    }
};

// ---------------------------------------------------------------------------
// Timing Functions
// ---------------------------------------------------------------------------

std::chrono::time_point<std::chrono::system_clock> markedTime;
inline void markTime() { markedTime = std::chrono::system_clock::now(); }
inline std::chrono::duration<double> checkTime() { return std::chrono::system_clock::now() - markedTime; }

// ===========================================================================
// Tests
// ===========================================================================

int main() {
    using std::cout;
    using std::endl;

    std::srand(time(nullptr));

    size_t nVertices = 1000000;
    size_t minEdges = 1;
    size_t maxEdges = 4;

    Graph graph;
    std::vector<Vertex> vertices;
    std::chrono::duration<double> duration;

    auto swapVertex = [&]() {
        static Vertex extraVertex = {"0x0", 0};
        static Vertex* outVertex = &extraVertex;
        static size_t vertIndex = 1; // which vertex to choose from edge - 0 or 1

//        cout << "               " << graph.str() << endl;
        // swap random vertex
        size_t edgeIndex = rand() % graph.size();
        Vertex* pIn = graph.vertex_at(edgeIndex, vertIndex = (vertIndex + 1) % 2);
        Vertex* pOut = outVertex;
        outVertex = pIn;
        graph.replace_vertex(*pIn, *pOut);
        // zero all edge counts
        for (auto v : graph.vertices()) { v->value = 0; }
        // count all edges
        for (auto it = (*graph.edges).begin(); it != (*graph.edges).end(); ++it) {
            auto a = it->a, b = it->b; 
            a->value = a->value + 1;
            b->value = b->value + 1;
        }
//        cout << "(" << pIn->name << ") -> (" << pOut->name << ") " << graph.str() << endl;
    };


    cout << "========== GENERATE VERTICES ==========" << endl
         << "Vertex Count: " << nVertices << endl;
    {
        const char* idFormat = "0x%zx";
        char idBuf[9];

        markTime();
        vertices.reserve(nVertices);
        for (size_t i = 1; i <= nVertices; ++i) {
            sprintf(idBuf, idFormat, i);
            vertices.emplace_back(idBuf, 0);
        }
        duration = checkTime();
    }
//    for (auto it = vertices.cbegin(); it != vertices.cend(); ++it) {
//        std::cout << it->str() << std::endl;
//    }
    cout << "Time: " << (duration.count() * 1000) << " ms" << endl;


    cout << "========== GENERATE GRAPH ==========" << endl;
    {
        size_t i, j, idx, idxRange, edgeCount;
        size_t edgeRange = maxEdges - minEdges + 1;

        markTime();
        for (i = 0; i < nVertices - 1; ++i) {
            edgeCount = (rand() % edgeRange) + minEdges;
//            cout << "edgeCount: " << edgeCount << endl;
            idxRange = nVertices - i - 1;
            for (j = 0; j < edgeCount; ++j) {
                idx = (rand() % idxRange) + 1 + i;
                graph.emplace_edge(&vertices[i], &vertices[idx]);
            }
        }
        duration = checkTime();
    }
    cout << "Edge Count: " << graph.size() << endl;
    cout << "Time: " << duration.count() * 1000 << " ms" << endl;


    cout << "========== PERFORMANCE TEST ==========" << endl;
    auto performanceTest = [&]() {
        size_t loopCount = 1;
        saveableWrites = 6000000;
        {
            markTime();
            for (size_t i = 0; i < loopCount; ++i) { swapVertex(); update_beforesave(); }
            duration = checkTime();
        }
        cout << "Test Time:                  " << duration.count() << " s" << std::endl
             << "Average Iteration:          " << duration.count() / loopCount * 1000 << " ms" << std::endl
             << "Iterations per Second:      " << loopCount / duration.count() << std::endl
             << "Saveable Writes:            " << saveableWrites << endl
             << "Saveable Writes per Second: " << (int)(saveableWrites / duration.count()) << endl;
    };
    cout << endl << "-[ isSaving: false ]-----" << endl;
    isSaving.store(false);
    performanceTest();
//    std::this_thread::sleep_for(std::chrono::milliseconds(5000));
    cout << endl << "-[ isSaving: true ]-----" << endl;
    isSaving.store(true);
    performanceTest();
//    std::this_thread::sleep_for(std::chrono::milliseconds(5000));
    
    return 0;
}

Larger scale comparison between double-write and new/delete DAG snapshots

These two files compare performance between the double-write (dag-snapshot-large_a.cpp) and new/delete (dag-snapshot-large_b.cpp) versions of the multi-layered DAG snapshot concept originally posted here with a larger more complex dataset.

Test Description

Each test generates 1,000,000 vertices and then builds a Directed Acyclic Graph (DAG) with between 1 and 4 forward edges per vertex (averaging 2.5 forward edges per vertex, or an average of 2.5 million total edges).

Each iteration of the test performs the following:

• Swaps out one vertex at random
• Sets the value of all vertices in the graph to zero
• Iterates all edges, adding one to each encountered vertex per pair -- i.e. it counts the number edges touching each vertex one at a time
• Makes a copy of the graph (as if preparing for a save)

This test is performed both with isSaving disabled and then again with it enabled to gauge performance in each case.

Note: There are some extra cout statements commented throughout that can make local tracing a bit easier if you want to see what's going on,

Expected Results

From early smaller-scale testing I expected the following:

• Double-Write would consume significantly more memory
• New/Delete would handily out-perform Double-Write in non-saving mode
• Double-Write would handily out-perform New/Delete in save mode

Actual results

Version	isSaving	Writes per second	RAM
Double-Write	false	1,922,466	590 MB
Double-Write	true	2,318,061	636 MB
New/Delete	false	2,049,558	470 MB
New/Delete	true	1,727,155	522 MB

All of the expected results were correct (eventually... see below), but the margins were not what I expected.

• Double-Write did use more RAM, but not as much more as I expected
• New/Delete did out-perform Double-Write in non-save mode... but by a much smaller than expected margin
• Double-Write did out-perform New/Delete in save mode -- by a lot

Test Complication

Adding a counter to test writes skews the result -- in this case significantly so.

• Adding a counter to Double-Write increased the number of underlying value writes from 2 to 3 per write (50% increase)
• Adding a counter to New/Delete increased the underlying _non-save _ value writes from 1 to 2 (100% increase)

So the results I obtained initially were skewed hard in Double-Write's favor and were not at all what I expecteed.
But, by taking the average number of counted writes (about 6 million per random graph), hard-setting that as the baseline, and removing the actual counting mechanic that was creating the skew, the results fell back in line with where I expected.

The above files are set up that way, with both tests setting saveableWrites = 6000000 and commenting out the write counter in Saveable::setValue().

If you don't like my estimated count, though, you can set saveableWrites = 0 in both tests (and in both files) and uncomment saveableWrites++ in Saveable::setValue() and run each a few times to determine your preferred baseline. I guarantee it'll be right around 6 million though ;)

Raw Test Output

Double-Write - dag-snapshot-large_a.cpp

========== GENERATE VERTICES ==========
Vertex Count: 1000000
Time: 936.17 ms
========== GENERATE GRAPH ==========
Edge Count: 2498000
Time: 2017.6 ms
========== PERFORMANCE TEST ==========

-[ isSaving: false ]-----
Test Time:                  3.02616 s
Average Iteration:          3026.16 ms
Iterations per Second:      0.330451
Saveable Writes:            5996000
Saveable Writes per Second: 1981385

-[ isSaving: true ]-----
Test Time:                  2.74909 s
Average Iteration:          2749.09 ms
Iterations per Second:      0.363757
Saveable Writes:            5996000
Saveable Writes per Second: 2181084

========== GENERATE VERTICES ==========
Vertex Count: 1000000
Time: 1039 ms
========== GENERATE GRAPH ==========
Edge Count: 2499999
Time: 2122.31 ms
========== PERFORMANCE TEST ==========

-[ isSaving: false ]-----
Test Time:                  3.09794 s
Average Iteration:          3097.94 ms
Iterations per Second:      0.322795
Saveable Writes:            5999998
Saveable Writes per Second: 1936770

-[ isSaving: true ]-----
Test Time:                  3.36857 s
Average Iteration:          3368.57 ms
Iterations per Second:      0.296862
Saveable Writes:            5999998
Saveable Writes per Second: 1781169

New/Delete - dag-snapshot-large_b.cpp

========== GENERATE VERTICES ==========
Vertex Count: 1000000
Time: 842.312 ms
========== GENERATE GRAPH ==========
Edge Count: 2500110
Time: 1695.74 ms
========== PERFORMANCE TEST ==========

-[ isSaving: false ]-----
Test Time:                  3.12099 s
Average Iteration:          3120.99 ms
Iterations per Second:      0.320411
Saveable Writes:            6000000
Saveable Writes per Second: 1922466

-[ isSaving: true ]-----
Test Time:                  2.58837 s
Average Iteration:          2588.37 ms
Iterations per Second:      0.386344
Saveable Writes:            6000000
Saveable Writes per Second: 2318061

========== GENERATE VERTICES ==========
Vertex Count: 1000000
Time: 1043.79 ms
========== GENERATE GRAPH ==========
Edge Count: 2499328
Time: 2293.16 ms
========== PERFORMANCE TEST ==========

-[ isSaving: false ]-----
Test Time:                  2.92746 s
Average Iteration:          2927.46 ms
Iterations per Second:      0.341593
Saveable Writes:            6000000
Saveable Writes per Second: 2049558

-[ isSaving: true ]-----
Test Time:                  3.47392 s
Average Iteration:          3473.92 ms
Iterations per Second:      0.287859
Saveable Writes:            6000000
Saveable Writes per Second: 1727155