On 12/24/2023 2:03 AM, Bonita Montero wrote:
> Am 23.12.2023 um 21:52 schrieb Chris M. Thomasson:
>
>> On 12/22/2023 8:55 AM, Bonita Montero wrote:
>
>>> False-sharing woudln't hurt my algorithm much since only the beginning
>>> and the end of the thread-local segment overlaps with other thread; but
>>> I do it anyway to have maximum performance.
>
>> That's is a good habit to get into. :^)
>
> I experimentally removed the masking of the lower bits of the
> partition bounds  according to the cacheline size and there was
> no measurable performance-loss.
>

Still, imvvho, it _is_ a good practice to get into wrt padding and
aligning...

Am 24.12.2023 um 22:24 schrieb Chris M. Thomasson:

> Still, imvvho, it _is_ a good practice to get into wrt padding and
> aligning...

With an upper bound of 2 ^ 32 I've got 131070 cachleines per thread.
If I have false sharing at the beginning and end of the range that
doesn't hurt much.

On 12/25/2023 9:00 PM, Bonita Montero wrote:
> Am 24.12.2023 um 22:24 schrieb Chris M. Thomasson:
>
>> Still, imvvho, it _is_ a good practice to get into wrt padding and
>> aligning...
>
> With an upper bound of 2 ^ 32 I've got 131070 cachleines per thread.
> If I have false sharing at the beginning and end of the range that
> doesn't hurt much.
>

Remember when Intel first started hyperthreading and god damn threads
could false share with each other (on the stacks!) the low and high 64
byte parts of the 128 byte cache lines? A workaround was to artificially
offset the threads stacks via alloca.

Am 26.12.2023 um 06:39 schrieb Chris M. Thomasson:

> Remember when Intel first started hyperthreading and god damn threads
> could false share with each other (on the stacks!) the low and high 64
> byte parts of the 128 byte cache lines? A workaround was to artificially
> offset the threads stacks via alloca.

If you have one core and two threads there's no false sharing.
It doesn't matter if the "conflicting" accesses come from either
thread of from one thread with that. False sharing is only pos-
sible with two cores or more.

On 12/26/2023 1:27 AM, Bonita Montero wrote:
> Am 26.12.2023 um 06:39 schrieb Chris M. Thomasson:
>
>> Remember when Intel first started hyperthreading and god damn threads
>> could false share with each other (on the stacks!) the low and high 64
>> byte parts of the 128 byte cache lines? A workaround was to
>> artificially offset the threads stacks via alloca.
>
> If you have one core and two threads there's no false sharing.

So, are you familiar with Intel's early hyper threading problem? There
was false sharing between the hyperhtreads. The workaround did improve
performance by quite a bit. IIRC, my older appcore project had this
workaround incorporated into it logic. I wrote that sucker back in very
early 2000's. Humm... I will try to find the exact line.

> It doesn't matter if the "conflicting" accesses come from either
> thread of from one thread with that. False sharing is only pos-
> sible with two cores or more.

On 2023-12-26, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 12/26/2023 1:27 AM, Bonita Montero wrote:
>> Am 26.12.2023 um 06:39 schrieb Chris M. Thomasson:
>>
>>> Remember when Intel first started hyperthreading and god damn threads
>>> could false share with each other (on the stacks!) the low and high 64
>>> byte parts of the 128 byte cache lines? A workaround was to
>>> artificially offset the threads stacks via alloca.
>>
>> If you have one core and two threads there's no false sharing.
>
> So, are you familiar with Intel's early hyper threading problem? There
> was false sharing between the hyperhtreads. The workaround did improve
> performance by quite a bit. IIRC, my older appcore project had this
> workaround incorporated into it logic. I wrote that sucker back in very
> early 2000's. Humm... I will try to find the exact line.

Could you be both right? The performance problem was real, but maybe
it wasn't "false sharing"? The hyper-thread are the same core; they
share the same caches.

Might you be describing a cache collision rather than false sharing?

A single processor can trigger degenerate cache uses (at any level
of a cache hierarchy). For instance, if pages of virtual memory
are accessed in certain patterns, they can trash the same TLB entry.

Was it perhaps the case that these thread stacks were allocated at such
a stride, that their addresses clashed on the same cache line set?

That could be a problem even on one processor, but it's obvious that
hyperthreading could exacerbate it because switches between hyperthreads
happen on a fine granularity. They don't get to run a full
scheduler-driven time quantum. A low-level processor event like a
pipeline stall (or other resource issue) can drive a hyper thread
switch.

