A boy can dream…

This post has moved to my new location, philosopherdeveloper.com:

http://philosopherdeveloper.com/posts/boy-can-dream.html

About these ads

10 thoughts on “A boy can dream…

  1. Alan Ning says:

    Nice idea.

    I read the code, and it looks like Count() has a spinwait, and won’t return until Add() operation completes (fuzzy = index).

    Maybe I am wrong, but doesn’t that hurt concurrency? It looks like a implicit spinlock.

    Thanks and good effort.

    … Alan

    • Daniel says:

      Alan, that’s a good question. Whether it “hurts” concurrency depends, I guess, on what your use case for this class is. My view was that it doesn’t hurt the use case I had in mind: Add operations would be unencumbered by any thread contention from one another or from reader threads; meanwhile, readers would not interfere with one another either. In fact, spinning while waiting for pending calls to Add to complete does not really represent any problem to concurrency at all (to performance, yes, but not arising from any contention between threads). I hope that makes sense!

      That said, there is actually a bug in my implementation of Count anyway. So, I plan to fix that. (By any chance, can you see what it is?)

      • Alan Ning says:

        Hmm… here’s my thought, which could be wrong as I don’t have much C# experience.

        It looks like there is a race condition between the following two lines.

        1. int count = m_index;

        2. if (count > m_fuzzyCount)

        So say 100 items have been added since the first line but before the second line, m0fuzzyCount can be far greater than m_index. Since you return m_index, the actual Count is smaller than it should be.

        Then again, the post condition of Count is unclear to me. This could be acceptable depending on your contract.

        … Alan

      • Alan Ning says:

        Hmm… here’s my thought, which could be wrong as I lack of experience in C#.

        It looks like there is a race condition between the following two lines.

        int count = m_index;

        if (count > m_fuzzyCount)

        So in the case 100 items have been added since the first line but before the second line, m0fuzzyCount can be far greater than m_index. Since you return m_index, the actual Count is smaller than it should be.

        Then again, the post condition of Count is unclear to me. This could be acceptable depending on your contract.

        … Alan

  2. damageboy says:

    The main benefit/performance boost is (I think) is for a specific scenario:
    multiple reader threads with a single writer/appender thread.

    That is where you should expect to see a performance boost as the plain dumb “use lock()” solution would still lock for every read/indexer operation while the concurrent list DOES NOT.

    You can’t and shouldn’t see a performance boost for the Add() operation. I don’t think it was ever the intention…

    • Daniel says:

      So, if you get a chance to take a look at my most recent post, you’ll see that I actually question whether this use case is a worthwhile one. In fact, if we restrict write operations to only Add and the indexed setter (and synchronize these via a lock statement), I don’t think readers need to be synchronized at all. Read the post, take a look at my SynchronizedList<T> class here, and let me know your thoughts.

  3. damageboy says:

    I’m performing some surgery to your implementation.
    Nothing too big, just a few perf. hacks to squeeze some more cycles out it.
    Since you didn’t put it on githun as a separate project, I won’t branch the whole thing, but I will post my version of your code on github as a separate repo. You can contact me if want to discuss this in a more fluent manner. I’m “damageboy” on skype too.

    • Daniel says:

      I would like to discuss this on Skype! My name is “danielltao”; I’ve actually added you already, so let’s chat some time when we’re both on.

  4. damageboy says:

    BTW, I will change your Count getter implementation
    to be non-spinning.

    Since Count is more often used by readers I want it to run as unhindered as possible.

    To keep it still correct I will change the Add() implementation to use CompareAndExchange() on _lazyCount instead of incrementing it, so that when there is more than one writer/appender to the ConcurrentList, the writers will compete BETWEEN themselves, without hindring readers.

    • Daniel says:

      Bad news: I’m relatively certain my Count implementation was actually broken anyway (though in a very subtle way which, clearly, was not even picked up by my unit tests).

      I am going to take a look at your GitHub repo soon and share my thoughts with you as well.

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: