Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

: is not an identifier


devel / comp.arch / On the power of zero-cycle renaming

SubjectAuthor
* On the power of zero-cycle renamingTerje Mathisen
+- Re: On the power of zero-cycle renamingTim Rentsch
+* Re: On the power of zero-cycle renamingAnton Ertl
|`* Re: On the power of zero-cycle renamingTerje Mathisen
| `* Re: On the power of zero-cycle renamingMichael S
|  `* Re: On the power of zero-cycle renamingTerje Mathisen
|   +* Re: On the power of zero-cycle renamingMichael S
|   |`- Re: On the power of zero-cycle renamingTerje Mathisen
|   `* Re: On the power of zero-cycle renamingAnton Ertl
|    `* Re: On the power of zero-cycle renamingTerje Mathisen
|     +- Re: On the power of zero-cycle renamingAnton Ertl
|     +* Re: On the power of zero-cycle renamingMichael S
|     |`- Re: On the power of zero-cycle renamingTerje Mathisen
|     `* Re: On the power of zero-cycle renamingTimothy McCaffrey
|      `* Re: On the power of zero-cycle renamingTerje Mathisen
|       +- Re: On the power of zero-cycle renamingAnton Ertl
|       `* Re: On the power of zero-cycle renamingAnton Ertl
|        `* Re: On the power of zero-cycle renamingTerje Mathisen
|         `* Re: On the power of zero-cycle renamingStefan Monnier
|          `- Re: On the power of zero-cycle renamingTerje Mathisen
`- Re: On the power of zero-cycle renamingThomas Koenig

1
On the power of zero-cycle renaming

<sr6dcr$80b$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22778&group=comp.arch#22778

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!To5nvU/sTaigmVbgRJ05pQ.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: On the power of zero-cycle renaming
Date: Thu, 6 Jan 2022 10:39:47 +0100
Organization: Aioe.org NNTP Server
Message-ID: <sr6dcr$80b$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="8203"; posting-host="To5nvU/sTaigmVbgRJ05pQ.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Mozilla-News-Host: news://news.aioe.org:119
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Thu, 6 Jan 2022 09:39 UTC

In the recently completed Advent of Code 2021 cycle, one of the puzzles
was called Lanternfish, where you had a population of these
light-flashing fish: Each fish would count down from 6 to 0, then it
would flash, reset to 6 and produce an offspring which needed two
additional days to mature, i.e. it would start at 8.

Directly modelling each fish was doable for 10+ generations (part 1
asked for 80 days), but part 2 required 256 days, at which point you had
to realize that you didn't need to model individual fishes, only the
counts of how many fish were at each countdown level. This insight
speeded up the process by many orders of magnitude and made the second
part easy instead of unfeasible.

Now we get to the interesting part for c.arch:

The obvious algorithm have a fish[9] array with counts for 0..8, then on
each day you do:

tmp = fish[0]; for (i = 1; i < 9; i++) fish[i-1]=fish[i];
fish[6]+=tmp; fish[8]=tmp;

and this runs very well indeed.

First optimization extends the array to 266 entries and simply moves the
front pointer instead of rotating, avoiding all of the copying:

f[7]+=f[9]=f[0]; f++;

Alternatively, make the array 16 entries long and do all accesses as
above, but masked by 15:

fish[(day+7)&15]+=fish[(day+9)&15]=fish[day&15]; day++;

However, Robert Collins came up with the to me non-obvious idea of
moving it all into registers and manually rotating them (using Rust):

for _ in 0..days {
tmp=t0;t0=t1;t1=t2;t2=t3;t4=t5;t5=t6;t6=t7+tmp;t7=t8;t8=tmp;
}

So this is 8 reg-reg moves and a single addition, plus the
tw-instruction loop overhead, but due to how modern OoO cpus can handle
such moves in the decoder, using zero execution slots, the running time
dropped by an order of magnitude compared to rotating memory variables.
(It did each iteration in ~0.5 cycles, so it had to run two
iterations/22 instructions per cycle!)

At this point I tried to unroll by four, which reduced the number of
reg-reg MOVes to 5 and did 4 ADDs per iteration:

u64 processdays(int days)
{ u64 tmp0, tmp1, tmp2, tmp3, t0 = fish[0], t1 = fish[1], t2 =
fish[2], t3 = fish[3],
t4 = fish[4], t5 = fish[5], t6 = fish[6], t7 = fish[7], t8 =
fish[8];

for (int d = 3; d < days; d += 4) {
tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;
t0 = t4, t1 = t5, t2 = t6;
t3 = t7 + tmp0;
t4 = t8 + tmp1;
t5 = tmp0 + tmp2;
t6 = tmp1 + tmp3;
t7 = tmp2;
t8 = tmp3;
}
return t0 + t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8;
}

This was less than twice as fast as the single update/iteration, so the
OoO magic did a very good job with Robert's original scalar version.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<867dbcydup.fsf@linuxsc.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22779&group=comp.arch#22779

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: tr.17...@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Thu, 06 Jan 2022 09:26:54 -0800
Organization: A noiseless patient Spider
Lines: 109
Message-ID: <867dbcydup.fsf@linuxsc.com>
References: <sr6dcr$80b$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="71316d3c1ed13b917214e5aac7839fb5";
logging-data="20274"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18DycKSHK8UTUUZ5sA2bH+aOUK2Z6rbCcY="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:rFaaE4HINil+YhCuMzwv5C5irJI=
sha1:OMq/TClNajvtcCfZCuxpU3mkM/g=
 by: Tim Rentsch - Thu, 6 Jan 2022 17:26 UTC

Terje Mathisen <terje.mathisen@tmsw.no> writes:

> In the recently completed Advent of Code 2021 cycle, one of the
> puzzles was called Lanternfish, where you had a population of these
> light-flashing fish: Each fish would count down from 6 to 0, then it
> would flash, reset to 6 and produce an offspring which needed two
> additional days to mature, i.e. it would start at 8.
>
> Directly modelling each fish was doable for 10+ generations (part 1
> asked for 80 days), but part 2 required 256 days, at which point you
> had to realize that you didn't need to model individual fishes, only
> the counts of how many fish were at each countdown level. This insight
> speeded up the process by many orders of magnitude and made the second
> part easy instead of unfeasible.
>
> Now we get to the interesting part for c.arch:
>
> The obvious algorithm have a fish[9] array with counts for 0..8, then
> on each day you do:
>
> tmp = fish[0]; for (i = 1; i < 9; i++) fish[i-1]=fish[i];
> fish[6]+=tmp; fish[8]=tmp;
>
> and this runs very well indeed.
>
> First optimization extends the array to 266 entries and simply moves
> the front pointer instead of rotating, avoiding all of the copying:
>
> f[7]+=f[9]=f[0]; f++;
>
> Alternatively, make the array 16 entries long and do all accesses as
> above, but masked by 15:
>
> fish[(day+7)&15]+=fish[(day+9)&15]=fish[day&15]; day++;
>
> However, Robert Collins came up with the to me non-obvious idea of
> moving it all into registers and manually rotating them (using Rust):
>
> for _ in 0..days {
> tmp=t0;t0=t1;t1=t2;t2=t3;t4=t5;t5=t6;t6=t7+tmp;t7=t8;t8=tmp;
> }
>
> So this is 8 reg-reg moves and a single addition, plus the
> tw-instruction loop overhead, but due to how modern OoO cpus can
> handle such moves in the decoder, using zero execution slots, the
> running time dropped by an order of magnitude compared to rotating
> memory variables. (It did each iteration in ~0.5 cycles, so it had to
> run two iterations/22 instructions per cycle!)
>
> At this point I tried to unroll by four, which reduced the number of
> reg-reg MOVes to 5 and did 4 ADDs per iteration:
>
> u64 processdays(int days)
> {
> u64 tmp0, tmp1, tmp2, tmp3, t0 = fish[0], t1 = fish[1], t2 =
> fish[2], t3 = fish[3],
> t4 = fish[4], t5 = fish[5], t6 = fish[6], t7 = fish[7], t8 =
> fish[8];
>
> for (int d = 3; d < days; d += 4) {
> tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;
> t0 = t4, t1 = t5, t2 = t6;
> t3 = t7 + tmp0;
> t4 = t8 + tmp1;
> t5 = tmp0 + tmp2;
> t6 = tmp1 + tmp3;
> t7 = tmp2;
> t8 = tmp3;
> }
> return t0 + t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8;
> }
>
> This was less than twice as fast as the single update/iteration, so
> the OoO magic did a very good job with Robert's original scalar
> version.

