c++ 基于堆栈缓冲的STL分配器

yeotifhr  于 2023-02-01  发布在  其他
关注(0)|答案(6)|浏览(174)

我想知道是否有一个符合C++标准库的allocator,它使用一个(固定大小)的缓冲区,该缓冲区位于堆栈上。
不知何故,这个问题似乎还没有在SO上这样问过,尽管它 * 可能 * 已经在其他地方得到了隐含的回答。
所以基本上,就我的搜索而言,似乎应该可以创建一个使用固定大小缓冲区的分配器。现在,乍一看,这应该意味着应该也有可能拥有一个使用固定大小缓冲区的分配器,它“驻留”在堆栈上,但似乎并没有广泛的这样的实现。
让我给予一个例子来说明我的意思:

{ ...
  char buf[512];
  typedef ...hmm?... local_allocator; // should use buf
  typedef std::basic_string<char, std::char_traits<char>, local_allocator> lstring;
  lstring str; // string object of max. 512 char
}

这将如何实施?
answer to this other question(感谢R. Martinho Fernandes)链接到来自 chrome 源的基于堆栈的分配器:http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h
然而,这个类看起来非常奇怪,特别是因为这个StackAllocator * 没有默认的ctor* --在那里我认为every allocator class needs a default ctor

vzgqcmou

vzgqcmou1#

创建一个完全符合C ++11/C ++14的堆栈分配器 * 绝对是 * 可能的 *,但是您需要考虑一些关于堆栈分配的实现和语义的分支,以及它们如何与标准容器交互。
下面是一个完全符合C ++11/C ++14的堆栈分配器(也托管在我的github上):

#include <functional>
#include <memory>

template <class T, std::size_t N, class Allocator = std::allocator<T>>
class stack_allocator
{
    public:

    typedef typename std::allocator_traits<Allocator>::value_type value_type;
    typedef typename std::allocator_traits<Allocator>::pointer pointer;
    typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
    typedef typename Allocator::reference reference;
    typedef typename Allocator::const_reference const_reference;
    typedef typename std::allocator_traits<Allocator>::size_type size_type;
    typedef typename std::allocator_traits<Allocator>::difference_type difference_type;

    typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
    typedef Allocator allocator_type;

    public:

    explicit stack_allocator(const allocator_type& alloc = allocator_type()) 
        : m_allocator(alloc), m_begin(nullptr), m_end(nullptr), m_stack_pointer(nullptr)
    { }

    explicit stack_allocator(pointer buffer, const allocator_type& alloc = allocator_type())
        : m_allocator(alloc), m_begin(buffer), m_end(buffer + N), 
            m_stack_pointer(buffer)
    { }

    template <class U>
    stack_allocator(const stack_allocator<U, N, Allocator>& other)
        : m_allocator(other.m_allocator), m_begin(other.m_begin), m_end(other.m_end),
            m_stack_pointer(other.m_stack_pointer)
    { }

    constexpr static size_type capacity()
    {
        return N;
    }

    pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
    {
        if (n <= size_type(std::distance(m_stack_pointer, m_end)))
        {
            pointer result = m_stack_pointer;
            m_stack_pointer += n;
            return result;
        }

        return m_allocator.allocate(n, hint);
    }

    void deallocate(pointer p, size_type n)
    {
        if (pointer_to_internal_buffer(p))
        {
            m_stack_pointer -= n;
        }
        else m_allocator.deallocate(p, n);  
    }

    size_type max_size() const noexcept
    {
        return m_allocator.max_size();
    }

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

    template <class U>
    void destroy(U* p)
    {
        m_allocator.destroy(p);
    }

    pointer address(reference x) const noexcept
    {
        if (pointer_to_internal_buffer(std::addressof(x)))
        {
            return std::addressof(x);
        }

        return m_allocator.address(x);
    }

    const_pointer address(const_reference x) const noexcept
    {
        if (pointer_to_internal_buffer(std::addressof(x)))
        {
            return std::addressof(x);
        }

        return m_allocator.address(x);
    }

