[ltt-dev] liburcu cache line size

[ltt-dev] liburcu cache line size

[David Goulet]

Hi,

I have some doubt about the value of #define CACHE_LINE_SIZE 
(urcu/arch_x86.h) that is set to 128.

After some research and looking on my computer, the x86 architecture 
seems to have most of the time 64 bytes size. On my i7 920, here's what 
I have :

# getconf LEVEL1_DCACHE_LINESIZE
64

# cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

Since the Intel NetBurst microarch., the Intel manual says 64 bytes also 
and it has not changed apparently for Nehalem.

So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value 
here for x86, it could have an effect on cache pressure since 2 lines 
are required for structure less then 64 bytes.

Thanks!
-- 
David Goulet
LTTng project, DORSAL Lab.

PGP/GPG : 1024D/16BD8563
BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* David Goulet (david.goulet at polymtl.ca) wrote:
> Hi,
>
> I have some doubt about the value of #define CACHE_LINE_SIZE  
> (urcu/arch_x86.h) that is set to 128.
>
> After some research and looking on my computer, the x86 architecture  
> seems to have most of the time 64 bytes size. On my i7 920, here's what  
> I have :
>
> # getconf LEVEL1_DCACHE_LINESIZE
> 64
>
> # cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
> 64
>
> Since the Intel NetBurst microarch., the Intel manual says 64 bytes also  
> and it has not changed apparently for Nehalem.
>
> So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value  
> here for x86, it could have an effect on cache pressure since 2 lines  
> are required for structure less then 64 bytes.

See Linux kernel source:

arch/x86/Kconfig.cpu

#
# Define implied options from the CPU selection here
config X86_INTERNODE_CACHE_SHIFT
        int
        default "12" if X86_VSMP
        default "7" if NUMA
        default X86_L1_CACHE_SHIFT

and

config X86_L1_CACHE_SHIFT
        int
        default "7" if MPENTIUM4 || MPSC
        default "6" if MK7 || MK8 || MPENTIUMM || MCORE2 || MATOM ||
MVIAC7 || X86_GENERIC || GENERIC_CPU
        default "4" if X86_ELAN || M486 || M386 || MGEODEGX1
        default "5" if MWINCHIP3D || MWINCHIPC6 || MCRUSOE || MEFFICEON
|| MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX ||
M586TSC || M586 || MVIAC3_2 || MGEODE_LX

So Pentium 4 seems to have 128 bytes cache lines.

Hopefully the ScaleMP vSMP machine are rare enough (they would require a
4k alignment).

NUMA is not that rare, and requires 128 bytes cache lines too.

Can you send a patch for userspace RCU that documents this briefly in
urcu/arch_x86.h ? (just a summary of the info I pasted here would be
fine)

Thanks,

Mathieu





>
> Thanks!
> -- 
> David Goulet
> LTTng project, DORSAL Lab.
>
> PGP/GPG : 1024D/16BD8563
> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>
> _______________________________________________
> ltt-dev mailing list
> ltt-dev at lists.casi.polymtl.ca
> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[David Goulet]

On 10-08-17 02:51 PM, Mathieu Desnoyers wrote:
> * David Goulet (david.goulet at polymtl.ca) wrote:
>> Hi,
>>
>> I have some doubt about the value of #define CACHE_LINE_SIZE
>> (urcu/arch_x86.h) that is set to 128.
>>
>> After some research and looking on my computer, the x86 architecture
>> seems to have most of the time 64 bytes size. On my i7 920, here's what
>> I have :
>>
>> # getconf LEVEL1_DCACHE_LINESIZE
>> 64
>>
>> # cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
>> 64
>>
>> Since the Intel NetBurst microarch., the Intel manual says 64 bytes also
>> and it has not changed apparently for Nehalem.
>>
>> So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value
>> here for x86, it could have an effect on cache pressure since 2 lines
>> are required for structure less then 64 bytes.
>
> See Linux kernel source:
>
> arch/x86/Kconfig.cpu
>
> #
> # Define implied options from the CPU selection here
> config X86_INTERNODE_CACHE_SHIFT
>          int
>          default "12" if X86_VSMP
>          default "7" if NUMA
>          default X86_L1_CACHE_SHIFT
>
> and
>
> config X86_L1_CACHE_SHIFT
>          int
>          default "7" if MPENTIUM4 || MPSC
>          default "6" if MK7 || MK8 || MPENTIUMM || MCORE2 || MATOM ||
> MVIAC7 || X86_GENERIC || GENERIC_CPU
>          default "4" if X86_ELAN || M486 || M386 || MGEODEGX1
>          default "5" if MWINCHIP3D || MWINCHIPC6 || MCRUSOE || MEFFICEON
> || MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX ||
> M586TSC || M586 || MVIAC3_2 || MGEODE_LX
>
> So Pentium 4 seems to have 128 bytes cache lines.
>

Yep I saw that and this is why I'm asking because only NUMA, P4 and vSMP 
machines are bigger then 64 bytes. The rest is 64 bytes (X86 generic, 
Core 2(Nehalem), Atom).

So you are saying that you prefer use 128 bytes knowing that most of X86 
is lower or equal to 64 bytes?