How about this:

typedef unsigned long Count;

Count
fish_after_N_days( Count const F[9], Count days ){
Count
a=F[0], b=F[1], c=F[2], d=F[3], e=F[4], f=F[5], g=F[6], h=F[7], i=F[8];

while( days > 8 ){
h += a;
i += b;
a += c;
b += d;
c += e;
d += f;
e += g;
f += h;
g += i;
days -= 9;
}

h += days > 0 ? a : 0;
i += days > 1 ? b : 0;
a += days > 2 ? c : 0;
b += days > 3 ? d : 0;
c += days > 4 ? e : 0;
d += days > 5 ? f : 0;
e += days > 6 ? g : 0;
f += days > 7 ? h : 0;

return a+b+c+d+e+f+g+h+i;
}

Re: On the power of zero-cycle renaming

<2022Jan6.193456@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22782&group=comp.arch#22782

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Thu, 06 Jan 2022 18:34:56 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 69
Message-ID: <2022Jan6.193456@mips.complang.tuwien.ac.at>
References: <sr6dcr$80b$1@gioia.aioe.org>
Injection-Info: reader02.eternal-september.org; posting-host="b68c6f51acff0547f87ae0126a968f4c";
logging-data="29613"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/irOU8DjQNq4uqO/uR60+s"
Cancel-Lock: sha1:C5Mf8Er0wKuHIgY2Mcjg4uj0mn4=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Thu, 6 Jan 2022 18:34 UTC

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>However, Robert Collins came up with the to me non-obvious idea of
>moving it all into registers and manually rotating them (using Rust):
>
>for _ in 0..days {
> tmp=t0;t0=t1;t1=t2;t2=t3;t4=t5;t5=t6;t6=t7+tmp;t7=t8;t8=tmp;
>}
>
>So this is 8 reg-reg moves and a single addition, plus the
>tw-instruction loop overhead, but due to how modern OoO cpus can handle
>such moves in the decoder, using zero execution slots, the running time
>dropped by an order of magnitude compared to rotating memory variables.
>(It did each iteration in ~0.5 cycles, so it had to run two
>iterations/22 instructions per cycle!)

Are you sure the compiler did not unroll it and eliminate many of the
moves? I know of no CPU that can feed 22 instructions per cycle into
the register renamer.

>At this point I tried to unroll by four, which reduced the number of
>reg-reg MOVes to 5 and did 4 ADDs per iteration:
>
>u64 processdays(int days)
>{
> u64 tmp0, tmp1, tmp2, tmp3, t0 = fish[0], t1 = fish[1], t2 =
>fish[2], t3 = fish[3],
> t4 = fish[4], t5 = fish[5], t6 = fish[6], t7 = fish[7], t8 =
>fish[8];
>
> for (int d = 3; d < days; d += 4) {
> tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;
> t0 = t4, t1 = t5, t2 = t6;
> t3 = t7 + tmp0;
> t4 = t8 + tmp1;
> t5 = tmp0 + tmp2;
> t6 = tmp1 + tmp3;
> t7 = tmp2;
> t8 = tmp3;
> }
> return t0 + t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8;
>}

Unrolling by 9 should make it possible to eliminate the moves
completely (modulo variable renaming). Whether it causes a speedup is
to be seen, but e.g., on a Skylake the register renamer can take 6
instructions/cycle, and the OoO engine can do 4 ALU ops/cycle, so I
expect a speedup.

The unrolled-by-9 loop might look as follows:

for (...; ...; d+=9) { // too lazy to work that out
t6=t7+t0; // first original iteration
t7=t8+t1; // second original iteration
t8=t0+t2;
t0=t1+t3;
t1=t2+t4;
t2=t3+t5;
t3=t4+t6;
t4=t5+t7;
t5=t6+t8;
}

Of course you need to do the extra iterations after (or maybe before)
this loop.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: On the power of zero-cycle renaming

<sr7k8e$1kjl$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22785&group=comp.arch#22785

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!Liunnst7X9VOeBBqqVtBCw.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Thu, 6 Jan 2022 21:42:54 +0100
Organization: Aioe.org NNTP Server
Message-ID: <sr7k8e$1kjl$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="53877"; posting-host="Liunnst7X9VOeBBqqVtBCw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Thu, 6 Jan 2022 20:42 UTC

Anton Ertl wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>> However, Robert Collins came up with the to me non-obvious idea of
>> moving it all into registers and manually rotating them (using Rust):
>>
>> for _ in 0..days {
>> tmp=t0;t0=t1;t1=t2;t2=t3;t4=t5;t5=t6;t6=t7+tmp;t7=t8;t8=tmp;
>> }
>>
>> So this is 8 reg-reg moves and a single addition, plus the
>> tw-instruction loop overhead, but due to how modern OoO cpus can handle
>> such moves in the decoder, using zero execution slots, the running time
>> dropped by an order of magnitude compared to rotating memory variables.
>> (It did each iteration in ~0.5 cycles, so it had to run two
>> iterations/22 instructions per cycle!)

The 3 GHz AMD Threadripper was timed at 40 ns (using 112M iterations
inside Criterion) for 256 iterations of the loop above, so that would be
120 clock cycles. OTOH, RObert Collins got 200 ns with inline timing
which is a much more believable 2.4 cycles/iteration.
>
> Are you sure the compiler did not unroll it and eliminate many of the
> moves? I know of no CPU that can feed 22 instructions per cycle into
> the register renamer.

I'm still not sure exactly what happens, but I extended the loop to run
1024 iterations, then I repeated the measurement 1E7 times and found
that the code below ran it in 700 clock cycles which is 3 cycles/iteration:
>
>> At this point I tried to unroll by four, which reduced the number of
>> reg-reg MOVes to 5 and did 4 ADDs per iteration:
>>
>> u64 processdays(int days)
>> {
>> u64 tmp0, tmp1, tmp2, tmp3, t0 = fish[0], t1 = fish[1], t2 =
>> fish[2], t3 = fish[3],
>> t4 = fish[4], t5 = fish[5], t6 = fish[6], t7 = fish[7], t8 =
>> fish[8];
>>
>> for (int d = 3; d < days; d += 4) {
>> tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;
>> t0 = t4, t1 = t5, t2 = t6;
>> t3 = t7 + tmp0;
>> t4 = t8 + tmp1;
>> t5 = tmp0 + tmp2;
>> t6 = tmp1 + tmp3;
>> t7 = tmp2;
>> t8 = tmp3;
>> }
>> return t0 + t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8;
>> }

The code generated was very straightforward, except for doing a two of
the reg-reg moves with LEA, probably to be able to use more execution
slots. It runs in just under 3 cycles/iteration.

$LL4@processday:

; 45 : tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;

lea rax, QWORD PTR [r9]
mov rdx, r11
lea rcx, QWORD PTR [r10]
mov r8, rbx

; 46 : t0 = t4, t1 = t5, t2 = t6;
; 47 : t3 = t7 + tmp0;

lea rbx, QWORD PTR [rax+r14]
mov r9, rdi

; 48 : t4 = t8 + tmp1;

lea rdi, QWORD PTR [rcx+r15]
mov r10, rsi

; 49 : t5 = tmp0 + tmp2;

lea rsi, QWORD PTR [rdx+rax]
mov r11, rbp

; 50 : t6 = tmp1 + tmp3;

lea rbp, QWORD PTR [r8+rcx]

; 51 : t7 = tmp2;

mov r14, rdx

; 52 : t8 = tmp3;

mov r15, r8
sub r12, 1
jne SHORT $LL4@processday

