Preserving principle of locality while performing memory allocation

Question

In order to implement an efficient AST visitor preserving the principle of locality, I implemented some reference counting mechanism in C++ with the following set of features:

• All the newly allocated memory shall be stored in a contiguous allocation memory, so to preserve the principle of locality (minimize the page faults).
• All the pointers pointing to the same memory region could point to a different one (this is a requirement when I want to perform rewriting operations over the AST and simplifications).
• One single pointer shall change the pointer to one single memory region.
• The allocated memory slots should be rearranged so that each AST is ordered in lexicographical order (the lexicographical ordering of the data structure is currently missing for MWE reasons)
• After sorting the nodes by lexicographical order, the weak_pointers shall be kept unchanged, and only the references in the strong pointers should be changed, as they will now point to different slots in the contiguously allocated memory.

Given this context, I would like you to ask how the following code can be improved so to maximise it performances: I guess that using a C-like coding style and completely avoiding classes and objects might get rid of the Virtual Tables, thus creating a more efficient code. On the other hand, I won't be able to use the forward construct to allocate new nodes for the AST.

I provide now some implementation of these constructs.

weak_pointer.h

The behaviour is similar to the weak_ptr from the STL, but somehow the principles and the aims are different, as the shared_ptrs are not necessarily stored in contiguous memory allocation, thus mining the principle of locality. Also, the shared_ptrs shall be never directly accessed by the programmer, that should only use the weak pointers for changing the global value.

#include <iostream>

/**
 * The repository is the actual memory allocator, that will contain the references to the strong pointers and to the actual
 * allocated elements
 * @tparam T
 */
template<typename T>
class repository;

/**
 * A weak pointer is just a pointer to a strong pointer, which is held within a repository alongside with the actual
 * allocated data.
 * @tparam T
 */
template<typename T>
class weak_pointer {
    repository<T> *element; // Memory repository that contains the actual information
    size_t strong_ptr_pos;  // Vector position for the current element in the strong pointer holder

public:

    /**
     * Creating a strong pointer by knowing a strong memory pointer position
     * @param element
     * @param strongPtrPos
     */
    weak_pointer(repository<T> *element, size_t strongPtrPos) : element(element), strong_ptr_pos(strongPtrPos) {
        // Increment the reference count in the main repository associated to the strong pointer
        if (element) element->increment(strong_ptr_pos);
    }

    /**
     * Copying a weak pointer that was (possibly) pointing to a new memory allocation
     * @param copy
     */
    weak_pointer(const weak_pointer &copy) : element{copy.element}, strong_ptr_pos{copy.strong_ptr_pos} {
        if (element) element->increment(strong_ptr_pos);
    }


    /**
     * Copying a weak pointer that was (possibly) pointing to a new memory allocation via assignment. This will not
     * change the stroing pointer for all the weak pointers.
     * @param copy
     * @return
     */
    weak_pointer &operator=(const weak_pointer &copy) {
        // Decrement the reference count of the element that was previously pointed
        if (element && (get() != nullptr))
            element->decrement(strong_ptr_pos);
        // Copying the new information
        element = copy.element;
        strong_ptr_pos = copy.strong_ptr_pos;
        // Incrementing the reference count
        if (element) element->increment(strong_ptr_pos);
    }

    /**
     * Demanding the repository to return the pointer if this is not missing
     * @return
     */
    T *get() const {
        // Resolving the pointer as an actual element in the remote reference
        return element ? element->resolvePointer(strong_ptr_pos) : nullptr;
    }

    T *operator->() {
        return get();
    }

    /**
     * Changing the value that is going to be pointed by the strong pointer. This will make all the weak pointers
     * associated to it to point to a new value
     * @param ptr
     */
    void setGlobal(const weak_pointer<T> &ptr) {
        assert(element);
        assert(ptr.element);
        if (element != ptr.element) {
            element = ptr.element;
            std::cerr << "Warning: element!=ptr.element, so I'm using ptr.element" << std::endl;
        }
        element->setGlobal(strong_ptr_pos, ptr.strong_ptr_pos);
    }

