4 ms·
I have some thoughts: - Doing better than atomic inc/dec for those reference counts is going to be hard. All of those techniques are still in an "unconfirmed m
by pizlonator 10y ago
I have some thoughts:
- Doing better than atomic inc/dec for those reference counts is going to be hard. All of those techniques are still in an "unconfirmed myth" state AFAICT: someone published a paper but nobody has confirmed that the result holds on a broader set of machines, workloads, baselines, etc.
- Great call on userspace locking. Note that you can do this portably. You don't need special OS support. See https://webkit.org/blog/6161/locking-in-webkit/ https://webkit.org/blog/6161/locking-in-webkit/
- Seems like lots of the locking use cases can indeed be made lock-free if you are willing to roll up your sleeves and get dirty. That's what I would do.
- I still bet that the dominant cost is lock contention and he is not analyzing his data correctly. He appears to claim that it can't be locks because the total CPU time is greater than the total length of critical sections and that some analysis tools tell him that there is massive cache trashing. But that's exactly what happens if you contend on locks too often. Lock contention causes context switches and thread migrations. Both of those things require cache flushes. So the code that runs under contention will report massive cache thrashing because it will have a high probability of being on a cold cache. Programs indeed will run slower under contention than without it, and while his slow-down is extreme, I've seen worse and fixed it by removing some contention. He should find every contended lock and kill it with fire.
- The dip at 4 cores doesn't surprise me. Computers are strange and most "scalability" charts (X axis is CPUs, Y axis is some measure of perf) I've made had weirdly reproducible dips and jerks.
- denfromufa 10y agoI asked about lock-free data structures from 2 major open-source libs, but Larry found major issues with them. He may consider some of these data structures in the future. I opened a bounty for this. See closed github issues for gilectomy.
- pizlonator 10y agoNot lock-free data structures. That's usually a fool's errand. You need lock-free hacks. Exhibit #1: the lock to protect lazy initialization. That just needs a CAS on the slow path and a load-load fence on the fast path. Delete the object you created if you lose the race and try again. Exhibit #2: you can probably do dirty things to make loading from dicts/lists not require locks even though storing to them does.
- denfromufa 10y agoHow maintainable are these hacks in the long run? Is there firm theoretical basis, if yes, then sources?
- pizlonator 10y agoThe lazy initialization example is a classic algorithm. Usually concurrency hackers rediscover it from first principles. It's easy to maintain because the concurrency protocol it uses is easy to understand. Here's how I'd write it: template<typename T, typename... Args> void constructSingleton(Atomic<T*>& singletonRef, Args&&... args) { for (;;) { T* oldValue = singletonRef.load(); if (oldValue) return oldValue; T* newValue = new T(std::forward<Args>(args)...); if (singletonRef.compareExchangeWeak(nullptr, newValue)) return newValue; delete newValue; } } This works so long as the singletons are happy to be deleted. I'm assuming that's true here.
- denfromufa 10y agoI think this is C++11, while CPython is using C89 and may update to use some C99 features supported by major compilers (GCC, Clang, MSVC).
- pizlonator 10y agoThen write it in C89. It's not hard. My first lock-free algo was in C89.