>
> Unrolling by 9 should make it possible to eliminate the moves
> completely (modulo variable renaming). Whether it causes a speedup is
> to be seen, but e.g., on a Skylake the register renamer can take 6
> instructions/cycle, and the OoO engine can do 4 ALU ops/cycle, so I
> expect a speedup.
>
> The unrolled-by-9 loop might look as follows:
>
> for (...; ...; d+=9) { // too lazy to work that out
> t6=t7+t0; // first original iteration
> t7=t8+t1; // second original iteration
> t8=t0+t2;
> t0=t1+t3;
> t1=t2+t4;
> t2=t3+t5;
> t3=t4+t6;
> t4=t5+t7;
> t5=t6+t8;
> }
>
> Of course you need to do the extra iterations after (or maybe before)
> this loop.

I will try your/Tim R's suggestion! I didn't manage to convince myself
that it would work out when I tried to manually construct the recurrence
for wider unrolls.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<sr7mcg$2jj$1@newsreader4.netcologne.de>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22787&group=comp.arch#22787

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!newsreader4.netcologne.de!news.netcologne.de!.POSTED.2001-4dd7-7488-0-7285-c2ff-fe6c-992d.ipv6dyn.netcologne.de!not-for-mail
From: tkoe...@netcologne.de (Thomas Koenig)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Thu, 6 Jan 2022 21:19:12 -0000 (UTC)
Organization: news.netcologne.de
Distribution: world
Message-ID: <sr7mcg$2jj$1@newsreader4.netcologne.de>
References: <sr6dcr$80b$1@gioia.aioe.org>
Injection-Date: Thu, 6 Jan 2022 21:19:12 -0000 (UTC)
Injection-Info: newsreader4.netcologne.de; posting-host="2001-4dd7-7488-0-7285-c2ff-fe6c-992d.ipv6dyn.netcologne.de:2001:4dd7:7488:0:7285:c2ff:fe6c:992d";
logging-data="2675"; mail-complaints-to="abuse@netcologne.de"
User-Agent: slrn/1.0.3 (Linux)
 by: Thomas Koenig - Thu, 6 Jan 2022 21:19 UTC

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:

> Directly modelling each fish was doable for 10+ generations (part 1
> asked for 80 days), but part 2 required 256 days, at which point you had
> to realize that you didn't need to model individual fishes, only the
> counts of how many fish were at each countdown level.

Certainly an important insight :-)

This is a population balance, similar to what people are doing modelling
particles or with polymer molecules.

Re: On the power of zero-cycle renaming

<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22789&group=comp.arch#22789

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:6214:d8e:: with SMTP id e14mr56134835qve.130.1641510752067;
Thu, 06 Jan 2022 15:12:32 -0800 (PST)
X-Received: by 2002:a05:6808:1283:: with SMTP id a3mr8096693oiw.110.1641510751844;
Thu, 06 Jan 2022 15:12:31 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Thu, 6 Jan 2022 15:12:31 -0800 (PST)
In-Reply-To: <sr7k8e$1kjl$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2a0d:6fc2:55b0:ca00:7948:7b7f:3434:a19b;
posting-account=ow8VOgoAAAAfiGNvoH__Y4ADRwQF1hZW
NNTP-Posting-Host: 2a0d:6fc2:55b0:ca00:7948:7b7f:3434:a19b
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at>
<sr7k8e$1kjl$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
Subject: Re: On the power of zero-cycle renaming
From: already5...@yahoo.com (Michael S)
Injection-Date: Thu, 06 Jan 2022 23:12:32 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 129
 by: Michael S - Thu, 6 Jan 2022 23:12 UTC

On Thursday, January 6, 2022 at 10:42:59 PM UTC+2, Terje Mathisen wrote:
> Anton Ertl wrote:
> > Terje Mathisen <terje.m...@tmsw.no> writes:
> >> However, Robert Collins came up with the to me non-obvious idea of
> >> moving it all into registers and manually rotating them (using Rust):
> >>
> >> for _ in 0..days {
> >> tmp=t0;t0=t1;t1=t2;t2=t3;t4=t5;t5=t6;t6=t7+tmp;t7=t8;t8=tmp;
> >> }
> >>
> >> So this is 8 reg-reg moves and a single addition, plus the
> >> tw-instruction loop overhead, but due to how modern OoO cpus can handle
> >> such moves in the decoder, using zero execution slots, the running time
> >> dropped by an order of magnitude compared to rotating memory variables.
> >> (It did each iteration in ~0.5 cycles, so it had to run two
> >> iterations/22 instructions per cycle!)
> The 3 GHz AMD Threadripper was timed at 40 ns (using 112M iterations
> inside Criterion) for 256 iterations of the loop above, so that would be
> 120 clock cycles. OTOH, RObert Collins got 200 ns with inline timing
> which is a much more believable 2.4 cycles/iteration.

Not really believable.
I don't think that there exist circumstances under which Zen3 can sustain more than 6 "normal" instructions per cycle.
May be, 7 or 8 when 1 or 2 of instructions are predicted branches. Or, more likely, still 6.
So, no less than 3.7 clocks for 22 "normal" instructions.
Could it be that in reality in Robert's test the core was running at 4.7 or 4.8 GHz rather than 3 GHz?

> >
> > Are you sure the compiler did not unroll it and eliminate many of the
> > moves? I know of no CPU that can feed 22 instructions per cycle into
> > the register renamer.
> I'm still not sure exactly what happens, but I extended the loop to run
> 1024 iterations, then I repeated the measurement 1E7 times and found
> that the code below ran it in 700 clock cycles which is 3 cycles/iteration:
> >
> >> At this point I tried to unroll by four, which reduced the number of
> >> reg-reg MOVes to 5 and did 4 ADDs per iteration:
> >>
> >> u64 processdays(int days)
> >> {
> >> u64 tmp0, tmp1, tmp2, tmp3, t0 = fish[0], t1 = fish[1], t2 =
> >> fish[2], t3 = fish[3],
> >> t4 = fish[4], t5 = fish[5], t6 = fish[6], t7 = fish[7], t8 =
> >> fish[8];
> >>
> >> for (int d = 3; d < days; d += 4) {
> >> tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;
> >> t0 = t4, t1 = t5, t2 = t6;
> >> t3 = t7 + tmp0;
> >> t4 = t8 + tmp1;
> >> t5 = tmp0 + tmp2;
> >> t6 = tmp1 + tmp3;
> >> t7 = tmp2;
> >> t8 = tmp3;
> >> }
> >> return t0 + t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8;
> >> }
> The code generated was very straightforward, except for doing a two of
> the reg-reg moves with LEA, probably to be able to use more execution
> slots. It runs in just under 3 cycles/iteration.
>
> $LL4@processday:
>
> ; 45 : tmp0 = t0, tmp1 = t1, tmp2 = t2, tmp3 = t3;
>
> lea rax, QWORD PTR [r9]
> mov rdx, r11
> lea rcx, QWORD PTR [r10]
> mov r8, rbx
>
> ; 46 : t0 = t4, t1 = t5, t2 = t6;
> ; 47 : t3 = t7 + tmp0;
>
> lea rbx, QWORD PTR [rax+r14]
> mov r9, rdi
>
> ; 48 : t4 = t8 + tmp1;
>
> lea rdi, QWORD PTR [rcx+r15]
> mov r10, rsi
>
> ; 49 : t5 = tmp0 + tmp2;
>
> lea rsi, QWORD PTR [rdx+rax]
> mov r11, rbp
>
> ; 50 : t6 = tmp1 + tmp3;
>
> lea rbp, QWORD PTR [r8+rcx]
>
> ; 51 : t7 = tmp2;
>
> mov r14, rdx
>
> ; 52 : t8 = tmp3;
>
> mov r15, r8
> sub r12, 1
> jne SHORT $LL4@processday
> >
> > Unrolling by 9 should make it possible to eliminate the moves
> > completely (modulo variable renaming). Whether it causes a speedup is
> > to be seen, but e.g., on a Skylake the register renamer can take 6
> > instructions/cycle, and the OoO engine can do 4 ALU ops/cycle, so I
> > expect a speedup.
> >
> > The unrolled-by-9 loop might look as follows:
> >
> > for (...; ...; d+=9) { // too lazy to work that out
> > t6=t7+t0; // first original iteration
> > t7=t8+t1; // second original iteration
> > t8=t0+t2;
> > t0=t1+t3;
> > t1=t2+t4;
> > t2=t3+t5;
> > t3=t4+t6;
> > t4=t5+t7;
> > t5=t6+t8;
> > }
> >
> > Of course you need to do the extra iterations after (or maybe before)
> > this loop.
> I will try your/Tim R's suggestion! I didn't manage to convince myself
> that it would work out when I tried to manually construct the recurrence
> for wider unrolls.
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<sr8q8j$1ai4$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22806&group=comp.arch#22806

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!Liunnst7X9VOeBBqqVtBCw.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Fri, 7 Jan 2022 08:31:34 +0100
Organization: Aioe.org NNTP Server
Message-ID: <sr8q8j$1ai4$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="43588"; posting-host="Liunnst7X9VOeBBqqVtBCw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Fri, 7 Jan 2022 07:31 UTC

Michael S wrote:
>> The 3 GHz AMD Threadripper was timed at 40 ns (using 112M iterations
>> inside Criterion) for 256 iterations of the loop above, so that would be
>> 120 clock cycles. OTOH, RObert Collins got 200 ns with inline timing
>> which is a much more believable 2.4 cycles/iteration.
>
> Not really believable.
> I don't think that there exist circumstances under which Zen3 can sustain more than 6 "normal" instructions per cycle.
> May be, 7 or 8 when 1 or 2 of instructions are predicted branches. Or, more likely, still 6.
> So, no less than 3.7 clocks for 22 "normal" instructions.
> Could it be that in reality in Robert's test the core was running at 4.7 or 4.8 GHz rather than 3 GHz?

All of those are possible, and this morning I implemented the 9-way
complete unroll and tested all the alternatives with 1024 days, so
1024/256/113+7 iterations, while inspecting the generated asm code which
was completely natural for all three versions (this is on my own Core i9
laptop cpu):

AoC 6!
Robert 1-day manual rotation: 9 reg-reg-moves, 1 add and 1
decrement/branch, 1.42 clock cycles/day
Part1: 1574445493136
Part2: 5971214410227557749
Init1: 326, 256 days: 378, init2: 10, 1024 days: 1456 clock cycles
Total: 2513417049 clock cycles for 1000000 iterations

In order to explain this timing, the CPU must have done zero-cycle
renames for 6 of the 9 moves, then executed the remaining 6 loop
instructions at a bit over 4 per clock cycle.

Terje 4-way unroll: 6 reg-reg MOV, 2 LEA moves, 4 LEA adds and 1
dec/branch: 1.90 clock cycles/4 days
Part1: 1574445493136
Part2: 5971214410227557749
Init1: 334, 256 days: 134, init2: 10, 1024 days: 486 clock cycles
Total: 1141854544 clock cycles for 1000000 iterations

This corresponds to 6 free renames and a steady state of about 5
instructions/cycle, also very impressive.

comp.arch 9-way unroll: 9 reg-reg ADDs, 1 dec/branch: 0.17 clock
cycles/day (113 loops + 7 single-day loops, 1.59 clock cycles/9 days
Part1: 1574445493136
Part2: 5971214410227557749
Init1: 334, 256 days: 52, init2: 10, 1024 days: 180 clock cycles
Total: 699566583 clock cycles for 1000000 iterations

Two iterations is 22 regular ALU instructions taking less than 3.2 clock
cycles which means 7+ instructions/cycle, so this probably requires the
loop sub/branch combo to be merged into a single macro-op, and then
sustain 6 ops/cycle.

So for this particular task which would have required ~2TB to directly
model all the individual fishes over 256 days, we instead can get away
with 72 bytes for the 9-fish array and about 0.2 clock cycles/day. :-)

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<9193d81b-094f-46de-88f7-8e9d4b079ad8n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22818&group=comp.arch#22818

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:622a:181c:: with SMTP id t28mr52323524qtc.633.1641552115338;
Fri, 07 Jan 2022 02:41:55 -0800 (PST)
X-Received: by 2002:a05:6808:1248:: with SMTP id o8mr9407587oiv.157.1641552115071;
Fri, 07 Jan 2022 02:41:55 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Fri, 7 Jan 2022 02:41:54 -0800 (PST)
In-Reply-To: <sr8q8j$1ai4$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2a0d:6fc2:55b0:ca00:7948:7b7f:3434:a19b;
posting-account=ow8VOgoAAAAfiGNvoH__Y4ADRwQF1hZW
NNTP-Posting-Host: 2a0d:6fc2:55b0:ca00:7948:7b7f:3434:a19b
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at>
<sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <9193d81b-094f-46de-88f7-8e9d4b079ad8n@googlegroups.com>
Subject: Re: On the power of zero-cycle renaming
From: already5...@yahoo.com (Michael S)
Injection-Date: Fri, 07 Jan 2022 10:41:55 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 68
 by: Michael S - Fri, 7 Jan 2022 10:41 UTC

On Friday, January 7, 2022 at 9:31:34 AM UTC+2, Terje Mathisen wrote:
> Michael S wrote:
> >> The 3 GHz AMD Threadripper was timed at 40 ns (using 112M iterations
> >> inside Criterion) for 256 iterations of the loop above, so that would be
> >> 120 clock cycles. OTOH, RObert Collins got 200 ns with inline timing
> >> which is a much more believable 2.4 cycles/iteration.
> >
> > Not really believable.
> > I don't think that there exist circumstances under which Zen3 can sustain more than 6 "normal" instructions per cycle.
> > May be, 7 or 8 when 1 or 2 of instructions are predicted branches. Or, more likely, still 6.
> > So, no less than 3.7 clocks for 22 "normal" instructions.
> > Could it be that in reality in Robert's test the core was running at 4.7 or 4.8 GHz rather than 3 GHz?
> All of those are possible, and this morning I implemented the 9-way
> complete unroll and tested all the alternatives with 1024 days, so
> 1024/256/113+7 iterations, while inspecting the generated asm code which
> was completely natural for all three versions (this is on my own Core i9
> laptop cpu):
>
> AoC 6!
> Robert 1-day manual rotation: 9 reg-reg-moves, 1 add and 1
> decrement/branch, 1.42 clock cycles/day
> Part1: 1574445493136
> Part2: 5971214410227557749
> Init1: 326, 256 days: 378, init2: 10, 1024 days: 1456 clock cycles
> Total: 2513417049 clock cycles for 1000000 iterations
>
> In order to explain this timing, the CPU must have done zero-cycle
> renames for 6 of the 9 moves, then executed the remaining 6 loop
> instructions at a bit over 4 per clock cycle.
>
>
> Terje 4-way unroll: 6 reg-reg MOV, 2 LEA moves, 4 LEA adds and 1
> dec/branch: 1.90 clock cycles/4 days
> Part1: 1574445493136
> Part2: 5971214410227557749
> Init1: 334, 256 days: 134, init2: 10, 1024 days: 486 clock cycles
> Total: 1141854544 clock cycles for 1000000 iterations
>
> This corresponds to 6 free renames and a steady state of about 5
> instructions/cycle, also very impressive.
>

Sorry, I don't understand.
You have 13 instructions per loop.
How many loops were executed and how many "cycles" it took?
And what is "cycle"? Is it a number reported by RDTSC instruction or something else?
The difference between RDTSC "cycles" and real processor cycles on Intel core-i9 laptop CPU, like i9-11900H,
could be 4.90/2.5= 1.96x on 45W laptops or even bigger on 35W laptop.

> comp.arch 9-way unroll: 9 reg-reg ADDs, 1 dec/branch: 0.17 clock
> cycles/day (113 loops + 7 single-day loops, 1.59 clock cycles/9 days
> Part1: 1574445493136
> Part2: 5971214410227557749
> Init1: 334, 256 days: 52, init2: 10, 1024 days: 180 clock cycles
> Total: 699566583 clock cycles for 1000000 iterations
>
> Two iterations is 22 regular ALU instructions taking less than 3.2 clock
> cycles which means 7+ instructions/cycle, so this probably requires the
> loop sub/branch combo to be merged into a single macro-op, and then
> sustain 6 ops/cycle.
>
> So for this particular task which would have required ~2TB to directly
> model all the individual fishes over 256 days, we instead can get away
> with 72 bytes for the 9-fish array and about 0.2 clock cycles/day. :-)
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<sr9gog$1i20$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22827&group=comp.arch#22827

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!Liunnst7X9VOeBBqqVtBCw.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Fri, 7 Jan 2022 14:55:29 +0100
Organization: Aioe.org NNTP Server
Message-ID: <sr9gog$1i20$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org>
<9193d81b-094f-46de-88f7-8e9d4b079ad8n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="51264"; posting-host="Liunnst7X9VOeBBqqVtBCw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Fri, 7 Jan 2022 13:55 UTC

