cmpxchg for WORD比BYTE更快
昨天我发布了this question关于如何编写快速螺旋锁。感谢Cory Nelson,我似乎找到了一种超越我的问题中讨论的其他方法的方法。我使用CMPXCHG
指令来检查锁是否为0,从而释放。 CMPXCHG
运行于'BYTE',WORD
和DWORD
。我会假设该指令在上运行得更快。但我写了一个锁实现每个数据类型:cmpxchg for WORD比BYTE更快
inline void spin_lock_8(char* lck)
{
__asm
{
mov ebx, lck ;move lck pointer into ebx
xor cl, cl ;set CL to 0
inc cl ;increment CL to 1
pause ;
spin_loop:
xor al, al ;set AL to 0
lock cmpxchg byte ptr [ebx], cl ;compare AL to CL. If equal ZF is set and CL is loaded into address pointed to by ebx
jnz spin_loop ;jump to spin_loop if ZF
}
}
inline void spin_lock_16(short* lck)
{
__asm
{
mov ebx, lck
xor cx, cx
inc cx
pause
spin_loop:
xor ax, ax
lock cmpxchg word ptr [ebx], cx
jnz spin_loop
}
}
inline void spin_lock_32(int* lck)
{
__asm
{
mov ebx, lck
xor ecx, ecx
inc ecx
pause
spin_loop:
xor eax, eax
lock cmpxchg dword ptr [ebx], ecx
jnz spin_loop
}
}
inline spin_unlock(<anyType>* lck)
{
__asm
{
mov ebx, lck
mov <byte/word/dword> ptr [ebx], 0
}
}
锁,然后用下面的伪代码进行测试(请注意,LCM-指针总是将4指向的地址整除):
<int/short/char>* lck;
threadFunc()
{
loop 10,000,000 times
{
spin_lock_8/16/32 (lck);
spin_unlock(lck);
}
}
main()
{
lck = (char/short/int*)_aligned_malloc(4, 4);//Ensures memory alignment
start 1 thread running threadFunc and measure time;
start 2 threads running threadFunc and measure time;
start 4 threads running threadFunc and measure time;
_aligned_free(lck);
}
我已经得到了以2个物理核心能够运行4个线程(Ivy Bridge)的处理器在msecs上测得的以下结果。
1 thread 2 threads 4 threads
8-bit 200 700 3200
16-bit 200 500 1400
32-bit 200 900 3400
数据表明所有函数都需要等量的时间才能执行。但是当多线程必须检查使用16位的lck == 0
可以显着更快。这是为什么?我不认为这与lck
的对齐有关系吗?
在此先感谢。
从我记得锁在一个单词(2字节)上工作。它是在486中首次引入时写入的。
如果您在不同的大小上执行锁定,它实际上会生成2个锁定(对于双字锁定字A和字B)。对于一个字节它可能必须防止锁定第二个字节,这有点类似于2个锁...
所以你的结果是符合CPU优化。
想象一下,有1234个线程和16个CPU。一个线程获取自旋锁,然后操作系统执行任务切换。现在你有16个CPU,每个都运行剩下的1233个线程中的一个线程,所有线程都以非常毫无意义的方式旋转,不管怎样,操作系统将CPU时间返回到唯一可以释放螺旋锁的线程需要很长时间。这意味着整个操作系统基本上都可以锁定(所有的CPU都会停止工作)几秒钟。这严重迟钝;那么你如何解决它?
您可以通过在用户空间中不使用螺旋锁来修复它。只有在任何开关可以被禁用的情况下才能使用自旋锁。只有内核应该能够禁用任务切换。
更具体地说,您需要使用互斥锁。现在,互斥体可能会在放弃并让线程等待锁之前旋转,而且(对于典型/低争用情况)这确实有所帮助,但它仍然是一个互斥锁,并不是自旋锁。
接下来;对于理智的软件来说,重要的是(为了性能)避免锁争用,然后确保无争用的情况很快(如果没有争用,好的互斥体不会导致任务切换)。您正在衡量相关/不相关的案例。
最后;你的锁不好。为避免过多使用lock
前缀,您应该测试您是否可以在不使用任何lock
前缀的情况下获取数据,并且只有当您可以使用前缀lock
时才能获取。英特尔(可能还有很多其他人)称这种策略为“测试;然后(测试和设置)”。另外,您还没有明白pause
的目的(或者对于那些不支持10年前的指令的汇编程序来说是“rep nop”)。
一个像样的自旋锁可能看起来像:
acquire:
lock bts dword [myLock],0 ;Optimistically attempt to acquire
jnc .acquired ;It was acquired!
.retry:
pause
cmp dword [myLock],0 ;Should we attempt to acquire again?
jne .retry ; no, don't use `lock`
lock bts dword [myLock],0 ;Attempt to acquire
jc .retry ;It wasn't acquired, so go back to waiting
.acquired:
ret
release:
mov dword [myLock],0 ;No lock prefix needed here as "myLock" is aligned
ret
另外请注意,如果你没有充分减少锁竞争的机会,那么你就需要关心“公平”,并且不应正在使用自旋锁。 “不公平的”螺旋锁的问题在于某些任务可能是幸运的,并且总是获得锁定,并且一些任务可能不吉利,并且从未获得锁定,因为幸运任务总是获得锁定。这一直是严重竞争锁定的问题,但对于现代NUMA系统来说,这成为更可能的问题。在这种情况下,您至少应该使用车票锁。
门票锁的基本思想是确保任务按照他们到达的顺序获取锁(而不是一些“可能非常糟糕”的随机顺序)。为了完整起见,一票锁定可能是这样的:
acquire:
mov eax,1
lock xadd [myLock],eax ;myTicket = currentTicket, currentTicket++
cmp [myLock+4],eax ;Is it my turn?
je .acquired ; yes
.retry:
pause
cmp [myLock+4],eax ;Is it my turn?
jne .retry ; no, wait
.acquired:
ret
release:
lock inc dword [myLock+4]
ret
TL;博士;你不应该使用错误的工具来开始工作(自旋锁)。但如果你坚持使用错误的工具,那么至少得到正确实施的错误工具... :-)
请注意,正确实现互斥体的唯一方法是使用螺旋锁,除非您希望内核仅在执行任务切换时允许互斥体(并且假设所有线程在发生时都停止)。我可以告诉你,在Linux互斥体正在使用自旋锁。 – 2014-05-30 21:52:38
'我知道这不是很多的区别,但作为螺旋锁是一个沉重使用的对象' - 天堂在30多年的多线程软件开发中没有明确地使用过单一的。 – 2012-08-15 23:23:05
尝试移动“暂停”指令进入旋转循环而不是循环之外。 16位指令需要额外的0x66/0x67前缀字节,使它们比8位或32位指令略大/慢。所以额外开销可能会减慢循环,以减少16位情况下的争用。 – 2012-08-16 00:41:13
如果这些锁导致随机损坏,我不会惊讶,因为它们修改ebx(一个被调用者保存寄存器)而不保存和恢复它,这可能会破坏调用者期望保留的一些值。改用edx。 – 2012-08-16 00:46:02