Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

["David S. Miller" <davem@redhat.com>]

   From: Victor Yodaiken <yodaiken@fsmlabs.com>
   Date: Wed, 10 Oct 2001 16:24:19 -0600
   
   In general you're right, and always its better to 
   reduce contention than to come up with silly algorithms for 
   reducing the cost of contention,

I want to second this and remind people that the "cost" of spinlocks
is mostly not "spinning idly waiting for lock", rather the big cost
is shuffling the dirty cacheline ownership between the processors.

Any scheme involving shared data which is written (the read counts
in the various "lockless" schemes are examples) have the same "cost"
assosciated with them.

In short, I see no performance gain from the lockless algorithms
even in the places where they can be applied.

I spent some time oogling over lockless algorithms a few years ago,
but I stopped once I realized where the true costs were.  In my view,
the lockless algorithms perhaps are a win in parallel processing
environments (in fact, the supercomputing field is where a lot of the
lockless algorithm research comes from) but not in the kinds of places
and with the kinds of data structure usage the Linux kernel has.

Franks a lot,
David S. Miller
davem@redhat.com