6 ms·

Piggybacking this question for people interested in the topic: Which everyday high level data structures you use are built on lock-free implementations? Cloju

Piggybacking this question for people interested in the topic: Which everyday high level data structures you use are built on lock-free implementations? Clojure's maps/vectors (which are persistent data structures) come to mind for me, for one.

forrestthewoods 6y ago
Almost zero. Queues or streams may have lockless properties. Or maybe not! For the most part concurrent, mutable access to a shared data structure is undesirable and to be avoided. If you find yourself wanting a lockless hashmap you’re going down the wrong path 99.9% of the time. There are always exceptions. But you better have a REALLY good reason why.
jeffreygoesto 6y ago
https://github.com/eclipse/iceoryx https://github.com/eclipse/iceoryx
bitcharmer 6y ago
SPSC (single producer single consumer) queues and ring buffers are used quite extensively in low-latency software engineering.
- jamesmunns 6y ago
  Yup! In Rust specifically, I've written bbqueue, which is a bipbuffer-inspired lock-free ring buffer, intended for embedded systems and DMA usage. https://github.com/jamesmunns/bbqueue https://github.com/jamesmunns/bbqueue It uses atomics (and Rust's borrow checker) heavily to safely guarantee lock free behavior, and works pretty darn quick.
  - caspper69 6y ago
    You reference a blog post on your Github (regarding the algo description). I believe the author of that blog (someone at Ferrous Systems) has a pretty significant misunderstanding of DMA and serial ports, which raises a whole host of other questions on down the chain <additional unnecessary comment removed>. edit: I know it's not cool to complain about downvotes, but this is a legitimate concern to raise for this poster. I am not attempting to denigrate anyone here.
    - twic 6y ago
      I assume you mean this blog post: https://ferrous-systems.com/blog/lock-free-ring-buffer/ https://ferrous-systems.com/blog/lock-free-ring-buffer/ Could you explain what you think the misunderstanding is, and what the consequences of that misunderstanding are?
      - deleted 6y ago
        [deleted]
      - caspper69 6y ago
        edit3: resolved below.
        jamesmunns 6y ago
        The comparison that I was aiming to make was comparing a "busy wait blocking" implementation, e.g. sending one byte at a time, until the byte has been sent, which is typical for bare metal embedded systems (that don't use some kind of DMA or concurrency like threads or tasks). In this case, your CPU would be left spinning for an equivalent amount of time to the line rate of the serial port, if you were busy waiting for data.
        jamesmunns 6y ago
        As a note, you can click on the time stamp of the child post, and respond directly there. > since I can't reply to the child I'll just say this: I don't like the math you used, I feel like it's making a point that shouldn't be made in a place where it doesn't need to be made. Of course it's going to be dog slow if you're busy waiting. Wtf? I guess I will just leave it at that. The entire post is about reducing the CPU time necessary to receive data from an external interface, like a serial port. The following paragraph states: > Instead of making our CPU waste all of this time waiting around, we allow the hardware to manage the simple sending and receiving process, allowing our CPU to either process other important tasks, or go into sleep mode, saving power or battery life. The intent for this example was to illustrate the difference between busy waiting and DMA. It is not uncommon on microcontrollers to only have a FIFO depth of one byte, which means if you aren't using interrupts, DMA, or threading, you will lose that data.
kvdr 6y ago
This is more about the way of doing lockless data operations than specific data structures - look up the RCU pattern, there are good CPP talks by Fedor Pikus on it.
franzwong 6y ago
log4j2 AsyncLogger uses RingBuffer (Disruptor) which is lock-free https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Articles https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Ar...
zaarn 6y ago
I've written some memory allocators that use lock-free allocation maps. In this case, a 4kb granularity allocator that used compressed free-bitmaps for usage in both userspace and kernelspace. The entire thing was lock-free, so allocations would never stall on a lock, even if the allocator had to decompress a bitmap (the way compression worked was by looking for free memory ranges and then replacing them by a range expression, which saved a few MB of memory per Gigabyte of memory available, as well as ordering largely free memory blocks to the start of the bitmap list to reduce seek time). Despite the complexity in the allocator, it could serve any number of threads without ever locking up. The worst case was a long latency if a thread had to scan the entire free list for a free block (It would switch to a different allocation behaviour if a thread had more than a dozen failed allocation attempts). A bunch of ring buffers I've worked with are atomic (ie, lock free), probably the most common application of lock-free stuff.
- jamesmunns 6y ago
  Interesting! Is this work public somewhere perhaps? I'm currently working on a similar technique (though with smaller blocks, currently ranging 64-1024 bytes - basically any 5 power-of-twos) for a lock-free allocator intended for real time embedded systems. I use a 32-bit word for each 1024 byte "page", and have a tree structure inside of the word (it takes 31 bits to cover 5 power-of-two ranges). My code (which only allocs and never frees at the moment) is here: https://github.com/jamesmunns/bitpool/ https://github.com/jamesmunns/bitpool/
  - zaarn 6y ago
    Only a much older version which sadly does not feature compressed bitmaps or reordering of the bitmaps, plus having one or two bugs rather critical bugs. It's part of my toy project kernel. Largely written in Rust with a few unsafe behaviours since it's intended to be able to bootstrap given only a pointer and size of a heap memory block using only 8 kilobytes of stack, as well as being able to add or remove memory to the entire list. There is only one section that behaves like a lock, which handles the free range decompression. It has to be somewhat exclusive in behaviour since it must be able to decompress the block without allocating memory, instead it simply uses the decompressed lock to allocate the memory necessary to accomodate for overhang memory in the range (ie, if a range is larger than a block). It simply means that during this time, the available memory shrinks by the amount represented by the range. IIRC it's about 128 bytes of metadata, the rest is bits in the bitmaps to handle page allocation. Each block can in theory handle about 124 MiB, though I do have some logic so that sections can be split into multiple blocks to reduce contention as well as handling large pages (which largely reside in a single block as even 16MB pages enable managing Terabytes of memory). Allocation is simply a CAS on the byte containing the free bit for the specific page (Base Address + 4KiB * Bit Index) then doing an atomic increment on the free page counter. Deallocation is the reverse. Failed CAS attempts mean it continues to the next free bit atleast on the next byte (= (Bit Index >> 3 + 1) << 3). The happy allocation path is fewer than a hundred instructions, the unhappy path is about a thousand instructions. CAS latency can be quite unpredictable though, so probably not suitable for realtime systems.
pats0 6y ago
I used Michael & Scott lock-free queue and bounded SPMC & MPMC queues in my fibers library. Queues with locks were faster though. I've also written some QSBR to reclaim sockets registered in epoll/kqueue without a need to wrap concurrent epoll/kqueue calls in a lock.
sgtnoodle 6y ago
A good rule to follow in software engineering in general is "never write your own lock free data structures". I'm the one writing them so that my coworkers don't need to, though. I've used atomics to implement various flavors of queues in low level C for use on microcontrollers. A good single-producer single-consumer queue abstraction is helpful for communicating with interrupt service routines in peripheral drivers. Bespoke multiple-producer single or multiple-consumer queues are often useful for implementing logging abstractions that work from any context, including in interrupt handlers and critical sections.

forrestthewoods 6y ago

Almost zero. Queues or streams may have lockless properties. Or maybe not! For the most part concurrent, mutable access to a shared data structure is undesirable and to be avoided. If you find yourself wanting a lockless hashmap you’re going down the wrong path 99.9% of the time. There are always exceptions. But you better have a REALLY good reason why.

jeffreygoesto 6y ago

https://github.com/eclipse/iceoryx https://github.com/eclipse/iceoryx

bitcharmer 6y ago

SPSC (single producer single consumer) queues and ring buffers are used quite extensively in low-latency software engineering.

jamesmunns 6y ago
Yup! In Rust specifically, I've written bbqueue, which is a bipbuffer-inspired lock-free ring buffer, intended for embedded systems and DMA usage. https://github.com/jamesmunns/bbqueue https://github.com/jamesmunns/bbqueue It uses atomics (and Rust's borrow checker) heavily to safely guarantee lock free behavior, and works pretty darn quick.
- caspper69 6y ago
  You reference a blog post on your Github (regarding the algo description). I believe the author of that blog (someone at Ferrous Systems) has a pretty significant misunderstanding of DMA and serial ports, which raises a whole host of other questions on down the chain <additional unnecessary comment removed>. edit: I know it's not cool to complain about downvotes, but this is a legitimate concern to raise for this poster. I am not attempting to denigrate anyone here.
  - twic 6y ago
    I assume you mean this blog post: https://ferrous-systems.com/blog/lock-free-ring-buffer/ https://ferrous-systems.com/blog/lock-free-ring-buffer/ Could you explain what you think the misunderstanding is, and what the consequences of that misunderstanding are?
    - deleted 6y ago
      [deleted]
    - caspper69 6y ago
      edit3: resolved below.
      - jamesmunns 6y ago
        The comparison that I was aiming to make was comparing a "busy wait blocking" implementation, e.g. sending one byte at a time, until the byte has been sent, which is typical for bare metal embedded systems (that don't use some kind of DMA or concurrency like threads or tasks). In this case, your CPU would be left spinning for an equivalent amount of time to the line rate of the serial port, if you were busy waiting for data.
      - jamesmunns 6y ago
        As a note, you can click on the time stamp of the child post, and respond directly there. > since I can't reply to the child I'll just say this: I don't like the math you used, I feel like it's making a point that shouldn't be made in a place where it doesn't need to be made. Of course it's going to be dog slow if you're busy waiting. Wtf? I guess I will just leave it at that. The entire post is about reducing the CPU time necessary to receive data from an external interface, like a serial port. The following paragraph states: > Instead of making our CPU waste all of this time waiting around, we allow the hardware to manage the simple sending and receiving process, allowing our CPU to either process other important tasks, or go into sleep mode, saving power or battery life. The intent for this example was to illustrate the difference between busy waiting and DMA. It is not uncommon on microcontrollers to only have a FIFO depth of one byte, which means if you aren't using interrupts, DMA, or threading, you will lose that data.

kvdr 6y ago

This is more about the way of doing lockless data operations than specific data structures - look up the RCU pattern, there are good CPP talks by Fedor Pikus on it.

franzwong 6y ago

log4j2 AsyncLogger uses RingBuffer (Disruptor) which is lock-free https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Articles https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Ar...

zaarn 6y ago

I've written some memory allocators that use lock-free allocation maps. In this case, a 4kb granularity allocator that used compressed free-bitmaps for usage in both userspace and kernelspace. The entire thing was lock-free, so allocations would never stall on a lock, even if the allocator had to decompress a bitmap (the way compression worked was by looking for free memory ranges and then replacing them by a range expression, which saved a few MB of memory per Gigabyte of memory available, as well as ordering largely free memory blocks to the start of the bitmap list to reduce seek time). Despite the complexity in the allocator, it could serve any number of threads without ever locking up. The worst case was a long latency if a thread had to scan the entire free list for a free block (It would switch to a different allocation behaviour if a thread had more than a dozen failed allocation attempts). A bunch of ring buffers I've worked with are atomic (ie, lock free), probably the most common application of lock-free stuff.

jamesmunns 6y ago
Interesting! Is this work public somewhere perhaps? I'm currently working on a similar technique (though with smaller blocks, currently ranging 64-1024 bytes - basically any 5 power-of-twos) for a lock-free allocator intended for real time embedded systems. I use a 32-bit word for each 1024 byte "page", and have a tree structure inside of the word (it takes 31 bits to cover 5 power-of-two ranges). My code (which only allocs and never frees at the moment) is here: https://github.com/jamesmunns/bitpool/ https://github.com/jamesmunns/bitpool/
- zaarn 6y ago
  Only a much older version which sadly does not feature compressed bitmaps or reordering of the bitmaps, plus having one or two bugs rather critical bugs. It's part of my toy project kernel. Largely written in Rust with a few unsafe behaviours since it's intended to be able to bootstrap given only a pointer and size of a heap memory block using only 8 kilobytes of stack, as well as being able to add or remove memory to the entire list. There is only one section that behaves like a lock, which handles the free range decompression. It has to be somewhat exclusive in behaviour since it must be able to decompress the block without allocating memory, instead it simply uses the decompressed lock to allocate the memory necessary to accomodate for overhang memory in the range (ie, if a range is larger than a block). It simply means that during this time, the available memory shrinks by the amount represented by the range. IIRC it's about 128 bytes of metadata, the rest is bits in the bitmaps to handle page allocation. Each block can in theory handle about 124 MiB, though I do have some logic so that sections can be split into multiple blocks to reduce contention as well as handling large pages (which largely reside in a single block as even 16MB pages enable managing Terabytes of memory). Allocation is simply a CAS on the byte containing the free bit for the specific page (Base Address + 4KiB * Bit Index) then doing an atomic increment on the free page counter. Deallocation is the reverse. Failed CAS attempts mean it continues to the next free bit atleast on the next byte (= (Bit Index >> 3 + 1) << 3). The happy allocation path is fewer than a hundred instructions, the unhappy path is about a thousand instructions. CAS latency can be quite unpredictable though, so probably not suitable for realtime systems.

pats0 6y ago

I used Michael & Scott lock-free queue and bounded SPMC & MPMC queues in my fibers library. Queues with locks were faster though. I've also written some QSBR to reclaim sockets registered in epoll/kqueue without a need to wrap concurrent epoll/kqueue calls in a lock.

sgtnoodle 6y ago

A good rule to follow in software engineering in general is "never write your own lock free data structures". I'm the one writing them so that my coworkers don't need to, though. I've used atomics to implement various flavors of queues in low level C for use on microcontrollers. A good single-producer single-consumer queue abstraction is helpful for communicating with interrupt service routines in peripheral drivers. Bespoke multiple-producer single or multiple-consumer queues are often useful for implementing logging abstractions that work from any context, including in interrupt handlers and critical sections.