Preserving Iterators on Fast, Lockless, Caches – Use the Trash
This was actually the most fun part of my day. I was worried about how to allow the quick cache's clients to run iterators over the cache data and not get nailed when the data in the cache is updated by the exchange feed. In general, it's hard to imagine. You have a cache that by design doesn't lock or notify anyone, and a reader that also by design is going to be slower than the ticker feed and will, very likely, always be looking at the entire cache and getting into a lot of trouble with it's iterators.
I was trying to think of a clever solution to the problem when I had another really nice eureka! moment: What I'd have is a temporary "trash can", and when the client asks to keep things "stable", the cache tosses the old values into the "trash". When the client is done, it'll "throw the trash away", and the cost of the deletes will be on the client's thread.
If I built it with a simple STL __gnu_cxx::slist, then I'd have a very fast queue. I don't need to have any specific order, just a place to hold these guys until they are no longer needed. So rather than calling delete on the 'old' message, the put() method on the cache will instead do a push_front() to the 'trash' queue. It's fast, clean, and should work wonderfully.
I have two methods that control an atomic boolean. It's a little utility class I wrote that wraps an atomic uint8_t as a simple boolean so it can be toggled/set/read atomically:
void QuickCache::saveToTrash() { if (!(bool)mUsingTrash) { // first, clean out anything that might be lingering in the trash Message *m = NULL; while (!mTrash.empty()) { if ((m = mTrash.front()) != NULL) { delete m; } mTrash.pop_front(); } // now set the flag that indicates that the trash is ready to use mUsingTrash = true; } } void QuickCache::takeOutTrash() { if ((bool)mUsingTrash) { // first, set the flag that indicates that the trash is NOT in use mUsingTrash = false; // next, clean out anything that might be lingering in the trash now Message *m = NULL; while (!mTrash.empty()) { if ((m = mTrash.front()) != NULL) { delete m; } mTrash.pop_front(); } } }
And then in my put() method, when I'd normally have deleted the 'old' message from the cache, I simply:
// the new one is in the cache - let's dispose of the old one if (oldMsg != NULL) { if ((bool)mUsingTrash) { mTrash.push_front(oldMsg); } else { delete oldMsg; } oldMsg = NULL; }
I haven't had a real chance to test it, but I'm hoping that tomorrow morning when I get ticks from the exchanges, I'll be able to see that this is going to work. If not, then it's back to the drawing board and figure something else out.