    std::optional<size_t> resolveStrongPonter() {
        if (element)
            return element->resolveToStrongPointer(strong_ptr_pos);
        else
            return {};
    }

    ~weak_pointer() {
        // On deallocation, decrement the reference count associated to the strong pointer
        if (element) element->decrement(strong_ptr_pos);
    }

    /**
     * Counting the references to the current element
     * @return
     */
    size_t getReferenceCounterToVal() {
        return element ? element->getReferenceCounterToVal(strong_ptr_pos) : 1;
    }

    bool operator==(const weak_pointer &rhs) const {
        return element == rhs.element && // Two weak pointers are equal if they share the same repository...
                                         (strong_ptr_pos == rhs.strong_ptr_pos || // and if either they point to the same region...
               element->strongPointerEquality(strong_ptr_pos, rhs.strong_ptr_pos)); //... or they point to strong pointers containing equivalent values
    }

    bool operator!=(const weak_pointer &rhs) const {
        return !(rhs == *this);
    }

    // Printing the actual value that is pointed by the strong pointer, if any
    friend std::ostream &operator<<(std::ostream &os, const weak_pointer &pointer) {
        auto ptr = pointer.get();
        if (ptr)
            os << *ptr;
        else
            os << "null";
        return os;
    }

};

repository.h

Repository contains the strong pointers memorized as optionals, and now now stored in contiguous memory within a vector. Now, they point to vector offsets rather than specific addresses in memory.

Given the aforrmentioned list of requirements, when an allocated object is deallocated from the contiguous_memory, I need to decrement the offsets in the strong_pointers. This requires an additional scanning cost.

#include <iostream>
#include <cassert>
#include <vector>
#include <optional>
#include <map>
#include <unordered_set>
#include <set>

#include "weak_pointer.h"