    template <class U>
    struct rebind { typedef stack_allocator<U, N, allocator_type> other; };

    pointer buffer() const noexcept
    {
        return m_begin;
    }

    private:

    bool pointer_to_internal_buffer(const_pointer p) const
    {
        return (!(std::less<const_pointer>()(p, m_begin)) && (std::less<const_pointer>()(p, m_end)));
    }

    allocator_type m_allocator;
    pointer m_begin;
    pointer m_end;
    pointer m_stack_pointer;
};

template <class T1, std::size_t N, class Allocator, class T2>
bool operator == (const stack_allocator<T1, N, Allocator>& lhs, 
    const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
    return lhs.buffer() == rhs.buffer();
}

template <class T1, std::size_t N, class Allocator, class T2>
bool operator != (const stack_allocator<T1, N, Allocator>& lhs, 
    const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
    return !(lhs == rhs);
}

此分配器使用用户提供的固定大小的缓冲区作为初始内存源,然后在空间不足时返回到辅助分配器(默认为std::allocator<T>)。

    • 要考虑的事项:**

在使用堆栈分配器之前,你需要考虑你的分配模式。首先,当在堆栈上使用内存缓冲区时,你需要考虑它到底意味着什么来分配和释放内存。
最简单的方法(以及上面使用的方法)是简单地为分配递增堆栈指针,为释放递减堆栈指针。请注意,这 * 严重地 * 限制了实际使用分配器的方式。对于std::vector来说,它将工作得很好(这将分配单个连续的内存块),但是对于例如std::map将不起作用,std::map将以变化的顺序分配和解除分配节点对象。
如果你的堆栈分配器只是简单地增加和减少一个堆栈指针,那么如果你的分配和释放不是按照LIFO顺序,你将得到未定义的行为。即使是std::vector,如果它首先从堆栈中分配一个连续的块,然后分配第二个堆栈块,然后释放第一个块,也会导致未定义的行为。每当向量的容量增加到小于stack_size的值时,就会发生这种情况,这就是为什么需要提前保留堆栈大小的原因(但请参阅下面关于Howard Hinnant实现的注解)。
这就引出了一个问题...
你真正想要从堆栈分配器得到什么?
您实际上是否需要一个通用分配器,它允许您以不同顺序分配和释放各种大小的内存块,(类似于malloc),除了它从预先分配的堆栈缓冲区中提取内存而不是调用sbrk之外?如果是这样,那么您基本上是在讨论实现一个通用分配器,它以某种方式维护内存块的空闲列表,只有用户可以提供一个预先存在的堆栈缓冲区。这是一个复杂得多的项目。(如果耗尽空间,它应该怎么做?抛出std::bad_alloc?退回堆?)
上面的实现假设您需要一个分配器,它将简单地使用LIFO分配模式,并在空间不足时返回到另一个分配器。这对于std::vector来说很好,它将始终使用可以提前保留的单个连续缓冲区。当std::vector需要更大的缓冲区时,它将分配更大的缓冲区copy(或移动)较小缓冲区中的元素,然后释放较小缓冲区。当向量请求较大缓冲区时,上述stack_allocator实现将简单地退回到辅助分配器(默认为std::allocator)。
例如:

const static std::size_t stack_size = 4;
int buffer[stack_size];

typedef stack_allocator<int, stack_size> allocator_type;

std::vector<int, allocator_type> vec((allocator_type(buffer))); // double parenthesis here for "most vexing parse" nonsense
vec.reserve(stack_size); // attempt to reserve space for 4 elements

std::cout << vec.capacity() << std::endl;

vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);

// Assert that the vector is actually using our stack
//
assert(
    std::equal(
        vec.begin(), 
        vec.end(), 
        buffer, 
        [](const int& v1, const int& v2) {
            return &v1 == &v2;
        }
    )
);