Michael S wrote:
> On Friday, January 7, 2022 at 9:31:34 AM UTC+2, Terje Mathisen wrote:
>> Michael S wrote:
>>>> The 3 GHz AMD Threadripper was timed at 40 ns (using 112M iterations
>>>> inside Criterion) for 256 iterations of the loop above, so that would be
>>>> 120 clock cycles. OTOH, RObert Collins got 200 ns with inline timing
>>>> which is a much more believable 2.4 cycles/iteration.
>>>
>>> Not really believable.
>>> I don't think that there exist circumstances under which Zen3 can sustain more than 6 "normal" instructions per cycle.
>>> May be, 7 or 8 when 1 or 2 of instructions are predicted branches. Or, more likely, still 6.
>>> So, no less than 3.7 clocks for 22 "normal" instructions.
>>> Could it be that in reality in Robert's test the core was running at 4.7 or 4.8 GHz rather than 3 GHz?
>> All of those are possible, and this morning I implemented the 9-way
>> complete unroll and tested all the alternatives with 1024 days, so
>> 1024/256/113+7 iterations, while inspecting the generated asm code which
>> was completely natural for all three versions (this is on my own Core i9
>> laptop cpu):
>>
>> AoC 6!
>> Robert 1-day manual rotation: 9 reg-reg-moves, 1 add and 1
>> decrement/branch, 1.42 clock cycles/day
>> Part1: 1574445493136
>> Part2: 5971214410227557749
>> Init1: 326, 256 days: 378, init2: 10, 1024 days: 1456 clock cycles
>> Total: 2513417049 clock cycles for 1000000 iterations
>>
>> In order to explain this timing, the CPU must have done zero-cycle
>> renames for 6 of the 9 moves, then executed the remaining 6 loop
>> instructions at a bit over 4 per clock cycle.
>>
>>
>> Terje 4-way unroll: 6 reg-reg MOV, 2 LEA moves, 4 LEA adds and 1
>> dec/branch: 1.90 clock cycles/4 days
>> Part1: 1574445493136
>> Part2: 5971214410227557749
>> Init1: 334, 256 days: 134, init2: 10, 1024 days: 486 clock cycles
>> Total: 1141854544 clock cycles for 1000000 iterations
>>
>> This corresponds to 6 free renames and a steady state of about 5
>> instructions/cycle, also very impressive.
>>
>
> Sorry, I don't understand.
> You have 13 instructions per loop.
> How many loops were executed and how many "cycles" it took?
> And what is "cycle"? Is it a number reported by RDTSC instruction or something else?
> The difference between RDTSC "cycles" and real processor cycles on Intel core-i9 laptop CPU, like i9-11900H,
> could be 4.90/2.5= 1.96x on 45W laptops or even bigger on 35W laptop.

The explanation was much simpler: While MSVC did a pretty naive
"optimized compile", Robert's Rust compiler used the clang backend which
applied an automatic 8x unroll of the inner loop!

This got rid of almost all the reg-reg moves, making it about 3X faster.

I.e. his 40 ns wall clock time was valid.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<2022Jan7.193428@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22832&group=comp.arch#22832

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Fri, 07 Jan 2022 18:34:28 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 67
Message-ID: <2022Jan7.193428@mips.complang.tuwien.ac.at>
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com> <sr8q8j$1ai4$1@gioia.aioe.org>
Injection-Info: reader02.eternal-september.org; posting-host="266a68bc2adbdc07b9125a6ea0f8acea";
logging-data="4790"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX197iEU1x93VBFzBNS0LujbS"
Cancel-Lock: sha1:GxK75Yr8Jh/oejrZFR/fS43AAl4=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Fri, 7 Jan 2022 18:34 UTC

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>All of those are possible, and this morning I implemented the 9-way
>complete unroll and tested all the alternatives with 1024 days, so
>1024/256/113+7 iterations, while inspecting the generated asm code which
>was completely natural for all three versions (this is on my own Core i9
>laptop cpu):

For such single-thread all-in-cache tasks without AVX the differences
between Celeron and Core i9 are irrelevant, what matters is what
microarchiecture you use; e.g., you could report the actual CPU model,
or just the microarchitecture. And even for cases where multiple
threads or cache are important, mentioning Core ix generally does not
tell us much; e.g., the Core i5-12600H has 4P+8E cores, 16 threads,
and 18MB L3 cache, Core i7-4510U has 2 cores, 4 threads, and 4MB L3
cache. Core i9 has not been used as long, so you don't get the
two-core variants, but e.g. the Core i9-8950HK has 6 cores, 12
threads, and 12MB L3 cache.

If some layman thinks about their CPU as Core i5, ok, that's what is
in front of the big hard-to-remember number, but someone interested in
computer architecture should know that it does not tell us anything.
Intel marketing is apparently too effective.

>AoC 6!

?

>Robert 1-day manual rotation: 9 reg-reg-moves, 1 add and 1
>decrement/branch, 1.42 clock cycles/day
>Part1: 1574445493136
>Part2: 5971214410227557749
>Init1: 326, 256 days: 378, init2: 10, 1024 days: 1456 clock cycles
>Total: 2513417049 clock cycles for 1000000 iterations
>
>In order to explain this timing, the CPU must have done zero-cycle
>renames for 6 of the 9 moves, then executed the remaining 6 loop
>instructions at a bit over 4 per clock cycle.

Not sure what all your numbers mean, but 11 instructions in 1.42
cycles means 7.75 IPC, so you need a uop cache that can produce and a
renamer that can consume at least 8 instructions per cycle. Golden
Cove can do that.

