多核机器上更快的基础数据结构？

我一直在思考这个问题:

您是否可以利用您拥有多个CPU的优势,在多核计算机上构建更快的基础数据结构(即链表,哈希表,集合,跳转列表,布隆过滤器,红黑树等)？

我做了一些pthreads的初步试验,发现pthread_create()的顺序为30us,但是一个简单的hash_map插入所花费的时间远远少于单个核心.因此,我很难想象创建一个更快的hash_map <>,因为同步原语和线程创建是如此之慢.我还可以想象树的遍历和并行平衡,但同样,同步原语似乎会使运行时更长,而不是更短.

对我来说,我仍然觉得"我有更多的CPU,因此,我应该能够更快地做到这一点",但我无法完全围绕证据或反证据证明这一点.我在C++中进行了相当多的实验,但我现在怀疑其他语言可能会为这项任务提供更好的解决方案(erlang？).思考？

编辑细节:我认为有几种经常使用的编程/数据结构范例可能会加速.例如,我发现自己经常编写基本上看起来像这样的代码(其中实际数据已被"rand()"替换)

static const int N = 1000000; 
static const int M = 10000000; // 10x more lookups 
hash_map m; 
// batch insert a bunch of interesting data 
for (int i = 0; i < N; i++) m[rand()] = rand(); 

// Do some random access lookups. 
for (int i = 0; i < M; i++) m[rand()]++;

这种范例经常用于名称 - 值设置和配置数据,批处理等等.10x(或更多)查找/插入比率使传统的hash_map <>成为这种操作的理想选择.

这可以很容易地分成两半,具有插入阶段和查找阶段,并且在并行世界中,在两半之间可能存在一些"刷新队列"操作.交错插入+查找版本更难:

hash_map m; 

for (int i = 0; i < N; i++) { 
   if (rand() % LOOKUP_RATIO == 0) 
     hash_map[rand()]++;  // "lookup" 
   else 
     hash_map[rand()] = rand();  // "insert" 
}

在那种情况下,只要在每次查找之前刷新插入队列,插入就可以是异步的,如果LOOKUP_RATIO足够大(例如,> 1000),那么它变得非常类似于上面的批处理示例,但是有一些排队.虽然,排队意味着同步原语.

想象一下,以下片段:

hash_map a;
hash_map b; 
for (int i = 0; i < N; i++) { 
  // the following 2 lines could be executed in parallel 
  a[rand()] = rand(); 
  b[rand()] = rand(); 
}

因此,查找可以通过以下方式"并行"完成:

int lookup(int value) { 
  // The following 2 lines could be executed in parallel: 
  v1 = a[value]; 
  v2 = b[value]; 
  if (v1)  // pseudo code for "value existed in a" 
    return v1; 
  else 
    return v2; 
}

Rob Lachlan.. 6

问题是共享数据本身就是并行计算的祸根.理想情况下,您希望每个核心处理单独的数据,否则会产生与同步相关的开销.(没有共享状态如何通信？通过消息传递.)

另外,谈论加速数据结构有点奇怪.我发现谈论正在加速的数据结构的操作更自然,因为不同数据结构上的不同操作具有不同的特征.是否有特定类型的访问权限要加快？

EDIT,响应额外的细节:我假设目标是有一个可以并行访问的哈希映射,它的基础可以是多个哈希表,但是它将透明地呈现给这个数据结构的用户作为单个哈希表.当然,我们会担心花太多时间在锁上旋转.同样在这个级别,我们必须了解缓存一致性问题.也就是说,如果核心或处理器具有指向相同数据的单独高速缓存,并且一个修改数据,则另一个上的高速缓存数据无效.如果这种情况反复发生,则可能会产生巨大的成本,并行性可能比在单个核心上进行操作更糟糕.所以我非常警惕共享数据.

我的直觉是拥有一个线程池,每个线程都拥有哈希表的不同部分.哈希首先从密钥映射到哈希表部分,然后映射到该部分内的偏移量.更新将作为消息传递给拥有该哈希表部分的该线程.这样,没有人试图同时修改同一件事.当然,这在语言(Erlang)中更容易,它具有异步消息传递并发性的特性.

问题是共享数据本身就是并行计算的祸根.理想情况下,您希望每个核心处理单独的数据,否则会产生与同步相关的开销.(没有共享状态如何通信？通过消息传递.)

另外,谈论加速数据结构有点奇怪.我发现谈论正在加速的数据结构的操作更自然,因为不同数据结构上的不同操作具有不同的特征.是否有特定类型的访问权限要加快？

EDIT,响应额外的细节:我假设目标是有一个可以并行访问的哈希映射,它的基础可以是多个哈希表,但是它将透明地呈现给这个数据结构的用户作为单个哈希表.当然,我们会担心花太多时间在锁上旋转.同样在这个级别,我们必须了解缓存一致性问题.也就是说,如果核心或处理器具有指向相同数据的单独高速缓存,并且一个修改数据,则另一个上的高速缓存数据无效.如果这种情况反复发生,则可能会产生巨大的成本,并行性可能比在单个核心上进行操作更糟糕.所以我非常警惕共享数据.

我的直觉是拥有一个线程池,每个线程都拥有哈希表的不同部分.哈希首先从密钥映射到哈希表部分,然后映射到该部分内的偏移量.更新将作为消息传递给拥有该哈希表部分的该线程.这样,没有人试图同时修改同一件事.当然,这在语言(Erlang)中更容易,它具有异步消息传递并发性的特性.