template <typename T> class repository {

    std::vector<T> contiguous_memory; ///<@ vector that is actually storing the allocated nodes for the AST
    std::vector<size_t> contiguous_memory_reference_count; ///<@ this contians the reference counters for each strong pointer
    std::vector<std::optional<size_t>> strong_pointers; ///<@ if the strong pointer is not a null pointer, it points to an offset within the contiguous memory
    std::map<size_t, std::unordered_set<size_t>> contiguous_memory_to_multimap; ///<@ getting all the strong pointers pointing to the same value

public:
    ~repository() {
        clear();
    }

    void clear() {
        // By deallocating in this order, I guarantee that all the information is freed in the right order, thus avoiding
        // sigfaults from mutual dependencies within the data structures
        contiguous_memory_to_multimap.clear();
        strong_pointers.clear();
        contiguous_memory_reference_count.clear();
        contiguous_memory.clear();
    }

    template <typename... Ts>
    weak_pointer<T> new_element(Ts&&... args) {
        //assert(newMHP == newPos);
        contiguous_memory.emplace_back(std::forward<Ts>(args)...); // The emplace now might trigger several pointer creations. So, I need to define the newPos differently...
        size_t newPos = contiguous_memory.size()-1;
        size_t newMHP = strong_pointers.size();                      // ... This also applies to the memory_holders, tha tis chained to "contiguous_memory"
        contiguous_memory_reference_count.emplace_back(0);
        strong_pointers.emplace_back(newPos);
        contiguous_memory_to_multimap[newPos].emplace(newMHP);
        return {this, newMHP};
    }

    template <typename... Ts>
    weak_pointer<T>& set_new_element(weak_pointer<T>& ptr, Ts&&... args) {
        //assert(newMHP == newPos);
        contiguous_memory.emplace_back(std::forward<Ts>(args)...); // The emplace now might trigger several pointer creations. So, I need to define the newPos differently...
        size_t newPos = contiguous_memory.size()-1;
        size_t newMHP = strong_pointers.size();                      // ... This also applies to the memory_holders, tha tis chained to "contiguous_memory"
        contiguous_memory_reference_count.emplace_back(0);
        strong_pointers.emplace_back(newPos);
        contiguous_memory_to_multimap[newPos].emplace(newMHP);
        weak_pointer<T> element{this, newMHP};
        ptr.setGlobal(element);
        return ptr;
    }

    /**
     * Creates a null pointer: guarantess that a not all the null pointers shall always point to the same memory region
     * @return 
     */
    weak_pointer<T> new_null_pointer() {
        size_t newMHP = strong_pointers.size();
        contiguous_memory_reference_count.emplace_back(0); /// The null pointer still is a pointer that will be allocated. It will have no value assocated to it (no contiguous_memory value is emplaced) but a strong_pointer is created
        strong_pointers.emplace_back(); /// A null pointer is defined by a strong pointer containing no reference to the contiguous memory
        return {this, newMHP};                      /// Pointer to the new strong pointer
    }

    /**
     * Returns whether two strong pointers point to an equivalent value.
     *
     * @param left
     * @param right
     * @return
     */
    bool strongPointerEquality(size_t left, size_t right) {
        const std::optional<size_t>& oleft = strong_pointers[left], &oright = strong_pointers[right];
        return (left == right) ||
                (oleft == oright) ||
                (oleft && oright && contiguous_memory[oleft.value()] == contiguous_memory[oright.value()]);
    }

    [[nodiscard]] std::optional<size_t> resolveToStrongPointer(size_t ptr) const {
        if (strong_pointers.size() <= ptr) {
            return {}; /// Cannot return a pointer that is not there
        } else {
            return strong_pointers.at(ptr);
        }
    }

    T* resolveStrongPointer(const std::optional<size_t>& ref) const {
        if (ref) {
            const size_t& x = ref.value();
            return (contiguous_memory.size() > x) ? (T*)&contiguous_memory.at(x) : nullptr; /// Returning the value if it is actually something good
        } else {
            return nullptr; /// Returning a value only if the pointer is pointing to something in the contiguous memory
        }
    }

    T* resolvePointer(size_t ptr) const {
        if (strong_pointers.size() <= ptr) {
            return nullptr; /// Cannot return a pointer that is not there
        } else {
            return resolveStrongPointer(strong_pointers.at(ptr));
        }
    }

    void increment(size_t ptr) {
        assert(contiguous_memory_reference_count.size() == strong_pointers.size());
        if (ptr < strong_pointers.size()) {
            contiguous_memory_reference_count[ptr]++;
        }
    }

    void decrement(size_t ptr) {
        assert(contiguous_memory_reference_count.size() == strong_pointers.size());
        if (ptr < strong_pointers.size()) {
            contiguous_memory_reference_count[ptr]--;
        }
        if (contiguous_memory_reference_count[ptr] == 0) {
            attempt_dispose_element(ptr);
        }
    }

    size_t getReferenceCounterToVal(size_t strong) {
        auto& x = strong_pointers.at(strong);
        if (x) {
            auto it = contiguous_memory_to_multimap.find(strong);
            assert (it != contiguous_memory_to_multimap.end());
            size_t sum = 0;
            for (size_t k : it->second) {
                sum += contiguous_memory_reference_count[k];
            }
            return sum;
        } else {
            return 0;
        }
    }

    /**
     * All the weak pointers pointing to the same strong pointer to the left, will now point to the same value in the
     * right pointer.
     * @param left
     * @param right
     */
    void setGlobal(size_t left, size_t right) {
        attempt_dispose_element(left);
        strong_pointers[left] = strong_pointers[right]; /// Setting the pointer left to the same value on the right
        auto& x = strong_pointers[right];
        if (x) {
            contiguous_memory_to_multimap[x.value()].emplace(left);
        }
        auto it = toDispose.find(left);
        if (it != toDispose.end()) {
            toDispose.erase(it);
        }
    }

private:

    void dispose_strong_ponter(size_t left) {
        strong_pointers.erase(strong_pointers.begin() + left);
        contiguous_memory_reference_count.erase(contiguous_memory_reference_count.begin() + left);

        std::vector<size_t> keysToDel;
        // Updating all the values in the map
        for (auto it = contiguous_memory_to_multimap.begin(), en = contiguous_memory_to_multimap.end(); it != en; ) {
            std::unordered_set<size_t> values;
            for (const size_t& x : it->second) {
                if (x > left) {
                    values.emplace(x-1);
                } else if (x < left) {
                    values.emplace(x);
                }
            }
            if (values.empty()) {
                keysToDel.emplace_back(it->first);
                //it = contiguous_memory_to_multimap.erase(it);
            } else {
                it->second.swap(values);
            }
            it++;
        }
        for (size_t& x : keysToDel)
            contiguous_memory_to_multimap.erase(contiguous_memory_to_multimap.find(x));

        // Updating all the values
    }

    void dispose_value(size_t pos) {
        assert(contiguous_memory_reference_count[pos] == 0);
        assert(pos < contiguous_memory.size()); // The current element should be there in the contiguous_memory
        contiguous_memory.erase(contiguous_memory.begin() + pos); // Removing the memory allocated in the vector in the current position

        // Removing all the elements from the map, as expected.
        auto posIt = contiguous_memory_to_multimap.find(pos);
        if (posIt != contiguous_memory_to_multimap.end())
            contiguous_memory_to_multimap.erase(posIt);

        // Restructuring the strong pointers: getting all the positions greater than pos
        auto it = contiguous_memory_to_multimap.upper_bound(pos);
        std::unordered_set<size_t> toInsert;
        std::map<size_t, std::unordered_set<size_t>> contiguous_memory_to_multimap2; // Decreased map values
        while (it != contiguous_memory_to_multimap.end()) {
            for (const size_t& strong : it->second) {
                toInsert.emplace(strong); // Getting all the strong pointers pointing at values greater than
            }
            contiguous_memory_to_multimap2[it->first-1] = it->second; // Decreasing the key for all the values
            it = contiguous_memory_to_multimap.erase(it);
        }
        for (size_t k : toInsert) { // Decreasing the stroing pointers value
            auto& x = strong_pointers.at(k);
            assert(x);
            x.value() = x.value() - 1;
        }
        // Copying the updated values
        contiguous_memory_to_multimap.insert(contiguous_memory_to_multimap2.begin(), contiguous_memory_to_multimap2.end());
    }

    std::set<size_t> toDispose;

    void attempt_dispose_element(size_t x) {
        toDispose.emplace(x);
        auto it = toDispose.rbegin();

        // I can start to remove elements only when the maximum
        while ((it != toDispose.rend()) && (*it == (strong_pointers.size()-1))) {
            size_t left = *it;
            bool hasDisposed = false;
            size_t valDisposed = 0;
            const std::optional<size_t>& ref = strong_pointers.at(left); /// Getting which is the actual pointed value, if any
            if (ref) { /// If there is a pointed value;
                auto set_ptr = contiguous_memory_to_multimap.find(ref.value());
                assert(set_ptr != contiguous_memory_to_multimap.end());
                auto it = set_ptr->second.find(left);
                if (set_ptr->second.size() == 1) {
                    assert(it != set_ptr->second.end());
                    hasDisposed = true;
                    valDisposed = ref.value();
                    // Removing the value via dispose_value --->
                }
                if (it != set_ptr->second.end())
                    set_ptr->second.erase(it);
            }
            dispose_strong_ponter(left);
            if (hasDisposed) {
                dispose_value(valDisposed); // <--
            }
            it = decltype(it)(toDispose.erase(std::next(it).base())); // Clear the current element from the set
        }

    }

public:
    /**
     * Printing how the memory and the elements 
     * @param os 
     * @param repository 
     * @return 
     */
    friend std::ostream &operator<<(std::ostream &os, const repository &repository) {
        for (size_t i = 0, n = repository.contiguous_memory.size(); i<n; i++) {
            os << '[' << i <<  "] --> |{" << repository.contiguous_memory[i] << "}| == " << repository.contiguous_memory_reference_count[i] << std::endl;
        }
        for (size_t i = 0, n = repository.strong_pointers.size(); i<n; i++) {
            os << '(' << i <<  ") --> ";
            if (repository.strong_pointers[i])
                os << repository.strong_pointers[i].value();
            else
                os << "null";
            os << std::endl;
        }
        return os;
    }

    /// A new class should inherit from repository for a specific type of AST = <typename T> and, for this, I should
    /// implement the lexicographical order soring.
};

