Courtesy of Craig ....
Lock Free Queues
And, if you scroll down to the end of the blog posting, the author has links for other lock-free data structures.
According to Craig, this is ideal for implementing the market-data pattern.
(The author of the blog, Julian Bucknall, is the CTO of DevExpress. This might become my new favorite component vendor. Their Xtra PivotGrid is a pretty nice grid for viewing OLAP cubes.)
©2008 Marc Adler - All Rights Reserved.
All opinions here are personal, and have no relation to my employer.
Subscribe to:
Post Comments (Atom)
4 comments:
devex is also my fav vendor. my last project we used the xtragrid. We also had another group that used the layout control and I started an effort to put their layout control over our binding framework as well. Excellent controls. Best grid on the marketplace IMO.
we had done an eval of xtragrid lately. it has an issue with pivot layout - the same ugly layout of pivot tables lifted from excel 2003. excel 2007 has much better layout manager for pivot reports than xtragrid.
so at the end we went with excel 2007.
Where can I find information onthe Market-Data pattern?
Actually I should have read through that code a bit more before pointing Marc at it. There are a few issues:
1) It declares head & tail adjacent to each other
This is a very bad design as both definitions will likely fall into the same L1/L2 cache segment causing the CPU cache coherency logic to thrash on multicore/multicpu systems.
2) The author dismisses array based structures without offering good reason.
Classic ring buffers are optimal for 99% of single writer single reader cases.
Its not too difficult (in C/C++ anyway) to design a resizeable lock free fifo implentation without locks, membars, or CAS/atomic operations.
The reason I originally pointed Marc at lock free queues was to avoid the classically bad pattern of stopping reading the market data stream while you update a the data structure associated with a market data symbol. Even if you have a lock per symbol it doesn't help as most feeds stream adjacent updates for the same symbol (think big order sweeping book) so it common for locks to be contended in this case.
The better pattern is to place lock free fifos/queues between the threads reading the feeds and the threads updating the symbols. That way no locks are required and you can be reading and updating simultaneously on multicore systems.
-c.
Post a Comment