我一直在分析我们的应用程序，发现一些显而易见的事情，内存分配器被调用了很多，并且消耗了大量的时间（百分之几）去年我把内存分配器做得快了很多倍，但我仍然认为我可以再加快一些所以作为优化的一部分，我想加速量化分配大小的代码部分。
内存分配器保存可用内存块的列表有一个832个列表的数组从0..128k开始的每个分配大小都有一个列表。从0..128k开始的所有分配请求都转换为832个quanta中的一个（quanta是正确的词吗？）832是任意的，是我在下面提出的计划的结果我正在平衡不浪费内存和大量重用的愿望另外，我希望使用尽可能少的位来存储分配的大小在我们的应用程序中，对小尺寸的需求远远大于对大尺寸的需求，也就是说，对于较小的尺寸，重用性更高所有数据都是按8字节对齐的，所以最小的量子数是8我选择量化所有低于256字节到8字节的分配，这样就不会浪费超过对齐所需的内存同样为了节省空间，当内存被添加到一个空闲内存列表时，我使用分配内存的前8个字节作为下一个指针，因此我也不能低于8个字节从2..8k开始，请求量为32字节从8..32k到128字节从32..128k到512字节随着请求大小的增加，您可以使用更大的量程，但仍然可以保持您所浪费的内存百分比较低因为我只有832个大小，所以重用率很高，即使对于更大/更稀疏的分配也是如此。
这是量化分配请求的函数iRecycle是列表数组的索引从0..831开始
void GetAlignedSize(QWORD cb, QWORD& cbPack8, WORD& iRecycle) {
// we assume cb is small, so the first 'if' will be hit the most.
if (cb < 0x000800 - 0x0007) { // 0k..2k = 8 byte chunks
cb += 0x0007; cbPack8 = cb & (~0x0007); // pad to 8
iRecycle = 000 + WORD(cb >> 3);
} else if (cb < 0x002000 - 0x001f) { // 2k..8k = 32 byte chunks
cb += 0x001f; cbPack8 = cb & (~0x001f); // pad to 32
iRecycle = 192 + WORD(cb >> 5);
} else if (cb < 0x008000 - 0x007f) { // 8k..32k = 128 byte chunks
cb += 0x007f; cbPack8 = cb & (~0x007f); // pad to 128
iRecycle = 384 + WORD(cb >> 7);
} else if (cb < 0x020000 - 0x01ff) { // 32k..128k = 512 byte chunks
cb += 0x01ff; cbPack8 = cb & (~0x01ff); // pad to 512
iRecycle = 576 + WORD(cb >> 9);
} else {
cbPack8 = Pack8(cb);
iRecycle = 0;
}
}
问题来了我怎么能做类似的事情，只有比特操作我想去掉compare语句，因为我认为它破坏了cpu流水线只要量子化随尺寸增加而增加，且128k以下尺寸的#很小，任何方案都是可行的我希望这将消除最后一种情况，并且iRecycle将无限制地增加，因此我们可以将iRecycle更改为不同大小的整数。
谢谢你的帮助！
最佳答案
最明显的做法就是用一张桌子我怀疑这样的计划会更快，但好奇。。。
…因此，为了创建一个基线，我调整了您的函数（在C中呈现它）：
static uint
GetAlignedSize(size_t size, size_t* rsize)
{
size_t sx = size - 1 ;
if (size <= 0x00800)
{
*rsize = (sx | 0x007) + 1 ;
return (sx >> 3) + ((256 - 64) * 0) ;
} ;
if (size <= 0x02000)
{
*rsize = (sx | 0x01F) + 1 ;
return (sx >> 5) + ((256 - 64) * 1) ;
} ;
if (size <= 0x08000)
{
*rsize = (sx | 0x07F) + 1 ;
return (sx >> 7) + ((256 - 64) * 2) ;
} ;
if (size <= 0x20000)
{
*rsize = (sx | 0x1FF) + 1 ;
return (sx >> 9) + ((256 - 64) * 3) ;
} ;
*rsize = 0 ;
return 64 + ((256 - 64) * 4) ;
} ;
注意，它的大小不超过并包括8字节单位的0x800等，并返回“index”0..831（对于所有已知大小）和832（对于输出大小）（而不是1..832和0）顺便问一下，我想知道圆形的尺寸是否真的有用要释放块，您需要“索引”，如果您需要可以查找的舍入大小[完全公开：这也假设传入的请求大小不是零在时间上做了一点小小的改进！]
不管怎样，最普遍的方法是用表驱动整个过程：
static uint
get_aligned_size_1(size_t size, size_t* rsize)
{
static const uint tb[0x40] =
{
/* 0x00 */ (0x007 << 16) + ((256 - 64) * 0) + 3,
/* 0x01 */ (0x01F << 16) + ((256 - 64) * 1) + 5,
/* 0x02 */ (0x01F << 16) + ((256 - 64) * 1) + 5,
/* 0x03 */ (0x01F << 16) + ((256 - 64) * 1) + 5,
/* 0x04 */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x05 */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x06 */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x07 */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x08 */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x09 */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x0A */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x0B */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x0C */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x0D */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x0E */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x0F */ (0x07F << 16) + ((256 - 64) * 2) + 7,
/* 0x10 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x11 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x12 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x13 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x14 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x15 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x16 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x17 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x18 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x19 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x1A */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x1B */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x1C */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x1D */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x1E */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x1F */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x20 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x21 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x22 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x23 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x24 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x25 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x26 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x27 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x28 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x29 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x2A */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x2B */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x2C */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x2D */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x2E */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x2F */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x30 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x31 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x32 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x33 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x34 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x35 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x36 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x37 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x38 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x39 */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x3A */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x3B */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x3C */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x3D */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x3E */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
/* 0x3F */ (0x1FF << 16) + ((256 - 64) * 3) + 9,
} ;
size_t sx = size - 1 ;
if (size <= 0x20000)
{
uint tx ;
tx = tb[sx >> 11] ;
*rsize = (sx | (tx >> 16)) + 1 ;
return (sx >> (tx & 0xF)) + (tx & 0xFFF0) ;
} ;
*rsize = 0 ;
return 64 + ((256 - 64) * 4) ;
} ;
如果要将大小舍入的掩码、“索引”基和创建“索引”所需的移位都在表中手工打包成小纸片。
我在随机选择的请求大小上对这两个函数进行了计时：80%1..0x800、15%0x801..0x2000、4%0x2001..0x8000、0.9%0x8001..0x20000和0.1%输出大小：
Setup: 15.610 secs: user 15.580 system 0.000 -- 500 million
Branches: 1.910 secs: user 1.910 system 0.000
Table 1: 1.840 secs: user 1.830 system 0.000
设置循环是：
srand(314159) ;
for (int i = 0 ; i < trial_count ; ++i)
{
int r ;
size_t mx, mn ;
r = rand() % 1000 ;
if (r < 800)
{
mn = 1 ;
mx = 0x00800 ;
}
else if (r < 950)
{
mn = 0x00801 ;
mx = 0x02000 ;
}
else if (r < 990)
{
mn = 0x02001 ;
mx = 0x08000 ;
}
else if (r < 999)
{
mn = 0x08001 ;
mx = 0x20000 ;
}
else
{
mn = 0x20001 ;
mx = 0x80000 ;
} ;
test_values[i] = (rand() % (mx - mn + 1)) + mn ;
} ;
仔细观察设置5亿测试值所需的时间表版本运行得更快（合同一般条件4.8，-O3）但这是对一个微不足道的函数的4%改进请注意，表驱动版本更灵活，可以在不改变代码或运行时间的情况下添加更多的量程。
FWIW，掩码可以（显然）由移位构造，因此：
static uint
get_aligned_size_5(size_t size, size_t* rsize)
{
static const uint8_t ts[0x40] =
{
/* 0 1 2 3 4 5 6 7 8 9 A B C D E F
/* 0x00 */ 3,
/* 0x01..0x03 */ 5, 5, 5,
/* 0x04..0x0F */ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
/* 0x10..0x1F */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
/* 0x20..0x2F */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
/* 0x30..0x3F */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
} ;
static const uint tb[16] =
{
/* 0 */ 0,
/* 1 */ 0,
/* 2 */ 0,
/* 3 */ ((256 - 64) / 2) * (3 - 3),
/* 4 */ 0,
/* 5 */ ((256 - 64) / 2) * (5 - 3),
/* 6 */ 0,
/* 7 */ ((256 - 64) / 2) * (7 - 3),
/* 8 */ 0,
/* 9 */ ((256 - 64) / 2) * (9 - 3),
/* 10 */ 0,
/* 11 */ 0,
/* 12 */ 0,
/* 13 */ 0,
/* 14 */ 0,
/* 15 */ 0,
} ;
size_t sx = size - 1 ;
if (size <= 0x20000)
{
uint8_t s ;
s = ts[sx >> 11] ;
*rsize = (sx | (((size_t)1 << s) - 1)) + 1 ;
return (sx >> s) + tb[s] ;
} ;
*rsize = 0 ;
return 64 + ((256 - 64) * 4) ;
} ;
我发现这是我尝试过的最快的变化：
Setup: 15.610 secs: user 15.580 system 0.000 -- 500 million
Branches: 1.910 secs: user 1.910 system 0.000
Table 1: 1.840 secs: user 1.830 system 0.000
Table 5: 1.750 secs: user 1.750 system 0.000
总的来说（读一读，叹一声）快了8%：-（。
嗯，我很无聊。