Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

To be awake is to be alive. -- Henry David Thoreau, in "Walden"


devel / comp.arch / Re: branchless binary search

SubjectAuthor
* Ill-advised use of CMOVEStefan Monnier
+* Re: Ill-advised use of CMOVEThomas Koenig
|`* Re: Ill-advised use of CMOVEStephen Fuld
| `* Re: Ill-advised use of CMOVEThomas Koenig
|  +* Re: Ill-advised use of CMOVEStephen Fuld
|  |`- Re: Ill-advised use of CMOVEaph
|  `* Re: Ill-advised use of CMOVEAnton Ertl
|   +* Re: Ill-advised use of CMOVEMichael S
|   |`* Re: Ill-advised use of CMOVEAnton Ertl
|   | `* Re: Ill-advised use of CMOVEMichael S
|   |  +* Re: Ill-advised use of CMOVEIvan Godard
|   |  |`* Re: Ill-advised use of CMOVEMichael S
|   |  | `* Re: Ill-advised use of CMOVEIvan Godard
|   |  |  `- Re: Ill-advised use of CMOVEMichael S
|   |  `* Re: Ill-advised use of CMOVEAnton Ertl
|   |   +- Re: Ill-advised use of CMOVEMichael S
|   |   `* branchless binary search (was: Ill-advised use of CMOVE)Anton Ertl
|   |    +* Re: branchless binary searchStefan Monnier
|   |    |`- Re: branchless binary searchAnton Ertl
|   |    +- Re: branchless binary searchTerje Mathisen
|   |    `* Re: branchless binary searchEricP
|   |     +* Re: branchless binary searchMichael S
|   |     |+* Re: branchless binary searchStephen Fuld
|   |     ||`* Re: branchless binary searchMichael S
|   |     || +- Re: branchless binary searchThomas Koenig
|   |     || `* Spectre fix (was: branchless binary search)Anton Ertl
|   |     ||  `- Re: Spectre fix (was: branchless binary search)Michael S
|   |     |+* Re: branchless binary searchStefan Monnier
|   |     ||`- Re: branchless binary searchMitchAlsup
|   |     |`* Re: branchless binary searchAndy Valencia
|   |     | `- Re: branchless binary searchTerje Mathisen
|   |     `* Re: branchless binary searchAnton Ertl
|   |      `* Re: branchless binary searchMitchAlsup
|   |       `* Spectre and resource comtention (was: branchless binary search)Anton Ertl
|   |        +* Re: Spectre and resource comtentionStefan Monnier
|   |        |+- Re: Spectre and resource comtentionMitchAlsup
|   |        |`- Re: Spectre and resource comtentionAnton Ertl
|   |        `* Re: Spectre and resource comtention (was: branchless binary search)MitchAlsup
|   |         `* Re: Spectre and resource comtention (was: branchless binary search)Anton Ertl
|   |          `- Re: Spectre and resource comtention (was: branchless binary search)MitchAlsup
|   +* Re: Ill-advised use of CMOVEStephen Fuld
|   |`* binary search vs. hash tables (was: Ill-advised use of CMOVE)Anton Ertl
|   | +* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Stephen Fuld
|   | |`* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)John Levine
|   | | `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |  `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |   `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |    `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |     `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |      `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |       `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | |        `* Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Brett
|   | |         `- Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)Michael S
|   | `- Re: binary search vs. hash tables (was: Ill-advised use of CMOVE)John Levine
|   +* Re: Ill-advised use of CMOVEEricP
|   |`* Re: Ill-advised use of CMOVEBGB
|   | +* Re: Ill-advised use of CMOVEMitchAlsup
|   | |+* Re: Ill-advised use of CMOVEBGB
|   | ||`* Re: Ill-advised use of CMOVEMitchAlsup
|   | || +* Re: Ill-advised use of CMOVEBGB
|   | || |`- Re: Ill-advised use of CMOVEMitchAlsup
|   | || `- Re: Ill-advised use of CMOVEIvan Godard
|   | |`* Re: Ill-advised use of CMOVEIvan Godard
|   | | `- Re: Ill-advised use of CMOVEMitchAlsup
|   | `- Re: Ill-advised use of CMOVEIvan Godard
|   `- Re: Ill-advised use of CMOVEThomas Koenig
+* Re: Ill-advised use of CMOVETerje Mathisen
|+* Re: Ill-advised use of CMOVEMitchAlsup
||`* Re: Ill-advised use of CMOVETerje Mathisen
|| `* Re: Ill-advised use of CMOVEMitchAlsup
||  `* Re: Ill-advised use of CMOVEMarcus
||   `* Re: Ill-advised use of CMOVEMitchAlsup
||    `* Re: Ill-advised use of CMOVEBGB
||     `* Re: Ill-advised use of CMOVEMitchAlsup
||      `- Re: Ill-advised use of CMOVEBGB
|+- Re: Ill-advised use of CMOVEIvan Godard
|`* Re: Ill-advised use of CMOVEStephen Fuld
| +* Re: Ill-advised use of CMOVEMichael S
| |`* Re: Ill-advised use of CMOVEStephen Fuld
| | `- Re: Ill-advised use of CMOVEAnton Ertl
| +* Re: Ill-advised use of CMOVEStefan Monnier
| |`* Re: Ill-advised use of CMOVEStephen Fuld
| | `* Re: Ill-advised use of CMOVEAnton Ertl
| |  `* Re: Ill-advised use of CMOVEBGB
| |   `* Re: Ill-advised use of CMOVEMitchAlsup
| |    +- Re: Ill-advised use of CMOVEBGB
| |    `* Re: Ill-advised use of CMOVEThomas Koenig
| |     +- Re: Ill-advised use of CMOVEAnton Ertl
| |     `- Re: Ill-advised use of CMOVEMitchAlsup
| +* Re: Ill-advised use of CMOVEAnton Ertl
| |`* Re: Ill-advised use of CMOVEMitchAlsup
| | `* Re: Ill-advised use of CMOVEEricP
| |  +* Re: Ill-advised use of CMOVEMichael S
| |  |`* Re: Ill-advised use of CMOVEEricP
| |  | +- Re: Ill-advised use of CMOVEMitchAlsup
| |  | +* Re: Ill-advised use of CMOVETerje Mathisen
| |  | |`* Re: Ill-advised use of CMOVEEricP
| |  | | `* Re: Ill-advised use of CMOVEMitchAlsup
| |  | |  `- Re: Ill-advised use of CMOVEBGB
| |  | `- Re: Ill-advised use of CMOVEAnton Ertl
| |  `* Re: Ill-advised use of CMOVEAnton Ertl
| `* Re: Ill-advised use of CMOVETerje Mathisen
+- Re: Ill-advised use of CMOVEAnton Ertl
`* Re: Ill-advised use of CMOVEScott Michel

