用什么数据结构来实现动态内存分配堆？ [英] What data structure is used to implement the dynamic memory allocation heap?

问题描述

我一直假设堆（数据结构）用于实现heap（动态内存分配），但我被告知我错了。

如何堆叠（例如，通过典型的 malloc 例程实现的，或者通过Windows的 HeapCreate 等等），通常？他们使用什么数据结构？

我不是问：

在网上搜索时，我看到了 我已经看到很多关于如何实现的描述：

• 堆不会释放内存回到操作系统（！）


• 只能在小型，相似大小的块上提供合理的性能


• 堆只能为大型连续块提供合理的性能


• 等。

这很有趣，他们都避免了更难的问题：

实现普通通用堆（如 malloc ， HeapCreate 之后的一个） >

他们使用什么数据结构（或算法）？

解决方案

分配器往往是相当复杂的，往往是不同的

您不能用一种常见的数据结构或算法来描述它们，但有一些共同的主题：

1. 内存以大块为单位，通常以兆字节为单位。


2. 这些块是然后在执行分配时分解成各种较小的块。不同于您分配的大小，但通常在一定范围内（200-250字节，251-500字节等）。有时候这是多层次的，在这里你会有一个额外的中间块层出现在你的实际需求之前。


3. 控制哪个大块是一个非常困难和重要的事情 - 这极大地影响内存碎片。


4. 一个或多个免费池（又名空闲列表，内存池，后备列表））为这些范围中的每一个维护。有时甚至线程本地池。这可以大大加快分配/取消分配类似大小的许多对象的模式。


5. 大量分配的处理方式有所不同，以免浪费大量的RAM，而不是很容易地集中很多，如果有的话。

如果你想查看一些源代码， jemalloc 是一个现代的高性能分配器，应该代表其他常见的分配器的复杂性。 TCMalloc 是另一个常见的通用分配器，它们的网站会涵盖所有的gory实现细节。英特尔的线程构建块具有专门用于高并发功能的分配器。

一个有趣的区别可以在Windows和* nix之间看到。在* nix中，分配器对应用程序使用的地址空间进行了非常低级的控制。在Windows中，您基本上有一个课程粒度较慢的分配器 VirtualAlloc 可以将您自己的分配器设置为off。

这导致* nix兼容的分配器通常直接给你一个 malloc / 免费实现，假设你只会使用一个分配器进行所有操作（否则它们会践踏每个其他分配器），而Windows特定的分配器提供其他功能，留下 malloc / free ，并且可以和谐使用（例如，您可以使用HeapCreate来制作可以与其他人一起工作的私人堆）。

在实践中，这种灵活的交易使得* nix分配器在性能方面有一个小腿。看到一个应用程序在Windows上有意使用多个堆栈是非常罕见的 - 主要是因为不同的DLL使用不同的运行时，每个都有自己的 malloc / free ，如果你不勤于跟踪某些内存来自哪个堆，可能会导致很多头痛。

I always assumed a heap (data structure) is used to implement a heap (dynamic memory allocation), but I've been told I'm wrong.

How are heaps (for example, the one implemented by typical malloc routines, or by Windows's HeapCreate, etc.) implemented, typically? What data structures do they use?

What I'm not asking:

While searching online, I've seen tons of descriptions of how to implement heaps with severe restrictions.
To name a few, I've seen lots of descriptions of how to implement:

• Heaps that never release memory back to the OS (!)
• Heaps that only give reasonable performance on small, similarly-sized blocks
• Heaps that only give reasonable performance for large, contiguous blocks
• etc.

And it's funny, they all avoid the harder question:
How are "normal", general-purpose heaps (like the one behind malloc, HeapCreate) implemented?

What data structures (and perhaps algorithms) do they use?

解决方案

Allocators tend to be quite complex and often differ significantly in how they're implemented.

You can't really describe them in terms of one common data structure or algorithm, but there are some common themes:

1. Memory is taken from the system in large chunks -- often megabytes at a time.
2. These chunks are then split up into various smaller chunks as you perform allocations. Not exactly the same size as you allocate, but usually in certain ranges (200-250 bytes, 251-500 bytes, etc.). Sometimes this is multi-tiered, where you'd have an additional layer of "medium chunks" which come before your actual requests.
3. Controlling which "large chunk" to break a piece off of is a very difficult and important thing to do -- this greatly affects memory fragmentation.
4. One or more free pools (aka "free list", "memory pool", "lookaside list") are maintained for each of these ranges. Sometimes even thread-local pools. This can greatly speed up a pattern of allocating/deallocating many objects of similar size.
5. Large allocations are treated a bit differently so as to not waste a lot of RAM and not be pooled quite so much if at all.

If you wanted to check out some source code, jemalloc is a modern high-performance allocator and should be representative in complexity of other common ones. TCMalloc is another common general-purpose allocator, and their website goes into all the gory implementation details. Intel's Thread Building Blocks has an allocator built specifically for high concurrency.

One interesting difference can be seen between Windows and *nix. In *nix, the allocator has very low-level control over the address space an app uses. In Windows, you basically have a course-grained, slow allocator VirtualAlloc to base your own allocator off of.

This results in *nix-compatible allocators typically directly giving you an malloc/free implementation where it's assumed you'll only use one allocator for everything (otherwise they'd trample each-other), while Windows-specific allocators provide additional functions, leaving malloc/free alone, and can be used in harmony (for instance, you can use HeapCreate to make private heaps which can work alongside others).

In practice, this trade in flexibility gives *nix allocators a small leg up performance-wise. It's very rare to see an app intentionally use multiple heaps on Windows -- mostly it's by accident due to different DLLs using different runtimes which each have their own malloc/free, and can cause a lot of headaches if you're not diligent in tracking which heap some memory came from.

这篇关于用什么数据结构来实现动态内存分配堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！