In order to both motivate this implementation and to provide a MWE, I also provide some toy example working on a specific prefix binary tree.

#include <gtest/gtest.h>
#include <sstream>
#include "repository.h"

struct tree {
    size_t value;
    weak_pointer<struct tree> left, right;

    tree(size_t key, repository<struct tree>* repo) : value{key}, left{repo->new_null_pointer()}, right{repo->new_null_pointer()} {}

    /*friend std::ostream &operator<<(std::ostream &os, const tree &tree) {
        os << "" << tree.value << " {" <<tree.left.memory_holder_pos<< "," <<tree.right.memory_holder_pos <<"}";
        return os;
    }*/

    std::string toString() {
        std::stringstream ss;
        print(ss, 0, false);
        return ss.str();
    }

    void print(std::ostream &os = std::cout, size_t depth = 0, bool isMinus = false) {
        os << std::string(depth*2, '.') << value << " @" << this << std::endl;
        if (left.get()) left->print(os, depth+1, true);
        if (right.get()) right->print(os, depth+1, false);
    }
};

void writeSequenceDown(repository<struct tree>* test_allocator, weak_pointer<struct tree> t, size_t i, std::vector<size_t> &sequence) {
    if (sequence.size() > i) {
        size_t current = (sequence[i]);
        if (!(t.get())) {
            {
                auto newElement = test_allocator->new_element(current, test_allocator);
                t.setGlobal(newElement);
            }
            writeSequenceDown(test_allocator, t, i + 1, sequence);
        } else {
            size_t currentX = (t)->value;
            if (currentX == current) {
                writeSequenceDown(test_allocator, t, i + 1, sequence);
            } else if (currentX < current) {
                writeSequenceDown(test_allocator, (t.operator->()->right), i, sequence);
            } else {
                writeSequenceDown(test_allocator, (t.operator->()->left), i, sequence);
            }
        }
    } // quit otherwise
}