Pages:123456
Re: branchless binary search

<165326189549.22185.1930728508024666098@media.vsta.org>

 copy mid

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

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: van...@vsta.org (Andy Valencia)
Newsgroups: comp.arch
Subject: Re: branchless binary search
Date: Sun, 22 May 2022 16:24:55 -0700
Lines: 19
Message-ID: <165326189549.22185.1930728508024666098@media.vsta.org>
References: <2022May17.110354@mips.complang.tuwien.ac.at> <2022May17.205327@mips.complang.tuwien.ac.at> <nkOhK.5260$wIO9.4690@fx12.iad> <89da1370-6a58-47d6-bfd0-7a32b1c2934dn@googlegroups.com>
X-Trace: individual.net 0n1+3rFaftLhs3Gxvd2u8AHgJ/1jjyUNuneCe5noQq2vAeolhj
X-Orig-Path: media
Cancel-Lock: sha1:ZgbQQ8fsxVicK4ZPDHK6W+ZdHlU=
User-Agent: rn.py v0.0.1
 by: Andy Valencia - Sun, 22 May 2022 23:24 UTC

Stefan Monnier <monnier@iro.umontreal.ca> writes:
> ... so maybe
> Spectre-proof hardware will only be seriously considered when it's used
> for things like leaking the private keys of BluRay, or breaking out of
> an iOS jail?

The virtual server hosting market is really big, and growing. So far, the
CPU makers--along with their counterpart OS devs--pretend like they're
staying ahead. And so far, we pretend like we believe them.

This participatory delusion may, at some point, burn away by something
sufficiently catastrophic. Then we might take another look at architectures
like Scaleway's "Bare Metal" ARM servers, where they gridded a bunch of ARM
CPU's across a server board, each customer getting one. No shared anything
until you get out to the network.

Andy Valencia
Home page: https://www.vsta.org/andy/
To contact me: https://www.vsta.org/contact/andy.html

Re: branchless binary search

<t6f9n5$1i56$1@gioia.aioe.org>

 copy mid

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

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!EhtdJS5E9ITDZpJm3Uerlg.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: branchless binary search
Date: Mon, 23 May 2022 08:31:04 +0200
Organization: Aioe.org NNTP Server
Message-ID: <t6f9n5$1i56$1@gioia.aioe.org>
References: <2022May17.110354@mips.complang.tuwien.ac.at>
<2022May17.205327@mips.complang.tuwien.ac.at> <nkOhK.5260$wIO9.4690@fx12.iad>
<89da1370-6a58-47d6-bfd0-7a32b1c2934dn@googlegroups.com>
<165326189549.22185.1930728508024666098@media.vsta.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="51366"; posting-host="EhtdJS5E9ITDZpJm3Uerlg.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.12
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Mon, 23 May 2022 06:31 UTC

Andy Valencia wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> ... so maybe
>> Spectre-proof hardware will only be seriously considered when it's used
>> for things like leaking the private keys of BluRay, or breaking out of
>> an iOS jail?
>
> The virtual server hosting market is really big, and growing. So far, the
> CPU makers--along with their counterpart OS devs--pretend like they're
> staying ahead. And so far, we pretend like we believe them.
>
> This participatory delusion may, at some point, burn away by something
> sufficiently catastrophic. Then we might take another look at architectures
> like Scaleway's "Bare Metal" ARM servers, where they gridded a bunch of ARM
> CPU's across a server board, each customer getting one. No shared anything
> until you get out to the network.

This is the real solution, i.e. as long as I as a cloud customer know
that only my own code runs on the ~100K cpu instances I'm using at any
given point in time, then I don't care about these types of attacks. It
is the mixing of my own code with other customers code on the same
physical hardware that matters.

As long as I pay for and get some form of gang scheduling, i.e. always
complete cpus/boards, then I only need to worry about JITing code
supplied by one of my own customers, and even that should then probably
run on separate cpus.

Terje

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

Re: Ill-advised use of CMOVE

<JF4jK.8600$xZtb.3509@fx41.iad>

 copy mid

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

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!peer03.ams4!peer.am4.highwinds-media.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx41.iad.POSTED!not-for-mail
From: ThatWoul...@thevillage.com (EricP)
User-Agent: Thunderbird 2.0.0.24 (Windows/20100228)
MIME-Version: 1.0
Newsgroups: comp.arch
Subject: Re: Ill-advised use of CMOVE
References: <jwv1qx4xe9z.fsf-monnier+comp.arch@gnu.org> <t58n6r$1riu$1@gioia.aioe.org> <t5e1ek$s7c$1@dont-email.me> <2022May10.194427@mips.complang.tuwien.ac.at> <0555194d-edc8-48fb-b304-7f78d62255d3n@googlegroups.com> <hlPeK.4263$pqKf.2583@fx12.iad> <2022May14.100411@mips.complang.tuwien.ac.at> <IZ8gK.6876$j0D5.5549@fx09.iad> <2022May15.194522@mips.complang.tuwien.ac.at> <0d201c5c-10a9-4954-994f-559e2adf9fc4n@googlegroups.com> <OQrgK.3333$6y5f.202@fx40.iad> <ZEwgK.60130$qMI1.19308@fx96.iad> <m-6dnanyXqYjmxf_nZ2dnUU7-dPNnZ2d@supernews.com>
In-Reply-To: <m-6dnanyXqYjmxf_nZ2dnUU7-dPNnZ2d@supernews.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 57
Message-ID: <JF4jK.8600$xZtb.3509@fx41.iad>
X-Complaints-To: abuse@UsenetServer.com
NNTP-Posting-Date: Tue, 24 May 2022 13:00:25 UTC
Date: Tue, 24 May 2022 09:00:04 -0400
X-Received-Bytes: 3946
 by: EricP - Tue, 24 May 2022 13:00 UTC