> Hopefully the ScaleMP vSMP machine are rare enough (they would require a
> 4k alignment).
>
> NUMA is not that rare, and requires 128 bytes cache lines too.
>
> Can you send a patch for userspace RCU that documents this briefly in
> urcu/arch_x86.h ? (just a summary of the info I pasted here would be
> fine)
>
> Thanks,
>
> Mathieu
>
>
>
>
>
>>
>> Thanks!
>> --
>> David Goulet
>> LTTng project, DORSAL Lab.
>>
>> PGP/GPG : 1024D/16BD8563
>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>
>> _______________________________________________
>> ltt-dev mailing list
>> ltt-dev at lists.casi.polymtl.ca
>> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>>
>

-- 
David Goulet
LTTng project, DORSAL Lab.

PGP/GPG : 1024D/16BD8563
BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* David Goulet (david.goulet at polymtl.ca) wrote:
>
>
> On 10-08-17 02:51 PM, Mathieu Desnoyers wrote:
>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>> Hi,
>>>
>>> I have some doubt about the value of #define CACHE_LINE_SIZE
>>> (urcu/arch_x86.h) that is set to 128.
>>>
>>> After some research and looking on my computer, the x86 architecture
>>> seems to have most of the time 64 bytes size. On my i7 920, here's what
>>> I have :
>>>
>>> # getconf LEVEL1_DCACHE_LINESIZE
>>> 64
>>>
>>> # cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
>>> 64
>>>
>>> Since the Intel NetBurst microarch., the Intel manual says 64 bytes also
>>> and it has not changed apparently for Nehalem.
>>>
>>> So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value
>>> here for x86, it could have an effect on cache pressure since 2 lines
>>> are required for structure less then 64 bytes.
>>
>> See Linux kernel source:
>>
>> arch/x86/Kconfig.cpu
>>
>> #
>> # Define implied options from the CPU selection here
>> config X86_INTERNODE_CACHE_SHIFT
>>          int
>>          default "12" if X86_VSMP
>>          default "7" if NUMA
>>          default X86_L1_CACHE_SHIFT
>>
>> and
>>
>> config X86_L1_CACHE_SHIFT
>>          int
>>          default "7" if MPENTIUM4 || MPSC
>>          default "6" if MK7 || MK8 || MPENTIUMM || MCORE2 || MATOM ||
>> MVIAC7 || X86_GENERIC || GENERIC_CPU
>>          default "4" if X86_ELAN || M486 || M386 || MGEODEGX1
>>          default "5" if MWINCHIP3D || MWINCHIPC6 || MCRUSOE || MEFFICEON
>> || MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX ||
>> M586TSC || M586 || MVIAC3_2 || MGEODE_LX
>>
>> So Pentium 4 seems to have 128 bytes cache lines.
>>
>
> Yep I saw that and this is why I'm asking because only NUMA, P4 and vSMP  
> machines are bigger then 64 bytes. The rest is 64 bytes (X86 generic,  
> Core 2(Nehalem), Atom).
>
> So you are saying that you prefer use 128 bytes knowing that most of X86  
> is lower or equal to 64 bytes?

Yes. The performance degradation caused by cache-line bouncing is _way_
worse than extra cache pressure.

Mathieu

>
>> Hopefully the ScaleMP vSMP machine are rare enough (they would require a
>> 4k alignment).
>>
>> NUMA is not that rare, and requires 128 bytes cache lines too.
>>
>> Can you send a patch for userspace RCU that documents this briefly in
>> urcu/arch_x86.h ? (just a summary of the info I pasted here would be
>> fine)
>>
>> Thanks,
>>
>> Mathieu
>>
>>
>>
>>
>>
>>>
>>> Thanks!
>>> --
>>> David Goulet
>>> LTTng project, DORSAL Lab.
>>>
>>> PGP/GPG : 1024D/16BD8563
>>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>>
>>> _______________________________________________
>>> ltt-dev mailing list
>>> ltt-dev at lists.casi.polymtl.ca
>>> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>>>
>>
>
> -- 
> David Goulet
> LTTng project, DORSAL Lab.
>
> PGP/GPG : 1024D/16BD8563
> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* Mathieu Desnoyers (compudj at krystal.dyndns.org) wrote:
> * David Goulet (david.goulet at polymtl.ca) wrote:
> >
> >
> > On 10-08-17 02:51 PM, Mathieu Desnoyers wrote:
> >> * David Goulet (david.goulet at polymtl.ca) wrote:
> >>> Hi,
> >>>
> >>> I have some doubt about the value of #define CACHE_LINE_SIZE
> >>> (urcu/arch_x86.h) that is set to 128.
> >>>
> >>> After some research and looking on my computer, the x86 architecture
> >>> seems to have most of the time 64 bytes size. On my i7 920, here's what
> >>> I have :
> >>>
> >>> # getconf LEVEL1_DCACHE_LINESIZE
> >>> 64
> >>>
> >>> # cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
> >>> 64
> >>>
> >>> Since the Intel NetBurst microarch., the Intel manual says 64 bytes also
> >>> and it has not changed apparently for Nehalem.
> >>>
> >>> So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value
> >>> here for x86, it could have an effect on cache pressure since 2 lines
> >>> are required for structure less then 64 bytes.
> >>
> >> See Linux kernel source:
> >>
> >> arch/x86/Kconfig.cpu
> >>
> >> #
> >> # Define implied options from the CPU selection here
> >> config X86_INTERNODE_CACHE_SHIFT
> >>          int
> >>          default "12" if X86_VSMP
> >>          default "7" if NUMA
> >>          default X86_L1_CACHE_SHIFT
> >>
> >> and
> >>
> >> config X86_L1_CACHE_SHIFT
> >>          int
> >>          default "7" if MPENTIUM4 || MPSC
> >>          default "6" if MK7 || MK8 || MPENTIUMM || MCORE2 || MATOM ||
> >> MVIAC7 || X86_GENERIC || GENERIC_CPU
> >>          default "4" if X86_ELAN || M486 || M386 || MGEODEGX1
> >>          default "5" if MWINCHIP3D || MWINCHIPC6 || MCRUSOE || MEFFICEON
> >> || MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX ||
> >> M586TSC || M586 || MVIAC3_2 || MGEODE_LX
> >>
> >> So Pentium 4 seems to have 128 bytes cache lines.
> >>
> >
> > Yep I saw that and this is why I'm asking because only NUMA, P4 and vSMP  
> > machines are bigger then 64 bytes. The rest is 64 bytes (X86 generic,  
> > Core 2(Nehalem), Atom).
> >
> > So you are saying that you prefer use 128 bytes knowing that most of X86  
> > is lower or equal to 64 bytes?
> 
> Yes. The performance degradation caused by cache-line bouncing is _way_
> worse than extra cache pressure.

