[concurrency-interest] MapDB 2.0 as fast as ConcurrentSkiplListMap

Jan Kotek discus at kotek.net
Thu Sep 25 15:00:07 EDT 2014


Hi,

I would like to share some news about MapDB, it is library which
provides alternative java collections [1]

I started work on new version. It removes a few bottlenecks and in
result BTreeMap[2] now (almost) outperforms ConcurrentSkipListMap. 

Here is a benchmark [3] with 32 byte strings keys, 10 million records
and random get/set operations:

  ConcurrentSkipListMap
    get @ 254,107 per second
    set @ 236,540 per second 

  BTreeMap from MapDB 2.0
    get @ 335,648 per second
    set @ 198,475 per second

  HTreeMap from MapDB 2.0
    get @ 526,645 per second
    set @ 225,270 per second

I used smaller set to avoid GC overhead. With 100M+ entries result
would be very different since BTreeMap is not limited by GC. 

This is single thread test. BTreeMap with concurrent updates scales
linearly up-to 6 threads (cores), than it degrades. Improved memory
allocator should push it to around 16 cores. 

There are no dirty tricks here, current version does not even use
Unsafe. This project is 14 years old, and it has several improvements
to minimize overhead and save memory.

For example BTreeMap uses plug-able specialized keys. Keys in BTree
Node can be represented as long[], or strings can be
represented as class{ int stringOffsets; byte[] stringData }

I have lot of plans for MapDB 2.0. For example I would like to
implement parallel streams to execute operations concurrently.

I could use some help from skilled veterans on this mailing list. My
stress tests sometimes find rare race conditions. But formal
verification of most of concurrent code is beyond my skills. I am
slowly improving, but it takes a lot of time. 

All best,

Jan Kotek
MapDB author

[1]
http://www.mapdb.org/
https://github.com/jankotek/mapdb/

[2]
https://github.com/jankotek/MapDB/blob/master/src/main/java/org/mapdb/BTreeMap.java

[3] 
https://github.com/jankotek/mapdb-benchmarks


More information about the Concurrency-interest mailing list