现在是否值得实施 slab 分配器？
is it worth to implement a slab allocator nowdays?
我在一台服务器上工作，该服务器必须从同时连接的数千个套接字客户端读取数据。客户端请求由具有完全相同的大约 32 字节大小的消息构成。
我正在阅读有关 slab allocator 的文章，我想在调用 read 以从套接字中获取数据时为我的应用程序使用这种特殊技术（read将内核缓冲区中的数据复制到我选择的缓冲区中，我想使用一些动态分配的内存）。
虽然我正在阅读，但 Linux 内核似乎已经在使用这种技术。如果这用于实施 malloc or new 考虑到分配已经高效，我仍然值得这样做吗？
我在想，在没有 SLAB 算法的情况下使用堆栈分配可能会更好，但我不确定哪种方法最好。
如果你是 C 程序员，你当然应该熟悉内存管理！
但是，简单地 malloc'ing 每个请求可能不会遇到任何问题，除非您真的接近机器的极限，这似乎不太可能。但我相信了解您的备选方案比相信别人的话要好。以下是一些需要考虑的想法。
静态数组
最简单的替代方法是使用单个全局请求槽数组，并跟踪正在使用的请求槽。这意味着对请求数量的静态限制，但另一方面，没有开销，也没有真正的碎片问题。只需将限制设置得非常高。
这是一个示例实现。如果您不熟悉按位运算，它可能看起来有点混乱，但要点是我们有一个额外的数组，每个请求槽包含一位（开或关），指定该槽是否正在使用。相反，您可以向结构本身添加一个 'is_used' 变量，但这最终会将结构填充多于一位，这与我们最小化开销的目标背道而驰。
头文件非常少（顺便说一下，这是 C 语言的真正优点！）：
typedef struct request_s {
/* your 32 bytes of information */
unsigned char data[32];
} request_t;
request_t *alloc_request(void);
void free_request(request_t *req);
源文件：
#include the header file
/* note: this example is not written with multithreading in mind */
/* allow a million requests (total 32 MB + 128 KB of memory) */
#define MAX_REQUESTS (1*1024*1024)
static request_t g_requests[MAX_REQUESTS];
/* use one bit per request to store whether it's in use */
/* unsigned int is 32 bits. shifting right by 5 divides by 32 */
static unsigned int g_requests_used[MAX_REQUESTS >> 5];
request_t *alloc_request(void) {
/* note: this is a very naive method. you really don't want to search
* from the beginning every time, but i'll leave improving that as an
* exercise for you. */
unsigned int word_bits;
unsigned int word, bit;
/* look through the bit array one word (i.e., 32 bits) at a time */
for (word = 0; word < (MAX_REQUESTS >> 5); word++) {
word_bits = g_requests_used[word];
/* we can tell right away whether the entire chunk of 32 requests is
* in use, and avoid the inner loop */
if (word_bits == 0xFFFFFFFFU)
continue;
/* now we know there is a gap somewhere in this chunk, so we loop
* through the 32 bits to find it */
for (bit = 0; bit < 32; bit++) {
if (word_bits & (1U << bit))
continue; /* bit is set, slot is in use */
/* found a free slot */
g_requests_used[word] |= 1U << bit;
return &g_requests[(word << 5) + bit];
}
}
/* we're all out of requests! */
return NULL;
}
void free_request(request_t *req) {
/* make sure the request is actually within the g_requests block of
* memory */
if (req >= g_requests && req < g_requests + MAX_REQUESTS) {
/* find the overall index of this request. pointer arithmetic like this
* is somewhat peculiar to c/c++, you may want to read up on it. */
ptrdiff_t index = req - g_requests;
/* reducing a ptrdiff_t to an unsigned int isn't something you should
* do without thinking about it first. but in our case, we're fine as
* long as we don't allow more than 2 billion requests, not that our
* computer could handle that many anyway */
unsigned int u_index = (unsigned int)index;
/* do some arithmetic to figure out which bit of which word we need to
* turn off */
unsigned int word = u_index >> 5; /* index / 32 */
unsigned int bit = u_index & 31; /* index % 32 */
g_requests_used[word] &= ~(1U << bit);
}
}
(是的，是的，你可以写index / 32而不是index >> 5，等等，编译器会为你优化它。但我觉得不对。 ..)
您可以深入研究并在优化分配器对空闲槽的搜索方面发挥创造性。一个简单的想法是从上次分配的位置开始搜索，并在结束时环绕。
这种方法有很多好处，但有一个很大的缺点：限制。您可能希望将限制设置为高于您预期同时拥有的最大请求数。但如果你能做到这一点，那么你可能 不会 突破你系统的极限，所以你一开始为什么会在这里？！
内存池（静态数组链表）
如果你不喜欢静态限制，你可以批量分配。保留一个内存链表"pools"，每个链表持有一定数量的请求槽。如上所述，每个单独的池基本上都是一个静态数组。如果所有现有池都已满，我们 malloc 一个新池并将其添加到链表中。一个池基本上是这样的：
#define REQUESTS_PER_POOL 1024
typedef struct request_pool_s request_pool_t;
struct request_pool_s {
request_t requests[REQUESTS_PER_POOL];
unsigned int requests_used[REQUESTS_PER_POOL >> 5];
request_pool_t *prev;
request_pool_t *next;
};
您将希望能够在流量减少时释放池，否则这与静态限制几乎没有区别！不幸的是，在那种情况下，您将处理碎片化问题。您可能会发现自己有很多很少使用的池，特别是如果请求有时可能会持续很长时间。直到最后一个槽为空时，才能释放整个池。您仍然可以节省开销（考虑到单个请求的规模较小），但处理碎片可能会将其从一个小型、优雅的解决方案转变为超出其价值的工作。
您可以减少每个池的请求数以减少碎片的影响，但此时我们将失去此方法的优势。
哪一个？
首先，您应该考虑替代单个 malloc 的主要原因是：您的结构较小（32 字节），它们的数量很大，以及它们的创建频率和销毁。
静态数组大大减少了开销，但在当今时代很难证明其合理性。除非你的服务器是 Arduino 上的 运行。
内存池是解决此类问题的明显方向，但它们可能需要相当多的工作才能顺利进行。如果这是你的拿手好戏，那我就说吧。
Slab 分配器就像复杂的内存池，不限于特定的单个结构大小。它们对你来说太过分了，因为你只有 32 字节的请求，尽管你也许可以找到适合你的第三方库。
走简单的路线并简单地 malloc'ing 每个请求是一个滑坡，最终可能会导致您完全放弃 C。 ;)
我在一台服务器上工作，该服务器必须从同时连接的数千个套接字客户端读取数据。客户端请求由具有完全相同的大约 32 字节大小的消息构成。
我正在阅读有关 slab allocator 的文章，我想在调用 read 以从套接字中获取数据时为我的应用程序使用这种特殊技术（read将内核缓冲区中的数据复制到我选择的缓冲区中，我想使用一些动态分配的内存）。
虽然我正在阅读，但 Linux 内核似乎已经在使用这种技术。如果这用于实施 malloc or new 考虑到分配已经高效，我仍然值得这样做吗？
我在想，在没有 SLAB 算法的情况下使用堆栈分配可能会更好，但我不确定哪种方法最好。
如果你是 C 程序员，你当然应该熟悉内存管理！
但是，简单地 malloc'ing 每个请求可能不会遇到任何问题，除非您真的接近机器的极限，这似乎不太可能。但我相信了解您的备选方案比相信别人的话要好。以下是一些需要考虑的想法。
静态数组
最简单的替代方法是使用单个全局请求槽数组，并跟踪正在使用的请求槽。这意味着对请求数量的静态限制，但另一方面，没有开销，也没有真正的碎片问题。只需将限制设置得非常高。
这是一个示例实现。如果您不熟悉按位运算，它可能看起来有点混乱，但要点是我们有一个额外的数组，每个请求槽包含一位（开或关），指定该槽是否正在使用。相反，您可以向结构本身添加一个 'is_used' 变量，但这最终会将结构填充多于一位，这与我们最小化开销的目标背道而驰。
头文件非常少（顺便说一下，这是 C 语言的真正优点！）：
typedef struct request_s {
/* your 32 bytes of information */
unsigned char data[32];
} request_t;
request_t *alloc_request(void);
void free_request(request_t *req);
源文件：
#include the header file
/* note: this example is not written with multithreading in mind */
/* allow a million requests (total 32 MB + 128 KB of memory) */
#define MAX_REQUESTS (1*1024*1024)
static request_t g_requests[MAX_REQUESTS];
/* use one bit per request to store whether it's in use */
/* unsigned int is 32 bits. shifting right by 5 divides by 32 */
static unsigned int g_requests_used[MAX_REQUESTS >> 5];
request_t *alloc_request(void) {
/* note: this is a very naive method. you really don't want to search
* from the beginning every time, but i'll leave improving that as an
* exercise for you. */
unsigned int word_bits;
unsigned int word, bit;
/* look through the bit array one word (i.e., 32 bits) at a time */
for (word = 0; word < (MAX_REQUESTS >> 5); word++) {
word_bits = g_requests_used[word];
/* we can tell right away whether the entire chunk of 32 requests is
* in use, and avoid the inner loop */
if (word_bits == 0xFFFFFFFFU)
continue;
/* now we know there is a gap somewhere in this chunk, so we loop
* through the 32 bits to find it */
for (bit = 0; bit < 32; bit++) {
if (word_bits & (1U << bit))
continue; /* bit is set, slot is in use */
/* found a free slot */
g_requests_used[word] |= 1U << bit;
return &g_requests[(word << 5) + bit];
}
}
/* we're all out of requests! */
return NULL;
}
void free_request(request_t *req) {
/* make sure the request is actually within the g_requests block of
* memory */
if (req >= g_requests && req < g_requests + MAX_REQUESTS) {
/* find the overall index of this request. pointer arithmetic like this
* is somewhat peculiar to c/c++, you may want to read up on it. */
ptrdiff_t index = req - g_requests;
/* reducing a ptrdiff_t to an unsigned int isn't something you should
* do without thinking about it first. but in our case, we're fine as
* long as we don't allow more than 2 billion requests, not that our
* computer could handle that many anyway */
unsigned int u_index = (unsigned int)index;
/* do some arithmetic to figure out which bit of which word we need to
* turn off */
unsigned int word = u_index >> 5; /* index / 32 */
unsigned int bit = u_index & 31; /* index % 32 */
g_requests_used[word] &= ~(1U << bit);
}
}
(是的，是的，你可以写index / 32而不是index >> 5，等等，编译器会为你优化它。但我觉得不对。 ..)
您可以深入研究并在优化分配器对空闲槽的搜索方面发挥创造性。一个简单的想法是从上次分配的位置开始搜索，并在结束时环绕。
这种方法有很多好处，但有一个很大的缺点：限制。您可能希望将限制设置为高于您预期同时拥有的最大请求数。但如果你能做到这一点，那么你可能 不会 突破你系统的极限，所以你一开始为什么会在这里？！
内存池（静态数组链表）
如果你不喜欢静态限制，你可以批量分配。保留一个内存链表"pools"，每个链表持有一定数量的请求槽。如上所述，每个单独的池基本上都是一个静态数组。如果所有现有池都已满，我们 malloc 一个新池并将其添加到链表中。一个池基本上是这样的：
#define REQUESTS_PER_POOL 1024
typedef struct request_pool_s request_pool_t;
struct request_pool_s {
request_t requests[REQUESTS_PER_POOL];
unsigned int requests_used[REQUESTS_PER_POOL >> 5];
request_pool_t *prev;
request_pool_t *next;
};
您将希望能够在流量减少时释放池，否则这与静态限制几乎没有区别！不幸的是，在那种情况下，您将处理碎片化问题。您可能会发现自己有很多很少使用的池，特别是如果请求有时可能会持续很长时间。直到最后一个槽为空时，才能释放整个池。您仍然可以节省开销（考虑到单个请求的规模较小），但处理碎片可能会将其从一个小型、优雅的解决方案转变为超出其价值的工作。
您可以减少每个池的请求数以减少碎片的影响，但此时我们将失去此方法的优势。
哪一个？
首先，您应该考虑替代单个 malloc 的主要原因是：您的结构较小（32 字节），它们的数量很大，以及它们的创建频率和销毁。
静态数组大大减少了开销，但在当今时代很难证明其合理性。除非你的服务器是 Arduino 上的 运行。
内存池是解决此类问题的明显方向，但它们可能需要相当多的工作才能顺利进行。如果这是你的拿手好戏，那我就说吧。
Slab 分配器就像复杂的内存池，不限于特定的单个结构大小。它们对你来说太过分了，因为你只有 32 字节的请求，尽管你也许可以找到适合你的第三方库。
走简单的路线并简单地 malloc'ing 每个请求是一个滑坡，最终可能会导致您完全放弃 C。 ;)