Oh, and by the way, given that these are arrays made of one variable per
cpu, the extra space allocated will not consume extra cache lines in any
of the CPU. We're just wasting a bit a memory here, not adding to cache
pressure.

Mathieu

> 
> Mathieu
> 
> >
> >> Hopefully the ScaleMP vSMP machine are rare enough (they would require a
> >> 4k alignment).
> >>
> >> NUMA is not that rare, and requires 128 bytes cache lines too.
> >>
> >> Can you send a patch for userspace RCU that documents this briefly in
> >> urcu/arch_x86.h ? (just a summary of the info I pasted here would be
> >> fine)
> >>
> >> Thanks,
> >>
> >> Mathieu
> >>
> >>
> >>
> >>
> >>
> >>>
> >>> Thanks!
> >>> --
> >>> David Goulet
> >>> LTTng project, DORSAL Lab.
> >>>
> >>> PGP/GPG : 1024D/16BD8563
> >>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
> >>>
> >>> _______________________________________________
> >>> ltt-dev mailing list
> >>> ltt-dev at lists.casi.polymtl.ca
> >>> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
> >>>
> >>
> >
> > -- 
> > David Goulet
> > LTTng project, DORSAL Lab.
> >
> > PGP/GPG : 1024D/16BD8563
> > BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
> >
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
> 
> _______________________________________________
> ltt-dev mailing list
> ltt-dev at lists.casi.polymtl.ca
> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[David Goulet]

On 10-08-17 03:45 PM, Mathieu Desnoyers wrote:
> * David Goulet (david.goulet at polymtl.ca) wrote:
>>
>>
>> On 10-08-17 02:51 PM, Mathieu Desnoyers wrote:
>>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>>> Hi,
>>>>
>>>> I have some doubt about the value of #define CACHE_LINE_SIZE
>>>> (urcu/arch_x86.h) that is set to 128.
>>>>
>>>> After some research and looking on my computer, the x86 architecture
>>>> seems to have most of the time 64 bytes size. On my i7 920, here's what
>>>> I have :
>>>>
>>>> # getconf LEVEL1_DCACHE_LINESIZE
>>>> 64
>>>>
>>>> # cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
>>>> 64
>>>>
>>>> Since the Intel NetBurst microarch., the Intel manual says 64 bytes also
>>>> and it has not changed apparently for Nehalem.
>>>>
>>>> So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value
>>>> here for x86, it could have an effect on cache pressure since 2 lines
>>>> are required for structure less then 64 bytes.
>>>
>>> See Linux kernel source:
>>>
>>> arch/x86/Kconfig.cpu
>>>
>>> #
>>> # Define implied options from the CPU selection here
>>> config X86_INTERNODE_CACHE_SHIFT
>>>           int
>>>           default "12" if X86_VSMP
>>>           default "7" if NUMA
>>>           default X86_L1_CACHE_SHIFT
>>>
>>> and
>>>
>>> config X86_L1_CACHE_SHIFT
>>>           int
>>>           default "7" if MPENTIUM4 || MPSC
>>>           default "6" if MK7 || MK8 || MPENTIUMM || MCORE2 || MATOM ||
>>> MVIAC7 || X86_GENERIC || GENERIC_CPU
>>>           default "4" if X86_ELAN || M486 || M386 || MGEODEGX1
>>>           default "5" if MWINCHIP3D || MWINCHIPC6 || MCRUSOE || MEFFICEON
>>> || MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX ||
>>> M586TSC || M586 || MVIAC3_2 || MGEODE_LX
>>>
>>> So Pentium 4 seems to have 128 bytes cache lines.
>>>
>>
>> Yep I saw that and this is why I'm asking because only NUMA, P4 and vSMP
>> machines are bigger then 64 bytes. The rest is 64 bytes (X86 generic,
>> Core 2(Nehalem), Atom).
>>
>> So you are saying that you prefer use 128 bytes knowing that most of X86
>> is lower or equal to 64 bytes?
>
> Yes. The performance degradation caused by cache-line bouncing is _way_
> worse than extra cache pressure.
>

