Evaluating Overhead and Contention in Concurrent Accesses to a Graph

The current spread of multicore processors reinforces the need for strategies to implement mutithreaded programs. Since using synchronization methods to coordinate the access to shared data introduces contention, finding new strategies to implement concurrent data structures can lead to performance gains. This paper introduces a case study in which a graph data structure is implemented using low contention strategies: one based on low level atomic operations, one based on mutexes and another using transactional memory. Results show that the first presents better performance, the second the worst performance and the later a higher level of abstraction for programmers with a similar performance to the first.