aph@littlepinkcloud.invalid wrote:
> EricP <ThatWouldBeTelling@thevillage.com> wrote:
>> I can't find any details on those ARM uArch's at all. None.
>> Almost all predication studies are proposals by Intel for doing OoO Itanium.
>
> Looking at the neoverse N2 Software Optimization Guide, I see that
> basic ALU ops have 1 clock latency, 4 ops/clock throughput. Basic ALU
> ops with condition run at only 1 op/clock. These predicated
> instructions run on the Integer Multicycle Unit, also used for things
> like multiplication, rather then the standard Integer Unit.
>
> Andrew.

It sounds like Arm may be using a predication implementation similar
to Intel's x86 CMOV reg,[mem] where it always does the load operation
and then conditionally copy the result to the dest reg.

That approach avoids having to sort out how to cancel disabled
instructions, and avoids having to distribute predicate conditions
to all the uOps as it really is mostly just doing normal operations
followed by a CMOV, and the CMOV's can all be done in a specialty F.U.

In the example below we see that if the first MUL is disabled and the
second MUL enabled, it still incurs the latency for doing the first MUL.
This means it is not cancelling disabled operations.

The OoO Cortex-A72 optimization guide says on conditional execution:

"This leads to conditional register writes for most types of
conditional instructions. In an out-of-order processor
such as Cortex-A72 processor, this has two side-effects:

- The first side-effect is that the conditional instruction requires
the old value of its destination register as an input operand.

- The second side-effect is that all subsequent consumers of the
conditional instruction destination register depend upon this operation,
regardless of the state of the condition flags (that is, even if the
destination register is unchanged in the event the condition is not met.).

These effects should be taken into account when considering whether to
use conditional execution for long latency operations. The overheads of
conditional execution might begin to outweigh the benefits. Consider the
following example.

MULEQ R1, R2, R3
MULNE R1, R2, R4

For this pair of instructions, the second multiply is dependent upon the
result of the first multiply, not through one of its normal input operands
(R2 and R4), but through the destination register R1. The combined latency
for these instructions is six cycles, rather than the four cycles that
would be required if these instructions were not conditional (three cycles
latency for the first, and one additional cycle for the second which is
fully pipelined behind the first)."

Re: Ill-advised use of CMOVE

<77b84bde-bf0a-401d-a0cf-4dc053bf5631n@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:620a:290d:b0:6b5:cecc:1cab with SMTP id m13-20020a05620a290d00b006b5cecc1cabmr21442627qkp.465.1658427418687;
Thu, 21 Jul 2022 11:16:58 -0700 (PDT)
X-Received: by 2002:a05:622a:591:b0:31d:4044:c457 with SMTP id
c17-20020a05622a059100b0031d4044c457mr35458369qtb.331.1658427418468; Thu, 21
Jul 2022 11:16:58 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Thu, 21 Jul 2022 11:16:58 -0700 (PDT)
In-Reply-To: <jwv1qx4xe9z.fsf-monnier+comp.arch@gnu.org>
Injection-Info: google-groups.googlegroups.com; posting-host=47.152.122.149; posting-account=SElZpwoAAADtNzbKlUw2Urm_8Oe1rSRp
NNTP-Posting-Host: 47.152.122.149
References: <jwv1qx4xe9z.fsf-monnier+comp.arch@gnu.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <77b84bde-bf0a-401d-a0cf-4dc053bf5631n@googlegroups.com>
Subject: Re: Ill-advised use of CMOVE
From: scooter....@gmail.com (Scott Michel)
Injection-Date: Thu, 21 Jul 2022 18:16:58 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3035
 by: Scott Michel - Thu, 21 Jul 2022 18:16 UTC

Your specific case might be one of the outliers compared to the dominant pattern against which GCC and LLVM match (and a branch would be disadvantageous.) C99 and onward treat boolean values as 0 or 1, which allows rewriting ternary expressions as an equivalent boolean:

x = cond ? val1 : val2

transforms to

x = (cond * val1) + (!cond * val2)

In a lot of code, val2 is often x:

x = cond ? val1 : x

Consequently, the expression lowers into using CMOVE if cond is true. In my experience, the pipeline bubble is preferable to getting stuck in the branch prediction unit, since most ternary expression conditions are indeterminate (no strong branch direction to predict.)