There is something I don't understand here. Correct me if (most likely) 
I am wrong.

How cache line bouncing is affected by the cache line size? If I 
understand correctly, cache line bounce is the problem where CPUs shares 
data and have to fetch it from CPU0 to CPU7 (between caches). And, I 
surely agree, this is costly!

However, if the size of the cache is bigger then the normal cache, you 
just loose space... For arch with 64 cache line size, you loose two line 
per structure aligned... How lowering down to 64 bytes will cause cache 
line bouncing?

Thanks for your help on that!
David

> Mathieu
>
>>
>>> Hopefully the ScaleMP vSMP machine are rare enough (they would require a
>>> 4k alignment).
>>>
>>> NUMA is not that rare, and requires 128 bytes cache lines too.
>>>
>>> Can you send a patch for userspace RCU that documents this briefly in
>>> urcu/arch_x86.h ? (just a summary of the info I pasted here would be
>>> fine)
>>>
>>> Thanks,
>>>
>>> Mathieu
>>>
>>>
>>>
>>>
>>>
>>>>
>>>> Thanks!
>>>> --
>>>> David Goulet
>>>> LTTng project, DORSAL Lab.
>>>>
>>>> PGP/GPG : 1024D/16BD8563
>>>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>>>
>>>> _______________________________________________
>>>> ltt-dev mailing list
>>>> ltt-dev at lists.casi.polymtl.ca
>>>> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>>>>
>>>
>>
>> --
>> David Goulet
>> LTTng project, DORSAL Lab.
>>
>> PGP/GPG : 1024D/16BD8563
>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>
>

-- 
David Goulet
LTTng project, DORSAL Lab.

PGP/GPG : 1024D/16BD8563
BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563

[ltt-dev] liburcu cache line size

[Alexandre Montplaisir]

On 10-08-17 03:54 PM, Mathieu Desnoyers wrote:
> * Mathieu Desnoyers (compudj at krystal.dyndns.org) wrote:
>    
>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>      
>>>
>>> On 10-08-17 02:51 PM, Mathieu Desnoyers wrote:
>>>        
>>>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>>>          
>>>>> Hi,
>>>>>
>>>>> I have some doubt about the value of #define CACHE_LINE_SIZE
>>>>> (urcu/arch_x86.h) that is set to 128.
>>>>>
>>>>> After some research and looking on my computer, the x86 architecture
>>>>> seems to have most of the time 64 bytes size. On my i7 920, here's what
>>>>> I have :
>>>>>
>>>>> # getconf LEVEL1_DCACHE_LINESIZE
>>>>> 64
>>>>>
>>>>> # cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
>>>>> 64
>>>>>
>>>>> Since the Intel NetBurst microarch., the Intel manual says 64 bytes also
>>>>> and it has not changed apparently for Nehalem.
>>>>>
>>>>> So, Mathieu, why 128 bytes? UST is using that, if it's the wrong value
>>>>> here for x86, it could have an effect on cache pressure since 2 lines
>>>>> are required for structure less then 64 bytes.
>>>>>            
>>>> See Linux kernel source:
>>>>
>>>> arch/x86/Kconfig.cpu
>>>>
>>>> #
>>>> # Define implied options from the CPU selection here
>>>> config X86_INTERNODE_CACHE_SHIFT
>>>>           int
>>>>           default "12" if X86_VSMP
>>>>           default "7" if NUMA
>>>>           default X86_L1_CACHE_SHIFT
>>>>
>>>> and
>>>>
>>>> config X86_L1_CACHE_SHIFT
>>>>           int
>>>>           default "7" if MPENTIUM4 || MPSC
>>>>           default "6" if MK7 || MK8 || MPENTIUMM || MCORE2 || MATOM ||
>>>> MVIAC7 || X86_GENERIC || GENERIC_CPU
>>>>           default "4" if X86_ELAN || M486 || M386 || MGEODEGX1
>>>>           default "5" if MWINCHIP3D || MWINCHIPC6 || MCRUSOE || MEFFICEON
>>>> || MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX ||
>>>> M586TSC || M586 || MVIAC3_2 || MGEODE_LX
>>>>
>>>> So Pentium 4 seems to have 128 bytes cache lines.
>>>>
>>>>          
>>> Yep I saw that and this is why I'm asking because only NUMA, P4 and vSMP
>>> machines are bigger then 64 bytes. The rest is 64 bytes (X86 generic,
>>> Core 2(Nehalem), Atom).
>>>
>>> So you are saying that you prefer use 128 bytes knowing that most of X86
>>> is lower or equal to 64 bytes?
>>>        
>> Yes. The performance degradation caused by cache-line bouncing is _way_
>> worse than extra cache pressure.
>>      
> Oh, and by the way, given that these are arrays made of one variable per
> cpu, the extra space allocated will not consume extra cache lines in any
> of the CPU. We're just wasting a bit a memory here, not adding to cache
> pressure.
>
> Mathieu
>
>    


