The reason I've rejected [RCU] for the iterator problem is that it isn't individual values changing that is the big danger; it is the state of the entire structure changing -- ie. resizes. In order to use RCU, the iterator would have to take a complete copy of the hash

Well, I'd see the RCU route as you continue to iterate over the old copy of the hash, ignoring updates that are being done in the new, resized copy of the hash. So the RCU iterator doesn't take a copy of the hash, it just references a copy of the hash. That is, iterators started before the resize are all iterating over the same (old) copy of the hash while iterators started after the resize are all iterating over the same (new) copy of the hash. The iterator could even recheck against the current copy of the hash even though it is still iterating through an old copy (so it wouldn't use stale values nor deleted keys but would not see new keys).

The major benefit to the approach described in the video is that a huge hash can be resized while other updates continue to happen. But both approaches involve full copies of the hash existing at the same time (but not a full copy per iterator; I'd not do that with either approach).

Not that I'm trying to argue that you should use RCU, just pushing back lightly on one reason you stated for avoiding it. There are plenty of advantages.

__int64 _InterlockedCompareExchange64(__int64 volatile *,__int64,__int
+64)
[download]

Although I think that you are probably aware of this, the risk with this is that updates happen so frequently that you have to retry your CAS over and over, even an unbounded number of times (at least in theory). I've run into a lot examples of people jumping through hoops to avoid such a problem. I have yet to stumble upon somebody presenting good evidence that this actually became a practical problem when doing something on the order of a simple increment.

So I still consider several possible explanations for such hoop jumping as plausible:

• I just haven't seen the evidence and CAS for incrementing a shared count can fairly easily become overly expensive.
• People are jumping through these hoops to avoid scaling problems with "obtain lock then increment" and they didn't try CAS on a single counter.
• People see real problems with too many retries via CAS for operations much more expensive than a simple increment and so avoid CAS on a single shared count due to those other scenarios, even though it hasn't been proved to lead to practical problems for a simple increment.
• People are jumping through these hoops as premature optimization simply out of fear that the number of retries could become problematically large.
• (Added soon after posting) Details of cache coherency between cores (or similar) is the real problem with frequent updates to a single shared count.

So I call out the risk because I see so many examples of people trying to avoid that risk, not because I'm convinced that it can be a real problem or that it is likely to be a real problem. If I had to predict whether it would be a practical problem, I'd predict that it would be very unlikely to be very significant. But I've managed to avoid needing such an approach so I wouldn't bet much money.

short _InterlockedIncrement16(short volatile *Addend)
[download]

This risk I've heard of with this is that, at least on some architectures, an interlocked increment is accomplished via a bus lock and the bus lock can have (I've heard it claimed) a bigger negative impact on concurrency than a write lock would (at least if you are using this on a lot of shared counts where contention for any single lock would be low while the frequency of bus locks would be high). The times I've used such, I haven't observed a significant drop in concurrency, but that doesn't mean such can't happen, of course.

Thanks for sharing your question, references, and plans. It has been quite interesting.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.