Ayende @ Rahien

James Newton-King commented on Caching, the funny way

Wed, 22 Jun 2011 11:27:37 GMT

There isn't just the cost of lock before adding, you also have to safe guard that a dictionary doesn't change while you're getting a value from it. But no I've never done any performance tests around it.

James Newton-King commented on Caching, the funny way

Wed, 22 Jun 2011 11:27:31 GMT

Luke commented on Caching, the funny way

Tue, 21 Jun 2011 13:50:57 GMT

Have you done any empirical tests showing that recreating the dictionary is actually faster than the straightforward lock-before-adding approach?

James Newton-King commented on Caching, the funny way

Sun, 19 Jun 2011 20:38:24 GMT

I use the same approach in Json.NET for caching reflection data. It has been in the wild for years and I've yet to have any problems with it.

Mike commented on Caching, the funny way

Fri, 17 Jun 2011 10:31:59 GMT

Earlier version of Rx for .net 3.5 contained backported System.Threading assembly. Last place I see them is here: http://code.google.com/p/rx-samples/source/browse/trunk/lib/Net35/?r=10 Also there are many nice LINQ in System.Interactive (also from .net 4)

Ayende Rahien commented on Caching, the funny way

Fri, 17 Jun 2011 08:31:10 GMT

Daniel, Very good point, yes. I haven't considered that, memory models usually make my head hurt.

Daniel Grunwald commented on Caching, the funny way

Thu, 16 Jun 2011 18:32:57 GMT

You are also making the assumption that the new dictionary will be initialized and in a valid state before it is published and visible to other threads. This is not guaranteed for non-volatile fields. The optimizer (or the CPU cache) might re-order the statements and assign the new dictionary to idPropertyChange before the Add() method is called, or even before the constructor has finished running! You need a volatile write to ensure that the dictionary contents are visible to other processors before the reference to the dictionary becomes visible. However, this is currently only a theoretical problem - the current .NET implementations implicitly treat all writes as volatile. But processors other than x86/x64 often have weaker memory models where volatile writes don't come for free, so I wouldn't rely on all future .NET implementations to keep this behavior.

Ayende Rahien commented on Caching, the funny way

Thu, 16 Jun 2011 15:15:33 GMT

Patrick, You are correct, expect that we are usually talking about a N < 20, so even with N^20, the cost is negligible.

Ayende Rahien commented on Caching, the funny way

Thu, 16 Jun 2011 15:14:56 GMT

Mike, That is the exact point of having lost writes. In a cache, this is perfectly fine to do.

Mike commented on Caching, the funny way

Thu, 16 Jun 2011 15:12:03 GMT

@tobi, . Wouldn't your "copy to local" idea just cause new bugs? What happens two threads both copy to local variables, then add their respective types then both save. Only one of the two types would be saved. . This is nice if they both happened to be the same type as you suggest, but not so useful if they are different types. Still, I suppose it is thread safe though.

Patrick Huizinga commented on Caching, the funny way

Thu, 16 Jun 2011 13:12:02 GMT

hmm, I guess I need to be more careful with < and > in messages. For similar reasons people will become violent when you have:

string s = "";
for (int i = 0; i < 13000; i++)
{
    s += (char) i;
}

You could argue that every iteration is just an O(N) operation, but that guy with the axe won't. ;-) btw, the code looked fine in the preview at the bottom, so I hereby file that bug :)

Patrick Huizinga commented on Caching, the funny way

Thu, 16 Jun 2011 12:41:17 GMT

Ayende, When you add 1 item you have O(N) where N is the amount of items you already have. However, if you want to add N items it will be an O(N^2) operation. For similar reasons people will become violent when you have:

string s = "";
for (int i = 0; i < 13000; i++)
{
    s += (char) i;
}

You could argue that every iteration is just an O(N) operation, but that guy with the axe won't. ;-)

Ayende Rahien commented on Caching, the funny way

Thu, 16 Jun 2011 11:40:22 GMT

Tobi, Nice catch, yes, it is there.

tobi commented on Caching, the funny way

Thu, 16 Jun 2011 11:33:26 GMT

I believe there is a threading bug. The dictionary initializer will call the add method which throws on duplicate keys. And that can happen because you are repeatedly accessing the field which can change. The type you try to add could have just been added. Fix: Copy the field to a local first.

Ayende Rahien commented on Caching, the funny way

Thu, 16 Jun 2011 09:42:31 GMT

Koen, Yes, this is an O(N) operation, basically, where N is the number of types. Then again, when you consider how many types there are, it isn't really meaningful. There are about 13,000 types in the .NET framework, for example. O(N) of that is meaningless, and it is VERY unlikely that you'll get to that level

Patrick Huizinga commented on Caching, the funny way

Thu, 16 Jun 2011 09:41:00 GMT

Meh, I guess I need to learn to type faster...

Patrick Huizinga commented on Caching, the funny way

Thu, 16 Jun 2011 09:38:57 GMT

To expand on what Konstantin said: You assume it doesn't matter if you lose a write to the cache. You assume it doesn't matter that you might 'generate' the identityProperty for the same type twice *and* not return the same value in those cases. (ConcurrentDictionary doesn't guarantee the generating a value only once, but does guarantee always returning the same value) Besides that you assume the cache will never grow too large. Because by copying the dictionary every time you generate a value, you have yourself an O(n^2) operation there.

Ayende Rahien commented on Caching, the funny way

Thu, 16 Jun 2011 09:37:44 GMT

Konstantin, Bing! Exactly, we might lose cached entries, but we don't care about that, since this is a cache, losing values is all right.

Koen commented on Caching, the funny way

Thu, 16 Jun 2011 09:33:25 GMT

Couldn't this become a rather heavy operation if you have a great amount of types. Everytime this is called on a new type, the cache "expands" and creating the new dictionary instance takes more "time" I would think... I also had the same thought as Konstantin, but indeed that's not critical for caching...

Konstantin commented on Caching, the funny way

Thu, 16 Jun 2011 09:22:03 GMT

This solution is OK for cache, but you could lose some entries, written to the cache, between new Dictionary being published and old dictionary being copied over...

Scooletz commented on Caching, the funny way

Thu, 16 Jun 2011 09:11:23 GMT

- trying getting value does not change the dictionary state (no dirty writes) - copying values to the new dict uses iterator (no dirty writes) - as you mentioned, idPropertyCache is replaced in atomic way (pointer) Summing up, not changing the read dictionary, replacing the read with a new one. That's the clue.