--
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/26/2023 3:35 PM, Kaz Kylheku wrote:
> On 2023-12-26, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 12/26/2023 1:27 AM, Bonita Montero wrote:
>>> Am 26.12.2023 um 06:39 schrieb Chris M. Thomasson:
>>>
>>>> Remember when Intel first started hyperthreading and god damn threads
>>>> could false share with each other (on the stacks!) the low and high 64
>>>> byte parts of the 128 byte cache lines? A workaround was to
>>>> artificially offset the threads stacks via alloca.
>>>
>>> If you have one core and two threads there's no false sharing.
>>
>> So, are you familiar with Intel's early hyper threading problem? There
>> was false sharing between the hyperhtreads. The workaround did improve
>> performance by quite a bit. IIRC, my older appcore project had this
>> workaround incorporated into it logic. I wrote that sucker back in very
>> early 2000's. Humm... I will try to find the exact line.
>
> Could you be both right? The performance problem was real, but maybe
> it wasn't "false sharing"? The hyper-thread are the same core; they
> share the same caches.
>
> Might you be describing a cache collision rather than false sharing?

Iirc, when I read the docs from Intel, it was the low 64 bytes being
falsely shared with the high 64 bytes of a 128 byte l2 cache line?

>
> A single processor can trigger degenerate cache uses (at any level
> of a cache hierarchy). For instance, if pages of virtual memory
> are accessed in certain patterns, they can trash the same TLB entry.
>
> Was it perhaps the case that these thread stacks were allocated at such
> a stride, that their addresses clashed on the same cache line set?
>
> That could be a problem even on one processor, but it's obvious that
> hyperthreading could exacerbate it because switches between hyperthreads
> happen on a fine granularity. They don't get to run a full
> scheduler-driven time quantum. A low-level processor event like a
> pipeline stall (or other resource issue) can drive a hyper thread
> switch.
>

Am 26.12.2023 um 21:24 schrieb Chris M. Thomasson:

> So, are you familiar with Intel's early hyper threading problem?
> There was false sharing between the ...

False sharing can only happen between different cores.

On 12/26/2023 3:37 PM, Chris M. Thomasson wrote:
> On 12/26/2023 3:35 PM, Kaz Kylheku wrote:
>> On 2023-12-26, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>> On 12/26/2023 1:27 AM, Bonita Montero wrote:
>>>> Am 26.12.2023 um 06:39 schrieb Chris M. Thomasson:
>>>>
>>>>> Remember when Intel first started hyperthreading and god damn threads
>>>>> could false share with each other (on the stacks!) the low and high 64
>>>>> byte parts of the 128 byte cache lines? A workaround was to
>>>>> artificially offset the threads stacks via alloca.
>>>>
>>>> If you have one core and two threads there's no false sharing.
>>>
>>> So, are you familiar with Intel's early hyper threading problem? There
>>> was false sharing between the hyperhtreads. The workaround did improve
>>> performance by quite a bit. IIRC, my older appcore project had this
>>> workaround incorporated into it logic. I wrote that sucker back in very
>>> early 2000's. Humm... I will try to find the exact line.
>>
>> Could you be both right? The performance problem was real, but maybe
>> it wasn't "false sharing"? The hyper-thread are the same core; they
>> share the same caches.
>>
>> Might you be describing a cache collision rather than false sharing?
>
> Iirc, when I read the docs from Intel, it was the low 64 bytes being
> falsely shared with the high 64 bytes of a 128 byte l2 cache line?

Something about false interference between threads that should not even
be interacting with one another to begin with. It was a problem. The fix
was based on alloca, so that is something to ponder on.

>
>
>
>>
>> A single processor can trigger degenerate cache uses (at any level
>> of a cache hierarchy). For instance, if pages of virtual memory
>> are accessed in certain patterns, they can trash the same TLB entry.
>>
>> Was it perhaps the case that these thread stacks were allocated at such
>> a stride, that their addresses clashed on the same cache line set?
>>
>> That could be a problem even on one processor, but it's obvious that
>> hyperthreading could exacerbate it because switches between hyperthreads
>> happen on a fine granularity. They don't get to run a full
>> scheduler-driven time quantum. A low-level processor event like a
>> pipeline stall (or other resource issue) can drive a hyper thread
>> switch.
>>
>

Am 27.12.2023 um 06:59 schrieb Chris M. Thomasson:

> Something about false interference between threads that should not even
> be interacting with one another to begin with. It was a problem. The fix
> was based on alloca, so that is something to ponder on.;

