On 12/29/2023 2:09 PM, Chris M. Thomasson wrote:
> On 12/29/2023 8:01 AM, Scott Lurndal wrote:
>> page 2-35 in the_Intel Pentium 4 Processor Optimization_
>> manual.
>
> I think it was in chapter 5 of Developing Multithreaded Applications: A
> Platform Consistent Approach cannot remember the damn section right now.

Wait a minute! I might have found it, lets see:

https://www.intel.com/content/dam/www/public/us/en/documents/training/developing-multithreaded-applications.pdf

Ahhh section 5.3! Nice! I read this a while back, before 2005.

Thanks for sparking my memory Scott.

Am 29.12.2023 um 23:12 schrieb Chris M. Thomasson:

> Wait a minute! I might have found it, lets see:
> https://www.intel.com/content/dam/www/public/us/en/documents/training/developing-multithreaded-applications.pdf
> Ahhh section 5.3! Nice! I read this a while back, before 2005.

This is nonsense what it says if the cache is really four-way
associative like in the other paper mentioned here. And of
course that has nothing to do with false sharing

On 12/29/2023 8:42 PM, Bonita Montero wrote:
> Am 29.12.2023 um 23:12 schrieb Chris M. Thomasson:
>
>> Wait a minute! I might have found it, lets see:
>> https://www.intel.com/content/dam/www/public/us/en/documents/training/developing-multithreaded-applications.pdf
>> Ahhh section 5.3! Nice! I read this a while back, before 2005.
>
> This is nonsense what it says if the cache is really four-way
> associative like in the other paper mentioned here. And of
> course that has nothing to do with false sharing

You should write Intel a letter. ;^o

Am 29.12.2023 um 18:29 schrieb Kaz Kylheku:

> I explained it. The allocation is not used. When you call alloca(n),
> the stack pointer moves by n bytes. If you then call a function,
> its stack frame will be offset by that much (plus any alignment if
> n is not aligned).

According to the paper Scott mentioned the associativity of the
Pentium 4's L1 data cache is four. With that it's not necessary
to have such aliasing preventions.

On 2023-12-29, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 12/29/2023 2:09 PM, Chris M. Thomasson wrote:
>> On 12/29/2023 8:01 AM, Scott Lurndal wrote:
>>> page 2-35 in the_Intel Pentium 4 Processor Optimization_
>>> manual.
>>
>> I think it was in chapter 5 of Developing Multithreaded Applications: A
>> Platform Consistent Approach cannot remember the damn section right now.
>
> Wait a minute! I might have found it, lets see:
>
> https://www.intel.com/content/dam/www/public/us/en/documents/training/developing-multithreaded-applications.pdf
>
> Ahhh section 5.3! Nice! I read this a while back, before 2005.

Wow, I guessed that one. Elsewhere in the thread, I made a remark
similar to "imagine that thread stacks are aligned at an address like
nnnnFFFF" I.e. the top of the stack starts at the top of a 64 kB
aligned window. I was exactly thinking of a typical L1 cache size
from aroudn that era, in fact.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 2023-12-30, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 29.12.2023 um 23:12 schrieb Chris M. Thomasson:
>
>> Wait a minute! I might have found it, lets see:
>> https://www.intel.com/content/dam/www/public/us/en/documents/training/developing-multithreaded-applications.pdf
>> Ahhh section 5.3! Nice! I read this a while back, before 2005.
>
> This is nonsense what it says if the cache is really four-way
> associative like in the other paper mentioned here. And of
> course that has nothing to do with false sharing

If it's four way associative, you star to have a performance problem as
soon as five things collide on it. For instance, suppose you have two
thread stack tops mapped to the same cache lines, plus three more data
structures heavily being accessed.

Oh, and the above Intel paper does actually mention alloca:

"The easiest way to adjust the initial stack address for each thread is
to call the memory allocation function, _alloca, with varying byte
amounts in the intermediate thread function."

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Am 30.12.2023 um 05:56 schrieb Kaz Kylheku:

> If it's four way associative, you star to have a performance problem as
> soon as five things collide on it. ...

With four-way associativity that's rather unlikely.

On 2023-12-30, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 30.12.2023 um 05:56 schrieb Kaz Kylheku:
>
>> If it's four way associative, you star to have a performance problem as
>> soon as five things collide on it. ...
>
> With four-way associativity that's rather unlikely.

