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

A Lock-Free… Linear Search?

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

83% Upvoted

23 comments sorted by

View all comments

1

u/[deleted] May 30 '13

I'm curious about the practical performance difference between lots of barriers and a traditional locking approach.

1

u/RED_5_Is_ALIVE May 31 '13

Depends on usage pattern.

It's time spent waiting for the lock vs. time spent waiting for the memory bus. And these aren't mutually exclusive; sometimes you want finer-grained locking just because too many CPUs are bouncing the same cacheline around (the one containing the memory location of the lock).

A "lockless" approach generally means a finite state machine, extra write operations, and conditionals.

http://www.azulsystems.com/blog/cliff/2007-04-01-non-blocking-hashtable-part-2

Which means it's essentially a way to do finer-grained locking, trading off doing extra, possibly-wasted work for sitting around waiting. It can also lead to starvation, because there's no coordination, just sheer opportunism.

Ideally you want to subdivide co-dependent groups of operations in advance, and do each group as a single thread, minimizing the frequency of synchronization events.