Sorry to chime in, but wouldn't padding to 128 bytes on architectures 
with 64-byte cache lines "waste" an extra line every time, thus 
indirectly adding to cache pressure?

(relatively newbie here, please be gentle :) )

Alexandre


>> Mathieu
>>
>>      
>>>        
>>>> Hopefully the ScaleMP vSMP machine are rare enough (they would require a
>>>> 4k alignment).
>>>>
>>>> NUMA is not that rare, and requires 128 bytes cache lines too.
>>>>
>>>> Can you send a patch for userspace RCU that documents this briefly in
>>>> urcu/arch_x86.h ? (just a summary of the info I pasted here would be
>>>> fine)
>>>>
>>>> Thanks,
>>>>
>>>> Mathieu
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>          
>>>>> Thanks!
>>>>> --
>>>>> David Goulet
>>>>> LTTng project, DORSAL Lab.
>>>>>
>>>>> PGP/GPG : 1024D/16BD8563
>>>>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>>>>
>>>>> _______________________________________________
>>>>> ltt-dev mailing list
>>>>> ltt-dev at lists.casi.polymtl.ca
>>>>> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>>>>>
>>>>>            
>>>>          
>>> -- 
>>> David Goulet
>>> LTTng project, DORSAL Lab.
>>>
>>> PGP/GPG : 1024D/16BD8563
>>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>>
>>>        
>> -- 
>> Mathieu Desnoyers
>> Operating System Efficiency R&D Consultant
>> EfficiOS Inc.
>> http://www.efficios.com
>>
>> _______________________________________________
>> ltt-dev mailing list
>> ltt-dev at lists.casi.polymtl.ca
>> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
>>
>>      
>    

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* David Goulet (david.goulet at polymtl.ca) wrote:
> On 10-08-17 03:45 PM, Mathieu Desnoyers wrote:
[...]
>> Yes. The performance degradation caused by cache-line bouncing is _way_
>> worse than extra cache pressure.
>>
>
> There is something I don't understand here. Correct me if (most likely)  
> I am wrong.
>
> How cache line bouncing is affected by the cache line size? If I  
> understand correctly, cache line bounce is the problem where CPUs shares  
> data and have to fetch it from CPU0 to CPU7 (between caches). And, I  
> surely agree, this is costly!

That's ok up to here.

>
> However, if the size of the cache is bigger then the normal cache, you  
> just loose space... For arch with 64 cache line size, you loose two line  
> per structure aligned... How lowering down to 64 bytes will cause cache  
> line bouncing?

Let's take the following example:

A multiprocessor machine with 256 bytes cache line size.
The program is built thinking the cache line size is only 128 bytes.

So we allocate an array of what we hope are per-cpu variables:

 malloc(nr_cpus * sizeof(struct type));

Where struct type is __attribute__((aligned(128))

So we end up having two structures sharing a cache-line, and these will
bounce between CPUs, even though the structures are not shared: only the
cache-lines are shared, because the structures happen to be on the same
cache line.

So for allocation of individual objects which are meant to be per-cpu,
e.g. a structure controlling the per-cpu buffer, the allocator can put
one structure next to another (belonging to another cpu), thus causing
cache line bouncing.

This phenomenon is called "false sharing".

Mathieu

>
> Thanks for your help on that!
> David
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* Alexandre Montplaisir (alexandre.montplaisir at polymtl.ca) wrote:
> On 10-08-17 03:54 PM, Mathieu Desnoyers wrote:
 [...]  
>> Oh, and by the way, given that these are arrays made of one variable per
>> cpu, the extra space allocated will not consume extra cache lines in any
>> of the CPU. We're just wasting a bit a memory here, not adding to cache
>> pressure.
>>
>> Mathieu
>
> Sorry to chime in, but wouldn't padding to 128 bytes on architectures  
> with 64-byte cache lines "waste" an extra line every time, thus  
> indirectly adding to cache pressure?

A cache line is only used if the data located in that cache line is
touched. If we only have padding in the second half of the 128 bytes,
then the associated 64 bytes cache line is never fetched by the cpu.

But reality can be a bit different when we speak of sequential accesses
with prefetching. However, this apply well to randomly-accessed memory.

Does that make sense ?

Thanks,

Mathieu

>
> (relatively newbie here, please be gentle :) )
>
> Alexandre


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[Alexandre Montplaisir]

On 10-08-17 04:27 PM, Mathieu Desnoyers wrote:
> * Alexandre Montplaisir (alexandre.montplaisir at polymtl.ca) wrote:
>    
>> On 10-08-17 03:54 PM, Mathieu Desnoyers wrote:
>>      
>   [...]
>    
>>> Oh, and by the way, given that these are arrays made of one variable per
>>> cpu, the extra space allocated will not consume extra cache lines in any
>>> of the CPU. We're just wasting a bit a memory here, not adding to cache
>>> pressure.
>>>
>>> Mathieu
>>>        
>> Sorry to chime in, but wouldn't padding to 128 bytes on architectures
>> with 64-byte cache lines "waste" an extra line every time, thus
>> indirectly adding to cache pressure?
>>      
> A cache line is only used if the data located in that cache line is
> touched. If we only have padding in the second half of the 128 bytes,
> then the associated 64 bytes cache line is never fetched by the cpu.
>
> But reality can be a bit different when we speak of sequential accesses
> with prefetching. However, this apply well to randomly-accessed memory.
>
> Does that make sense ?
>
>    
Yes, thanks for the explanation!