TEST(TreeTest, test1) {
    repository<struct tree> test_allocator;
    weak_pointer<struct tree> root = test_allocator.new_null_pointer();
    std::vector<size_t > v1{5,3,2,1};
    writeSequenceDown(&test_allocator, root, 0, v1);
    //std::cout << test_allocator << std::endl;
    //std::cout << "Printing " << root.memory_holder_pos << std::endl;
    std::stringstream ss;
    root->print(ss); // This test is passed
    //std::cout << std::endl<<std::endl<<std::endl;
    std::vector<size_t> v2{4,3,2,0};
    writeSequenceDown(&test_allocator,root, 0, v2);
    //std::cout << test_allocator << std::endl;
    //std::cout << "Printing " << root.memory_holder_pos << std::endl;
    root->print(ss);
}

Any advice on how to possibly optimize the current code are more than welcome. Further context can be provided by this initial question that I have on another Stack Exchange platform, where I provide some hints on how I'm trying not to reinvent the wheel. I also provide the previous code in a GitHub repo, so that it is easier to run and test.

Answer 1

Your code seems very dense; I see a mix of snake_case and camelCase identifiers, and a lot of code comments that somehow manage to be very detailed and technical and yet make my eyes glaze over. Like this:

    // Restructuring the strong pointers: getting all the positions greater than pos
    auto it = contiguous_memory_to_multimap.upper_bound(pos);
    std::unordered_set<size_t> toInsert;
    std::map<size_t, std::unordered_set<size_t>> contiguous_memory_to_multimap2; // Decreased map values
    while (it != contiguous_memory_to_multimap.end()) {
        for (const size_t& strong : it->second) {
            toInsert.emplace(strong); // Getting all the strong pointers pointing at values greater than
        }
        contiguous_memory_to_multimap2[it->first-1] = it->second; // Decreasing the key for all the values
        it = contiguous_memory_to_multimap.erase(it);
    }

