在无锁数据结构中需要多少个ABA标签位？(How many ABA tag bits are needed in lock-free data structures?)

 无锁数据结构中ABA问题的一种流行解决方案是使用额外的单调递增标签来标记指针。 
 
 struct aba {
      void *ptr;
      uint32_t tag;
 };
 
 但是，这种方法有一个问题。 它非常慢，并且存在巨大的缓存问题。 如果我丢弃标签字段，我可以获得两倍的加速。 但这是不安全的？ 
 
 所以我的下一个尝试64位平台的东西在ptr字段填充位。 
 
struct aba {
    uintptr __ptr;
};
uint32_t get_tag(struct aba aba) { return aba.__ptr >> 48U; }
 
 但有人对我说标签只有16位是不安全的。 我的新计划是使用指针对齐到缓存行来填充更多标签位，但我想知道这是否会起作用。 
 
 如果这样做失败了，我的下一个计划是使用Linux的MAP_32BIT mmap标志分配数据，所以我只需要32位指针空间。 
 
 无锁数据结构中的ABA标签需要多少位？ 

One popular solution to the ABA problem in lock-free data structures is to tag pointers with an additional monotonically incrementing tag.
 
 struct aba {
      void *ptr;
      uint32_t tag;
 };
 
However, this approach has a problem. It is really slow and has huge cache problems. I can obtain a speed-up of twice as much if I ditch the tag field. But this is unsafe?
 
So my next attempt stuff for 64 bit platforms stuffs bits in the ptr field.
 
struct aba {
    uintptr __ptr;
};
uint32_t get_tag(struct aba aba) { return aba.__ptr >> 48U; }
 
But someone said to me that only 16 bits for the tag is unsafe. My new plan is to use pointer alignment to cache-lines to stuff more tag bits in but I want to know if that'll work.
 
If that fails to work my next plan is to use Linux's MAP_32BIT mmap flag to allocated data so I only need 32 bits of pointer space.
 
How many bits do I need for the ABA tag in lock-free data-structures?

原文：https://stackoverflow.com/questions/42514565