I see now why we *clearly* don't want the align attribute to be smaller 
than the actual cache-line size.

Me and David's concerns were more about the other architectures (core2, 
atom, "generic", etc., which do seem to be more common than P4 & NUMA) 
where the lib is still defining 128-byte cache line sizes even though 
they use 64-byte ones. Would it be worth it to have a per-architecture 
definition?

Alexandre

> Thanks,
>
> Mathieu
>
>    
>> (relatively newbie here, please be gentle :) )
>>
>> Alexandre
>>      
>
>    

[ltt-dev] liburcu cache line size

[David Goulet]

On 10-08-17 04:24 PM, Mathieu Desnoyers wrote:
> * David Goulet (david.goulet at polymtl.ca) wrote:
>> On 10-08-17 03:45 PM, Mathieu Desnoyers wrote:
> [...]
>>> Yes. The performance degradation caused by cache-line bouncing is _way_
>>> worse than extra cache pressure.
>>>
>>
>> There is something I don't understand here. Correct me if (most likely)
>> I am wrong.
>>
>> How cache line bouncing is affected by the cache line size? If I
>> understand correctly, cache line bounce is the problem where CPUs shares
>> data and have to fetch it from CPU0 to CPU7 (between caches). And, I
>> surely agree, this is costly!
>
> That's ok up to here.
>
>>
>> However, if the size of the cache is bigger then the normal cache, you
>> just loose space... For arch with 64 cache line size, you loose two line
>> per structure aligned... How lowering down to 64 bytes will cause cache
>> line bouncing?
>
> Let's take the following example:
>
> A multiprocessor machine with 256 bytes cache line size.
> The program is built thinking the cache line size is only 128 bytes.
>
> So we allocate an array of what we hope are per-cpu variables:
>
>   malloc(nr_cpus * sizeof(struct type));
>
> Where struct type is __attribute__((aligned(128))
>
> So we end up having two structures sharing a cache-line, and these will
> bounce between CPUs, even though the structures are not shared: only the
> cache-lines are shared, because the structures happen to be on the same
> cache line.
>
> So for allocation of individual objects which are meant to be per-cpu,
> e.g. a structure controlling the per-cpu buffer, the allocator can put
> one structure next to another (belonging to another cpu), thus causing
> cache line bouncing.
>
> This phenomenon is called "false sharing".
>

Very nice. That clarify yes!

However, please refer to Intel? 64 and IA-32 Architectures Software 
Developer's Manual Volume 3A: System Programming Guide.

http://www.intel.com/Assets/PDF/manual/253668.pdf

P. 527, Table 11-1

? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
  microarchitecture): 8-KByte, 4-way set associative, 64-byte cache line
size.
? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
  microarchitecture): 16-KByte, 8-way set associative, 64-byte cache line
size.

David

> Mathieu
>
>>
>> Thanks for your help on that!
>> David
>>
>

-- 
David Goulet
LTTng project, DORSAL Lab.

PGP/GPG : 1024D/16BD8563
BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* David Goulet (david.goulet at polymtl.ca) wrote:
>
>
> On 10-08-17 04:24 PM, Mathieu Desnoyers wrote:
>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>> On 10-08-17 03:45 PM, Mathieu Desnoyers wrote:
>> [...]
>>>> Yes. The performance degradation caused by cache-line bouncing is _way_
>>>> worse than extra cache pressure.
>>>>
>>>
>>> There is something I don't understand here. Correct me if (most likely)
>>> I am wrong.
>>>
>>> How cache line bouncing is affected by the cache line size? If I
>>> understand correctly, cache line bounce is the problem where CPUs shares
>>> data and have to fetch it from CPU0 to CPU7 (between caches). And, I
>>> surely agree, this is costly!
>>
>> That's ok up to here.
>>
>>>
>>> However, if the size of the cache is bigger then the normal cache, you
>>> just loose space... For arch with 64 cache line size, you loose two line
>>> per structure aligned... How lowering down to 64 bytes will cause cache
>>> line bouncing?
>>
>> Let's take the following example:
>>
>> A multiprocessor machine with 256 bytes cache line size.
>> The program is built thinking the cache line size is only 128 bytes.
>>
>> So we allocate an array of what we hope are per-cpu variables:
>>
>>   malloc(nr_cpus * sizeof(struct type));
>>
>> Where struct type is __attribute__((aligned(128))
>>
>> So we end up having two structures sharing a cache-line, and these will
>> bounce between CPUs, even though the structures are not shared: only the
>> cache-lines are shared, because the structures happen to be on the same
>> cache line.
>>
>> So for allocation of individual objects which are meant to be per-cpu,
>> e.g. a structure controlling the per-cpu buffer, the allocator can put
>> one structure next to another (belonging to another cpu), thus causing
>> cache line bouncing.
>>
>> This phenomenon is called "false sharing".
>>
>
> Very nice. That clarify yes!
>
> However, please refer to Intel? 64 and IA-32 Architectures Software  
> Developer's Manual Volume 3A: System Programming Guide.
>
> http://www.intel.com/Assets/PDF/manual/253668.pdf
>
> P. 527, Table 11-1
>
> ? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
>  microarchitecture): 8-KByte, 4-way set associative, 64-byte cache line
> size.
> ? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
>  microarchitecture): 16-KByte, 8-way set associative, 64-byte cache line
> size.

