使用CAS以primefaces方式递增两个整数
显然，可以使用比较和交换指令以primefaces方式递增两个整数。 这个谈话声称存在这样的算法，但它没有详细说明它的样子。
如何才能做到这一点？
（注意，一个接一个地递增整数的明显解决方案不是primefaces的。另外，将多个整数填充到一个机器字中并不算数，因为它会限制可能的范围。）
让我想起序列锁定。 不是很准确（从记忆中提出这个）但是有些东西：
令x，y和s为64位整数。
增量：
atomic s++ （我的意思是使用64位CAS op的primefaces增量）
memory barrier atomic x++ atomic y++ atomic s++ memory barrier
阅读：
do { S1 = load s X = load x Y = load y memory barrier S2 = load s } while (S1 != S2)
另请参阅https://en.wikipedia.org/wiki/Seqlock
如果sse2可用，则可以使用paddq在一条指令中将2个64位整数添加到另外两个64位整数。
#include "emmintrin.h" //initialize your values somewhere: //const __m128i ones = _mm_set1_epi64x(1); //volatile register __m128i vars = // _mm_set_epi64x(24,7); static inline __m128i inc_both(__m128i vars, __m128i ones){ return _mm_add_epi64(vars,ones); }
这应该编译为
paddq %xmm0, %xmm1
由于它是静态内联的，它可能会使用其他xmm寄存器。 如果存在显着的套准压力，则操作数可能变为1（℅rip）
注意：这可以用于添加除1之外的值，并且对于大多数其他数学，按位和比较指令，如果需要，它们也有类似的操作。
因此，您可以使用锁定前缀并将其设置为内联asm宏
#define inc64x2(vars) asm volatile( \ "paddq %0, %1\n":"+x"(vars):"x"(ones) \ );
arm霓虹灯的等价物是这样的：vaddq_s64（…），但这里有一篇关于arm / x86等价物的文章。
我有一个我测试过的解决方案。 这里包含的是坚果概念certificate计划的汤。
该算法是“使用CAS线程id门”作为第3个整数。 我看了两次video谈话，我相信这是合格的。 它可能不是演示者想到的算法，但确实有效。
X和Y值可以在内存中的任何位置，并且程序将它们放置得彼此远离它们在不同的高速缓存行上。 这并不重要。
算法的快速描述：
每个线程都有一个unique id number或tid （非零），取自一个人最喜欢的来源： pthead_t ， getpid ， gettid ， make one up by whatever means you want 。 在程序中，它只是从1开始按顺序分配它们。
每个线程将使用此数字调用递增函数。
增量函数将使用具有旧值0和新值tid CAS在全局gate变量上旋转。
当CAS成功时，线程现在“拥有”东西。 换句话说，如果gate是零，那就是争夺。 非零值是所有者的tid并且gate被锁定。
现在，所有者可以使用简单的x += 1和y += 1来自由增加X和Y值。
之后，增量函数通过在gate存储0来释放。
这是一个包含所有内容的诊断/概念validation程序。 算法本身没有限制，但我为我的机器编码。
一些警告：
- 它假设
gcc/clang - 它假定64位
x86_64拱。 - 这只使用内联asm进行编码，并且为了清晰，简单和透明， 不需要 [也不使用任何]编译器
atomic支持。 - 这是在linux下构建的，但应该适用于任何“合理的”x86机器/操作系统（例如BSD，OSX应该没问题，可能是cygwin，也许是mingw）
- 如果它们支持CAS，其他的拱门都没问题，我只是没有为它们编码（例如，如果使用
ldex/stex对编码CAS，arm可能会起作用） - 有足够的抽象原语，这将是/应该是容易的。
- 没有尝试Windows兼容性[如果你想要它，做你自己的端口，但发送给我没有眼泪 – 或评论:-)]。
- makefile和程序已默认为最佳值
- 某些x86 CPU可能需要使用不同的默认值（例如需要fence指令）。 请参阅makefile。
无论如何，这里是：
// caslock -- prove cas lock algorithm #include #include #include #include #include #define systls __thread // repeat the madness only once #ifdef __clang__ #define inline_common inline #else #define inline_common static inline #endif #define inline_always inline_common __attribute__((__always_inline__)) #define inline_never __attribute__((__noinline__)) // WARNING: inline CAS fails for gcc but works for clang! #if _USE_CASINLINE_ #define inline_cas inline_always #else #define inline_cas inline_never #endif typedef unsigned int u32; typedef unsigned long long u64; #ifndef LOOPMAX #define LOOPMAX 1000000 #endif #ifndef TIDMAX #define TIDMAX 20 #endif #if _USE_VPTR_ typedef volatile u32 *xptr32_p; typedef volatile u64 *xptr64_p; #else typedef u32 *xptr32_p; typedef u64 *xptr64_p; #endif #if _USE_TID64_ typedef u64 tid_t; #define tidload(_xptr) loadu64(_xptr) #define tidcas(_xptr,_oval,_nval) casu64(_xptr,_oval,_nval) #define tidstore(_xptr,_nval) storeu64(_xptr,_nval) #else typedef u32 tid_t; #define tidload(_xptr) loadu32(_xptr) #define tidcas(_xptr,_oval,_nval) casu32(_xptr,_oval,_nval) #define tidstore(_xptr,_nval) storeu32(_xptr,_nval) #endif tid_t tidgate; // gate control tid_t readycnt; // number of threads ready tid_t donecnt; // number of threads complete // ensure that the variables are nowhere near each other u64 ary[100]; #define kickoff ary[32] // sync to fire threads #define xval ary[31] // the X value #define yval ary[87] // the Y value int inctype; // increment algorithm to use tid_t tidmax; // maximum number of tasks u64 loopmax; // loop maximum for each task // task control struct tsk { tid_t tsk_tid; // task id u32 tsk_casmiss; // cas miss count }; typedef struct tsk tsk_t; tsk_t *tsklist; // task list systls tsk_t *tskcur; // current task block // show progress #define PGR(_pgr) \ do { \ fputs(_pgr,stdout); \ fflush(stdout); \ } while (0) // NOTE: some x86 arches need fence instructions // 0 -- no fence instructions // 1 -- use mfence // 2 -- use lfence/sfence #if _USE_BARRIER_ == 0 #define BARRIER_RELEASE "" #define BARRIER_ACQUIRE "" #define BARRIER_ALL "" #elif _USE_BARRIER_ == 1 #define BARRIER_ACQUIRE "\tmfence\n" #define BARRIER_RELEASE "\tmfence\n" #define BARRIER_ALL "\tmfence\n" #elif _USE_BARRIER_ == 2 #define BARRIER_ACQUIRE "\tlfence\n" #define BARRIER_RELEASE "\tsfence\n" #define BARRIER_ALL "\tmfence\n" #else #error caslock: unknown barrier type #endif // barrier_acquire -- acquire barrier inline_always void barrier_acquire(void) { __asm__ __volatile__ ( BARRIER_ACQUIRE : : : "memory"); } // barrier_release -- release barrier inline_always void barrier_release(void) { __asm__ __volatile__ ( BARRIER_RELEASE : : : "memory"); } // barrier -- barrier inline_always void barrier(void) { __asm__ __volatile__ ( BARRIER_ALL : : : "memory"); } // casu32 -- compare and exchange four bytes // RETURNS: 1=ok, 0=fail inline_cas int casu32(xptr32_p xptr,u32 oldval,u32 newval) { char ok; __asm__ __volatile__ ( " lock\n" " cmpxchg %[newval],%[xptr]\n" " sete %[ok]\n" : [ok] "=r" (ok), [xptr] "=m" (*xptr) : "a" (oldval), [newval] "r" (newval) : "memory"); return ok; } // casu64 -- compare and exchange eight bytes // RETURNS: 1=ok, 0=fail inline_cas int casu64(xptr64_p xptr,u64 oldval,u64 newval) { char ok; __asm__ __volatile__ ( " lock\n" " cmpxchg %[newval],%[xptr]\n" " sete %[ok]\n" : [ok] "=r" (ok), [xptr] "=m" (*xptr) : "a" (oldval), [newval] "r" (newval) : "memory"); return ok; } // loadu32 -- load value with barrier // RETURNS: loaded value inline_always u32 loadu32(const xptr32_p xptr) { u32 val; barrier_acquire(); val = *xptr; return val; } // loadu64 -- load value with barrier // RETURNS: loaded value inline_always u64 loadu64(const xptr64_p xptr) { u64 val; barrier_acquire(); val = *xptr; return val; } // storeu32 -- store value with barrier inline_always void storeu32(xptr32_p xptr,u32 val) { *xptr = val; barrier_release(); } // storeu64 -- store value with barrier inline_always void storeu64(xptr64_p xptr,u64 val) { *xptr = val; barrier_release(); } // qsleep -- do a quick sleep inline_always void qsleep(int bigflg) { struct timespec ts; if (bigflg) { ts.tv_sec = 1; ts.tv_nsec = 0; } else { ts.tv_sec = 0; ts.tv_nsec = 1000; } nanosleep(&ts,NULL); } // incby_tidgate -- increment by using thread id gate void incby_tidgate(tid_t tid) // tid -- unique id for accessing entity (eg thread id) { tid_t *gptr; tid_t oval; gptr = &tidgate; // acquire the gate while (1) { oval = 0; // test mode -- just do a nop instead of CAS to prove diagnostic #if _USE_CASOFF_ *gptr = oval; break; #else if (tidcas(gptr,oval,tid)) break; #endif ++tskcur->tsk_casmiss; } #if _USE_INCBARRIER_ barrier_acquire(); #endif // increment the values xval += 1; yval += 1; #if _USE_INCBARRIER_ barrier_release(); #endif // release the gate // NOTE: CAS will always provide a barrier #if _USE_CASPOST_ && (_USE_CASOFF_ == 0) oval = tidcas(gptr,tid,0); #else tidstore(gptr,0); #endif } // tskcld -- child task void * tskcld(void *arg) { tid_t tid; tid_t oval; u64 loopcur; tskcur = arg; tid = tskcur->tsk_tid; // tell master thread that we're fully ready while (1) { oval = tidload(&readycnt); if (tidcas(&readycnt,oval,oval + 1)) break; } // wait until we're given the starting gun while (1) { if (loadu64(&kickoff)) break; qsleep(0); } // do the increments for (loopcur = loopmax; loopcur > 0; --loopcur) incby_tidgate(tid); barrier(); // tell master thread that we're fully complete while (1) { oval = tidload(&donecnt); if (tidcas(&donecnt,oval,oval + 1)) break; } return (void *) 0; } // tskstart -- start a child task void tskstart(tid_t tid) { pthread_attr_t attr; pthread_t thr; int err; tsk_t *tsk; tsk = tsklist + tid; tsk->tsk_tid = tid; pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr,1); err = pthread_create(&thr,&attr,tskcld,tsk); pthread_attr_destroy(&attr); if (err) printf("tskstart: error -- err=%d\n",err); } // tskall -- run a single test void tskall(void) { tid_t tidcur; tsk_t *tsk; u64 incmax; u64 val; int err; xval = 0; yval = 0; kickoff = 0; readycnt = 0; donecnt = 0; tidgate = 0; // prealloc the task blocks tsklist = calloc(tidmax + 1,sizeof(tsk_t)); // start all tasks PGR(" St"); for (tidcur = 1; tidcur <= tidmax; ++tidcur) tskstart(tidcur); // wait for all tasks to be fully ready PGR(" Sw"); while (1) { if (tidload(&readycnt) == tidmax) break; qsleep(1); } // the starting gun -- all tasks are waiting for this PGR(" Ko"); storeu64(&kickoff,1); // wait for all tasks to be fully done PGR(" Wd"); while (1) { if (tidload(&donecnt) == tidmax) break; qsleep(1); } PGR(" Done\n"); // check the final count incmax = loopmax * tidmax; // show per-task statistics for (tidcur = 1; tidcur <= tidmax; ++tidcur) { tsk = tsklist + tidcur; printf("tskall: tsk=%llu tsk_casmiss=%d (%.3f%%)\n", (u64) tidcur,tsk->tsk_casmiss,(double) tsk->tsk_casmiss / loopmax); } err = 0; // check for failure val = loadu64(&xval); if (val != incmax) { printf("tskall: xval fault -- xval=%lld incmax=%lld\n",val,incmax); err = 1; } // check for failure val = loadu64(&yval); if (val != incmax) { printf("tskall: yval fault -- yval=%lld incmax=%lld\n",val,incmax); err = 1; } if (! err) printf("tskall: SUCCESS\n"); free(tsklist); } // main -- master control int main(void) { loopmax = LOOPMAX; tidmax = TIDMAX; inctype = 0; tskall(); return 0; }
这是Makefile。 对不起，额外的样板：
# caslock/Makefile -- make file for caslock # # options: # LOOPMAX -- maximum loops / thread # # TIDMAX -- maximum number of threads # # BARRIER -- generate fence/barrier instructions # 0 -- none # 1 -- use mfence everywhere # 2 -- use lfence for acquire, sfence for release # # CASOFF -- disable CAS to prove diagnostic works # 0 -- normal mode # 1 -- inhibit CAS during X/Y increment # # CASINLINE -- inline the CAS functions # 0 -- do _not_ inline # 1 -- inline them (WARNING: this fails for gcc but works for clang!) # # CASPOST -- increment gate release mode # 0 -- use fenced store # 1 -- use CAS store (NOTE: not really required) # # INCBARRIER -- use extra barriers around increments # 0 -- rely on CAS for barrier # 1 -- add extra safety barriers immediately before increment of X/Y # # TID64 -- use 64 bit thread "id"s # 0 -- use 32 bit # 1 -- use 64 bit # # VPTR -- use volatile pointers in function definitions # 0 -- use ordinary pointers # 1 -- use volatile pointers (NOTE: not really required) ifndef _CASLOCK_MK_ _CASLOCK_MK_ = 1 OLIST += caslock.o ifndef LOOPMAX LOOPMAX = 1000000 endif ifndef TIDMAX TIDMAX = 20 endif ifndef BARRIER BARRIER = 0 endif ifndef CASINLINE CASINLINE = 0 endif ifndef CASOFF CASOFF = 0 endif ifndef CASPOST CASPOST = 0 endif ifndef INCBARRIER INCBARRIER = 0 endif ifndef TID64 TID64 = 0 endif ifndef VPTR VPTR = 0 endif CFLAGS += -DLOOPMAX=$(LOOPMAX) CFLAGS += -DTIDMAX=$(TIDMAX) CFLAGS += -D_USE_BARRIER_=$(BARRIER) CFLAGS += -D_USE_CASINLINE_=$(CASINLINE) CFLAGS += -D_USE_CASOFF_=$(CASOFF) CFLAGS += -D_USE_CASPOST_=$(CASPOST) CFLAGS += -D_USE_INCBARRIER_=$(INCBARRIER) CFLAGS += -D_USE_TID64_=$(TID64) CFLAGS += -D_USE_VPTR_=$(VPTR) STDLIB += -lpthread ALL += caslock CLEAN += caslock OVRPUB := 1 ifndef OVRTOP OVRTOP := $(shell pwd) OVRTOP := $(dir $(OVRTOP)) endif endif # ovrlib/rules.mk -- rules control # # options: # GDB -- enable debug symbols # 0 -- normal # 1 -- use -O0 and define _USE_GDB_=1 # # CLANG -- use clang instead of gcc # 0 -- use gcc # 1 -- use clang # # BNC -- enable benchmarks # 0 -- normal mode # 1 -- enable benchmarks for function enter/exit pairs ifdef OVRPUB ifndef SDIR SDIR := $(shell pwd) STAIL := $(notdir $(SDIR)) endif ifndef GENTOP GENTOP := $(dir $(SDIR)) endif ifndef GENDIR GENDIR := $(GENTOP)/$(STAIL) endif ifndef ODIR ODIR := $(GENDIR) endif PROTOLST := true PROTOGEN := @true endif ifndef SDIR $(error rules: SDIR not defined) endif ifndef ODIR $(error rules: ODIR not defined) endif ifndef GENDIR $(error rules: GENDIR not defined) endif ifndef GENTOP $(error rules: GENTOP not defined) endif ifndef _RULES_MK_ _RULES_MK_ = 1 CLEAN += *.proto CLEAN += *.a CLEAN += *.o CLEAN += *.i CLEAN += *.dis CLEAN += *.TMP QPROTO := $(shell $(PROTOLST) -i -l -O$(GENTOP) $(SDIR)/*.c $(CPROTO)) HDEP += $(QPROTO) ###VPATH += $(GENDIR) ###VPATH += $(SDIR) ifdef INCLUDE_MK -include $(INCLUDE_MK) endif ifdef GSYM CFLAGS += -gdwarf-2 endif ifdef GDB CFLAGS += -gdwarf-2 DFLAGS += -D_USE_GDB_ else CFLAGS += -O2 endif ifndef ZPRT DFLAGS += -D_USE_ZPRT_=0 endif ifdef BNC DFLAGS += -D_USE_BNC_=1 endif ifdef CLANG CC := clang endif DFLAGS += -I$(GENTOP) DFLAGS += -I$(OVRTOP) CFLAGS += -Wall -Werror CFLAGS += -Wno-unknown-pragmas CFLAGS += -Wempty-body CFLAGS += -fno-diagnostics-color # NOTE: we now need this to prevent inlining (enabled at -O2) ifndef CLANG CFLAGS += -fno-inline-small-functions endif # NOTE: we now need this to prevent inlining (enabled at -O3) CFLAGS += -fno-inline-functions CFLAGS += $(DFLAGS) endif all: $(PREP) proto $(ALL) %.o: %.c $(HDEP) $(CC) $(CFLAGS) -c -o $*.o $< %.i: %.c cpp $(DFLAGS) -P $*.c > $*.i %.s: %.c $(CC) $(CFLAGS) -S -o $*.s $< # build a library (type (2) build) $(LIBNAME):: $(OLIST) ar rv $@ $(OLIST) .PHONY: proto proto:: $(PROTOGEN) -i -v -O$(GENTOP) $(SDIR)/*.c $(CPROTO) .PHONY: clean clean:: rm -f $(CLEAN) .PHONY: help help:: egrep '^#' Makefile caslock:: $(OLIST) $(LIBLIST) $(STDLIB) $(CC) $(CFLAGS) -o caslock $(OLIST) $(LIBLIST) $(STDLIB)
注意：我可能已经破坏了一些asm约束，因为在将CAS函数作为内联进行编译时，使用gcc会产生不正确的结果。 但是， clang与内联工作正常。 因此，默认情况下CAS函数不是内联的。 为了保持一致性，我没有对gcc / clang使用不同的默认值，即使我可以。
这是由gcc构建的内联相关函数的反汇编（失败）：
00000000004009c0 : 4009c0: 31 c0 xor %eax,%eax 4009c2: f0 0f b1 3d 3a 1a 20 lock cmpxchg %edi,0x201a3a(%rip) # 602404 4009c9: 00 4009ca: 0f 94 c2 sete %dl 4009cd: 84 d2 test %dl,%dl 4009cf: 75 23 jne 4009f4 4009d1: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) 4009d8:L00 64 48 8b 14 25 f8 ff mov %fs:0xfffffffffffffff8,%rdx 4009df: ff ff 4009e1: 83 42 04 01 addl $0x1,0x4(%rdx) 4009e5: f0 0f b1 3d 17 1a 20 lock cmpxchg %edi,0x201a17(%rip) # 602404 4009ec: 00 4009ed: 0f 94 c2 sete %dl 4009f0: 84 d2 test %dl,%dl 4009f2: 74 e4 je 4009d8 4009f4:L01 48 83 05 dc 17 20 00 addq $0x1,0x2017dc(%rip) # 6021d8 4009fb: 01 4009fc: 48 83 05 94 19 20 00 addq $0x1,0x201994(%rip) # 602398 400a03: 01 400a04: c7 05 f6 19 20 00 00 movl $0x0,0x2019f6(%rip) # 602404 400a0b: 00 00 00 400a0e: c3 retq
这里是clang构建的内联相关函数的反汇编（这个成功）：
0000000000400990 : 400990: 31 c0 xor %eax,%eax 400992: f0 0f b1 3d 3a 1a 20 lock cmpxchg %edi,0x201a3a(%rip) # 6023d4 400999: 00 40099a: 0f 94 c0 sete %al 40099d: eb 1a jmp 4009b9 40099f: 90 nop 4009a0:L00 64 48 8b 04 25 f8 ff mov %fs:0xfffffffffffffff8,%rax 4009a7: ff ff 4009a9: ff 40 04 incl 0x4(%rax) 4009ac: 31 c0 xor %eax,%eax 4009ae: f0 0f b1 3d 1e 1a 20 lock cmpxchg %edi,0x201a1e(%rip) # 6023d4 4009b5: 00 4009b6: 0f 94 c0 sete %al 4009b9:L01 84 c0 test %al,%al 4009bb: 74 e3 je 4009a0 4009bd: 48 ff 05 e4 17 20 00 incq 0x2017e4(%rip) # 6021a8 4009c4: 48 ff 05 9d 19 20 00 incq 0x20199d(%rip) # 602368 4009cb: c7 05 ff 19 20 00 00 movl $0x0,0x2019ff(%rip) # 6023d4 4009d2: 00 00 00 4009d5: c3 retq 4009d6: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1) 4009dd: 00 00 00