// Output some values in the stack, we see it is the same values we
// inserted in our vector.
//
std::cout << buffer[0] << std::endl;
std::cout << buffer[1] << std::endl;
std::cout << buffer[2] << std::endl;
std::cout << buffer[3] << std::endl;

// Attempt to push back some more values.  Since our stack allocator only has 
// room for 4 elements, we cannot satisfy the request for an 8 element buffer.  
// So, the allocator quietly falls back on using std::allocator.
//
// Alternatively, you could modify the stack_allocator implementation
// to throw std::bad_alloc
//
vec.push_back(50);
vec.push_back(60);
vec.push_back(70);
vec.push_back(80);

// Assert that we are no longer using the stack buffer
//
assert(
    !std::equal(
        vec.begin(), 
        vec.end(), 
        buffer, 
        [](const int& v1, const int& v2) {
            return &v1 == &v2;
        }
    )
);

// Print out all the values in our vector just to make sure 
// everything is sane.
//
for (auto v : vec) std::cout << v << ", ";
std::cout << std::endl;

参见:http://ideone.com/YhMZxt
同样,这对vector也很有效--但是你需要问自己,你到底想用堆栈分配器做什么。如果你想要一个通用的内存分配器,碰巧从堆栈缓冲区中提取内存,那么你就在谈论一个复杂得多的项目。然而,一个简单的堆栈分配器,仅增加和减少堆栈指针的方法只适用于有限的用例集。注意,对于非POD类型,您需要使用std::aligned_storage<T, alignof(T)>来创建实际的堆栈缓冲区。
我还要指出,与Howard Hinnant's implementation不同,上面的实现没有显式地检查在调用deallocate()时,传入的指针是最后分配的块,如果传入的指针不是LIFO顺序的释放,Hinnant的实现将什么也不做,这将使您能够使用std::vector而无需提前保留,因为分配器基本上会"忽略"向量试图释放初始缓冲区。但是这也模糊了分配器的语义,并且依赖于与std::vector的工作方式有着明确联系的行为。我的感觉是,我们不妨简单地说,传递任何指向deallocate()的指针,而该指针 * 不是 * 通过最后一次调用返回的到allocate()将导致未定义的行为,并将其保留在那里。

  • 最后-以下警告:检查指针是否在堆栈缓冲区边界内的函数是否是标准定义的行为似乎是debatable。对来自不同new/malloc缓冲区的两个指针进行顺序比较可以说是实现定义的行为(即使对于std::less),这可能使编写一个符合标准的堆栈分配器实现不可能退回到堆分配。(但实际上,这并不重要,除非你在MS-DOS上运行80286。)

**最后(现在真的),还值得注意的是,stack allocator 中的单词“stack”有点重载,既指内存的 *source(固定大小的堆栈数组)和分配的 * 方法 *(一个LIFO递增/递减堆栈指针)当大多数程序员说他们需要一个堆栈分配器时,他们只考虑前一种含义,而没有考虑后一种含义的语义,以及这些语义如何限制这种分配器与标准容器的使用。

9gm1akwq

9gm1akwq2#

很明显,有is a conforming Stack Allocator从一个Howard Hinnant
它的工作原理是使用固定大小的缓冲区(通过引用的arena对象),如果请求的空间太大,则回退到堆。
这个分配器没有默认的ctor,因为霍华德说:
我用一个完全符合C++11的新分配器更新了本文。
我认为分配器不一定要有一个默认的ctor。

pgx2nnw8

pgx2nnw83#

从c++17开始,这实际上很容易做到,完全归功于the dumbest allocator的作者,因为这就是它的基础。
dumbest分配器是一个单调的bump分配器,它将char[]资源作为底层存储,在最初的版本中,char[]通过mmap放在堆上,但是将它改为指向堆栈上的char[]是很简单的。

template<std::size_t Size=256>                                                                                                                               
class bumping_memory_resource {                                                                                                                              
  public:                                                                                                                                                    
  char buffer[Size];                                                                                                                                         
  char* _ptr;                                                                                                                                                
                                                                                                                                                             