On Sunday, May 8, 2022 at 8:05:50 AM UTC-7, Stefan Monnier wrote:
> We recently bumped into a funny performance behavior in Emacs.
> Some code computing the length of a (possibly circular) list ended up
> macroexpanded to something like:
>
> for (struct for_each_tail_internal li = { list, 2, 0, 2 };
> CONSP (list);
> (list = XCDR (list),
> ((--li.q != 0
> || 0 < --li.n
> || (li.q = li.n = li.max <<= 1, li.n >>= USHRT_WIDTH,
> li.tortoise = (list), false))
> && EQ (list, li.tortoise))
> ? (void) (list = Qnil) : (void) 0))
> len++;
>
> `EQ` is currently a slightly costly operation but in this specific case
> it can be replaced with a plain `==`. When we tried that, the resulting
> loop ended up running almost twice *slower*.
>
> The problem turned out that with the simpler comparison, both GCC and
> LLVM decided it would be a good idea to use CMOVE for the
> `?:` operation, which just ends up making the data flow's critical path
> longer whereas a branch works much better here since it's trivial
> to predict.
>
>
> Stefan

Re: Ill-advised use of CMOVE

<da6f78a2-5702-4cd1-9fbe-6027a7c6a6bdn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:620a:a01:b0:6b5:c4e3:65af with SMTP id i1-20020a05620a0a0100b006b5c4e365afmr25027450qka.192.1658430388116;
Thu, 21 Jul 2022 12:06:28 -0700 (PDT)
X-Received: by 2002:a05:6214:1cc3:b0:46e:64aa:842a with SMTP id
g3-20020a0562141cc300b0046e64aa842amr35066106qvd.101.1658430387963; Thu, 21
Jul 2022 12:06:27 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Thu, 21 Jul 2022 12:06:27 -0700 (PDT)
In-Reply-To: <77b84bde-bf0a-401d-a0cf-4dc053bf5631n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=104.59.204.55; posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 104.59.204.55
References: <jwv1qx4xe9z.fsf-monnier+comp.arch@gnu.org> <77b84bde-bf0a-401d-a0cf-4dc053bf5631n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <da6f78a2-5702-4cd1-9fbe-6027a7c6a6bdn@googlegroups.com>
Subject: Re: Ill-advised use of CMOVE
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Thu, 21 Jul 2022 19:06:28 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2338
 by: MitchAlsup - Thu, 21 Jul 2022 19:06 UTC

On Thursday, July 21, 2022 at 1:17:00 PM UTC-5, Scott Michel wrote:
> Your specific case might be one of the outliers compared to the dominant pattern against which GCC and LLVM match (and a branch would be disadvantageous.) C99 and onward treat boolean values as 0 or 1, which allows rewriting ternary expressions as an equivalent boolean:
>
> x = cond ? val1 : val2
>
> transforms to
>
> x = (cond * val1) + (!cond * val2)
<
what happens when cond = 37 or 14569 ?
<
But to be pedantic as any good C programmer would do: it transforms to::
<
x = (!!cond & val1)|(!cond&val2)
>
> In a lot of code, val2 is often x:
>
> x = cond ? val1 : x
>
> Consequently, the expression lowers into using CMOVE if cond is true. In my experience, the pipeline bubble is preferable to getting stuck in the branch prediction unit, since most ternary expression conditions are indeterminate (no strong branch direction to predict.)
<
My 66000 has an instruction to perform my rewrite of your transform
without a pipeline bubble, but with a dependency on x.
>

Re: Ill-advised use of CMOVE

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

 copy mid

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

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: monn...@iro.umontreal.ca (Stefan Monnier)
Newsgroups: comp.arch
Subject: Re: Ill-advised use of CMOVE
Date: Thu, 21 Jul 2022 19:38:28 -0400
Organization: A noiseless patient Spider
Lines: 19
Message-ID: <jwvr12edowt.fsf-monnier+comp.arch@gnu.org>
References: <jwv1qx4xe9z.fsf-monnier+comp.arch@gnu.org>
<77b84bde-bf0a-401d-a0cf-4dc053bf5631n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="0973ff048980ce6bf11c50d7a74a50ec";
logging-data="2815796"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+9Do451IFDDOp1SdhhQ4iV"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
Cancel-Lock: sha1:IR5C8awlTcTPypT/YHU7XQXubvI=
sha1:ZbDih0ezbUrUEI37MADvlUGk6Xc=
 by: Stefan Monnier - Thu, 21 Jul 2022 23:38 UTC

