如何在不使指针失效的情况下扩大缓冲区?

3

这里的“pool”和“buffer”可以互换使用。
假设我想在程序开始时分配一个池,以便不必一直调用new
现在,我不想人为地限制池的大小,但如果我重新分配更大的池,所有指向旧池的指针都将失效,这肯定不太好。


我想到的一种方法是“分页”,也就是

const int NUM_PAGES = 5;
char* pool[NUM_PAGES];

而不是只重新分配一个页面,分配一个新页面。这将使所有指针保持有效,但使页面池的管理变得更加困难。此外,我限制了页面数量,因此最终又限制了池的大小。
另一种方法是从我的分配函数返回的指针到实际内存空间的指针进行映射。这将使所有旧指针保持有效,但会占用更多的内存,并且我需要编写一个智能指针来从我的分配函数中返回进行映射。
还有哪些其他可能的方法可以实现我想要的目标?在上面的示例实现中,我错过了什么(不)优点?
5个回答

2
扩展您的分页“池”概念,如果将页面存储为链表呢?要从池中分配新数据,您只需要访问位于列表头部的顶部“页面”,因此这是O(1)的。如果您需要增加池的总大小,请分配一个新页面并将其推送到列表的头部,也是O(1)。我基本上使用相同的想法来进行池化分配器,但同时还有最近取消分配项目的“空闲列表”...根据您的评论,如果您还想利用取消分配的数据,您还可以将空闲列表存储为链接列表。因此,当您取消分配数据时,将指针和大小标记推入空闲列表。从池中分配数据时,您首先检查是否可以使用空闲列表中的任何项目,如果不能,则从池中分配。标准内存管理器通常已经做了类似的事情,因此这种方法并不总是更好。具体来说,我通常仅在分配的项目大小相同时才使用此类自定义分配器(以便遍历空闲列表是O(1)!)。std :: list的自定义分配器就是一个例子。希望这会有所帮助。

另一个(现已删除的)答案也让我想到了这个想法。就像我在关于“分页”思路的问题中提到的那样,如果“旧”的页面中的指针被释放,如何有效地组织以重用该空间将需要更多的工作。 - Xeo
1
+1 对于这种方法并不总是更好,因为增加了复杂度,可能得不偿失:在增加复杂度之前要进行测量!那么,在vector(或者deque)中存储实际页面指针如何呢?我不太明白为什么需要一个链表(通常更难维护),而且页面指针的重新分配实际上不应该成为问题,因为用户代码拥有的指针指向的是页面内容,而不是指针。 - David Rodríguez - dribeas

2

您提到的内容让我想起了一个 std::deque。我不确定您是否可以直接使用 std::deque,或者您只需要使用其基本设计来实现某种类型的分配器。


1
你已经涵盖了我要说的大部分内容。它可以增长而不会使任何引用失效,但在中间擦除对象将会使所有引用无效。也许这已经足够了。 - cgmb
我最终使用了双端队列。之前不知道双端队列具有特殊的增长属性,谢谢! - Xeo

1

1

当然,有一个问题,为什么要自己麻烦呢?

你说你想避免new的开销,但为什么不选择更好的new实现呢?例如,tcmallocjemalloc通常是多线程应用程序的非常好的竞争者。

事实上,你正在尝试创建的东西非常类似于编写定制的malloc/new实现。因此,如果你真的不想使用经过验证的实现,你将受益于那些已经这样做的人的见解。

我的个人兴趣倾向于BiBOP策略(大页面包)来对抗碎片化。其思想是针对每种分配大小有一个专用池,因此一个简单的空闲列表(与分配交错)就足够了(无需合并)。通常,只要请求的大小小于页面大小(我见过4KB被使用),任何更大的都会单独分配(在几个页面中)。废弃的页面会被回收利用。

我的主要兴趣在于使用BiBOP轻松地维护一个区间树地址范围->页头,从而通过(可能是)内部元素(如属性)的地址确定对象的完整大小,这对于垃圾回收(引用跟踪步骤)非常有用。

对于多线程分配,tcmallocjemalloc使用两种不同的方法:

  • jemalloc使用每个线程池:适用于固定数量的线程/线程池,但使得创建线程的过程更加昂贵
  • tcmalloc使用全局多线程池,并采用无锁技术,尝试将线程平衡负载到可用的池中,以限制争用,当线程查找新的池时,如果使用的池被“锁定”(而不是等待),则会有一些争用,并且每个线程将上次使用的池缓存到线程本地变量中。因此,线程是轻量级的,但如果池的数量过低,则可能会产生一些争用。

0
一些想法:
  • 当你有一个 std::vector<T*> 时,添加元素并触发调整大小会使该容器中的引用/指针/迭代器无效,但不会影响直接寻址指向对象的引用/指针。因此,根据你实际想要使用这些引用/指针/迭代器的方式,可能需要增加一层间接性来解决问题。

  • 在具有虚拟内存和大地址空间的系统中,你可以进行巨大的分配,而不必担心浪费任何有价值的物理内存资源,因为这些页面只有在写入时才会从物理内存资源中分配。因此,在这样的系统上,你可以为 vector 设置比实际需要更大的初始容量。

  • 其他容器 - std::map<>std::list<> - 在添加新元素时不会移动其现有元素,因此迭代器/指针/引用仍然有效。


这样的系统:例如Linux。 - Matthieu M.
@Matthieu:Linux 绝对满足虚拟内存方面的需求;如果你想处理几千兆字节的数据,32 位构建可能无法满足“大地址空间”标准... :-/ - Tony Delroy

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接