内存不足，无法快速分配？

Question

假设您被委托解决应用程序中的性能瓶颈。 通过分析，我们发现瓶颈与内存分配有关。我们发现应用程序每秒只能执行N次内存分配，无论我们有多少线程分配内存。为什么会出现这种情况，如何增加应用程序分配内存的速率？（假设我们无法更改正在分配的内存块的大小。假设我们不能减少动态分配内存的使用。）

- whothat

---

是啊！我在想 - 如果有任何锁定来获取内存分配，请摆脱它们。也许可以针对每个线程进行单独的分配等...还有其他问题吗？ - whothat

这是一个多么愚蠢的问题。它制造了一个不可能的情况，即问题是内存分配速率固定，而问如何增加内存分配速率。你做不到。解决方案很明显，通过减少对动态分配内存的需求或重新设计内存分配策略来解决问题。不幸的是，这个问题还告诉你，你不能采取显而易见的解决方案。当然，这永远不会是真实世界中的情况。 - Cody Gray

@ter，你对问题可能是正确的，但是你对这个网站的目的却有所误解。根据帮助中心的规定，我们处理的是基于实际世界中遇到的问题的实用性问题。 - Cody Gray

这很容易。在开始时分配内存。安全关键系统都会这样做。 - Ed Heal

谢谢大家！我自己也觉得这是一个相当奇怪的问题，有那么多限制...答案很明显——预分配、像你们所说的那样分离堆。我不会因为这家公司问的这种垃圾问题而去应聘。 - whothat

Answer 1

好的，有几种解决方案 - 但是几乎所有的解决方案似乎都因为某些限制而被排除。

1. 增加线程分配内存

我们发现无论有多少个线程分配内存，应用程序每秒只能执行N次内存分配。

因此，我们可以取消任何增加线程数量的想法（因为“无论有多少个线程”...）。

2. 每次分配 更多 内存

假设我们无法更改正在分配的内存块的大小。

显然，我们必须分配相同大小的块。

3. 使用（某些）静态内存

假设我们无法减少动态分配的内存使用。

我觉得这个最有趣了...让我想起了一个关于FORTRAN程序员的故事（在Fortran没有动态内存分配之前），他只是用一个在堆栈上分配的巨大静态数组作为私有堆。不幸的是，这个限制阻止了我们使用这样的技巧.. 然而，它确实为解决方案的一个方面提供了一些线索。

---

我的解决方案

在执行开始时（无论是程序还是每个线程），进行多次^{^}内存分配系统调用。然后在程序中稍后使用这些内存（以及现有的动态内存分配）。

_{* 注意：“几次”可能是一个精确的数量，根据您在问题开头提到的“分析”来确定。}

简短概述

诀窍 就是修改内存分配的时间。

- Tersosauros

---

有趣的想法。基本上，你只需要预先分配一个本地堆，然后从中进行后续的动态分配，而不是每次都返回到操作系统。这可能会稍微快一点，因为它避免了系统调用的开销。但我不确定它是否满足问题的要求。似乎违反了减少动态分配内存使用的禁令。我不确定该如何理解。 - Cody Gray

我认为这并没有减少动态分配内存的使用，只是把它向前移动了一点时间。毕竟分配内存的系统调用还是一样的。 - Tersosauros

Answer 2

看起来是一个具有挑战性的问题，尽管没有细节，你只能猜测一些。(这很可能是这个问题的目的)

这里的限制是分配数量，而不是分配大小。 如果我们可以假设你控制着分配位置，你可以一次性为多个实例分配内存。请将下面的代码视为伪代码，因为它仅用于说明目的。

const static size_t NR_COMBINED_ALLOCATIONS = 16;
auto memoryBuffer = malloc(size_of(MyClass)*NR_COMBINED_ALLOCATIONS);
size_t nextIndex = 0;
// Some looping code
    auto myNewClass = new(memoryBuffer[nextIndex++]) MyClass;
    // Some code
    myNewClass->~MyClass();
free(memoryBuffer);

你的代码很可能会变得更加复杂，但你很可能会克服这个瓶颈。如果你必须返回这个新的类，你甚至需要更多的代码来进行内存管理。

根据这些信息，你可以编写自己的 STL 的分配器实现，覆盖 'new' 和 'delete' 操作符......

如果这还不够，尝试挑战限制。为什么你只能进行固定数量的分配，是因为唯一锁定吗？如果是这样，我们能不能改进呢？为什么你需要那么多的分配，改变正在使用的算法是否会解决这个问题......

- JVApen

Answer 3

应用程序每秒只能执行N次内存分配，无论我们有多少个线程进行内存分配。我们为什么会看到这种行为，如何增加应用程序分配内存的速率是值得考虑的。在我看来，最可能的原因是分配来自一个公共系统池。

因为它们共享一个池，所以每个线程必须通过某些关键部分阻塞机制（可能是信号量）获得访问权限。

更多竞争动态内存（即使用new）的线程将导致更多的关键部分阻塞。

任务之间的上下文切换是时间浪费的主要原因。

---

如何提高速率？

选项1 - 序列化使用...这意味着，您不能简单地尝试在另一个级别使用信号量。我曾经工作过的一个系统，在系统启动期间发生了高动态内存利用。在这种情况下，最容易的方法是更改启动方式，使得此集合的线程n+1仅在线程n完成其初始化并进入其等待输入循环后才开始运行。只有1个线程在进行启动时（而且几乎没有其他动态内存用户正在运行），不会发生关键部分阻塞。4个同时启动需要30秒。4个序列化启动在5秒钟内完成。

选项2 - 为每个特定线程提供一组RAM和私有的new/delete。如果只有一个线程同时访问池，则不需要关键部分或信号量。在嵌入式系统中，挑战在于为线程分配合理的私有池，并避免浪费太多。在具有多GB RAM的桌面上，这可能不是问题。

- 2785528

---

在Ubuntu 15.10（64位）上，使用g++ v5.2.1，未优化（-O0），强制使用std::mutex的std::thread上下文切换每个需要花费12,000纳秒。另一方面，Mutex方法调用可以在42纳秒内同时执行lock()和unlock()。因此，在没有竞争的情况下，Mutex的成本非常低。 - 2785528

Answer 4

我认为你可以使用一个单独的线程来负责内存分配。这个线程将拥有一个队列，其中包含线程标识符和所需内存分配的映射。线程不会直接分配内存，而是向队列发送分配请求并进入等待状态。队列会尝试从队列中处理每个请求的内存分配，并唤醒相应的休眠线程。当负责内存处理的线程由于限制无法处理分配时，它应该等待直到可以再次分配内存。

可以像@Tersosauros的解决方案建议的那样构建另一层解决方案来略微优化速度，但它仍应基于上述思想。

- Lajos Arpad