Dunno why the Linux kernel choses that for P4. But we definitely have to
handle NUMA systems.

Mathieu

>
> David
>
>> Mathieu
>>
>>>
>>> Thanks for your help on that!
>>> David
>>>
>>
>
> -- 
> David Goulet
> LTTng project, DORSAL Lab.
>
> PGP/GPG : 1024D/16BD8563
> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[David Goulet]

On 10-08-17 04:51 PM, Mathieu Desnoyers wrote:
> * David Goulet (david.goulet at polymtl.ca) wrote:
>>
>>
>> On 10-08-17 04:24 PM, Mathieu Desnoyers wrote:
>>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>>> On 10-08-17 03:45 PM, Mathieu Desnoyers wrote:
>>> [...]
>>>>> Yes. The performance degradation caused by cache-line bouncing is _way_
>>>>> worse than extra cache pressure.
>>>>>
>>>>
>>>> There is something I don't understand here. Correct me if (most likely)
>>>> I am wrong.
>>>>
>>>> How cache line bouncing is affected by the cache line size? If I
>>>> understand correctly, cache line bounce is the problem where CPUs shares
>>>> data and have to fetch it from CPU0 to CPU7 (between caches). And, I
>>>> surely agree, this is costly!
>>>
>>> That's ok up to here.
>>>
>>>>
>>>> However, if the size of the cache is bigger then the normal cache, you
>>>> just loose space... For arch with 64 cache line size, you loose two line
>>>> per structure aligned... How lowering down to 64 bytes will cause cache
>>>> line bouncing?
>>>
>>> Let's take the following example:
>>>
>>> A multiprocessor machine with 256 bytes cache line size.
>>> The program is built thinking the cache line size is only 128 bytes.
>>>
>>> So we allocate an array of what we hope are per-cpu variables:
>>>
>>>    malloc(nr_cpus * sizeof(struct type));
>>>
>>> Where struct type is __attribute__((aligned(128))
>>>
>>> So we end up having two structures sharing a cache-line, and these will
>>> bounce between CPUs, even though the structures are not shared: only the
>>> cache-lines are shared, because the structures happen to be on the same
>>> cache line.
>>>
>>> So for allocation of individual objects which are meant to be per-cpu,
>>> e.g. a structure controlling the per-cpu buffer, the allocator can put
>>> one structure next to another (belonging to another cpu), thus causing
>>> cache line bouncing.
>>>
>>> This phenomenon is called "false sharing".
>>>
>>
>> Very nice. That clarify yes!
>>
>> However, please refer to Intel? 64 and IA-32 Architectures Software
>> Developer's Manual Volume 3A: System Programming Guide.
>>
>> http://www.intel.com/Assets/PDF/manual/253668.pdf
>>
>> P. 527, Table 11-1
>>
>> ? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
>>   microarchitecture): 8-KByte, 4-way set associative, 64-byte cache line
>> size.
>> ? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
>>   microarchitecture): 16-KByte, 8-way set associative, 64-byte cache line
>> size.
>
> Dunno why the Linux kernel choses that for P4. But we definitely have to
> handle NUMA systems.
>

arch_numa.h ... possible?

> Mathieu
>
>>
>> David
>>
>>> Mathieu
>>>
>>>>
>>>> Thanks for your help on that!
>>>> David
>>>>
>>>
>>
>> --
>> David Goulet
>> LTTng project, DORSAL Lab.
>>
>> PGP/GPG : 1024D/16BD8563
>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>
>

-- 
David Goulet
LTTng project, DORSAL Lab.

PGP/GPG : 1024D/16BD8563
BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* Alexandre Montplaisir (alexandre.montplaisir at polymtl.ca) wrote:
> On 10-08-17 04:27 PM, Mathieu Desnoyers wrote:
>> * Alexandre Montplaisir (alexandre.montplaisir at polymtl.ca) wrote:
>>    
>>> On 10-08-17 03:54 PM, Mathieu Desnoyers wrote:
>>>      
>>   [...]
>>    
>>>> Oh, and by the way, given that these are arrays made of one variable per
>>>> cpu, the extra space allocated will not consume extra cache lines in any
>>>> of the CPU. We're just wasting a bit a memory here, not adding to cache
>>>> pressure.
>>>>
>>>> Mathieu
>>>>        
>>> Sorry to chime in, but wouldn't padding to 128 bytes on architectures
>>> with 64-byte cache lines "waste" an extra line every time, thus
>>> indirectly adding to cache pressure?
>>>      
>> A cache line is only used if the data located in that cache line is
>> touched. If we only have padding in the second half of the 128 bytes,
>> then the associated 64 bytes cache line is never fetched by the cpu.
>>
>> But reality can be a bit different when we speak of sequential accesses
>> with prefetching. However, this apply well to randomly-accessed memory.
>>
>> Does that make sense ?
>>
>>    
> Yes, thanks for the explanation!
>
> I see now why we *clearly* don't want the align attribute to be smaller  
> than the actual cache-line size.
>
> Me and David's concerns were more about the other architectures (core2,  
> atom, "generic", etc., which do seem to be more common than P4 & NUMA)  
> where the lib is still defining 128-byte cache line sizes even though  
> they use 64-byte ones. Would it be worth it to have a per-architecture  
> definition?