Like with any SMT-core there could be cache-thrashing between the
cores. The L1 data cache was only 8kB, maybe only two was associative
that could be thrashing between the cores. But I've no clue what this
would have to to with alloca().

On 2023-12-27, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 27.12.2023 um 06:59 schrieb Chris M. Thomasson:
>
>> Something about false interference between threads that should not even
>> be interacting with one another to begin with. It was a problem. The fix
>> was based on alloca, so that is something to ponder on.;
>
> Like with any SMT-core there could be cache-thrashing between the
> cores. The L1 data cache was only 8kB, maybe only two was associative
> that could be thrashing between the cores. But I've no clue what this
> would have to to with alloca().

Say you have thread stacks that are offset by some power of two amount,
like a megabyte. Stack addresses at the same depth (like the local
variables of threads executing the same function) are likely to collide
on the same cache set (at different levels of the caching hierachy: L1,
L2, translation caches).

With alloca, since it moves the stack pointer, we can carve variable
amounts of stack space to randomize the stack offsets (before calling
the work functions). In different threads, we use differently-sized
alloca allocations.

--
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 27.12.2023 um 21:49 schrieb Kaz Kylheku:

> Say you have thread stacks that are offset by some power of two amount,
> like a megabyte. Stack addresses at the same depth (like the local
> variables of threads executing the same function) are likely to collide
> on the same cache set (at different levels of the caching hierachy: L1,
> L2, translation caches).
>> With alloca, since it moves the stack pointer, we can carve variable
> amounts of stack space to randomize the stack offsets (before calling
> the work functions). In different threads, we use differently-sized
> alloca allocations.

That's not sth. alloca() could alleviate. The startup-code inside the
userspace-part of the thread should randomize the starting address of
the stack within the size of a set.
Most resources on the net say that the Pentium 4's L1 data cache asso-
ciativity is eight, so there's not much chance of aliasing inside the
L1D cache.

On 12/28/2023 3:00 AM, Bonita Montero wrote:
> Am 27.12.2023 um 21:49 schrieb Kaz Kylheku:
>
>> Say you have thread stacks that are offset by some power of two amount,
>> like a megabyte. Stack addresses at the same depth (like the local
>> variables of threads executing the same function) are likely to collide
>> on the same cache set (at different levels of the caching hierachy: L1,
>> L2, translation caches).
> >> With alloca, since it moves the stack pointer, we can carve variable
>> amounts of stack space to randomize the stack offsets (before calling
>> the work functions). In different threads, we use differently-sized
>> alloca allocations.
>
> That's not sth. alloca() could alleviate. The startup-code inside the
> userspace-part of the thread should randomize the starting address of
> the stack within the size of a set.
> Most resources on the net say that the Pentium 4's L1 data cache asso-
> ciativity is eight, so there's not much chance of aliasing inside the
> L1D cache.
>

