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.