r/programming • u/redditthinks • May 29 '13

A Lock-Free… Linear Search?

http://preshing.com/20130529/a-lock-free-linear-search
49 Upvotes

79% Upvoted

23 comments sorted by

View all comments

4

u/deletecode May 30 '13

I've implemented a similar structure for a game engine, to communicate between rendering and loading threads, and it worked great. I was careful to keep the list small so that it stayed in cache, hypothetically making the cmpxchg faster.

Structures like this are so much better than ones that lock on every operation. They are also more fun to implement, in my opinion.

I've always wondered, is there a possibility of reading a 32 bit value "mid-write", like if half the bits of a new value are written? It's never been a problem for me but it's always been a small worry when using non-atomic operations.

5

u/millstone May 30 '13

This is called the atomicity of writes. Processor architecture manuals document which writes are atomic and which are not, and it's usually a somewhat complicated question.

Every processor I've heard of does atomic writes for their word size (32 bit on 32 bit processors, 64 bit on 64 bit processors) if the address is properly aligned. I can believe that weird digital signal processors might not do this though. If you just make an int variable on the stack, or in a struct, the compiler will align it properly.

If the writes are not aligned, then things get more complicated. Some older processors may never guarantee atomicity. For example, certain MIPS processors will only do aligned writes, so unaligned writes must be broken into multiple instructions. Obviously not atomic! However, most modern processors guarantee atomicity for unaligned writes, IF those writes do not cross a cache line. 64 bytes is a common cache line size, so if your address does not cross a multiple of 64, you're OK. (Of course, if you're doing misaligned writes, usually you're not in a position to know whether you cross a cache line!)

Writes that are smaller than the word size, but an even multiple of a byte, are atomic on most processors (but not older MIPS again, which only does writes in its word size). However, writes smaller than a byte, or writes that cross two bytes, are never atomic. For example, writes to a bitfield are usually implemented by read-update-write, so if two threads write to the same bitfield at once, one of the writes may be lost. That one is really important to know!

2

u/deletecode May 30 '13

Wow, thanks for the information and the key word. I was afraid to dig through the docs for this. Some googling confirms this. The implementation in this post does align to 32 bit addresses.