https://github.com/DNedic/lockfree Skip to content Toggle navigation Sign up * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Case Studies + Customer Stories + Resources * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing [ ] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} DNedic / lockfree Public * Notifications * Fork 6 * Star 231 A collection of lock-free data structures written in standard C++11 License MIT license 231 stars 6 forks Star Notifications * Code * Issues 0 * Pull requests 0 * Discussions * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Discussions * Actions * Projects * Security * Insights DNedic/lockfree This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. main Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 1 branch 1 tag Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/D] Use Git or checkout with SVN using the web URL. [gh repo clone DNedic] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @DNedic DNedic Remove construction note on queue documentation but add inverse for r... ... ed7f837 May 10, 2023 Remove construction note on queue documentation but add inverse for r... ...ing buffer documentation ed7f837 Git stats * 7 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .github/workflows docs lockfree tests .clang-format .gitignore .pre-commit-config.yaml CHANGELOG.md CMakeLists.txt LICENSE README.md View code [ ] lockfree What are lock-free data structures? Why use lockfree What data structures are available? How to get Configuration FAQ Why would I use this over locking data structures on a hosted machine? Why use this over RTOS-provided IPC mechanisms on an embedded system? What advantages does the C++ version of the library bring? Give me more theory README.md lockfree CMake lockfree is a collection of lock-free single-producer/single-consumer data structures written in standard C++11 and suitable for all platforms - from deeply embedded to HPC. What are lock-free data structures? Lock-free data structures are data structures that are thread and interrupt safe without having to use mutual exclusion mechanisms. Lock-free data structures are most useful for inter process communication, but due to the efficiency of lockfree, it can safely be used for single threaded uses as well, making it good for general purpose use. Why use lockfree * Written in standard C++11, compatible with all platforms supporting it * All data structures are thread and multicore safe in single producer single consumer scenarios * No dynamic allocation * Optimized for high performance * MIT Licensed * Additional APIs for newer C++ versions What data structures are available? At the moment the following data structures are available: * Queue - Best for single element operations, extremely fast, simple API consisting of only 2 methods. * Ring Buffer - A more general data structure with the ability to handle multiple elements at a time, uses standard library copies making it very fast for bulk operations. * Bipartite Buffer - A variation of the ring buffer with the ability to always provide linear space in the buffer, enables in-buffer processing. All of these are available as separate libraries and ring buffer and bipartite buffer also have C library variants. How to get There are three main ways to get the library: * Using CMake FetchContent() * As a git submodule * By downloading a release from GitHub Configuration For cache coherent systems the False Sharing phenomenom can reduce performance to some extent which is why passing LOCKFREE_CACHE_COHERENT as true is advisable. This aligns the indexes to LOCKFREE_CACHELINE_LENGTH, 64 by default. On embedded systems, LOCKFREE_CACHE_COHERENT should almost always be left as false. Some systems have a non-typical cacheline length (for instance the apple M1/M2 CPUs have a cacheline length of 128 bytes), and LOCKFREE_CACHELINE_LENGTH should be set accordingly in those cases. FAQ Why would I use this over locking data structures on a hosted machine? The biggest reason you would want to use a lockfree data structure in such a scenario would be performance. Locking has a non-neglegible runtime cost on hosted systems as every lock requires a syscall. Additional benefits would be performance from cache locality as lockfree data structures are array-based or code portability to non-POSIX environments. Why use this over RTOS-provided IPC mechanisms on an embedded system? While locking usually isn't expensive on embedded systems such as microcontrollers, there is a wide variety of RTOS-es and no standardized API for locking. The fact that multiple architectures are present from 8051 to RISC-V means that architecture-specific locking methods are not standardized either. lockfree provides a way to build portable embedded code with a neglegible performance cost as opposed to locking, code using lockfree can be compiled to run on any embedded platform supporting C++11. Additionally, the code can easily be tested on a host machine without the need for mocking. What advantages does the C++ version of the library bring? * Type safety, as data structures are type and size templated * Much simpler and less error-prone instantiation * Higher performance due to compile-time known size and header-only implementation * Encapsulation, the data buffer is a class member instead of being passed by a pointer Give me more theory All structures in lockfree are bounded, array-based, lockfree and waitfree for single consumer single producer scenarios. For more insight into lock-free programming, take a look at this brilliant talk series from Herb Sutter. About A collection of lock-free data structures written in standard C++11 Topics library cmake embedded queue cpp buffer cpp11 embedded-systems ring-buffer lock-free inter-process-communication circular-buffer fifo dma circular-queue bipartite lock-free-queue Resources Readme License MIT license Stars 231 stars Watchers 6 watching Forks 6 forks Report repository Releases 1 1.0.0 Latest May 10, 2023 Packages 0 No packages published Languages * C++ 97.8% * CMake 2.2% Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.