0

I'm writing a custom allocator for unordered_map to allocate on the stack. I'm a bit lost on how to do this idiomatically: Should I pass the stack resource as pointer to the allocator or even define the byte array inside the allocator? What is common practice here?

#include <memory>
#include <unordered_map>
#include <utility>
#include <limits>
#include <cstdio>
#include <string_view>
#include <array>

class some_stack_resource
{
    std::array<std::byte, 100> container_; // <-- how to allocate to this?
};

template <typename T>
class custom_allocator
{
public:
    using value_type = T;

    using pointer = T*;
    using const_pointer = const T*;

    using void_pointer = void*;
    using const_void_pointer = const void*;

    using size_type = size_t;
    using difference_type = std::ptrdiff_t;

    template <typename U>
    struct rebind
    {
        using other = custom_allocator<U>;
    };

    custom_allocator() noexcept {
        printf("Default constructed\n");
    }

    template <typename U>
    custom_allocator(const custom_allocator<U>& other) noexcept {
        printf("Copy constructed\n");

    }

    ~custom_allocator() {
        printf("Destructed\n");
    }

    pointer allocate(size_type numObjects, const_void_pointer hint) {
        return allocate(numObjects);
    }

    pointer allocate(size_type numObjects) {
        printf("allocate %zu\n", numObjects);
        return static_cast<pointer>(operator new(sizeof(T) * numObjects));
    }

    void deallocate(pointer p, size_type numObjects) {
        printf("deallocate %zu\n", numObjects);
        operator delete(p);
    }

    size_type max_size() const {
        return std::numeric_limits<size_type>::max();
    }

    template<typename U, typename... Args>
    void construct(U* p, Args&&... args) {
        new(p) U(std::forward<Args>(args)...);
    }

    template <typename U>
    void destroy(U *p) {
        p->~U();
    }
};

int main()
{
    some_stack_resource res; // <-- where to pass res idiomatically?

    using Key = std::string_view;
    using T = int;
    std::unordered_map<Key, T, std::hash<Key>, std::equal_to<Key>, custom_allocator<std::pair<const Key, T>>> m{ {"hello", 2} };
}
glades
  • 3,778
  • 1
  • 12
  • 34
  • When you say "stack", what do you mean by that? The process stack (where the compiler usually puts local variables, and which isn't really mandated by the language)? – Some programmer dude Aug 03 '22 at 07:38
  • 2
    "*What is common practice here?*" [`std::pmr::unordered_map`](https://en.cppreference.com/w/cpp/container/unordered_map) with [`std::pmr::monotonic_buffer_resource`](https://en.cppreference.com/w/cpp/memory/monotonic_buffer_resource). – 康桓瑋 Aug 03 '22 at 07:41
  • Defining the byte array inside the allocator seems reasonable to me – john Aug 03 '22 at 07:41
  • @Someprogrammerdude Yes that one. When you put local variables in function scope – glades Aug 03 '22 at 07:59
  • @康桓瑋 That is great thank you! Even though a 3x increase from dynamic to stack allocation seems somewhat underwhelming? Maybe this is because of virtual function calls? – glades Aug 03 '22 at 08:00
  • This is actually kind of hard to do, since there are no standard way to allocate from the stack (which is natural since the C++ specification doesn't even specify such a stack). On systems with a stack the natural way to "allocate" from the stack is to create an array as a local variable inside a function. The problem is that this memory will be "free'd" when the function returns, so any structure using that memory must have a shorter life-time. And if the object using the memory needs to be copied, how should that copying be handled? – Some programmer dude Aug 03 '22 at 08:33
  • You also have to remember that the stack is a limited resource. On Windows the default stack size per process is only one single MiB, and that can fill up quite rapidly. And as you have noticed, it's not really easy to pass stack-allocated memory to the allocator. – Some programmer dude Aug 03 '22 at 08:34
  • All in all, my big question to you is: ***Why*** do you need to create a stack-based allocator? What problem is it supposed to solve? Perhaps that problem could be solved in some other way, a way that's more practical? – Some programmer dude Aug 03 '22 at 08:35
  • @Someprogrammerdude Thank you for your elaboration. The purpose is to parse a json and read it out as a container in the same function. However, in another use case the object will be allocated with memory in another object and json strings will be parsed into this object. So the memory lives inside the object. This all happens on an embedded system where I follow a strict no heap allocs policy. – glades Aug 03 '22 at 09:20
  • On an embedded system the stack will probably be even more limited than on a normal PC. Perhaps a single global buffer where you allocate from instead? – Some programmer dude Aug 03 '22 at 09:27
  • @Someprogrammerdude No I can adjust stack size myself. I could allocate to a single global buffer as well, doesn't matter. It just has get around new / delete – glades Aug 03 '22 at 09:49
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/247029/discussion-between-glades-and-some-programmer-dude). – glades Aug 04 '22 at 11:52

1 Answers1

1

here is a good example of a short allocator Hinnant's short_alloc and based on it you can see how to 'hide' some_stack_resource inside custom_allocator from users. As a user of your code I wont create an extra entity some_stack_resource res; because it doesn't make code clean.

Dmitrii
  • 98
  • 6