4 ms·

I 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

I 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 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 ago
  How maintainable are these hacks in the long run? Is there firm theoretical basis, if yes, then sources?
  - pizlonator 10y ago
    The 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 ago
      I 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 ago
        Then write it in C89. It's not hard. My first lock-free algo was in C89.

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 ago
How maintainable are these hacks in the long run? Is there firm theoretical basis, if yes, then sources?
- pizlonator 10y ago
  The 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 ago
    I 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 ago
      Then write it in C89. It's not hard. My first lock-free algo was in C89.