  explicit bumping_memory_resource()                                                                                                                         
    : _ptr(&buffer[0]) {}                                                                                                                                    
                                                                                                                                                             
  void* allocate(std::size_t size) noexcept {                                                                                                                
    auto ret = _ptr;                                                                                                                                         
    _ptr += size;                                                                                                                                            
    return ret;                                                                                                                                              
  }                                                                                                                                                          
                                                                                                                                                             
  void deallocate(void*) noexcept {}                                                                                                                         
};

这在创建时在堆栈上分配Size字节,默认为256

template <typename T, typename Resource=bumping_memory_resource<256>>                                                                                        
class bumping_allocator {                                                                                                                                    
  Resource* _res;                                                                                                                                            
                                                                                                                                                             
  public:                                                                                                                                                    
  using value_type = T;                                                                                                                                      
                                                                                                                                                             
  explicit bumping_allocator(Resource& res)                                                                                                                  
    : _res(&res) {}                                                                                                                                          
                                                                                                                                                             
  bumping_allocator(const bumping_allocator&) = default;                                                                                                     
  template <typename U>                                                                                                                                      
  bumping_allocator(const bumping_allocator<U,Resource>& other)                                                                                              
    : bumping_allocator(other.resource()) {}                                                                                                                 
                                                                                                                                                             
  Resource& resource() const { return *_res; }                                                                                                               
                                                                                                                                                             
  T*   allocate(std::size_t n) { return static_cast<T*>(_res->allocate(sizeof(T) * n)); }                                                                    
  void deallocate(T* ptr, std::size_t) { _res->deallocate(ptr); }                                                                                            
                                                                                                                                                             
  friend bool operator==(const bumping_allocator& lhs, const bumping_allocator& rhs) {                                                                       
    return lhs._res == rhs._res;                                                                                                                             
  }                                                                                                                                                          
                                                                                                                                                             
  friend bool operator!=(const bumping_allocator& lhs, const bumping_allocator& rhs) {                                                                       
    return lhs._res != rhs._res;                                                                                                                             
  }                                                                                                                                                          
};

这是实际的分配器。注意,给资源管理器添加一个reset是很简单的,它允许你再次从区域的开始处创建一个新的分配器。也可以实现一个环形缓冲区,带有所有常见的风险。
至于什么时候你可能会想要这样的东西:我在嵌入式系统中使用它,嵌入式系统通常对堆碎片没有很好的React,所以有能力使用不进入堆的动态分配有时是很方便的。

wd2eg0qa

wd2eg0qa4#

这真的取决于你的需求,当然如果你愿意,你可以创建一个只对栈操作的分配器,但是它会非常有限,因为同一个栈对象不像堆对象那样可以从程序的任何地方访问。
我认为这篇文章很好地解释了分配器
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

oxosxuxt

oxosxuxt5#

基于堆栈的STL分配器的实用性非常有限,我怀疑您是否能找到更多现有技术。如果您后来决定复制或加长初始的lstring,即使是您引用的简单示例也会很快崩溃。
对于其他STL容器,如关联容器(内部基于树),甚至使用单个或多个连续RAM块的vectordeque,内存使用语义在几乎任何实际使用中都会很快变得无法在堆栈上管理。

k4aesqcs

k4aesqcs6#

这实际上是一个非常有用的实践,在性能开发中使用得非常多,比如游戏。将内存内嵌在堆栈上或类结构的分配中,对于容器的速度和,或管理至关重要。
为了回答你的问题,这归结到stl容器的实现上。如果容器不仅示例化,而且作为一个成员保持对你的分配器的引用,那么你就可以去创建一个固定的堆,我发现这并不总是这样,因为它不是规范的一部分。否则就会有问题。一个解决方案可以是 Package 容器,向量,列表等。与另一个包含存储的类。然后你可以使用一个分配器来从中提取。这可能需要大量的模板magickery(tm)。

相关问题