16

我遇到了这个 SO question并阅读它最终导致我查看boost::detail::spinlock_pool.

的目的是通过对s 地址进行散列boost::detail::spinlock_pool从 s 数组中进行选择来减少对全局自旋锁的潜在争用。这似乎是一个合理的解决方案,但当前(Boost v1.49)版本的实现似乎存在问题。spinlockshared_ptr

spinlock_pool管理一个由 41 个spinlock实例组成的静态分配数组。看来,sizeof(spinlock)==4对于我所查看的平台——这意味着在 x64 上使用 64 字节缓存线,spinlock每个缓存线将有 16 秒。

即整个阵列跨越所有2 1/2 高速缓存行。

即一个随机自旋锁与另一个错误共享的概率为 40%。

...首先,这几乎完全违背了游泳池的目的。

我的分析是正确的还是我遗漏了一些重要的东西?

更新: 我终于写了一个小基准程序:

#include <boost/shared_ptr.hpp>
#include <boost/thread.hpp>
#include <boost/timer.hpp>
#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

enum { BufferSize = 1<<24,  SLsPerCacheLine = 1 };

int          ibuffer[BufferSize];

using boost::detail::spinlock;
size_t nslp = 41;
spinlock* pslp = 0;

spinlock& getSpinlock(size_t h)
{
  return pslp[ (h%nslp) * SLsPerCacheLine ];
}


void threadFunc(int offset)
{
  const size_t mask = BufferSize-1;
  for (size_t ii=0, index=(offset&mask); ii<BufferSize; ++ii, index=((index+1)&mask))
  {
    spinlock& sl = getSpinlock(index);
    sl.lock();
    ibuffer[index] += 1;
    sl.unlock();
  }
};


int _tmain(int argc, _TCHAR* argv[])
{
  if ( argc>1 )
  {
    size_t n = wcstoul(argv[1], NULL, 10);
    if ( n>0 )
    {
      nslp = n;
    }
  }

  cout << "Using pool size: "<< nslp << endl;
  cout << "sizeof(spinlock): "<< sizeof(spinlock) << endl;
  cout << "SLsPerCacheLine: "<< int(SLsPerCacheLine) << endl;
  const size_t num = nslp * SLsPerCacheLine;
  pslp = new spinlock[num ];
  for (size_t ii=0; ii<num ; ii++)
  { memset(pslp+ii,0,sizeof(*pslp)); }

  const size_t nThreads = 4;
  boost::thread* ppThreads[nThreads];
  const int offset[nThreads] = { 17, 101, 229, 1023 };

  boost::timer timer;

  for (size_t ii=0; ii<nThreads; ii++)
  { ppThreads[ii] = new boost::thread(threadFunc, offset[ii]); }

  for (size_t ii=0; ii<nThreads; ii++)
  { ppThreads[ii]->join(); }

  cout << "Elapsed time: " << timer.elapsed() << endl;

  for (size_t ii=0; ii<nThreads; ii++)
  { delete ppThreads[ii]; }

  delete[] pslp;

  return 0;
}

我编译了两个版本的代码,一个带有SLsPerCacheLine==1,一个带有SLsPerCacheLine==8. 使用 MSVS 2010 优化的 32 位,在 4 核 Xeon W3520 @ 2.67Ghz(禁用超线程)上运行。

我很难从这些测试中获得一致的结果——偶尔会观察到高达 50% 的虚假时序变化。然而,平均而言,该版本似乎比具有大小为 41 的自旋锁表的版本SLsPerCacheLine==8快约 25-30% 。SLsPerCacheLine==1

看看它如何随着更多的核心、NUMA、超线程等扩展会很有趣。我目前无法访问那种硬件。

4

1 回答 1

14

简短的

你是对的,因为自旋锁共享相同的缓存行,而它们可能位于不同的缓存行中。又名虚假分享。通过在不同的缓存行中分配锁可能会获得一些性能提升(但请参见下文)。

但是,这与争用不同。当一个人持有一个锁并且一个或多个其他人想要访问它时,就会出现锁争用。

即 spinlock_pool 存在由锁共驻在同一缓存行中引起的缓存行争用。但它(减少了)软件锁争用。

减少软件锁争用无疑是好事。

正如您的基准测试在某种程度上显示的那样,缓存行争用可能会造成一些伤害,但与软件锁争用相比是二阶效应。

细节

背景

首先,一些背景:

经典的自旋循环是 test-and-test-and-set:

    loop: 
         tmp := load( memory_location_of_sw_lock )
         if( is_locked(tmp) ) goto loop
         was_locked := atomic_hw_locked_rmw( memory_location_of_sw_lock, 
                                             value_that_will_get_sw_lock )
         if( was_locked(tmp) ) goto loop
     got_the_sw_lock:
          ...
          ... critical section
          ...
          // release the lock, e.g.
          memory_location_of_sw_lock := 0

还有测试和设置自旋锁,看起来像

    loop: 
         was_locked := atomic_hw_locked_rmw( memory_location_of_sw_lock, 
                                             value_that_will_get_sw_lock )
         if( was_locked(tmp) ) goto loop

在大多数具有高速缓存、直写或回写的现代内存系统上,这些性能可能非常差。(尽管我提出的一些硬件优化使测试和设置自旋循环与测试和测试和设置自旋循环一样快 - 因为它们更小所以稍微快一些。)

请注意,这里有两个不同的锁概念:自旋锁正在获取的“软件”锁,以及 atomic_hw_locked_rmw 指令使用的硬件锁,例如 Intel LOCK INC mem 或 CMPXCHG。我们不太关心后者,只是知道它通常无条件地写入持有软件锁的缓存行,使缓存行的其他副本无效。(使写入有条件是另一种可能的硬件优化。)

O(N^2) 高速缓存未命中突发(软件)锁争用

使用 test-and-test-and-set spinloop 的锁争用尤其糟糕。服务员都在锁上旋转,当它被释放时,会有一阵总线访问。一个人赢了,其他人意识到他们输了,最终他们安定下来再次旋转。这种活动爆发特别糟糕,因为对于 N 个等待的人(线程/进程/处理器)来说,总线活动的爆发在大小上可能是 O(N^2),因为在最坏的情况下,每个人都退出了测试的测试部分- and-test-and-set spinloop,每个人都尝试同时执行原子锁定 RMW(读-修改-写)指令,例如 x86 LOCK INC mem 或 CMPXCHG。这意味着每个人最终都会写这行代码,即使除了第一个之外的所有人都不需要写锁,因为他们不会得到锁。

例如

Lock is held by P0
P1-PN are spinning in test-and-test-and-set spinloops waiting for it.

P0 releases the lock, e.g. by writing it to 0

P1's "test-" instruction reads the lock
...
PN's "test-" instruction reads the lock

All of P1-PN see the lock as released, 
   so they fall out of the "test-" part of the spinloop which uses ordinary instructions
   to the test-and-set part of the spinloop, which uses a hardware atomic RMW like LOCK INC mem

P1's locked RMW happens, and acquires the spinlock for P1
   It invalidates all other cache lines
   P1 goes away and does something with the data protected by the lock

P2's locked RMW fails to acquire the spinlock
   It invalidates all other caches because it has a write
   P1 falls back into its test- spinloop

P3's locked RMW fails
   It invalidates all other caches because it has a write
   P1 falls back into its test- spinloop

...

PN's locked RMW fails

现在,至少,所有剩余的 P2..PN 处理器必须为它们的测试自旋循环执行普通的未锁定缓存未命中。这意味着至少有 N+(N-1) 次缓存未命中。情况可能会更糟,因为每次写入都可能由无法获取锁的服务员触发所有其他服务员进行未锁定的读取。即,根据时间,您可能会得到

   1 release the lock
   N reads to test- the lock
   1 locked atomic RMW to acquire the lock
   N reads...
   for each of the remaining N-1 processors
      1 locked RMW that fails to acquire the lock
      N reads 

这是O(N ^ 2)。或者可能,对于处理器 M,1 个锁定的 RMW,然后是 2..M 读取 - 这仍然是 O(N^2)。

这对这个问题意味着什么?

好的,如果有真正的锁争用,当一个争用锁被释放时,你会得到这个 O(N^2) 的缓存未命中突发。

然而,spinlock_pool 将等待者分散到多个锁中。如果自旋锁池中有 S 把锁,你得到的等待者会少得多:可能少于 N/S(因为共享同一个锁的人数往往是超线性的)。

即使用 Boost 的 spinlock_pool,您可能天真地期望获得 1/41 的争用量 --- 并且可能更少。

请记住,spinlock_pool 是在每个 shared_pointer 拥有一个锁、增加共享指针的大小以及让所有 shared_pointer 共享同一个锁之间的折衷。因此,对 shared_pointer 的自旋锁的任何争用都可能是 (a) 真正的争用,或 (b) 由独立散列到自旋锁池中的同一条目的 shared_pointer 引起的虚假争用。