I'm sure those comments are meant to be helpful, but they really don't clarify what's going on in this code at all. Just removing all the comments and mechanically translating the code line by line, I get something like this:

    auto first = contiguous_memory_to_multimap.upper_bound(pos);
    auto last = contiguous_memory_to_multimap.end();
    std::unordered_set<size_t> toInsert;
    std::map<size_t, std::unordered_set<size_t>> decreased;
    for (const auto& [k, ptrs] : make_range(first, last)) {
        toInsert.insert(ptrs.begin(), ptrs.end());
        decreased.emplace(k-1, ptrs);
    }
    contiguous_memory_to_multimap.erase(first, last);

(Here make_range(first, last) is a helper function that returns a lightweight view over those elements, like C++20 std::ranges::subrange.)

---

I notice there's a circular dependency between weak_pointer and repository. You broke the dependency by forward-declaring template<class> class repository; at the top of "weak_pointer.h". However, forward declarations aren't really so great for maintainability — what if you wanted to add a second (defaulted?) template parameter to repository?

John Lakos has a bunch of material on this. What I'd do here is parameterize weak_pointer on a Repository type parameter:

template<class T, class Repository>
class weak_pointer {
    Repository *element;
    size_t strong_ptr_pos;

Then in "repository.h":

template<class T>
class repository {
    using pointer = weak_pointer<T, repository<T>>;

    template<class... Args> pointer new_element(Args&&...);
    template<class... Args> pointer& set_new_element(pointer&, Args&&...);

and so on. Ta-da, no more circular dependency!

---

Your T *operator->() should be const-qualified.

Your resolveStrongPonter() is misspelled, and completely unused, and should have been const-qualified, too. (But since it's unused, you should delete it instead.)

Your getReferenceCounterToVal() is also unused, and should have been const-qualified.

Your operator<< could be written slightly more tersely as

friend std::ostream& operator<<(std::ostream& os, const weak_pointer& wptr) {
    if (T *p = wptr.get()) {
        os << *p;
    } else {
        os << "null";
    }
    return os;
}

---

I see you're using std::optional<size_t>, which must store a size_t and a bool, which is a lot of wasted memory. You'd get a 50% memory savings by using a plain old size_t where size_t(-1) means "null." Just watch out and don't type sizeof(-1) when you mean size_t(-1), as I just almost did. :)

For extra bonus points, implement a class StrongPointer { size_t data; } with implicit conversion from nullptr_t and so on.

---

void clear() {
    // By deallocating in this order, I guarantee that all the information is freed in the right order, thus avoiding
    // sigfaults from mutual dependencies within the data structures
    contiguous_memory_to_multimap.clear();
    strong_pointers.clear();
    contiguous_memory_reference_count.clear();
    contiguous_memory.clear();
}

First of all, you're just clearing things in reverse order of their construction, which means this is exactly what the compiler-generated destructor would do anyway. Second of all, there cannot be any "mutual dependencies" between elements of those data structures, because they're all just simple value types. Clearing the contents of one container cannot possibly affect the contents of any other container.

So, you can eliminate your non-defaulted ~repository(). The defaulted destructor is fine.

You can also eliminate the misleading comment. (And btw, it's "segfault," as in "segmentation fault" — not "sigfault.")

---

strong_pointers.emplace_back();

I'd prefer to see

strong_pointers.push_back(std::nullopt);

or, if you use my class StrongPointer idea, you could just write

strong_pointers.push_back(nullptr);

---

const std::optional<size_t>& oleft = strong_pointers[left], &oright = strong_pointers[right];

Pop quiz, hotshot: What is the const-qualification of oright?

Avoid multiple declarations on the same line. Instead, write two lines:

const StrongPointer& oleft = strong_pointers[left];
const StrongPointer& oright = strong_pointers[right];

Even if you don't use class StrongPointer, consider adding a member typedef

using StrongPointer = std::optional<size_t>;

Anyway, that's probably enough for a first review.