diTii.com | D' Technology Weblog

The second part of this series covers Data Structures and Locks. I will provide general guidance on which data structures to use under certain circumstances and how to use locks without having a negative impact on performance.  Finally, there will be examples covering common problems/solutions and a simple cookbook detailing functional requirements and recommendations when using data structures and locks.

In order to avoid cache line thrashing and a high rate of lock collisions, the following are suggested guidelines when designing an application:

· Minimize the need for a large number of locks by partitioning data amongst threads or processors.
· Be aware of the hardware cache-line size because accessing different data items that fall on the same cache-line is considered a collision by the hardware.
· Use the minimum mechanism necessary in data structures.  For example, don’t use a doubly-linked list to implement a queue unless it is necessary to remove from the middle or scan both ways.
· Don’t use a FIFO queue for a free list.
· Use lock-free techniques when possible.  For example, claim buffer space with InterlockedAdd and use an S-List for free lists or producer/consumer queues.

Full Article