测试分布式内存池
5.00/5 (8投票s)
本文描述了一种简单的方法和测试结果，用于在多核PC上为高性能应用程序创建分布式对象池。
引言
开发高性能应用程序通常需要使用快速内存分配器存储。使用分布式内存池可以提高多核PC上多线程应用程序的性能[1-3]。
分布式内存池旨在最大限度地减少“伪共享”和线程争用对多核PC的影响。与其同时访问全局内存存储（这可能成为瓶颈），不如使用每线程分配的内存池，并结合平衡私有池和全局池，以利用快速无锁算法。这种分布式解决方案并不简单。最新版本的Microsoft Windows提供了优化的同步原语。我们可能希望利用它们，设计简单但仍然快速的池解决方案。
最简单的分布式池可以是池数组。应用程序线程根据某些分布规则在这些池中“分布”。这些规则可能取决于线程的创建和结束方式——它可以是在应用程序启动时创建的均匀分布，也可以是“基于哈希”的分布。为了尝试这些技术，我们引入了一个模板类Pool_t，它代表池数组的一个元素。然后，我们将实现一个类Array_of_pools_t，它代表一个分布式池。对于Pool_t对象，我们使用一个直接的实现，利用Windows的Interlockedxxx API来实现单链表。
/*
Copyright (c) 2009 Valery Grebnev.
CPOL (Code Project Open License) Licensed https://codeproject.org.cn/info/cpol10.aspx
*/
template <typename Entry_t, size_t pool_size>
class CACHE_ALIGN Pool_t
{
public:
inline Entry_t* pop(void)
{
List_entry* plist = static_cast<List_entry*>(interlocked_pop_entry_slist(&m_head));
return (plist)? reinterpret_cast<Entry_t*>(reinterpret_cast<char*>(plist) +
data_offset): NULL;
}
inline void push(Entry_t* data)
{
List_entry* plist =
reinterpret_cast<List_entry*>(reinterpret_cast<char*>(data) - data_offset);
interlocked_push_entry_slist(&m_head, plist);
}
Pool_t()
{
::InitializeSListHead(&m_head);
for(size_t i = 0; i < pool_size; i++)
{
interlocked_push_entry_slist(&m_head, &m_pool[i].m_list_entry);
}
}
virtual ~Pool_t()
{
}
private:
typedef SLIST_HEADER CACHE_ALIGN SLIST_HEADER_;
struct CACHE_ALIGN List_entry: public SLIST_ENTRY
{
//some extra data if needed
};
struct CACHE_ALIGN
_Internal_entry_t
{
CACHE_PADDING(1);
List_entry m_list_entry;
Entry_t m_value;
};
static const int data_offset = offsetof(_Internal_entry_t, m_value) -
offsetof(_Internal_entry_t, m_list_entry);
CACHE_PADDING(1);
_Internal_entry_t CACHE_ALIGN m_pool[pool_size];
CACHE_PADDING(2);
SLIST_HEADER_ m_head;
};
这个池实现是线程安全的。它在单处理器PC上速度很快。在多核PC上，共享列表头m_head会带来性能损失。影响取决于硬件，并且可能相当显著。引入分布式池后，我们希望不同的线程在不同的内存位置更新列表头，从而使线程争用和“伪共享”的影响不那么显著。如果所有线程都在应用程序启动时创建，一个简单的解决方案是在池数组中均匀分布所有线程。
/*
Copyright (c) 2009 Valery Grebnev.
CPOL (Code Project Open License) Licensed
https://codeproject.org.cn/info/cpol10.aspx
*/
template <typename Entry_t, size_t pool_size, size_t number_of_pools>
class CACHE_ALIGN Array_of_pools_t
{
public:
inline Entry_t* pop(size_t index)
{
return m_pools[index].pop();
}
inline void push(Entry_t* data, size_t index)
{
m_pools[index].push(data);
}
inline size_t get_pool_index()
{
volatile static LONG m_counter = 0L;
return (::InterlockedIncrement(&m_counter) - 1) % number_of_pools;
}
Array_of_pools_t()
{
}
private:
Pool_t<Entry_t, pool_size> m_pools[number_of_pools];
};
当创建线程时，它首先获取并存储索引 = get_pool_index()。此索引指向数组中的一个池，线程将在后续的pop/push调用中访问该池。线程始终使用相同的索引很重要。创建线程分布的另一种方法是使用哈希作为池索引，例如：
inline size_t Array_of_pools_t::get_pool_index()
{
return hash(::GetCurrentThreadId());
}
long Array_of_pools_t::hash(long key)
{
const float golden=0.6180339f;
float val = (float)key * golden;
int ival = (int) val;
return((long) ((val - (float)ival) * (float) number_of_pools));
}
单个Pool_t对象和Array_of_pools_t对象的测试结果总结在图5中。八个线程（4个写入器和4个读取器）在四核PC上并发访问池。写入器线程从池中弹出一个缓冲区，用随机字节填充缓冲区，并计算CRC。然后，写入器将缓冲区推回。每个读取器线程从池中弹出一个缓冲区，计算CRC，并将其与写入器保存的CRC进行比较（如果出现CRC错误，将抛出异常，这表明池实现不正确）。测试应用程序已附在此文章中。
每次读/写操作的平均持续时间（以微秒计）是基于50次测试计算的；每次测试分别包括写入器和读取器的1,000,000和4,000,000次迭代。测试结果表明，分布式池Array_of_pools_t的性能优于单个池，在四核PC上，当池的数量从1增加到4时，性能显著提高（最多约5-6倍）。当线程数量从8增加到32时，性能提高更为显著，最多可达10倍。影响这些池性能的两个因素是“伪共享”和线程争用。为了减少线程争用的影响，我们可以尝试“按处理器”的分布规则，而不是“按线程”的分布规则。图6说明了Pool_t和Array_of_pools_t代码中与“按处理器”相关的修改。
/*
Copyright (c) 2009 Valery Grebnev.
CPOL (Code Project Open License) Licensed
https://codeproject.org.cn/info/cpol10.aspx
*/
template <typename Entry_t, size_t pool_size>
class CACHE_ALIGN Pool_t
{
public:
inline Entry_t* pop(void)
{
List_entry* plist =
static_cast<List_entry*>(interlocked_pop_entry_slist(&m_head));
return (plist)? reinterpret_cast<Entry_t*>(reinterpret_cast<char*>(plist) +
data_offset): NULL;
}
inline void push(Entry_t* data)
{
List_entry* plist =
reinterpret_cast<List_entry*>(reinterpret_cast<char*>(data) - data_offset);
interlocked_push_entry_slist(&m_head, plist);
}
inline static size_t get_pool_id(Entry_t* data)
{
List_entry* plist =
reinterpret_cast<List_entry*>(reinterpret_cast<char*>(data) - data_offset);
return plist->m_pool_id;
}
void set_pool_id(size_t id)
{
for(size_t i = 0; i < pool_size; i++)
{
m_pool[i].m_list_entry.m_pool_id = id;
}
}
Pool_t()
{
::InitializeSListHead(&m_head);
for(size_t i = 0; i < pool_size; i++)
{
m_pool[i].m_list_entry.m_pool_id = 0;
interlocked_push_entry_slist(&m_head, &m_pool[i].m_list_entry);
}
}
virtual ~Pool_t()
{
}
private:
typedef SLIST_HEADER CACHE_ALIGN SLIST_HEADER_;
struct CACHE_ALIGN List_entry: public SLIST_ENTRY
{
size_t m_pool_id;
};
struct CACHE_ALIGN
_Internal_entry_t
{
CACHE_PADDING(1);
List_entry m_list_entry;
Entry_t m_value;
};
static const int data_offset = offsetof(_Internal_entry_t, m_value) -
offsetof(_Internal_entry_t, m_list_entry);
CACHE_PADDING(1);
_Internal_entry_t CACHE_ALIGN m_pool[pool_size];
CACHE_PADDING(2);
SLIST_HEADER_ m_head;
};
template <typename Entry_t, size_t pool_size, size_t number_of_pools>
class CACHE_ALIGN Array_of_pools_t
{
public:
inline Entry_t* pop()
{
return m_pools[::GetCurrentProcessorNumber()% number_of_pools].pop();
}
inline void push(Entry_t* data)
{
m_pools[Pool_t<Entry_t, pool_size>::get_pool_id(data)].push(data);
}
Array_of_pools_t()
{
for(size_t i = 0; i < number_of_pools; i++)
{
m_pools[i].set_pool_id(i);
}
}
private:
Pool_t<Entry_t, pool_size> m_pools[number_of_pools];
};
“按处理器”分布的理念是减少在多核PC上可以同时访问池对象共享成员的线程数量。这应该会进一步减少池头上的线程争用，从而提高性能。但图5中的测试结果显示，“按处理器”和“按线程”分布的池性能差异不大。“按线程”分布式池并没有更慢。为了查看“按线程”和“按处理器”分布之间的争用差异，我们可以引入我们测试版本的Interlockedxxx函数，用于带有“争用”计数器的单链表。下面的x32位实现很简单，可能与微软为x32位单链表API所做的工作相差不远。
#if defined(TEST_CONTENTION_COUNT)
/*
The functions test_interlocked_pop_entry_slist32 and test_interlocked_push_entry_slist32
are for testing purposes. You should have not used these functions in your production
code without reviewing them "“ if SLIST_ENTRY objects are allocated and disposed dynamically,
the instructions (exch.Next).Next = (prev_header.Next).Next->Next may not refer
to a valid memory location.
*/
#define interlocked_pop_entry_slist test_interlocked_pop_entry_slist32
#define interlocked_push_entry_slist test_interlocked_push_entry_slist32
extern volatile long g_contention_count;
PSLIST_ENTRY WINAPI
test_interlocked_pop_entry_slist32(__inout PSLIST_HEADER ListHead)
{
SLIST_HEADER cmp_header, prev_header;
prev_header.Alignment = ListHead->Alignment;
_read_compiler_barrier_();
long count = -1;
do
{
count++;
if ((prev_header.Next).Next == 0)
{
return NULL;
}
else
{
}
SLIST_HEADER exch = {0};
(exch.Next).Next = (prev_header.Next).Next->Next;
exch.Sequence = prev_header.Sequence + 1;
cmp_header.Alignment = prev_header.Alignment;
prev_header.Alignment = ::_InterlockedCompareExchange64(
reinterpret_cast<__int64*>(&(ListHead->Alignment)),
exch.Alignment,
cmp_header.Alignment
);
__asm{pause}
}
while(prev_header.Alignment != cmp_header.Alignment);
::_InterlockedExchangeAdd(&g_contention_count, count);
return prev_header.Next.Next;
}
PSLIST_ENTRY WINAPI test_interlocked_push_entry_slist32(
__inout PSLIST_HEADER ListHead,
__inout PSLIST_ENTRY ListEntry)
{
PSLIST_ENTRY prev_entry;
PSLIST_ENTRY first_entry;
prev_entry = ListHead->Next.Next;
_read_compiler_barrier_();
long count = -1;
do
{
count++;
first_entry = prev_entry;
ListEntry->Next = prev_entry;
prev_entry = reinterpret_cast<PSLIST_ENTRY>(
::_InterlockedCompareExchange(
reinterpret_cast<long*>(&(ListHead->Next.Next)),
reinterpret_cast<long>(ListEntry),
reinterpret_cast<long>(first_entry)));
__asm{pause}
} while (first_entry != prev_entry);
::_InterlockedExchangeAdd(&g_contention_count, count);
return prev_entry;
}
#else
#define interlocked_pop_entry_slist ::InterlockedPopEntrySList
#define interlocked_push_entry_slist ::InterlockedPushEntrySList
#endif
测试结果总结在图8中。“争用”计数器以百分比表示（计数器 = (g_contention_count / total_number_of_iterations) * 100%）。与“按处理器”分布式池相比，“按线程”分布的池的“争用”计数器更高（~20%）。
尽管“按线程”分布式池的“争用”计数器值更高，但它们并未变慢，甚至比“按处理器”分布的池更快，参见图5。如果分布式池使用快速同步原语（例如Windows slist的API），则线程争用似乎不是影响性能的唯一因素。此外，图9中“按线程”分布式池的测试结果表明，即使线程数量从8增加到32，池数量增加到4以上也无法进一步提高性能。
如果线程数量等于32，并且池数量等于4，则八个线程将并发访问数组中的一个池。在这种情况下，我们可能会期望随着池数量的进一步增加而提高性能。但是，如图9所示，当池数量达到4时，在四核PC上，“争用”计数器和性能都保持不变。实际上，这意味着没有必要为每个应用程序线程创建私有内存池（正如有时建议的那样）。根据硬件情况，创建一个大小（池数量）大于处理器/核心数量的分布式池也可能是资源的浪费。
结论
- 使用简单的池数组可以显著提高使用Microsoft编译器VC++9.0为Microsoft Windows Vista开发、在多核PC上运行的x32/x64应用程序的性能。
- 创建的池数量多于处理器/核心数量可能是一个缺点。
参考文献
- Charles Leiserson。“多核存储分配”，http://www.cilk.com/multicore-blog/bid/7904/Multicore-Storage-Allocation
- Barry Tannenbaum。“Miser - 多线程应用程序的动态可加载内存分配器”，http://www.cilk.com/multicore-blog/?Tag=memory%20management
- “Hoard内存分配器”，http://www.hoard.org/
致谢
非常感谢Dmitriy V'jukov和Serge Dukhopel。在多核PC上尝试“按处理器”分布式池，包括池内线程分布方法，是他们的想法。Dmitriy V'jukov还对本文中代码的使用和局限性提出了宝贵意见。