This post has moved to my new location, philosopherdeveloper.com:
http://philosopherdeveloper.com/posts/how-to-build-a-thread-safe-lock-free-resizable-array.html
- Comment
- Reblog
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
the philosopher developer 
Nice job ! dude, this is what I’m looking for ! Thanks
Hello there!
Thanks for a nice idea, I quite like it.
I would like to propose a few optimizations.
First,
index -= ((int)Math.Pow(2, arrayIndex) – 1);
can be replaced with:
index -= ((1 << arrayIndex) – 1);
Secondly,
GetArrayIndex(int count) can be implemented using this code:
x++;
//compute floor(log2(x)):
double x2 = (double)x;
int* ptr = (int*)(double*)&x2;
int d1 = ptr[1];
int log = (d1 >> 20) – 1023;
return log;
Or with this (I am not sure this is always faster than the series of if’s in Your code in GitHub):
x++;
//compute floor(log2(x)):
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
//count the number of set bits:
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x = unchecked((x * 0x01010101) >> 24);
return x – 1;
You can find more bit hacks here:
http://aggregate.org/MAGIC/
Thanks for the input, and sorry for the late reply! If you’re serious about these changes, feel free to submit a pull request on GitHub. I’ll take a look, and if your proposed changes have a positive impact on performance then I’ll merge them in (and you’ll be a contributor!).