>comp.arch 9-way unroll: 9 reg-reg ADDs, 1 dec/branch: 0.17 clock
>cycles/day (113 loops + 7 single-day loops, 1.59 clock cycles/9 days
>Part1: 1574445493136
>Part2: 5971214410227557749
>Init1: 334, 256 days: 52, init2: 10, 1024 days: 180 clock cycles
>Total: 699566583 clock cycles for 1000000 iterations
>
>Two iterations is 22 regular ALU instructions taking less than 3.2 clock
>cycles which means 7+ instructions/cycle, so this probably requires the
>loop sub/branch combo to be merged into a single macro-op, and then
>sustain 6 ops/cycle.

Did you mean 20 ALU instructions? Yes, Intel has been combining ALU
with branches for some time. Golen Cove can do 5 ALU
operations/cycle, so I would expect 2 cycles/9-day iteration. I have
no idea how you can get 1.59cycles per iteration on any Intel CPU with
this code.

Another thing you could do is to use SIMD code.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: On the power of zero-cycle renaming

<sraa1b$nfl$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22835&group=comp.arch#22835

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!Liunnst7X9VOeBBqqVtBCw.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Fri, 7 Jan 2022 22:06:54 +0100
Organization: Aioe.org NNTP Server
Message-ID: <sraa1b$nfl$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="24053"; posting-host="Liunnst7X9VOeBBqqVtBCw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Fri, 7 Jan 2022 21:06 UTC

Anton Ertl wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>> All of those are possible, and this morning I implemented the 9-way
>> complete unroll and tested all the alternatives with 1024 days, so
>> 1024/256/113+7 iterations, while inspecting the generated asm code which
>> was completely natural for all three versions (this is on my own Core i9
>> laptop cpu):
>
> For such single-thread all-in-cache tasks without AVX the differences
> between Celeron and Core i9 are irrelevant, what matters is what
> microarchiecture you use; e.g., you could report the actual CPU model,
> or just the microarchitecture. And even for cases where multiple
> threads or cache are important, mentioning Core ix generally does not
> tell us much; e.g., the Core i5-12600H has 4P+8E cores, 16 threads,
> and 18MB L3 cache, Core i7-4510U has 2 cores, 4 threads, and 4MB L3
> cache. Core i9 has not been used as long, so you don't get the
> two-core variants, but e.g. the Core i9-8950HK has 6 cores, 12
> threads, and 12MB L3 cache.

The code is completely single-threaded, so the number of cores doesn't
matter, only the cycles taken by the running core.

However, as I posted a bit later, the real explanation for the
unbelievable numbers was the automatic 8x unroll which clang backend
applied to Robert's reg-reg-filled code.
>
> If some layman thinks about their CPU as Core i5, ok, that's what is
> in front of the big hard-to-remember number, but someone interested in
> computer architecture should know that it does not tell us anything.
> Intel marketing is apparently too effective.

My exact model is "Intel(R) Core(TM) i9-10885H CPU @ 2.40GHz", but the
only thing that should matter is the micro-architecture, right?

I.e. how many execution units can do MOV/ADD/SUB/JNZ operations, with
some of the reg-reg MOVes handled in the renamer.

> Did you mean 20 ALU instructions? Yes, Intel has been combining ALU
> with branches for some time. Golen Cove can do 5 ALU
> operations/cycle, so I would expect 2 cycles/9-day iteration. I have
> no idea how you can get 1.59cycles per iteration on any Intel CPU with
> this code.

I, perhaps naively, thought that the original RDTSC opcode is still
reporting actual clock cycles, with new variants that measure constant time?

>
> Another thing you could do is to use SIMD code.

I looked closely at that, it would be hard: Each counter needs to be 64
bits so SSE means 2 counters/reg, AVX2 can fit 4, but then you get into
trouble with RAW hazards since the second pair you are reading is just
about to be updated by the previous quad.

t7 += t0, t8+= t1, t0 += t2, t1 += t3; t2 += t4, t3 += t5, t4 += t6, t5
+= t7, t6 += t8;

Working with 2x8-byte variables could look like this:

t6t7.hi += t0t1.lo; t8 += t0t1.hi;
t0t1 += t2t3; t2t3 += t4t5; t4t5 += t6t7; t6t7.lo += t8;

I.e. 9 scalar adds gets turned into 3 SIMD adds and 3 scalar adds
needing hi/lo extraction, so probably the same actual number of
operations and you can run quite a few more integer ops/cycle than SSE ops.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<2022Jan7.235600@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22844&group=comp.arch#22844

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Fri, 07 Jan 2022 22:56:00 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 57
Message-ID: <2022Jan7.235600@mips.complang.tuwien.ac.at>
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com> <sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at> <sraa1b$nfl$1@gioia.aioe.org>
Injection-Info: reader02.eternal-september.org; posting-host="eca042e37b89111e037ca1e8c61dc68a";
logging-data="20153"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/1o0baR8W04wb8ZdhYYuep"
Cancel-Lock: sha1:83vHqDPA5wI3KaUA8+ySm60cnFo=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Fri, 7 Jan 2022 22:56 UTC

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>However, as I posted a bit later, the real explanation for the
>unbelievable numbers was the automatic 8x unroll which clang backend
>applied to Robert's reg-reg-filled code.

And, as Michael S pointed out, not using CPU cycles, but rdtsc.

>My exact model is "Intel(R) Core(TM) i9-10885H CPU @ 2.40GHz", but the
>only thing that should matter is the micro-architecture, right?

Yes, if we get the real cycles. The microarchitecture is Skylake;
that feeds 6uops into the renamer and 4 uops from the renamer into
execution (two of these uops can be fused decrement+branches).

>I, perhaps naively, thought that the original RDTSC opcode is still
>reporting actual clock cycles, with new variants that measure constant time?

RDTSC is like a wall clock (and has been for more than a decade): It
does not speed up or slow down with the CPU clock, so it does not tell
you how many CPU clocks have been used.

If I understand Michael S correctly, RDTSC clocks with the base clock,
i.e., 2.4GHz for the Core i9-10885H. The actual CPU clock can go up
to 5.3GHz, so it can be more than twice as fast as the RDTSC clock.

For good measurements, I use the clock cycles reported through the
performance monitoring counters (using the Linux tool perf).

>> Another thing you could do is to use SIMD code.
>
>I looked closely at that, it would be hard: Each counter needs to be 64
>bits so SSE means 2 counters/reg, AVX2 can fit 4, but then you get into
>trouble with RAW hazards since the second pair you are reading is just
>about to be updated by the previous quad.
>
>t7 += t0, t8+= t1, t0 += t2, t1 += t3; t2 += t4, t3 += t5, t4 += t6, t5
>+= t7, t6 += t8;
>
>Working with 2x8-byte variables could look like this:
>
> t6t7.hi += t0t1.lo; t8 += t0t1.hi;
> t0t1 += t2t3; t2t3 += t4t5; t4t5 += t6t7; t6t7.lo += t8;
>
>I.e. 9 scalar adds gets turned into 3 SIMD adds and 3 scalar adds
>needing hi/lo extraction, so probably the same actual number of
>operations and you can run quite a few more integer ops/cycle than SSE ops.

I would try AVX or (not present on your Skylake) AVX-512, and then
work a bit with the permutation instructions to get the operands
aligned. Not sure if AVX supports 64-bit integers well, though. And
yes, there is some overhead, and combined with the fewer AVX resources
compared to scalar resources it may turn out that it does not pay off.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: On the power of zero-cycle renaming

<921a0117-9fa6-4725-9778-22b98f1ccce2n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22864&group=comp.arch#22864

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:620a:1235:: with SMTP id v21mr9334903qkj.278.1641669937572;
Sat, 08 Jan 2022 11:25:37 -0800 (PST)
X-Received: by 2002:a9d:206a:: with SMTP id n97mr51810418ota.142.1641669937330;
Sat, 08 Jan 2022 11:25:37 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Sat, 8 Jan 2022 11:25:37 -0800 (PST)
In-Reply-To: <sraa1b$nfl$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2a0d:6fc2:55b0:ca00:502f:93b0:d812:df41;
posting-account=ow8VOgoAAAAfiGNvoH__Y4ADRwQF1hZW
NNTP-Posting-Host: 2a0d:6fc2:55b0:ca00:502f:93b0:d812:df41
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at>
<sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at> <sraa1b$nfl$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <921a0117-9fa6-4725-9778-22b98f1ccce2n@googlegroups.com>
Subject: Re: On the power of zero-cycle renaming
From: already5...@yahoo.com (Michael S)
Injection-Date: Sat, 08 Jan 2022 19:25:37 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 75
 by: Michael S - Sat, 8 Jan 2022 19:25 UTC

On Friday, January 7, 2022 at 11:06:54 PM UTC+2, Terje Mathisen wrote:
> Anton Ertl wrote:
> > Terje Mathisen <terje.m...@tmsw.no> writes:
> >> All of those are possible, and this morning I implemented the 9-way
> >> complete unroll and tested all the alternatives with 1024 days, so
> >> 1024/256/113+7 iterations, while inspecting the generated asm code which
> >> was completely natural for all three versions (this is on my own Core i9
> >> laptop cpu):
> >
> > For such single-thread all-in-cache tasks without AVX the differences
> > between Celeron and Core i9 are irrelevant, what matters is what
> > microarchiecture you use; e.g., you could report the actual CPU model,
> > or just the microarchitecture. And even for cases where multiple
> > threads or cache are important, mentioning Core ix generally does not
> > tell us much; e.g., the Core i5-12600H has 4P+8E cores, 16 threads,
> > and 18MB L3 cache, Core i7-4510U has 2 cores, 4 threads, and 4MB L3
> > cache. Core i9 has not been used as long, so you don't get the
> > two-core variants, but e.g. the Core i9-8950HK has 6 cores, 12
> > threads, and 12MB L3 cache.
> The code is completely single-threaded, so the number of cores doesn't
> matter, only the cycles taken by the running core.
>
> However, as I posted a bit later, the real explanation for the
> unbelievable numbers was the automatic 8x unroll which clang backend
> applied to Robert's reg-reg-filled code.
> >
> > If some layman thinks about their CPU as Core i5, ok, that's what is
> > in front of the big hard-to-remember number, but someone interested in
> > computer architecture should know that it does not tell us anything.
> > Intel marketing is apparently too effective.
> My exact model is "Intel(R) Core(TM) i9-10885H CPU @ 2.40GHz", but the
> only thing that should matter is the micro-architecture, right?
>
> I.e. how many execution units can do MOV/ADD/SUB/JNZ operations, with
> some of the reg-reg MOVes handled in the renamer.

If you code is dominated by MOVs, as you said in the post above (8 out of 13 fused uOps)
then EUs do not matter. What matters is an output width of renamer.
In your case (Comet Lake, microarchitecturally near identical to Skylake) its 4.
So, the best you can hope for is 13 instructions in 3.25 clocks.
At maximal boost frequency it translates to 3.25*2.4/5.3 = 1.47 RDTSC "clocks".

BTW, not all Intel's 10th gen core CPUs are Skylake variants.
For example, core i7-1068NG7 is Ice Lake. It has 5-wide renamer output.

> > Did you mean 20 ALU instructions? Yes, Intel has been combining ALU
> > with branches for some time. Golen Cove can do 5 ALU
> > operations/cycle, so I would expect 2 cycles/9-day iteration. I have
> > no idea how you can get 1.59cycles per iteration on any Intel CPU with
> > this code.
> I, perhaps naively, thought that the original RDTSC opcode is still
> reporting actual clock cycles, with new variants that measure constant time?
> >
> > Another thing you could do is to use SIMD code.
> I looked closely at that, it would be hard: Each counter needs to be 64
> bits so SSE means 2 counters/reg, AVX2 can fit 4, but then you get into
> trouble with RAW hazards since the second pair you are reading is just
> about to be updated by the previous quad.
>
> t7 += t0, t8+= t1, t0 += t2, t1 += t3; t2 += t4, t3 += t5, t4 += t6, t5
> += t7, t6 += t8;
>
> Working with 2x8-byte variables could look like this:
>
> t6t7.hi += t0t1.lo; t8 += t0t1.hi;
> t0t1 += t2t3; t2t3 += t4t5; t4t5 += t6t7; t6t7.lo += t8;
>
> I.e. 9 scalar adds gets turned into 3 SIMD adds and 3 scalar adds
> needing hi/lo extraction, so probably the same actual number of
> operations and you can run quite a few more integer ops/cycle than SSE ops.
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<sreq62$55r$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=22877&group=comp.arch#22877

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!Liunnst7X9VOeBBqqVtBCw.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Sun, 9 Jan 2022 15:06:59 +0100
Organization: Aioe.org NNTP Server
Message-ID: <sreq62$55r$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at>
<sraa1b$nfl$1@gioia.aioe.org>
<921a0117-9fa6-4725-9778-22b98f1ccce2n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="5307"; posting-host="Liunnst7X9VOeBBqqVtBCw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Sun, 9 Jan 2022 14:06 UTC

Michael S wrote:
> On Friday, January 7, 2022 at 11:06:54 PM UTC+2, Terje Mathisen wrote:
>> Anton Ertl wrote:
>>> Intel marketing is apparently too effective.
>> My exact model is "Intel(R) Core(TM) i9-10885H CPU @ 2.40GHz", but the
>> only thing that should matter is the micro-architecture, right?
>>
>> I.e. how many execution units can do MOV/ADD/SUB/JNZ operations, with
>> some of the reg-reg MOVes handled in the renamer.
>
> If you code is dominated by MOVs, as you said in the post above (8 out of 13 fused uOps)
> then EUs do not matter. What matters is an output width of renamer.
> In your case (Comet Lake, microarchitecturally near identical to Skylake) its 4.
> So, the best you can hope for is 13 instructions in 3.25 clocks.
> At maximal boost frequency it translates to 3.25*2.4/5.3 = 1.47 RDTSC "clocks".

Thanks! I obviously need to catch up again with the various
micro-architectures that have turned up while I didn't pay attention. :-(

The MSVC-generated asm was a direct translate of the C code, so 9 MOV
(first 4 MOV, then 3 LEA with plain "lea reg2,[reg1]" as an alternate
way to copy a register, and then a final pair of MOV), 1 ADD (done with
LEA to get two sources and a third destination) and the presumably fused
SUB/JNZ loop combo: 11 u-ops.

The reg-reg copies done with LEA indicates that the compiler knows about
the renamer limit.
>
> BTW, not all Intel's 10th gen core CPUs are Skylake variants.
> For example, core i7-1068NG7 is Ice Lake. It has 5-wide renamer output.

OK, noted.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23004&group=comp.arch#23004

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:622a:1a89:: with SMTP id s9mr17000300qtc.625.1642543802788;
Tue, 18 Jan 2022 14:10:02 -0800 (PST)
X-Received: by 2002:a05:6808:22a2:: with SMTP id bo34mr498694oib.119.1642543802652;
Tue, 18 Jan 2022 14:10:02 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Tue, 18 Jan 2022 14:10:02 -0800 (PST)
In-Reply-To: <sraa1b$nfl$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=73.188.126.34; posting-account=ujX_IwoAAACu0_cef9hMHeR8g0ZYDNHh
NNTP-Posting-Host: 73.188.126.34
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at>
<sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at> <sraa1b$nfl$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com>
Subject: Re: On the power of zero-cycle renaming
From: timcaff...@aol.com (Timothy McCaffrey)
Injection-Date: Tue, 18 Jan 2022 22:10:02 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 22
 by: Timothy McCaffrey - Tue, 18 Jan 2022 22:10 UTC

On Friday, January 7, 2022 at 4:06:54 PM UTC-5, Terje Mathisen wrote:

> I, perhaps naively, thought that the original RDTSC opcode is still
> reporting actual clock cycles, with new variants that measure constant time?

RDTSC has been "real world" rate invariant since Nehalem (I asked Intel at IDC when it was introduced).

Found the following:
https://perfmon-events.intel.com/
For Skylake the following performance counter is available:

CPU_CLK_UNHALTED.THREAD_P This is an architectural event that counts the number of thread cycles while the thread is not in a halt state. The thread enters the halt state when it is running the HLT instruction. The core frequency may change from time to time due to power or thermal throttling. For this reason, this event may have a changing ratio with regards to wall clock time. EventSel=3CH UMask=00H
Counter=0,1,2,3 CounterHTOff=0,1,2,3,4,5,6,7
Architectural

- Tim

Re: On the power of zero-cycle renaming

<ss8f0n$vsm$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23009&group=comp.arch#23009

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!To5nvU/sTaigmVbgRJ05pQ.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Wed, 19 Jan 2022 08:35:54 +0100
Organization: Aioe.org NNTP Server
Message-ID: <ss8f0n$vsm$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at>
<sraa1b$nfl$1@gioia.aioe.org>
<c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="32662"; posting-host="To5nvU/sTaigmVbgRJ05pQ.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Wed, 19 Jan 2022 07:35 UTC

Timothy McCaffrey wrote:
> On Friday, January 7, 2022 at 4:06:54 PM UTC-5, Terje Mathisen wrote:
>
>> I, perhaps naively, thought that the original RDTSC opcode is still
>> reporting actual clock cycles, with new variants that measure constant time?
>
> RDTSC has been "real world" rate invariant since Nehalem (I asked Intel at IDC when it was introduced).
>
> Found the following:
> https://perfmon-events.intel.com/
> For Skylake the following performance counter is available:
>
> CPU_CLK_UNHALTED.THREAD_P This is an architectural event that counts the number of thread cycles while the thread is not in a halt state. The thread enters the halt state when it is running the HLT instruction. The core frequency may change from time to time due to power or thermal throttling. For this reason, this event may have a changing ratio with regards to wall clock time. EventSel=3CH UMask=00H
> Counter=0,1,2,3 CounterHTOff=0,1,2,3,4,5,6,7
> Architectural

Thanks!

Constant-rate RDTSC makes the world much easier for all those who use it
for interval timing, and much harder for those of us who try to count
actual cycles. :-(

My problem was that I (falsely?) remembered reading that the
constant-rate counter would be a new opcode and RDTSC would keep doing
what its name promises.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<2022Jan19.095638@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23010&group=comp.arch#23010

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Wed, 19 Jan 2022 08:56:38 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 22
Message-ID: <2022Jan19.095638@mips.complang.tuwien.ac.at>
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com> <sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at> <sraa1b$nfl$1@gioia.aioe.org> <c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com> <ss8f0n$vsm$1@gioia.aioe.org>
Injection-Info: reader02.eternal-september.org; posting-host="f2fe5bd51e266ec9d19a5ffa687c7859";
logging-data="19985"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX184oiqYte40r3scy0AEWm7P"
Cancel-Lock: sha1:Ke8nbk32cwNKO1UchwVO6si+W90=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Wed, 19 Jan 2022 08:56 UTC

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>Timothy McCaffrey wrote:
>> RDTSC has been "real world" rate invariant since Nehalem (I asked Intel at IDC when it was introduced).

According to <https://en.wikipedia.org/wiki/Time_Stamp_Counter>, "the
time-stamp counter increments at a constant rate" since Pentium 4
models 03H and higher, i.e., Prescott. Only Pentium M and Williamette
and Northwood supported SpeedStep with variable rate.

>My problem was that I (falsely?) remembered reading that the
>constant-rate counter would be a new opcode and RDTSC would keep doing
>what its name promises.

Its name promises a time stamp counter, and that's what it has
delivered in Intel CPUs since 2004. For AMD CPUs, TSC were core
clocks up to and including K8, and changed to constant rate with
K10/Barcelona/Phenom (introduced in 2007).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: On the power of zero-cycle renaming

<2022Jan19.101124@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23011&group=comp.arch#23011

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Wed, 19 Jan 2022 09:11:24 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 26
Message-ID: <2022Jan19.101124@mips.complang.tuwien.ac.at>
References: <sr6dcr$80b$1@gioia.aioe.org> <2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org> <35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com> <sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at> <sraa1b$nfl$1@gioia.aioe.org> <c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com> <ss8f0n$vsm$1@gioia.aioe.org>
Injection-Info: reader02.eternal-september.org; posting-host="f2fe5bd51e266ec9d19a5ffa687c7859";
logging-data="19985"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/XCKvBK4/r6XMcGKkQCodP"
Cancel-Lock: sha1:kQXR9NzYskn1hAB+fn41ZqR7zJ4=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Wed, 19 Jan 2022 09:11 UTC

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>Constant-rate RDTSC makes the world much easier for all those who use it
>for interval timing, and much harder for those of us who try to count
>actual cycles. :-(

I find it pretty easy to count actual cycles:

perf stat -e cycles <command>

or, for more details:

perf stat -e cycles:u -e cycles:k <command>

(gives me cycles split into user and kernel mode). For a few years
now, I have had to set

echo 0 >/proc/sys/kernel/perf_event_paranoid

for that to work (apparently the balance of people actually using
performance counters vs. people that don't use them and for whom they
just pose a (small) security risk tips towards the latter by default).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: On the power of zero-cycle renaming

<ss92pd$hat$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23012&group=comp.arch#23012

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!To5nvU/sTaigmVbgRJ05pQ.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Wed, 19 Jan 2022 14:13:17 +0100
Organization: Aioe.org NNTP Server
Message-ID: <ss92pd$hat$1@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at>
<sraa1b$nfl$1@gioia.aioe.org>
<c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com>
<ss8f0n$vsm$1@gioia.aioe.org> <2022Jan19.101124@mips.complang.tuwien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="17757"; posting-host="To5nvU/sTaigmVbgRJ05pQ.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Wed, 19 Jan 2022 13:13 UTC

Anton Ertl wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>> Constant-rate RDTSC makes the world much easier for all those who use it
>> for interval timing, and much harder for those of us who try to count
>> actual cycles. :-(
>
> I find it pretty easy to count actual cycles:
>
> perf stat -e cycles <command>
>
> or, for more details:
>
> perf stat -e cycles:u -e cycles:k <command>
>
> (gives me cycles split into user and kernel mode). For a few years
> now, I have had to set
>
> echo 0 >/proc/sys/kernel/perf_event_paranoid
>
> for that to work (apparently the balance of people actually using
> performance counters vs. people that don't use them and for whom they
> just pose a (small) security risk tips towards the latter by default).

That does not work for micro-benchmarks where you want to run maybe 100k
iterations of a small function, collecting histograms of the actual
counts, but you are of course in the enviable situation here of having
an OS which includes this functionality.
:-)

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Re: On the power of zero-cycle renaming

<jwvbl05ge3p.fsf-monnier+comp.arch@gnu.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23024&group=comp.arch#23024

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: monn...@iro.umontreal.ca (Stefan Monnier)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Fri, 21 Jan 2022 13:06:05 -0500
Organization: A noiseless patient Spider
Lines: 13
Message-ID: <jwvbl05ge3p.fsf-monnier+comp.arch@gnu.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at>
<sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org>
<2022Jan7.193428@mips.complang.tuwien.ac.at>
<sraa1b$nfl$1@gioia.aioe.org>
<c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com>
<ss8f0n$vsm$1@gioia.aioe.org>
<2022Jan19.101124@mips.complang.tuwien.ac.at>
<ss92pd$hat$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="befc5c294b105420522ac31f2943f86e";
logging-data="26103"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Be+D3J0WJwUUPPBTH4nbA"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
Cancel-Lock: sha1:7VvKj6dls713IIXPdWoZ+FDAFWc=
sha1:KVHCGfdc3zwu8O1KhtDuRGa6gBw=
 by: Stefan Monnier - Fri, 21 Jan 2022 18:06 UTC

Terje Mathisen [2022-01-19 14:13:17] wrote:
> That does not work for micro-benchmarks where you want to run maybe 100k
> iterations of a small function, collecting histograms of the actual counts,
> but you are of course in the enviable situation here of having an OS which
> includes this functionality.

Not sure why "enviable": this OS is one of those with the property that
pretty much anyone can use it: it only depends on a personal choice.

So, give in to the temptation ;-)

Stefan

Re: On the power of zero-cycle renaming

<ssgqmr$vef$2@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23042&group=comp.arch#23042

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!To5nvU/sTaigmVbgRJ05pQ.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: On the power of zero-cycle renaming
Date: Sat, 22 Jan 2022 12:44:27 +0100
Organization: Aioe.org NNTP Server
Message-ID: <ssgqmr$vef$2@gioia.aioe.org>
References: <sr6dcr$80b$1@gioia.aioe.org>
<2022Jan6.193456@mips.complang.tuwien.ac.at> <sr7k8e$1kjl$1@gioia.aioe.org>
<35130924-d54d-47eb-9b07-f047132a6d78n@googlegroups.com>
<sr8q8j$1ai4$1@gioia.aioe.org> <2022Jan7.193428@mips.complang.tuwien.ac.at>
<sraa1b$nfl$1@gioia.aioe.org>
<c312d294-4e6d-432f-af60-6a95c5b289d6n@googlegroups.com>
<ss8f0n$vsm$1@gioia.aioe.org> <2022Jan19.101124@mips.complang.tuwien.ac.at>
<ss92pd$hat$1@gioia.aioe.org> <jwvbl05ge3p.fsf-monnier+comp.arch@gnu.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="32207"; posting-host="To5nvU/sTaigmVbgRJ05pQ.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Sat, 22 Jan 2022 11:44 UTC

Stefan Monnier wrote:
> Terje Mathisen [2022-01-19 14:13:17] wrote:
>> That does not work for micro-benchmarks where you want to run maybe 100k
>> iterations of a small function, collecting histograms of the actual counts,
>> but you are of course in the enviable situation here of having an OS which
>> includes this functionality.
>
> Not sure why "enviable": this OS is one of those with the property that
> pretty much anyone can use it: it only depends on a personal choice.
>
> So, give in to the temptation ;-)

I have used Linux for 2+ decades and FreeBSD even longer, it is just
that I have so much Windows-only software that I use daily that I have
to live with the drawbacks on my primary machine.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor