search

benjamin-bader / cppmetrics

A zero-dependency c++14 port of Dropwizard Metrics.
Apache License 2.0
7 stars 2 forks source link

Find alternative to std::map in ExponentiallyDecayingReservoir #7

Open benjamin-bader opened 5 years ago

benjamin-bader commented 5 years ago

Java uses a ConcurrentSkipListMap, whose salient characteristics are: 1) It's threadsafe in that multiple threads can update it without significant contention 2) It is ordered - we can efficiently iterate keys in order, and find the lowest/highest key.

The STL doesn't have anything remotely like this, so we've fallen back on mutual exclusion - much to the detriment of performance of histograms and timers.

benjamin-bader commented 5 years ago

Seems like the state-of-the-art in C++ OSS concurrent ordered maps is nascent. I've found a promising thesis that appears to be reasonably-implementable: http://www.utdallas.edu/~arunmoezhi/thesis.pdf

I'll have to read it more closely to verify that the algos described therein don't have some kind of fatal drawback (e.g. no memory reclamation).

benjamin-bader commented 5 years ago

Well, turns out - that paper describes its algorithm "without memory reclamation, which can be implemented with the well-known technique of hazard pointers". Har har. Like Okasaki's functional red-black tree algorithms, deletion is left as an exercise for the reader.

benjamin-bader commented 2 years ago

Found a nice hazard pointer implementation in Facebook's Folly library. Too bad it's such a huge dependency.