A Lock-Free Atomic Shared Pointer in Modern Cpp - Timur Doumler - CppCon 2022

cppcon.org/
---
A Lock-Free Atomic Shared Pointer in Modern Cpp - Timur Doumler - CppCon 2022
github.com/CppCon/CppCon2022
std::shared_ptr is a standard smart pointer utility widely used in modern C++. A commonly overlooked property of std::shared_ptr is that while its control block is thread-safe, the shared_ptr itself isn't. To fix this, C++20 introduced std::atomic＜std::shared_ptr＞. However, existing implementations are typically not lock-free, rendering std::atomic＜std::shared_ptr＞ useless for low-latency and real-time applications.
What would it take to implement a lock-free atomic shared_ptr? In this talk, we first discuss the motivation and use case, review how std::shared_ptr works and the history of std::atomic＜std::shared_ptr＞. We then look at existing implementations and different implementation strategies. Finally, we present a new implementation of a lock-free atomic shared_ptr which is portable to multiple platforms.
---
Timur Doumler
Timur Doumler is the Developer Advocate for C++ tools at JetBrains and an active member of the ISO C++ standard committee. As a developer, he worked many years in the audio and music technology industry and co-founded the music tech startup Cradle. Timur is passionate about building inclusive communities, clean code, good tools, low latency, and the evolution of the C++ language.
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
KZbin Channel Managed by Digital Medium Ltd events.digital-medium.co.uk
#cppcon #programming #cpp

[@BalanNarcis]

Great talk! Is is just me or "because ABI" is more and more used in CppCon talks 🤔

[@Omnifarious0]

I agree. Break the ABI already. I'm sorry, just deal with it.

[@diablodale]

MSVC is hardcore about not breaking ABI. I and a few others tried to get them to fix std::exception::what(). Their impl doesn't align with the standards `noexcept`. Their answer...no...not until we batch many features and finally break ABI.

[@tetraquark2402]

Lots of hoops to jump through to do this could be avoided if only the manufacturers added more useful atomic instructions we could take advantage of.

[@timurdoumler4813]

Please note that this is a shortened, 60 minute version of the original 90 minute talk I gave at C++Now. I recommend to watch the full 90 minute C++Now version: kzbin.info/www/bejne/m3TKpmuPg7GMg6c

[@denis_iii]

Добрый день, вы можете использовать clang для компиляции lib на всех платформах, он позволяет внедрять ассемблерные вставки в методы с++. Я часто это делаю при компиляции в dll в msvc. С уважением.

[@RandomScreenName]

It seems the solution to some of this is just to pre-allocate a small but manageable amount of memory so you don't have to store 64-bit pointers, which solves the problem entirely if you don't need millions and millions of atomic shared_ptr's to millions of unique objects and aliases. Just have a pool of N addresses as a static member of your atomic shared_ptr class which all can see, put the pointer addresses you're using in there, and instead of storing the entire 64-bit pointer into the atomic_shared ptr, store the index into the pool which has your pointer address. There are several ways you can synchronize this process which are lock-free: for instance, you could have your pool as an array, and a simple lock-free stack with all numbers in it from 0 to N representing availability. When you create a shared pointer, instead of storing the pointer directly, pop_front from the stack to get the next available index to store the pointer, put the pointer address there and then store the index in the atomic shared_ptr. When the refcount is zero, after deallocating, set the value in the pool back to 0 and put the index back at the front of the stack. If you set N=2^20 you'd have the ability to manage ~1M unique addresses/aliases with shared pointers and the entire thing would take 12.5MB globally. You then have plenty of leeway to do just about anything in an 8-byte atomic: 20 bits for the cb_ptr_index, 20 bits for the alias_ptr_index, 16 bits for the refcount and 8 bits left over.

[@jameswu7850]

RISC-V ISA to date does not have a DWCAS and has no plan to include it. It would be strange to rely on it in the language's standard library.

[@bigboysteen7638]

how? the compiler knows what processor it's compiling for, it could default to a mutex implementation for platforms that don't support it, that's sound

[@TheNovakon]

You still need to cycle when there is race access to the pointer. So how less effective is to use spin-lock to protect the pointer.

[@nexus7c0]

Exactly, this is just a clever way to put a spinlock into the shared pointer object.

[@blacklion79]

Double CAS is possible with hardware transaction memory which is available on modern Intel CPUs

[@ProfessorWaltherKotz]

Jesus that code from Anthony Williams looks impressive.

[@benjaminshinar9509]

@CppCon where are the slides for this talk?

[@samanthaqiu3416]

this presentation is missing from the github repo

[@kingduckVI]

Is it just me or does that find(T t) method at 6:10 not do what it's supposed to at all...

[@PedroOliveira-sl6nw]

Thought the same. It was weird, right? It returned the pointer after head (next) - actually the reference construction of that pointer but still - didn't see the "finding".

[@samanthaqiu3416]

he gave this same talk at ACCU conference back in August, some atendee pointed this exact mistake (find parameter not being used) he said huh thanks I will fix it... but he didn't

[@fob3476]

Probably replace 'p=p->next;' with: while (p && p->t != t) p=p->next;

[@Roibarkan]

I believe the missing code is “while(p && p->t != t)” between the first at second statements of find()

[@Cons-Cat]

​@@samanthaqiu3416 Relatable.

[@sheeftz]

11:15 What?! How in the world can you compare "reading int" with a ref counter increment, which is Read-Modify-Write? This comparsion not explains, but confuses even more. Ok, I've found him explaining this exact moment in another video: kzbin.info/www/bejne/m3TKpmuPg7GMg6csi=AiRySq4lLfaTvRvH&t=380