quadratic behavior in SyncTab::GetAndLock

[GoogleCodeExporter]

% cat atomic_stress.cc 
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
  int n = argc == 1 ? 100 : atoi(argv[1]);
  int n_iter = 10000;
  int *a = new int [n];
  printf("n: %5d:  ", n);
  for (int i = 0; i < n_iter; i++) {
    for (int j = 0; j < n; j++) {
      __sync_lock_test_and_set(a + j, 0);
    }
  }
  return 0;
}
% clang -pie -fPIE -fsanitize=thread -O atomic_stress.cc
% for((i=128; i<=1024*1024; i*=2)); do (TIMEFORMAT=%R;  time ./a.out $i) ; done
n:   128:  0.328
n:   256:  0.690
n:   512:  4.380
n:  1024:  19.285
n:  2048:  87.791

Profile: 
    87.93%    a.out  a.out              [.] __tsan::SyncTab::GetAndLock(__tsan::ThreadState*, unsigned long, unsigned long, bool, bool)
     2.59%    a.out  a.out              [.] __tsan_atomic32_exchange
     1.31%    a.out  a.out              [.] __tsan::Mutex::Unlock()

The code: 
  if (PrimaryAllocator::PointerIsMine((void*)addr)) {
    MBlock *b = user_mblock(thr, (void*)addr);
    CHECK_NE(b, 0);
    MBlock::ScopedLock l(b);
    SyncVar *res = 0;
    int iter = 0;
    for (res = b->ListHead(); res; res = res->next) {
      iter++;
      if (res->addr == addr)
        break;
    }

Obviously, if a given heap-allocated block has N objects accessed atomically, 
we will spend O(N) time handling each of them. 
This was previously known, but one of our users has hit it in a real test.

We may need a more efficient data structure here :( 

Original issue reported on code.google.com by konstant...@gmail.com on 22 Aug 2013 at 9:45

[GoogleCodeExporter]

Fixed by r209810.

Now numbers look like:
n:   128:  0.172
n:   256:  0.284
n:   512:  0.469
n:  1024:  0.852
n:  2048:  1.679
n:  4096:  3.298
n:  8192:  6.618
n: 16384:  13.252

Original comment by dvyu...@google.com on 29 May 2014 at 1:59

• Changed state: Fixed