It becomes a mess trying to have defines for each sub-architecture when
not clearly needed. In this case, we just waste a few bytes of memory
here and there, nothing to call home about, really.

We always have to think that these are usually packaged by distros,
which have to use defaults that will work well on a wide set of
machines.

Thanks,

Mathieu

>
> Alexandre
>
>> Thanks,
>>
>> Mathieu
>>
>>    
>>> (relatively newbie here, please be gentle :) )
>>>
>>> Alexandre
>>>      
>>
>>    
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] liburcu cache line size

[Mathieu Desnoyers]

* David Goulet (david.goulet at polymtl.ca) wrote:
>
>
> On 10-08-17 04:51 PM, Mathieu Desnoyers wrote:
>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>>
>>>
>>> On 10-08-17 04:24 PM, Mathieu Desnoyers wrote:
>>>> * David Goulet (david.goulet at polymtl.ca) wrote:
>>>>> On 10-08-17 03:45 PM, Mathieu Desnoyers wrote:
>>>> [...]
>>>>>> Yes. The performance degradation caused by cache-line bouncing is _way_
>>>>>> worse than extra cache pressure.
>>>>>>
>>>>>
>>>>> There is something I don't understand here. Correct me if (most likely)
>>>>> I am wrong.
>>>>>
>>>>> How cache line bouncing is affected by the cache line size? If I
>>>>> understand correctly, cache line bounce is the problem where CPUs shares
>>>>> data and have to fetch it from CPU0 to CPU7 (between caches). And, I
>>>>> surely agree, this is costly!
>>>>
>>>> That's ok up to here.
>>>>
>>>>>
>>>>> However, if the size of the cache is bigger then the normal cache, you
>>>>> just loose space... For arch with 64 cache line size, you loose two line
>>>>> per structure aligned... How lowering down to 64 bytes will cause cache
>>>>> line bouncing?
>>>>
>>>> Let's take the following example:
>>>>
>>>> A multiprocessor machine with 256 bytes cache line size.
>>>> The program is built thinking the cache line size is only 128 bytes.
>>>>
>>>> So we allocate an array of what we hope are per-cpu variables:
>>>>
>>>>    malloc(nr_cpus * sizeof(struct type));
>>>>
>>>> Where struct type is __attribute__((aligned(128))
>>>>
>>>> So we end up having two structures sharing a cache-line, and these will
>>>> bounce between CPUs, even though the structures are not shared: only the
>>>> cache-lines are shared, because the structures happen to be on the same
>>>> cache line.
>>>>
>>>> So for allocation of individual objects which are meant to be per-cpu,
>>>> e.g. a structure controlling the per-cpu buffer, the allocator can put
>>>> one structure next to another (belonging to another cpu), thus causing
>>>> cache line bouncing.
>>>>
>>>> This phenomenon is called "false sharing".
>>>>
>>>
>>> Very nice. That clarify yes!
>>>
>>> However, please refer to Intel? 64 and IA-32 Architectures Software
>>> Developer's Manual Volume 3A: System Programming Guide.
>>>
>>> http://www.intel.com/Assets/PDF/manual/253668.pdf
>>>
>>> P. 527, Table 11-1
>>>
>>> ? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
>>>   microarchitecture): 8-KByte, 4-way set associative, 64-byte cache line
>>> size.
>>> ? Pentium 4 and Intel Xeon processors (Based on Intel NetBurst
>>>   microarchitecture): 16-KByte, 8-way set associative, 64-byte cache line
>>> size.
>>
>> Dunno why the Linux kernel choses that for P4. But we definitely have to
>> handle NUMA systems.
>>
>
> arch_numa.h ... possible?

See my comment to Alexandre about multiplying the number of targets
needlessly. Which one will be chosen by distros ?

We'll do it if you can find a real-world benchmark that is affected by
this. Good luck ;)

Mathieu

>
>> Mathieu
>>
>>>
>>> David
>>>
>>>> Mathieu
>>>>
>>>>>
>>>>> Thanks for your help on that!
>>>>> David
>>>>>
>>>>
>>>
>>> --
>>> David Goulet
>>> LTTng project, DORSAL Lab.
>>>
>>> PGP/GPG : 1024D/16BD8563
>>> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>>>
>>
>
> -- 
> David Goulet
> LTTng project, DORSAL Lab.
>
> PGP/GPG : 1024D/16BD8563
> BE3C 672B 9331 9796 291A  14C6 4AF7 C14B 16BD 8563
>

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com