在 c++ 中使用 realloc
如果 malloc 的内存包含非 Pod 类型,则 std::realloc 在 C++ 中是危险的。似乎唯一的问题是,如果 std::realloc 无法在原位增加内存,则它不会调用类型析构函数。
一个简单的解决方法是使用 try_realloc
函数。如果新内存无法在原位增长,则不会对其进行 malloc,而是简单地返回 false。在这种情况下,可以分配新内存,将对象复制(或移动)到新内存,最后释放旧内存。
这看起来非常有用。 std::vector
可以充分利用这一点,可能避免所有复制/重新分配。
抢占式阻燃剂:从技术上讲,这与 Big-O 性能相同,但如果矢量增长是应用中的瓶颈,那么即使 Big-O 保持不变,x2 速度也很好。
但是,我找不到任何像 try_realloc
一样工作的 c api。
我错过了什么吗? try_realloc
没有我想象的那么有用吗?是否存在一些隐藏的错误导致 try_realloc
无法使用?
更好的是,是否有一些文档较少的 API 可以像 try_realloc
一样执行?
注意:我显然是在库/平台特定的代码中。我并不担心,因为 try_realloc
本质上是一种优化。
更新: 在 Steve Jessops 关于使用 realloc vector
是否会更有效的评论之后,我写了一个概念验证来测试。 realloc-vector
模拟向量的增长模式,但可以选择重新分配。我运行该程序,向量中的元素达到一百万个。
为了进行比较,向量
在增长到 100 万个元素时必须分配 19 次。
结果,如果 realloc-vector 是唯一使用堆的东西,那么结果非常棒,3-4 次分配,同时增长到百万字节的大小。
如果将 realloc-vector
与一个以 realloc-vector
速度增长 66% 的 vector
一起使用,结果不太乐观,分配生长期8-10次。
最后,如果 realloc-vector
与以相同速率增长的 vector
一起使用,则 realloc-vector
分配 17-18 次。与标准向量行为相比,仅节省一次分配。
我毫不怀疑黑客可以玩弄分配大小来提高节省,但我同意史蒂夫的观点,即编写和维护这样一个分配器的巨大努力并没有带来好处。
std::realloc
is dangerous in c++ if the malloc'd memory contains non-pod types. It seems the only problem is that std::realloc
wont call the type destructors if it cannot grow the memory in situ.
A trivial work around would be a try_realloc
function. Instead of malloc'ing new memory if it cannot be grown in situ, it would simply return false. In which case new memory could be allocated, the objects copied (or moved) to the new memory, and finally the old memory freed.
This seems supremely useful. std::vector
could make great use of this, possibly avoiding all copies/reallocations.
preemptive flame retardant: Technically, that is same Big-O performance, but if vector growth is a bottle neck in your application a x2 speed up is nice even if the Big-O remains unchanged.
BUT, I cannot find any c api that works like a try_realloc
.
Am I missing something? Is try_realloc
not as useful as I imagine? Is there some hidden bug that makes try_realloc
unusable?
Better yet, Is there some less documented API that performs like try_realloc
?
NOTE: I'm obviously, in library/platform specific code here. I'm not worried as try_realloc
is inherently an optimization.
Update:
Following Steve Jessops comment's on whether vector
would be more efficient using realloc I wrote up a proof of concept to test. The realloc-vector
simulates a vector's growth pattern but has the option to realloc instead. I ran the program up to a million elements in the vector.
For comparison a vector
must allocate 19 times while growing to a million elements.
The results, if the realloc-vector
is the only thing using the heap the results are awesome, 3-4 allocation while growing to the size of million bytes.
If the realloc-vector
is used alongside a vector
that grows at 66% the speed of the realloc-vector
The results are less promising, allocating 8-10 times during growth.
Finally, if the realloc-vector
is used alongside a vector
that grows at the same rate, the realloc-vector
allocates 17-18 times. Barely saving one allocation over the standard vector behavior.
I don't doubt that a hacker could game allocation sizes to improve the savings, but I agree with Steve that the tremendous effort to write and maintain such an allocator isn't work the gain.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
vector
通常会以较大的增量增长。你不能在不重新定位的情况下重复执行此操作,除非你仔细安排事情,以便在向量的内部缓冲区上方有大量的空闲地址(这实际上需要分配整个页面,因为显然你不能有其他分配稍后在同一页上)。所以我认为,为了在这里获得真正好的优化,您需要的不仅仅是一个“简单的解决方法”,如果可能的话,可以进行廉价的重新分配 - 您必须以某种方式做一些准备来使其成为可能,而这种准备工作会消耗你的地址空间。如果您只对某些向量(表明它们将变大的向量)执行此操作,那么这是毫无意义的,因为它们可以使用
reserve()
表明它们将变大。如果你有一个巨大的地址空间,你只能对所有向量自动执行此操作,这样你就可以在每个向量上“浪费”很大一部分地址空间。据我了解,
Allocator
概念没有重新分配功能的原因是为了保持简单。如果std::allocator
有一个try_realloc
函数,那么每个 Allocator 都必须有一个(在大多数情况下无法实现,并且只需要返回false 始终),否则每个标准容器都必须专门针对 std::allocator 才能利用它。这两个选项都不是一个很好的 Allocator 接口,尽管我认为对于几乎所有 Allocator 类的实现者来说,仅仅添加一个什么也不做的try_realloc
函数并不需要付出巨大的努力。如果
vector
由于重新分配而变慢,deque
可能是一个很好的替代品。vector
generally grows in large increments. You can't do that repeatedly without relocating, unless you carefully arrange things so that there's a large extent of free addresses just above the internal buffer of the vector (which in effect requires assigning whole pages, because obviously you can't have other allocations later on the same page).So I think that in order to get a really good optimization here, you need more than a "trivial workaround" that does a cheap reallocation if possible - you have to somehow do some preparation to make it possible, and that preparation costs you address space. If you only do it for certain vectors, ones that indicate they're going to become big, then it's fairly pointless, because they can indicate with
reserve()
that they're going to become big. You can only do it automatically for all vectors if you have a vast address space, so that you can "waste" a big chunk of it on every vector.As I understand it, the reason that the
Allocator
concept has no reallocation function is to keep it simple. Ifstd::allocator
had atry_realloc
function, then either every Allocator would have to have one (which in most cases couldn't be implemented, and would just have to return false always), or else every standard container would have to be specialized forstd::allocator
to take advantage of it. Neither option is a great Allocator interface, although I suppose it wouldn't be a huge effort for implementers of almost all Allocator classes just to add a do-nothingtry_realloc
function.If
vector
is slow due to re-allocation,deque
might be a good replacement.您可以实现类似于您建议的
try_realloc
的功能,使用mmap
与MAP_ANONYMOUS
和MAP_FIXED
以及mremap< /code> 与
MREMAP_FIXED
。编辑:刚刚注意到 mremap 的手册页甚至说:
You could implement something like the
try_realloc
you proposed, usingmmap
withMAP_ANONYMOUS
andMAP_FIXED
andmremap
withMREMAP_FIXED
.Edit: just noticed that the man page for mremap even says:
C 中的realloc 只不过是一个方便的函数;它对性能/减少副本几乎没有什么好处。我能想到的主要例外是分配一个大数组的代码,然后在知道所需的大小后减小大小 - 但即使这可能需要在某些
malloc
实现上移动数据(通过严格隔离块的实现) size),所以我认为这种使用 realloc 的做法非常糟糕。只要您不在每次添加元素时不断地重新分配数组,而是在空间不足时以指数方式增长数组(例如 25%、50% 或 100%),只需手动分配新内存,复制和释放旧的将产生与使用realloc大致相同(并且在内存碎片的情况下相同)的性能。这肯定是 C++ STL 实现使用的方法,所以我认为您的整个担忧是没有根据的。
编辑:
realloc
实际有用的一种(罕见但并非闻所未闻)情况是对于具有虚拟内存的系统上的巨型块,其中C库与内核交互将整个页面重新定位到新地址。我之所以说这种情况很少见,是因为在大多数实现进入处理页面粒度分配的领域之前,您需要处理非常大的块(至少几百 kB),并且可能更大(可能有几个 MB)在进入和退出内核空间之前重新排列虚拟内存比简单地进行复制要便宜。当然,try_realloc
在这里没有用处,因为整个好处来自于实际以低廉的成本进行移动。realloc
in C is hardly more than a convenience function; it has very little benefit for performance/reducing copies. The main exception I can think of is code that allocates a big array then reduces the size once the size needed is known - but even this might require moving data on somemalloc
implementations (ones which segregate blocks strictly by size) so I consider this usage ofrealloc
really bad practice.As long as you don't constantly reallocate your array every time you add an element, but instead grow the array exponentially (e.g. by 25%, 50%, or 100%) whenever you run out of space, just manually allocating new memory, copying, and freeing the old will yield roughly the same (and identical, in case of memory fragmentation) performance to using
realloc
. This is surely the approach that C++ STL implementations use, so I think your whole concern is unfounded.Edit: The one (rare but not unheard-of) case where
realloc
is actually useful is for giant blocks on systems with virtual memory, where the C library interacts with the kernel to relocate whole pages to new addresses. The reason I say this is rare is because you need to be dealing with very big blocks (at least several hundred kB) before most implementations will even enter the realm of dealing with page-granularity allocation, and probably much larger (several MB maybe) before entering and exiting kernelspace to rearrange virtual memory is cheaper than simply doing the copy. Of coursetry_realloc
would not be useful here, since the whole benefit comes from actually doing the move inexpensively.