Brief Announcement: MultiLane - A Concurrent Blocking Multiset

摘要

We introduce an extremely simple transformation that allows composition of a more scalable concurrent blocking multiset, or bag, from multiple "lanes" of a potentially less scalable underlying multiset. Our design disperses accesses over the various lanes, reducing contention and memory coherence hot spots. Implemented in Java, for instance, we construct a multiset from multiple lanes of java.util.concurrent.SynchrvnousQueue [9] that yields more than 8 times the aggregate throughput of a single instance of SynchronousQueue when run on a 64-way Sun Niagara-2 system with 16 producer threads and 16 consumer threads. We experimented with various queues from java.util.conconcurrent and found that in general a MultiLane form will outperform its underlying counterpart.