How to build a thread-safe lock-free resizable “array”

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

About these ads

3 thoughts on “How to build a thread-safe lock-free resizable “array”

  1. Khoa Nguyen says:

    Nice job ! dude, this is what I’m looking for ! Thanks

  2. 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/

    • Daniel says:

      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!).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: