4 ms·
Not 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
by pizlonator 10y ago
Not 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.