现在,是的,如果不是有 N 个服务员,而是“只有”N/41 个服务员,那么突发仍然是 O((N/41)^2) 或 O(N^2)。但是,如果 N 通常小于 41……你就明白了。

基本上,散列以将 shared_Pointers 分散到多个 spinlock_pool 条目上可以快速减少争用量。

但是......自旋锁住在同一个高速缓存行中?对...但是其他缓存行上的服务员不会前进到他们自旋循环的测试和设置部分。

即,如果与 M 个等待者的竞争锁与 M 个其他进程共享一个缓存行,您将获得 M*N 流量。但是,如果散列将 M 减少到 O(1),那么您只会获得 N 流量。

如果大多数时候根本没有其他服务员,那么在锁释放时你只会得到 O(1) raffic。

底线

减少软件锁竞争在性能方面比减少导致硬件缓存行竞争的缓存错误共享要高得多。

现在,不将这么多 spinlock_pool 条目打包到同一个缓存行中仍然可能有好处。但这绝不是显而易见的。这是一个经验问题,我的意思是你需要进行一个实验,它会随着工作量的不同而变化。

有时,在同一缓存行中错误地共享这些锁会很糟糕。一个典型的例子是保护处理器运行队列的锁。

有时,在同一缓存行中错误地共享这些锁是好的——它可以提供与预取在缓存中相同的好处。例如,假设您分配了一个 shared_pointers 数组,并且人们通常访问 aosptr[i],然后访问 aosptr[i+1],等等。

这完全取决于您的工作量。我已经看到它双向下跌。通常,根据我的经验,每个缓存行一个锁会更好,尽管通常不会很多。

更多乐趣

如果您关心,测试和测试和设置自旋循环的硬件优化是我的 MS 论文“同步基元的特征分类,包括总线放弃锁”的主题 - 一种消除突发的硬件更新缓存协议总线访问。未在任何正式出版物上发表,大学缩微胶片除外。

我的工作受到 T Anderson - IEEE Transactions on Parallel and Distributed Systems 1990 的论文“共享内存多处理器的自旋锁替代方案的性能”的启发。

我认为公平地说,大多数出版物都是关于软件、算法的,包括著名的 MCS 锁。我认为公平地说,这些技术虽然在理论上很流行,但很少被熟练的程序员使用。

顺便说一句,这里还有一些硬件优化可能。例如 CMPXCHG 根本不需要写锁。不幸的是,在当前的 Intel 硬件上,或者至少在我 1991 年设计的 Intel 硬件上,我仍然认为仍在使用,释放硬件锁(用于实现原子锁定 RMW)的唯一方法是使用特殊的微码写“存储解锁”。哎呀,微代码甚至可以使用 LoadLinked/StoreConditional (LL/SC),在幼稚的 LL/SC 在某些线程上没有向前进展的情况下回退到锁定。

英特尔最近可能已修复此问题。我在 2009 年离开了 Intel。我试图修复、改进、优化它,哦,从 1991 年开始。而且 Intel最近一直在改进锁的性能。但我认为他们主要致力于非竞争锁性能,并没有优化竞争锁性能。

同样,Alain Kagi 在他的论文和一些出版物以及专利http://www.google.com/patents/US6460124中表明,通过添加明智的延迟,缓存硬件可以使自旋锁与排队锁一样高效。

其中一些硬件优化使测试和设置自旋循环比测试和测试和设置自旋循环更好。

最新的开发是 Intel TSX(事务同步扩展),包括 HLE(硬件锁消除(Ravi Rajwar 在 UWisc 从事此工作,而我和 Alain Kagi 在那里,虽然我在同步方面的工作早在 UIUC))和 RTM (受限事务内存)。这两个都有助于无竞争......嗯,它们有助于解决错误竞争的竞争锁,例如保护可能是独立内容的粗粒度锁。即假锁争用。在某些方面,HLE 可能不需要 spinlock_pool。

道歉

对不起:我提供了一个冗长的答案,归结为“减少软件锁争用可能比自旋循环的硬件缓存行争用重要得多”。

虽然我希望通过为每个高速缓存行分配 1 个自旋循环来获得一些性能,但它可能很小,并且在一些不完全不常见的工作负载上甚至可能会有损失。

可以肯定的是,你必须测量它。

但是,无论如何,最大的收获来自于减少软件锁争用。

于 2012-07-04T01:33:43.900 回答