Proust: A Design Space for Highly-Concurrent Transactional Data Structures

T Dickerson, P Gazzillo, M Herlihy, E Koskinen

Read the Paper! Download Source!

Download Proust!

The implementation will be available soon!


Here is a summary of the experimental results on some standard benchmarks. The graphs show the time to process 1,000,000 operations on concurrent hash maps using a 32-core Amazon EC2 m4.10xlarge instance as the number of threads increases. Each chart is the result for a particular fraction of writes and operations per transaction. For each chart, the x-axis is the number of threads from 0 to 32 and the y-axis is the average time in milliseconds from 0 to 250.

MapThroughputTest o2,u0.25

MapThroughputTest o2,u0.5

MapThroughputTest o2,u0.75

MapThroughputTest o2,u1.0

MapThroughputTest o16,u0.25

MapThroughputTest o16,u0.5

MapThroughputTest o16,u0.75

MapThroughputTest o16,u1.0

The performance of the Proust scales much better than the traditional STM implementation as contention increases (varying u). We are outperformed by the highly-engineered Transactional Predication (in green), but Predication doesn't appear to apply to anything other than set-based data-structures.


Read the Docs!