The use of alloca to try to get around the problem in their (Intel's)
early hyperthreaded processors was real, and actually helped. It was in
the Intel docs.

Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:

> The use of alloca to try to get around the problem in their (Intel's)
> early hyperthreaded processors was real, and actually helped. It was in
> the Intel docs.

I don't believe it.

On 12/28/2023 7:17 PM, Bonita Montero wrote:
> Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:
>
>> The use of alloca to try to get around the problem in their (Intel's)
>> early hyperthreaded processors was real, and actually helped. It was
>> in the Intel docs.
>
> I don't believe it.
>

Why not?

Am 29.12.2023 um 05:58 schrieb Chris M. Thomasson:

> On 12/28/2023 7:17 PM, Bonita Montero wrote:

>> Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:

>>> The use of alloca to try to get around the problem in their (Intel's)
>>> early hyperthreaded processors was real, and actually helped. It was
>>> in the Intel docs.

>> I don't believe it.

> Why not?

Because I don't understand what's different with the access pattern
of alloca() and usual stack allocation. And if I google for "alloca
Pentium 4 site:intel.com" I can't find anything that fits.

On 29/12/2023 10:58, Bonita Montero wrote:
> Am 29.12.2023 um 05:58 schrieb Chris M. Thomasson:
>
>> On 12/28/2023 7:17 PM, Bonita Montero wrote:
>
>>> Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:
>
>>>> The use of alloca to try to get around the problem in their
>>>> (Intel's) early hyperthreaded processors was real, and actually
>>>> helped. It was in the Intel docs.
>
>>> I don't believe it.
>
>> Why not?
>
> Because I don't understand what's different with the access pattern
> of alloca() and usual stack allocation. And if I google for "alloca
> Pentium 4 site:intel.com" I can't find anything that fits.
>

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). 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.

Bonita Montero <Bonita.Montero@gmail.com> writes:
>Am 29.12.2023 um 05:58 schrieb Chris M. Thomasson:
>
>> On 12/28/2023 7:17 PM, Bonita Montero wrote:
>
>>> Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:
>
>>>> The use of alloca to try to get around the problem in their (Intel's)
>>>> early hyperthreaded processors was real, and actually helped. It was
>>>> in the Intel docs.
>
>>> I don't believe it.
>
>> Why not?
>
>Because I don't understand what's different with the access pattern
>of alloca() and usual stack allocation. And if I google for "alloca
>Pentium 4 site:intel.com" I can't find anything that fits.
>

See page 2-35 in the _Intel Pentium 4 Processor Optimization_
manual.

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.

> 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. The point is that if there's a fixed upper limit you would
allocate you could allocate it always statically.

Am 29.12.2023 um 17:01 schrieb Scott Lurndal:

> See page 2-35 in the _Intel Pentium 4 Processor Optimization_
> manual.

Where can I find sth. referring to alloca() there ?

On 2023-12-29, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 29.12.2023 um 05:58 schrieb Chris M. Thomasson:
>
>> On 12/28/2023 7:17 PM, Bonita Montero wrote:
>
>>> Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:
>
>>>> The use of alloca to try to get around the problem in their (Intel's)
>>>> early hyperthreaded processors was real, and actually helped. It was
>>>> in the Intel docs.
>
>>> I don't believe it.
>
>> Why not?
>
> Because I don't understand what's different with the access pattern
> of alloca() and usual stack allocation. And if I google for "alloca
> Pentium 4 site:intel.com" I can't find anything that fits.

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).

--
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 24/12/2023 08:36, Tim Rentsch wrote:
> Depending on how the code is written, no modulo operations need
> to be done, because they will be optimized away and done at
> compile time. If we look at multiplying two numbers represented
> by bits in bytes i and j, the two numbers are
>
> i*30 + a
> j*30 + b
>
> for some a and b in { 1, 7, 11, 13 17, 19, 23, 29 }.
>
> The values we're interested in are the index of the product and
> the residue of the product, namely
>
> (i*30+a) * (j*30+b) / 30 (for the index)
> (i*30+a) * (j*30+b) % 30 (for the residue)
>
> Any term with a *30 in the numerator doesn't contribute to
> the residue, and also can be combined with the by-30 divide
> for computing the index. Thus these expressions can be
> rewritten as
>
> i*30*j + i*b + j*a + (a*b/30) (for the index)
> a*b%30 (for the residue)
>
> When a and b have values that are known at compile time,
> neither the divide nor the remainder result in run-time
> operations being done; all of that heavy lifting is
> optimized away and done at compile time. Of course there
> are some multiplies, but they are cheaper than divides, and
> also can be done in parallel. (The multiplication a*b also
> can be done at compile time.)
>
> The residue needs to be turned into a bit mask to do the
> logical operation on the byte of bits, but here again that
> computation can be optimized away and done at compile time.
>
> Does that all make sense?

Right now, no. But that's me. I'll flag it to read again when I've had a
better night's sleep.

Andy

On 12/29/2023 8:06 AM, Bonita Montero wrote:
> Am 29.12.2023 um 17:01 schrieb Scott Lurndal:
>
>> See page 2-35 in the _Intel Pentium 4 Processor Optimization_
>> manual.
>
> Where can I find sth. referring to alloca() there ?

Huh?

On 12/28/2023 7:17 PM, Bonita Montero wrote:
> Am 29.12.2023 um 00:38 schrieb Chris M. Thomasson:
>
>> The use of alloca to try to get around the problem in their (Intel's)
>> early hyperthreaded processors was real, and actually helped. It was
>> in the Intel docs.
>
> I don't believe it.
>

I actually found an early version my old code on the wayback machine
that does this. Take note of the following function. It did improve
performance way back on those early hyperthreaded processors.

https://web.archive.org/web/20060214112446/http://appcore.home.comcast.net/appcore/src/ac_thread_c.html
___________________
void* AC_CDECL
prv_thread_entry
( void *state )
{ int ret;
void *uret;
ac_thread_t *_this = state;

ret = pthread_setspecific
( g_tls_key,
_this );
if ( ret ) { assert( ! ret ); abort(); }

if ( _this->id < 64 )
{
AC_OS_ALLOCA( 2048 * _this->id );
uret = _this->fp_entry( (void*)_this->state );
}

else
{
uret = _this->fp_entry( (void*)_this->state );
}

return uret;
} ___________________

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.