Under four-way associativity, five isn't greater than four?

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Am 30.12.2023 um 06:51 schrieb Kaz Kylheku:

> Under four-way associativity, five isn't greater than four?

Two-way associativeness would leave no space if both threads have
synchronous stack frames. With four-way associativeness there's
not much likehood for that to happen.

On 29/12/2023 17:04, Bonita Montero wrote:
> Am 29.12.2023 um 13:56 schrieb David Brown:
>
>> There is nothing different from alloca() and ordinary stack
>> allocations.  But alloca() makes it quick and easy to make large
>> allocations, and to do so with random sizes (or at least sizes that
>> differ significantly between threads, even if they are running the
>> same code).
>
> I've got my own class overflow_array<> which is like an array<> and a
> vector<>. If you append more than the internal array<> can handle the
> objects are moved to an internal vector. I think Boost's small_array
> is similar to that.

I'm sure that's all very nice, but it is completely and utterly
irrelevant to the issue being discussed. Perhaps you didn't understand
your own post?

>
>> Without  alloca(), you'd need to do something like arranging to call a
>> recursive  function a random number of times before it then calls the
>> next bit of  code in your thread.  alloca() is simply far easier and
>> faster.
>
> You've got strange ideas. alloca() has been completely removed from the
> Linux kernel.

Citation? You are usually wrong in your claims, or at least mixed-up,
so I won't trust you without evidence. (That does not mean you are
wrong here - I don't know either way.)

Of course, avoiding alloca() within the kernel is, again, utterly
irrelevant to the point under discussion.

> The point is that if there's a fixed upper limit you would
> allocate you could allocate it always statically.
>

No, that would be useless.

The idea is to have /different/ allocation sizes in different threads,
so that the different threads have their stacks at wildly different
address bits in their tags for the processor caches.

I can't tell you how helpful or not this may be in practice. I am
merely trying to explain to you what the idea is, since you said you did
not understand it.

On 12/29/2023 8:45 PM, Bonita Montero wrote:
> Am 29.12.2023 um 18:29 schrieb Kaz Kylheku:
>
>> I explained it. The allocation is not used. When you call alloca(n),
>> the stack pointer moves by n bytes. If you then call a function,
>> its stack frame will be offset by that much (plus any alignment if
>> n is not aligned).
>
> According to the paper Scott mentioned the associativity of the
> Pentium 4's L1 data cache is four. With that it's not necessary
> to have such aliasing preventions.
>

Huh? Wow, you really need to write Intel a letter about it wrt their
older hyperthreaded processors! Although, it seems like you simply do
not actually _understand_ what is going on here...

Intel's suggestions for how to mitigate the problem in their earlier
hyperhtreaded processors actually worked wrt improving performance. Keep
in mind this was a while back in 2004-2005. I am happy that the way back
machine has my older code.

On 12/29/2023 8:51 PM, Kaz Kylheku wrote:
> On 2023-12-29, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 12/29/2023 2:09 PM, Chris M. Thomasson wrote:
>>> On 12/29/2023 8:01 AM, Scott Lurndal wrote:
>>>> page 2-35 in the_Intel Pentium 4 Processor Optimization_
>>>> manual.
>>>
>>> I think it was in chapter 5 of Developing Multithreaded Applications: A
>>> Platform Consistent Approach cannot remember the damn section right now.
>>
>> Wait a minute! I might have found it, lets see:
>>
>> https://www.intel.com/content/dam/www/public/us/en/documents/training/developing-multithreaded-applications.pdf
>>
>> Ahhh section 5.3! Nice! I read this a while back, before 2005.
>
> Wow, I guessed that one. Elsewhere in the thread, I made a remark
> similar to "imagine that thread stacks are aligned at an address like
> nnnnFFFF" I.e. the top of the stack starts at the top of a 64 kB
> aligned window. I was exactly thinking of a typical L1 cache size
> from aroudn that era, in fact.
>

Yup! You pretty much got it. Thanks Kaz )

On 2023-12-30, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 30.12.2023 um 06:51 schrieb Kaz Kylheku:
>
>> Under four-way associativity, five isn't greater than four?
>
> Two-way associativeness would leave no space if both threads have
> synchronous stack frames. With four-way associativeness there's
> not much likehood for that to happen.

My comment makes it clear that there are two thread stacks vying
for that cache line, plus a couple of other accesses that
are not thread stacks.

(By the way, set associative caches don't always have full LRU
replacement strategies.)

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 12/30/2023 11:58 AM, Chris M. Thomasson wrote:
> On 12/29/2023 8:45 PM, Bonita Montero wrote:
>> Am 29.12.2023 um 18:29 schrieb Kaz Kylheku:
>>
>>> I explained it. The allocation is not used. When you call alloca(n),
>>> the stack pointer moves by n bytes. If you then call a function,
>>> its stack frame will be offset by that much (plus any alignment if
>>> n is not aligned).
>>
>> According to the paper Scott mentioned the associativity of the
>> Pentium 4's L1 data cache is four. With that it's not necessary
>> to have such aliasing preventions.
>>
>
> Huh? Wow, you really need to write Intel a letter about it wrt their
> older hyperthreaded processors! Although, it seems like you simply do
> not actually _understand_ what is going on here...
>
> Intel's suggestions for how to mitigate the problem in their earlier
> hyperhtreaded processors actually worked wrt improving performance. Keep
> in mind this was a while back in 2004-2005. I am happy that the way back
> machine has my older code.

Oh, come on, Chris. It's clear that Bonita knows more about what's
going on inside an Intel processor than Intel does.

Am 30.12.2023 um 20:58 schrieb Chris M. Thomasson:

> Huh? Wow, you really need to write Intel a letter about it wrt their
> older hyperthreaded processors! ...

The suggestion Intel made at this point is superfluous.

> Intel's suggestions for how to mitigate the problem in their earlier
> hyperhtreaded processors actually worked wrt improving performance. ...

I'm pretty sure they never ran the numbers on that.

Am 30.12.2023 um 21:35 schrieb Kaz Kylheku:

> My comment makes it clear that there are two thread stacks
> vying for that cache line, plus a couple of other accesses
> that are not thread stacks.

With four way associativity that's rather unlikely to happen.

On 2023-12-31, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 30.12.2023 um 21:35 schrieb Kaz Kylheku:
>
>> My comment makes it clear that there are two thread stacks
>> vying for that cache line, plus a couple of other accesses
>> that are not thread stacks.
>
> With four way associativity that's rather unlikely to happen.

What? The associativity of the cache is not the determiner of
program behavior; if the program accesses five different
areas whose addresses are the same modulo 65536 bytes,
that happens whether there a direct mapped cache, fully
associative cache or no cache at all, or ...

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Am 31.12.2023 um 08:01 schrieb Kaz Kylheku:
> On 2023-12-31, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> Am 30.12.2023 um 21:35 schrieb Kaz Kylheku:
>>
>>> My comment makes it clear that there are two thread stacks
>>> vying for that cache line, plus a couple of other accesses
>>> that are not thread stacks.
>>
>> With four way associativity that's rather unlikely to happen.
>
> What? The associativity of the cache is not the determiner
> of program behavior; if the program accesses five different
> areas whose addresses are the same modulo 65536 bytes, ...

The set size is smaller than 64kB an of course there can be aliasing
but with four way associativity it's unlikely that there's a need to
control aliasing. And if the set size would be 64kB aliasing would be
even less likely through page colouring.

> that happens whether there a direct mapped cache, fully
> associative cache or no cache at all, or ...
>
>
>
>

Am 30.12.2023 um 19:27 schrieb David Brown:

> The idea is to have /different/ allocation sizes in different threads,
> so that the different threads have their stacks at wildly different
> address bits in their tags for the processor caches.

There's not much need to do that with four-way associativity.

> I can't tell you how helpful or not this may be in practice. ...

Even Intel cant't do that.

On 2023-12-31, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 31.12.2023 um 08:01 schrieb Kaz Kylheku:
>> On 2023-12-31, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> Am 30.12.2023 um 21:35 schrieb Kaz Kylheku:
>>>
>>>> My comment makes it clear that there are two thread stacks
>>>> vying for that cache line, plus a couple of other accesses
>>>> that are not thread stacks.
>>>
>>> With four way associativity that's rather unlikely to happen.
>>
>> What? The associativity of the cache is not the determiner
>> of program behavior; if the program accesses five different
>> areas whose addresses are the same modulo 65536 bytes, ...
>
> The set size is smaller than 64kB an of course there can be aliasing
> but with four way associativity it's unlikely that there's a need to
> control aliasing. And if the set size would be 64kB aliasing would be
> even less likely through page colouring.

When I describe a scenario in which five items are being frequently
accessed and collide to the same cache line, which is associative with a
set size of four, there is necessarily a conflict, because five is
greater than four.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Bonita Montero <Bonita.Montero@gmail.com> writes:
>Am 30.12.2023 um 05:56 schrieb Kaz Kylheku:
>
>> If it's four way associative, you star to have a performance problem as
>> soon as five things collide on it. ...
>
>With four-way associativity that's rather unlikely.
>

Why? The set selection is based on specific bits in the address. As soon
as a fifth address hits the set, you lose one of the existing lines.

Given the aligned stacks in the specified processor, the next function
called would _always_ overwrite the elements of the set(s) used by the calling function.

David Brown <david.brown@hesbynett.no> writes:
>On 29/12/2023 17:04, Bonita Montero wrote:

>>
>> You've got strange ideas. alloca() has been completely removed from the
>> Linux kernel.
>
>Citation? You are usually wrong in your claims, or at least mixed-up,
>so I won't trust you without evidence. (That does not mean you are
>wrong here - I don't know either way.)

Kernel threads generally run with a small, fixed stack. Stack-based
dynamic allocation is generally avoided. I don't know of any
hard restrictions, but I suspect that Linus would look askance
at it.

>
>Of course, avoiding alloca() within the kernel is, again, utterly
>irrelevant to the point under discussion.

Very true

On 12/30/2023 9:51 PM, Bonita Montero wrote:
> Am 30.12.2023 um 20:58 schrieb Chris M. Thomasson:
>
>> Huh? Wow, you really need to write Intel a letter about it wrt their
>> older hyperthreaded processors! ...
>
> The suggestion Intel made at this point is superfluous.
>
>> Intel's suggestions for how to mitigate the problem in their earlier
>> hyperhtreaded processors actually worked wrt improving performance. ...
>
> I'm pretty sure they never ran the numbers on that.
>
>

I am pretty sure you are trolling, Bonita?

On 12/30/2023 9:51 PM, Bonita Montero wrote:
> Am 30.12.2023 um 20:58 schrieb Chris M. Thomasson:
>
>> Huh? Wow, you really need to write Intel a letter about it wrt their
>> older hyperthreaded processors! ...
>
> The suggestion Intel made at this point is superfluous.
>
>> Intel's suggestions for how to mitigate the problem in their earlier
>> hyperhtreaded processors actually worked wrt improving performance. ...
>
> I'm pretty sure they never ran the numbers on that.

I am pretty sure you never read that paper before, even now.

>
>

On 12/30/2023 2:58 PM, red floyd wrote:
> On 12/30/2023 11:58 AM, Chris M. Thomasson wrote:
>> On 12/29/2023 8:45 PM, Bonita Montero wrote:
>>> Am 29.12.2023 um 18:29 schrieb Kaz Kylheku:
>>>
>>>> I explained it. The allocation is not used. When you call alloca(n),
>>>> the stack pointer moves by n bytes. If you then call a function,
>>>> its stack frame will be offset by that much (plus any alignment if
>>>> n is not aligned).
>>>
>>> According to the paper Scott mentioned the associativity of the
>>> Pentium 4's L1 data cache is four. With that it's not necessary
>>> to have such aliasing preventions.
>>>
>>
>> Huh? Wow, you really need to write Intel a letter about it wrt their
>> older hyperthreaded processors! Although, it seems like you simply do
>> not actually _understand_ what is going on here...
>>
>> Intel's suggestions for how to mitigate the problem in their earlier
>> hyperhtreaded processors actually worked wrt improving performance.
>> Keep in mind this was a while back in 2004-2005. I am happy that the
>> way back machine has my older code.
>
> Oh, come on, Chris.  It's clear that Bonita knows more about what's
> going on inside an Intel processor than Intel does.
>

Sometimes, I hope it is trolling. Afaict, Bonita seems to be full of
crap to a point where I actually feel sorry for the damn toilets it has
to punish.