Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #214

Re: False sharing

Show all headers | View raw

On 05/31/2011 12:21 PM, curious wrote:
>
> Hi Edek,
>
> Thanks for your reply.
>>
>> False sharing happens when data reaches RAM (or cache at least). Here,
>> it probably doesn't (at least not for every loop).
>>
>
> I was under the the understanding (most likely miss guided) that only
> one CPU can have a cache line in modified state (it should be invalid
> at all others), when the another cpu tries to read the data from that
> line it must be written and changed to exclusive state. This would
> then cause so called cache line ping pong between the two competing
> CPUs. Are you saying that the two CPUs can have two different modified
> copies of the cache line that they keep updating?

No, but it is not said a cache line is modified always when there is
a store (I mean "immediately") - some stores may be pending first.

>
>
>> However, the CPU still has to do addition. If you just store, the thing
>> is much simpler. Multiplication takes about 1.5x time for addition
>> when multiplying zeroes,
>> (interesting on its own). So: not RAM access takes time.
>> Division: 7x addition.
>>
> Good point, the simpler loop was doing less. I changed my second
> experiment so that I kept adding another number to work so that the
> only difference within the loop would be reading back the work value.
>
> // loop with read back and adding ( work += i )
> .L3:
> 	movq	(%rax), %rcx	#* data, D.22006
> 	leaq	(%rdx,%rcx), %rcx	#, D.22007
> 	addq	$1, %rdx	#, i
> 	cmpq	%rsi, %rdx	# tmp71, i
> 	movq	%rcx, (%rax)	# D.22007,* data
> 	jne	.L3	#,
>
> real	0m24.414s
> user	0m47.130s
> sys	0m0.680s
>
> // loop with adding ( work = i + dummy )
> .L3:
> 	leaq	(%rdx,%rdi), %rcx	#, D.22006
> 	addq	$1, %rdx	#, i
> 	cmpq	%rsi, %rdx	# tmp72, i
> 	movq	%rcx, (%rax)	# D.22006,* data
> 	jne	.L3	#,
>
> real	0m8.092s
> user	0m15.920s
> sys	0m0.010s
>
> So the loop with adding is still much faster than the loop with
> reading and adding. It makes sense that it is faster as it does not
> need to care what is the old value for the work is. I would really
> like to understand what causes the difference.

Like I wrote before, "work = work", which is read and store back,
is just as slow. It is like your first test.
It is called "loop-carried data dependency"
(previous loop result is fed into next loop), and there is
Store-Forwarding (instead of writing to memory and reading it back
data is fed back with a shortcut and stored only later; data
dependency nevertheless in this example)


Is it because in the
> latter case the CPU can issue "request for ownership" instead of first
> reading it (shared state) and invalidating other copies (modified
> state)? Or something else all together?

See above, something else. To know better, write assembly where work is
in register (instead of memory) and measure.
That will preserve the data dependency, but make no memory handling
in the CPU necessary.
No way to write it without assembly, or gcc will optimise it out.

As a side note, CPU may not be optimised for something as stupid
as reading a memory and storing it back in a loop. That's what
registers are for.

>
> Also it would be interesting to know if the "buffer" would make a
> bigger difference with cores that would not share any caches.

The buffer makes the cores not share any caches, that's what it is for.
The point is rather if the ping-pong you are referring to takes place.
It does not in this example, and does happen with synchronisation,
can be guessed from tests.

Cache coherency has a "builtin support" for threading. It changes
some things, but the memory model is not very strict,
Write-Combining is allowed for example, which by definition
changes ordering.
Synchronisation totally changes the behaviour, forcing certain points
where data must become visible. That means making changes visible across
CPUs immediately.

>
> Many Thanks

Edek

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

False sharing curious <curious.oskar58@gmail.com> - 2011-05-30 04:26 -0700
  Re: False sharing Edek <edek.pienkowski@gmail.com> - 2011-05-30 22:29 +0200
    Re: False sharing curious <curious.oskar58@gmail.com> - 2011-05-31 03:21 -0700
      Re: False sharing Marcel Müller <news.5.maazl@spamgourmet.com> - 2011-05-31 15:41 +0200
        Re: False sharing curious <curious.oskar58@gmail.com> - 2011-05-31 10:18 -0700
        Re: False sharing Edek <edek.pienkowski@gmail.com> - 2011-05-31 20:10 +0200
      Re: False sharing Edek <edek.pienkowski@gmail.com> - 2011-05-31 20:37 +0200
        Re: False sharing Edek <edek.pienkowski@gmail.com> - 2011-05-31 21:18 +0200
          Re: False sharing curious <curious.oskar58@gmail.com> - 2011-05-31 14:40 -0700
            Re: False sharing "Balog Pal" <pasa@lib.hu> - 2011-06-01 03:17 +0200
            Re: False sharing Edek <edek.pienkowski@gmail.com> - 2011-06-01 22:20 +0200
        Re: False sharing curious <curious.oskar58@gmail.com> - 2011-05-31 14:29 -0700
  Re: False sharing David Schwartz <davids@webmaster.com> - 2011-05-31 14:12 -0700
  Re: False sharing "Chris M. Thomasson" <cristom@charter.net> - 2011-06-11 15:34 -0700
    Re: False sharing "Chris M. Thomasson" <cristom@charter.net> - 2011-06-11 19:56 -0700
      Re: False sharing "Chris M. Thomasson" <cristom@charter.net> - 2011-06-11 21:07 -0700

csiph-web