> In my experience, the pipeline bubble is preferable to getting stuck
> in the branch prediction unit, since most ternary expression
> conditions are indeterminate (no strong branch direction to predict.)

I'm surprised to hear that "most ternary expression conditions are
indeterminate". In our code it's used very commonly to provide fallback
default values (like ... `x ? x : <foo>`) and, in most of those, one of
the two branches is a lot more frequent.

I suspect that the behavior of ternary expressions depends very strongly
on the coder: in my experience, many coders use them *extremely* rarely
(they will go through a fair bit of effort (usually without knowing it)
to turn them into `if`s). Whereas anyone with a functional programming
background will happily use them whenever possible (and will usually
wonder why on earth those weird languages decided to use two completely
different syntaxes for "if instruction" and "if expression").

Stefan

Re: Ill-advised use of CMOVE

<tbdeni$6nu$1@newsreader4.netcologne.de>

 copy mid

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

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!newsreader4.netcologne.de!news.netcologne.de!.POSTED.2001-4dd6-2699-0-7285-c2ff-fe6c-992d.ipv6dyn.netcologne.de!not-for-mail
From: tkoe...@netcologne.de (Thomas Koenig)
Newsgroups: comp.arch
Subject: Re: Ill-advised use of CMOVE
Date: Fri, 22 Jul 2022 06:05:38 -0000 (UTC)
Organization: news.netcologne.de
Distribution: world
Message-ID: <tbdeni$6nu$1@newsreader4.netcologne.de>
References: <jwv1qx4xe9z.fsf-monnier+comp.arch@gnu.org>
<77b84bde-bf0a-401d-a0cf-4dc053bf5631n@googlegroups.com>
<jwvr12edowt.fsf-monnier+comp.arch@gnu.org>
Injection-Date: Fri, 22 Jul 2022 06:05:38 -0000 (UTC)
Injection-Info: newsreader4.netcologne.de; posting-host="2001-4dd6-2699-0-7285-c2ff-fe6c-992d.ipv6dyn.netcologne.de:2001:4dd6:2699:0:7285:c2ff:fe6c:992d";
logging-data="6910"; mail-complaints-to="abuse@netcologne.de"
User-Agent: slrn/1.0.3 (Linux)
 by: Thomas Koenig - Fri, 22 Jul 2022 06:05 UTC

Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>> In my experience, the pipeline bubble is preferable to getting stuck
>> in the branch prediction unit, since most ternary expression
>> conditions are indeterminate (no strong branch direction to predict.)
>
> I'm surprised to hear that "most ternary expression conditions are
> indeterminate". In our code it's used very commonly to provide fallback
> default values (like ... `x ? x : <foo>`) and, in most of those, one of
> the two branches is a lot more frequent.
>
> I suspect that the behavior of ternary expressions depends very strongly
> on the coder: in my experience, many coders use them *extremely* rarely
> (they will go through a fair bit of effort (usually without knowing it)
> to turn them into `if`s). Whereas anyone with a functional programming
> background will happily use them whenever possible (and will usually
> wonder why on earth those weird languages decided to use two completely
> different syntaxes for "if instruction" and "if expression").

I would expect that most compilers just convert the ternary expression
to an if-statement first thing.

Example:

$ cat ternary.c
int ternary (int a, int b, _Bool cond)
{ return cond ? a : b;
} $ gcc -fdump-tree-gimple -c ternary.c
$ ls *ternary.c.*
ternary.c.005t.gimple
$ cat ternary.c.005t.gimple
ternary (int a, int b, _Bool cond)
{ int D.1916;
int iftmp.0;

if (cond != 0) goto <D.1918>; else goto <D.1919>;
<D.1918>:
iftmp.0 = a;
goto <D.1920>;
<D.1919>:
iftmp.0 = b;
<D.1920>:
D.1916 = iftmp.0;
return D.1916;
}

Conversion to gimple is actually the first thing that gcc does
after having created the original source tree, which can be
inspected with -fdump-tree-original. The name of the dump
file varies depending on compiler version and precise options,
it's best to look for it.

Pages:123456
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor