Groups > comp.programming.threads > #2217

Re: About lockfree and waitfree... (2nd try)

From	Ivan Godard <ivan@ootbcomp.com>
Newsgroups	comp.programming.threads, comp.programming, comp.arch
Subject	Re: About lockfree and waitfree... (2nd try)
Date	2014-04-22 15:30 -0700
Organization	A noiseless patient Spider
Message-ID	<lj6qhp$vus$1@dont-email.me> (permalink)
References	(5 earlier) <lis216$i8l$1@dont-email.me> <lj42ch$60f$1@speranza.aioe.org> <lj42mn$6l2$1@speranza.aioe.org> <lj4412$s26$1@dont-email.me> <lj6mgv$kiv$1@speranza.aioe.org>

Cross-posted to 3 groups.

Show all headers | View raw

On 4/22/2014 2:21 PM, Chris M. Thomasson wrote:
>> "Ivan Godard"  wrote in message news:lj4412$s26$1@dont-email.me... On
>> 4/21/2014 2:31 PM, Chris M. Thomasson wrote:
>> [massive snip]
>
>> > Will the eventcount work with #StoreLoad ordering if multiple
>> > producers/consumers are executing on different physical chips and/or
>> > cores within a single chip?
>
>> I think so, on one chip and for cores that use the same global address
>> space. But I'd really like someone who knows this stuff to work it
>> through and confirm. It's not my expertise.
>
> First test would be can you emulate Linux on a box with
> multiple chips, and run the futexs through a contrived heavy
> load environment, with all affinity masks of participating threads
> bound to a single chip?
>
> So, using two chips reading with non-conflicting pieces of a single
> shared main memory is bad? Think of RCU, with two reader chips...
>
> RCU = Read-Copy Update
>
> Another chip is the writer; the update part in RCU.
>
> So, three chips, two readers, one writer.
>
>
> A simple description:
>
> http://en.wikipedia.org/wiki/Read-copy-update

In-memory RCU and all other memory-based coordination does not work on a 
Mill, because on a Mill the data in cache may be backless and have no 
DRAM behind it. Consequently RCU and other algorithms must be 
cache-based. However, the critical read and write operations to the key 
pointer are atomic (so long as the pointer is aligned or, if not 
aligned, does not cross a line boundary) for both backed and backless 
data, so I see no problem there.

The basic RCU trick of serializing writers by forcing them to be readers 
and scheduling around the cores should work on a Mill. However, this 
scheme has costs that scale at least with the number of cores. I'm 
doubtful about usage in high-update-high-corecount environments, on any 
architecture. The scaling should be no worse on a Mill, although the 
constant factor may be higher: Mills do significantly less task 
switching than other architectures because most of what involves IPC on 
a conventional machine uses portal calls instead of task switches on a 
Mill; as a result we expect more of a time slice to be consumed on 
average, so daisy-chaining around the cores will take longer.

I also expect the Mills optimistic synchronization primitive will 
provide a better way to do writer serialization than classic RCU. To 
begin with, it deals with multiple-update algorithms, such as updating a 
bi-linked list, which RCU doesn't do. Secondly, it permits writers to 
update at rates faster than the daisy-chain latency, although it could 
still use the daisy-chain to know that readers have been purged for 
scavenge. Thus adding a new node to a list (using the Mill primitive, 
and assuming no update contention) takes a read and two writes, without 
any trip around the cores. Deleting one takes two loads and a store 
before the next writer can go to work, although scavenging the deleted 
node requires a trip around, although more likely the deleted node is 
put on the work list of a scavenge thread that does the daisy chain on 
behalf of the deleting thread.

Conclusion: classic RCU should work with the same costs and scale 
factors, but using the Mill optimistic concurrency is more general and 
scales better than classic, especially in high-update and high core 
count environments.

That is, if I have understood the RCU :-)

Thread

About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 19:54 -0700
  Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:38 -0700
    Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:47 -0700
      Re: About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 22:56 -0700
      Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 14:08 -0700
        Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 14:23 -0700
          Re: About lockfree and waitfree... Ivan Godard <ivan@ootbcomp.com> - 2014-04-14 16:27 -0700
          Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-14 16:29 -0700
            Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-15 10:04 -0700
              Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-15 10:34 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-17 16:35 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 17:04 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-18 09:54 +0100
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-18 02:31 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-18 11:56 +0100
                Re: About lockfree and waitfree... (2nd try) rpw3@rpw3.org (Rob Warnock) - 2014-04-18 11:26 +0000
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-18 13:30 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:25 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:31 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-21 14:53 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 14:21 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 14:36 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-22 15:30 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-05-01 00:48 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-05-25 13:16 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:34 -0700
                Re: About lockfree and waitfree... (2nd try) Robert Wessel <robertwessel2@yahoo.com> - 2014-04-21 16:42 -0500
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-21 15:02 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-22 09:05 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-22 09:27 -0700
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-22 09:45 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-22 18:08 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-23 12:08 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-23 20:32 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-23 13:21 -0700
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-23 21:51 +0100
                Re: About lockfree and waitfree... (2nd try) Chris Gray <cg@GraySage.COM> - 2014-04-24 10:53 -0600
                Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-24 18:02 +0100
                Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-25 13:39 -0700
                Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 22:08 -0700
            Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-17 21:15 -0400
              Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-17 21:25 -0400
                Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 19:17 -0700
                Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-18 00:46 -0400
              Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 18:52 -0700
    Re: About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 22:54 -0700

csiph-web