www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Standard way to supply hints to branches

reply Manu <turkeyman gmail.com> writes:
I'm working on microcontrollers, and many don't have a branch predictor.
They do "static" prediction, that is, they just predict branch-not-taken
and it's on you to write your code as such, and that's not always possible.
(like the loop condition in a for loop)

This leads to a lot of awkward looking if's written in unnatural
'backwards' terms, and also, leads to undesirable depth of nested scopes.

The compiler backend can and should re-jig the comparisons, but it needs to
receive a hint which way is 'likely' from the programmer.

How can we add an attribute to the branch condition that the backend can
take advantage of? I think it needs to be in the language spec...
Aug 22
next sibling parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 I'm working on microcontrollers, and many don't have a branch 
 predictor. They do "static" prediction, that is, they just 
 predict branch-not-taken and it's on you to write your code as 
 such, and that's not always possible. (like the loop condition 
 in a for loop)

 This leads to a lot of awkward looking if's written in 
 unnatural 'backwards' terms, and also, leads to undesirable 
 depth of nested scopes.

 The compiler backend can and should re-jig the comparisons, but 
 it needs to receive a hint which way is 'likely' from the 
 programmer.

 How can we add an attribute to the branch condition that the 
 backend can take advantage of? I think it needs to be in the 
 language spec...


For LDC see, 
https://github.com/ldc-developers/ldc/blob/master/runtime/druntime/src/ld
/intrinsics.di#L619 and see also `llvm_assume` just beneath it.

GDC probably has something similar too.
Aug 22
next sibling parent reply Iain Buclaw <ibuclaw gdcproject.org> writes:
On Friday, 23 August 2024 at 02:23:37 UTC, Nicholas Wilson wrote:

 GDC probably has something similar too.


https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect


Regarding DMD, I recall it being said that its code generator 
always treats the true branch as the "likely" code path taken. So 
if you have `if (cond) cold; else hot;`, invert the condition for 
the benefit of DMD.
Aug 23
next sibling parent reply Manu <turkeyman gmail.com> writes:
On Fri, 23 Aug 2024, 19:02 Iain Buclaw via Digitalmars-d, <
digitalmars-d puremagic.com> wrote:


 On Friday, 23 August 2024 at 02:23:37 UTC, Nicholas Wilson wrote:

 GDC probably has something similar too.



 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect


 Regarding DMD, I recall it being said that its code generator
 always treats the true branch as the "likely" code path taken. So
 if you have `if (cond) cold; else hot;`, invert the condition for
 the benefit of DMD.


Yes, I understand, and this is part of my point here; that leads to really
ugly code and deep nested scopes. That's what I've been doing, and I don't
want my program to look like that. It's just bad software.

For instance, an extraordinarily common function pattern is to receive some
inputs, validate a few things, and then do the thing at the end with valid
inputs.
Validations are usually a series of exclusionary checks framed as
`if(fails_validity_check) return;`
That flow keeps code in a nice linear flow, it doesn't introduce any scopes
at all... but it's the opposite of what the assume(true) prediction rule
wants. This is what lead me to this; almost every if statement I write is
predicted wrong... and I definitely don't want to solve that by writing
functions with 10 level deep nested scopes.






 Aug 23



 next sibling parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 24/08/2024 5:39 AM, Manu wrote:

 On Fri, 23 Aug 2024, 19:02 Iain Buclaw via Digitalmars-d, 
 <digitalmars-d puremagic.com <mailto:digitalmars-d puremagic.com>> wrote:
 
     On Friday, 23 August 2024 at 02:23:37 UTC, Nicholas Wilson wrote:
      >
      > GDC probably has something similar too.
 
     https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_00
fbuiltin_005fexpect <https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect>
 
 
     Regarding DMD, I recall it being said that its code generator
     always treats the true branch as the "likely" code path taken. So
     if you have `if (cond) cold; else hot;`, invert the condition for
     the benefit of DMD.
 
 
 Yes, I understand, and this is part of my point here; that leads to 
 really ugly code and deep nested scopes. That's what I've been doing, 
 and I don't want my program to look like that. It's just bad software.
 
 For instance, an extraordinarily common function pattern is to receive 
 some inputs, validate a few things, and then do the thing at the end 
 with valid inputs.
 Validations are usually a series of exclusionary checks framed as 
 `if(fails_validity_check) return;`
 That flow keeps code in a nice linear flow, it doesn't introduce any 
 scopes at all... but it's the opposite of what the assume(true) 
 prediction rule wants. This is what lead me to this; almost every if 
 statement I write is predicted wrong... and I definitely don't want to 
 solve that by writing functions with 10 level deep nested scopes.


If you want to propose something like an attribute on if statement, I'd 
be keen to see it (in ideas forum).

```d
void func() {
	 unlikely
	if (random() > 0.5)
		return;
	 likely
	else {

	}
}
```



 Aug 23



 next sibling parent  "H. S. Teoh" <hsteoh qfbox.info>  writes:


On Sat, Aug 24, 2024 at 05:43:33AM +1200, Richard (Rikki) Andrew Cattermole via
Digitalmars-d wrote:

 
 On 24/08/2024 5:39 AM, Manu wrote:


[...]

 For instance, an extraordinarily common function pattern is to
 receive some inputs, validate a few things, and then do the thing at
 the end with valid inputs.
 Validations are usually a series of exclusionary checks framed as
 `if(fails_validity_check) return;`
 That flow keeps code in a nice linear flow, it doesn't introduce any
 scopes at all... but it's the opposite of what the assume(true)
 prediction rule wants.




[...]

 If you want to propose something like an attribute on if statement, I'd be
 keen to see it (in ideas forum).
 
 ```d
 void func() {
 	 unlikely
 	if (random() > 0.5)
 		return;
 	 likely
 	else {
 
 	}
 }
 ```


This would be very nice to have.  I have quite a lot of code with early
return, because it keeps nesting down to a sane level. But there are two
opposing cases: the first is Manu's case, you want to validate
parameters and abort early if you find something amiss.

But the second case is, you exit early to avoid an expensive computation
if an initial stab got the right answer / is good enough / or the answer
is cached and you just return it instead of recomputing it.

The second case works well with the assume(true) prediction rule.  But
the first case works poorly.  I'd say a standardized attribute would be
very nice to have.


T

-- 
Doubt is a self-fulfilling prophecy.



 Aug 23



prev sibling  parent  Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Friday, 23 August 2024 at 17:43:33 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

 On 24/08/2024 5:39 AM, Manu wrote:

 On Fri, 23 Aug 2024, 19:02 Iain Buclaw via Digitalmars-d, 
 <digitalmars-d puremagic.com 
 <mailto:digitalmars-d puremagic.com>> wrote:
 
     On Friday, 23 August 2024 at 02:23:37 UTC, Nicholas Wilson 
 wrote:
      >
      > GDC probably has something similar too.
 
     
 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_00
fbuiltin_005fexpect <https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect>
 
 
     Regarding DMD, I recall it being said that its code 
 generator
     always treats the true branch as the "likely" code path 
 taken. So
     if you have `if (cond) cold; else hot;`, invert the 
 condition for
     the benefit of DMD.
 
 
 Yes, I understand, and this is part of my point here; that 
 leads to really ugly code and deep nested scopes. That's what 
 I've been doing, and I don't want my program to look like 
 that. It's just bad software.
 
 For instance, an extraordinarily common function pattern is to 
 receive some inputs, validate a few things, and then do the 
 thing at the end with valid inputs.
 Validations are usually a series of exclusionary checks framed 
 as `if(fails_validity_check) return;`
 That flow keeps code in a nice linear flow, it doesn't 
 introduce any scopes at all... but it's the opposite of what 
 the assume(true) prediction rule wants. This is what lead me 
 to this; almost every if statement I write is predicted 
 wrong... and I definitely don't want to solve that by writing 
 functions with 10 level deep nested scopes.


 If you want to propose something like an attribute on if 
 statement, I'd be keen to see it (in ideas forum).

 ```d
 void func() {
 	 unlikely
 	if (random() > 0.5)
 		return;
 	 likely
 	else {

 	}
 }
 ```


It should be a pragma. In general, a pragma is something a 
conforming compiler can ignore without changing semantics. Inline 
is a pragma for exactly this reason. An attribute makes no sense.
```d
if (cond()) { pragma(unlikely); return; }
```



 Sep 06



prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com>  writes:


I recently learned a syntactical trick on how to do this.

```
if (x) return;
if (y) return;
if (z) return;
hotPath();
```

Rewrite as:

```
do
{
     if (x) break;
     if (y) break;
     if (z) break;
     hotPath();
} while (0);
```

Of course, this will also work:

```
if (x) goto Lreturn;
if (y) goto Lreturn;
if (z) goto Lreturn;
hotPath();
Lreturn:
```



 Aug 23



  parent  Rob T <alanb ucora.com>  writes:


On Saturday, 24 August 2024 at 02:34:04 UTC, Walter Bright wrote:

 I recently learned a syntactical trick on how to do this.

 ```
 if (x) return;
 if (y) return;
 if (z) return;
 hotPath();
 ```

 Rewrite as:

 ```
 do
 {
     if (x) break;
     if (y) break;
     if (z) break;
     hotPath();
 } while (0);
 ```

 Of course, this will also work:

 ```
 if (x) goto Lreturn;
 if (y) goto Lreturn;
 if (z) goto Lreturn;
 hotPath();
 Lreturn:
 ```


I almost always do a similar thing as a general coding principle, 
ie, get all the conditional checks out of the way first, before 
moving on to the main code path. In most cases, the "hot path" 
will be the main code path to take, but the main reason I do it 
in this way (as a general rule), is to make the code easier to 
understand and manage.

As for the branch predicting, my understanding is that it will 
depend on the combination of the choice of compiler, and the 
processor the code is executed on. Some processors, will attempt 
to execute more than one path simultaneously until the correct 
path is determined. As for optimizing your code, in my 
experience, is that in general, there will always be much more 
effective methods to prioritize than trying to optimize branch 
predictions, but I suppose it depends entirely on the fine 
details of what is being attempted.



 Sep 13



prev sibling  parent reply Kagamin <spam here.lot>  writes:


On Friday, 23 August 2024 at 17:39:39 UTC, Manu wrote:

 Validations are usually a series of exclusionary checks framed 
 as
 `if(fails_validity_check) return;`
 That flow keeps code in a nice linear flow, it doesn't 
 introduce any scopes


Aren't returns grouped near the end of function? Then validation 
checks would be implemented as forward jumps, which at least 
riscv interprets as unlikely by default.



 Aug 28



  parent  Manu <turkeyman gmail.com>  writes:


I'm not sure what you mean? In my experience, returns are generally grouped
at the top.

void f(int x)
{
  if (x < 0)
    return;

  do;
  if (do.error)
    return;

  some;
  work;
}

In lieu of any hinting, the if is assumed true; so the compiler will branch
over the return in the nominal case.

You would need to write this to fix that bad prediction:

void f(int x)
{
  if (x >= 0)
  {
    do;
    if (!do.error)
    {
      some;
      work;
    }
  }
}

You can see how the function body will accumulate unmitigated scopes now.
That's just straight up bad code. (Linus would sack me on the spot if I
wrote that!)
It's not at all unlikely to find functions that have several such checks in
series... I won't write code that's an ugly sea of nesting.

On Wed, 28 Aug 2024 at 19:01, Kagamin via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Friday, 23 August 2024 at 17:39:39 UTC, Manu wrote:

 Validations are usually a series of exclusionary checks framed
 as
 `if(fails_validity_check) return;`
 That flow keeps code in a nice linear flow, it doesn't
 introduce any scopes


 Aren't returns grouped near the end of function? Then validation
 checks would be implemented as forward jumps, which at least
 riscv interprets as unlikely by default.





 Aug 28



prev sibling next sibling parent  Manu <turkeyman gmail.com>  writes:


On Sat, 24 Aug 2024, 03:39 Manu, <turkeyman gmail.com> wrote:


 On Fri, 23 Aug 2024, 19:02 Iain Buclaw via Digitalmars-d, <
 digitalmars-d puremagic.com> wrote:


 On Friday, 23 August 2024 at 02:23:37 UTC, Nicholas Wilson wrote:

 GDC probably has something similar too.



 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect


 Regarding DMD, I recall it being said that its code generator
 always treats the true branch as the "likely" code path taken. So
 if you have `if (cond) cold; else hot;`, invert the condition for
 the benefit of DMD.


 Yes, I understand, and this is part of my point here; that leads to really
 ugly code and deep nested scopes. That's what I've been doing, and I don't
 want my program to look like that. It's just bad software.

 For instance, an extraordinarily common function pattern is to receive
 some inputs, validate a few things, and then do the thing at the end with
 valid inputs.
 Validations are usually a series of exclusionary checks framed as
 `if(fails_validity_check) return;`
 That flow keeps code in a nice linear flow, it doesn't introduce any
 scopes at all... but it's the opposite of what the assume(true) prediction
 rule wants. This is what lead me to this; almost every if statement I write
 is predicted wrong... and I definitely don't want to solve that by writing
 functions with 10 level deep nested scopes.


Sorry, I meant *expect(true)*, not assume! ;)






 Aug 23



prev sibling  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 8/23/2024 1:56 AM, Iain Buclaw wrote:

 Regarding DMD, I recall it being said that its code generator always treats
the 
 true branch as the "likely" code path taken. So if you have `if (cond) cold; 
 else hot;`, invert the condition for the benefit of DMD.


That's correct.



 Aug 23



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 8/23/2024 7:24 PM, Walter Bright wrote:

 On 8/23/2024 1:56 AM, Iain Buclaw wrote:

 Regarding DMD, I recall it being said that its code generator always treats 
 the true branch as the "likely" code path taken. So if you have `if (cond) 
 cold; else hot;`, invert the condition for the benefit of DMD.


 
 That's correct.


It's not pedantically correct. More precisely, any code following the `if` is 
presumed to be the hot path. A branch instruction doesn't count, i.e. it's the 
branch-not-taken that is considered the hot path.



 Aug 23



 next sibling parent reply Dukc <ajieskola gmail.com>  writes:


Walter Bright kirjoitti 24.8.2024 klo 6.37:

 It's not pedantically correct. More precisely, any code following the 
 `if` is presumed to be the hot path. A branch instruction doesn't count, 
 i.e. it's the branch-not-taken that is considered the hot path.


Can you elaborate? I'm not sure what's the difference between `if` and a 
branch instruction.



 Aug 23



  parent  "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 24/08/2024 5:48 PM, Dukc wrote:

 Walter Bright kirjoitti 24.8.2024 klo 6.37:

 It's not pedantically correct. More precisely, any code following the 
 `if` is presumed to be the hot path. A branch instruction doesn't 
 count, i.e. it's the branch-not-taken that is considered the hot path.


 Can you elaborate? I'm not sure what's the difference between `if` and a 
 branch instruction.


In pseudo assembly it would look something like this:

```
test condition;
jump-if-zero ColdPath;

HotPath:
	...
	goto End;

ColdPath:
	...

End:
	...
```


In pseudo code:

```
if (condition == 0)
	goto ColdPath;

HotPath:
{
}
goto End;

ColdPath:
{
}

End:
{
}
```

Converted to an if statement:

```d
if (condition) {
	// cold path
} else {
	// hot path
}

// hot path at end
``

In essence in the CPU, any instruction that jumps around conditionally 
can be assumed to not be taken. Note: this is very CPU dependent and in 
the last 15 years has gotten a LOT smarter.



 Aug 23



prev sibling  parent reply IchorDev <zxinsworld gmail.com>  writes:


On Saturday, 24 August 2024 at 03:37:32 UTC, Walter Bright wrote:

 It's not pedantically correct. More precisely, any code 
 following the `if` is presumed to be the hot path. A branch 
 instruction doesn't count, i.e. it's the branch-not-taken that 
 is considered the hot path.


I think everyone in this thread can agree that we need a 
compiler-agnostic solution for changing the presumed hot-path, 
and one that doesn’t require rewriting existing code more than 
just adding on one word. For example, `if((x == 
y).expect(false)){}` makes it a pain to rewrite existing `if`s, 
where ` unlikely if(x == y) {}` is easy.



 Aug 24



  parent reply user1234 <user1234 12.de>  writes:


On Saturday, 24 August 2024 at 08:06:21 UTC, IchorDev wrote:

 On Saturday, 24 August 2024 at 03:37:32 UTC, Walter Bright 
 wrote:

 It's not pedantically correct. More precisely, any code 
 following the `if` is presumed to be the hot path. A branch 
 instruction doesn't count, i.e. it's the branch-not-taken that 
 is considered the hot path.


 I think everyone in this thread can agree that we need a 
 compiler-agnostic solution for changing the presumed hot-path, 
 and one that doesn’t require rewriting existing code more than 
 just adding on one word. For example, `if((x == 
 y).expect(false)){}` makes it a pain to rewrite existing `if`s, 
 where ` unlikely if(x == y) {}` is easy.


You also have the `pragma` option. I think that would be more 
adequate as not every vendor has to support it. In other words 
"dmd can just ignore it". Bonus: pragma can be attached to 
statements, that's not the case of attributes.



 Aug 24



  parent reply IchorDev <zxinsworld gmail.com>  writes:


On Saturday, 24 August 2024 at 09:11:34 UTC, user1234 wrote:

 On Saturday, 24 August 2024 at 08:06:21 UTC, IchorDev wrote:

 I think everyone in this thread can agree that we need a 
 compiler-agnostic solution for changing the presumed hot-path, 
 and one that doesn’t require rewriting existing code more than 
 just adding on one word. For example, `if((x == 
 y).expect(false)){}` makes it a pain to rewrite existing 
 `if`s, where ` unlikely if(x == y) {}` is easy.


 You also have the `pragma` option. I think that would be more 
 adequate as not every vendor has to support it. In other words 
 "dmd can just ignore it". Bonus: pragma can be attached to 
 statements, that's not the case of attributes.


Like `pragma(likely, false)`? It’s a bit long, maybe 
`pragma(unlikely)`? It’s something I’d want to use fairly often, 
after all. Or we could just add some new grammar for adding 
special modifiers to if statements. Something like…
```d
if: unlikely(x){
   //…
}
if(!x){
   //…
}else: likely{
   //…
}
```



 Aug 24



  parent reply Manu <turkeyman gmail.com>  writes:


On Sat, 24 Aug 2024 at 21:46, IchorDev via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Saturday, 24 August 2024 at 09:11:34 UTC, user1234 wrote:

 On Saturday, 24 August 2024 at 08:06:21 UTC, IchorDev wrote:

 I think everyone in this thread can agree that we need a
 compiler-agnostic solution for changing the presumed hot-path,
 and one that doesn=E2=80=99t require rewriting existing code more than
 just adding on one word. For example, `if((x =3D=3D
 y).expect(false)){}` makes it a pain to rewrite existing
 `if`s, where ` unlikely if(x =3D=3D y) {}` is easy.


 You also have the `pragma` option. I think that would be more
 adequate as not every vendor has to support it. In other words
 "dmd can just ignore it". Bonus: pragma can be attached to
 statements, that's not the case of attributes.


 Like `pragma(likely, false)`? It=E2=80=99s a bit long, maybe
 `pragma(unlikely)`? It=E2=80=99s something I=E2=80=99d want to use fairly=


 often,

 after all. Or we could just add some new grammar for adding
 special modifiers to if statements. Something like=E2=80=A6
 ```d
 if: unlikely(x){
    //=E2=80=A6
 }
 if(!x){
    //=E2=80=A6
 }else: likely{
    //=E2=80=A6
 }
 ```


C++ is way ahead on this... they added attributes to the language years
back, and they defined [[likely]] and [[unlikely]] post-fix on control
statements. It's really convenient, it reads well, and it's easy to
retrofit without disturbing the code.
That's the de-facto now, and we should follow it.



 Aug 24



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 8/24/2024 9:47 AM, Manu wrote:

 C++ is way ahead on this... they added attributes to the language years back, 
 and they defined [[likely]] and [[unlikely]] post-fix on control statements. 
 It's really convenient, it reads well, and it's easy to retrofit without 
 disturbing the code.
 That's the de-facto now, and we should follow it.


It's unattractive.

I provided two alternate means to accomplish the same thing elsewhere in this 
thread.

https://www.digitalmars.com/d/archives/digitalmars/D/Standard_way_to_supply_hints_to_branches_375697.html#N375717



 Aug 26



 next sibling parent reply Dom DiSc <dominikus scherkl.de>  writes:


On Monday, 26 August 2024 at 07:12:47 UTC, Walter Bright wrote:

 I recently learned a syntactical trick on how to do this.
 
 ```
 do
 {
    if (x) break;
    if (y) break;
    if (z) break;
    hotPath();
 } while (0);
 ```


Why does this work? The else path is still the cold path, isn't 
it?



 Aug 26



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 8/26/2024 2:08 AM, Dom DiSc wrote:

 Why does this work? The else path is still the cold path, isn't it?


It works because the "break" is not considered the hot path.



 Aug 27



prev sibling next sibling parent  Manu <turkeyman gmail.com>  writes:


On Mon, 26 Aug 2024 at 17:16, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 8/24/2024 9:47 AM, Manu wrote:

 C++ is way ahead on this... they added attributes to the language years


 back,

 and they defined [[likely]] and [[unlikely]] post-fix on control


 statements.

 It's really convenient, it reads well, and it's easy to retrofit without
 disturbing the code.
 That's the de-facto now, and we should follow it.


 It's unattractive.

 I provided two alternate means to accomplish the same thing elsewhere in
 this
 thread.


 https://www.digitalmars.com/d/archives/digitalmars/D/Standard_way_to_supply_hints_to_branches_375697.html#N375717


"Unattractive"? ... seriously?
Your suggestions were to quite seriously molest the code, reordering,
adding extra scopes, inverting logic, nonsense statements like `do {}
while(0)`, using labels and goto's which doesn't marry well with general
control flow and RAII type things... sorry; but "unattractive"? That might
be the most bizarre thing I've ever heard you say! ;)



 Aug 26



prev sibling  parent reply Manu <turkeyman gmail.com>  writes:


On Tue, 27 Aug 2024 at 15:27, Manu <turkeyman gmail.com> wrote:


 On Mon, 26 Aug 2024 at 17:16, Walter Bright via Digitalmars-d <
 digitalmars-d puremagic.com> wrote:


 On 8/24/2024 9:47 AM, Manu wrote:

 C++ is way ahead on this... they added attributes to the language years


 back,

 and they defined [[likely]] and [[unlikely]] post-fix on control


 statements.

 It's really convenient, it reads well, and it's easy to retrofit


 without

 disturbing the code.
 That's the de-facto now, and we should follow it.


 It's unattractive.

 I provided two alternate means to accomplish the same thing elsewhere in
 this
 thread.


 https://www.digitalmars.com/d/archives/digitalmars/D/Standard_way_to_supply_hints_to_branches_375697.html#N375717


 "Unattractive"? ... seriously?
 Your suggestions were to quite seriously molest the code, reordering,
 adding extra scopes, inverting logic, nonsense statements like `do {}
 while(0)`, using labels and goto's which doesn't marry well with general
 control flow and RAII type things... sorry; but "unattractive"? That might
 be the most bizarre thing I've ever heard you say! ;)


Just so it's clear what's going on here; certain microcontrollers don't
have branch predictors at all; so hinting is essential on these exotic
platforms. Your suggestions could appear in almost every single
at-least-warm function, and it's not clear how they marry with eachother.
We discussed 2 principle cases; likely early return because of short-path
or cached value, and unlikely early return due to argument validation
failure. Plenty of functions contain both cases, and plenty of functions
contain numerous such items.
Try and imagine how your suggestion scales when there are 4-5 conditions
that need to be tested on function entry, and they don't all receive the
same hint. I value readable and maintainable code...



 Aug 26



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 8/26/2024 10:39 PM, Manu wrote:

 Your suggestions could appear in almost every single at-least-warm function,
and 
 it's not clear how they marry with eachother. We discussed 2 principle cases; 
 likely early return because of short-path or cached value, and unlikely early 
 return due to argument validation failure. Plenty of functions contain both 
 cases, and plenty of functions contain numerous such items.
 Try and imagine how your suggestion scales when there are 4-5 conditions that 
 need to be tested on function entry, and they don't all receive the same hint.
I 
 value readable and maintainable code...


For reference, a real world example of your code?



 Aug 27



  parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 28 Aug 2024 at 07:26, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 8/26/2024 10:39 PM, Manu wrote:

 Your suggestions could appear in almost every single at-least-warm


 function, and

 it's not clear how they marry with eachother. We discussed 2 principle


 cases;

 likely early return because of short-path or cached value, and unlikely


 early

 return due to argument validation failure. Plenty of functions contain


 both

 cases, and plenty of functions contain numerous such items.
 Try and imagine how your suggestion scales when there are 4-5 conditions


 that

 need to be tested on function entry, and they don't all receive the same


 hint. I

 value readable and maintainable code...


 For reference, a real world example of your code?


Here's one that I just wrote a short while ago:
https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c

This function can be very hot; called once for every byte in a byte stream
when sifting for a signal in a noisy transmission environment.
There are 4-5 guaranteed mispredictions in the nominal path in lieu of
hints...



 Aug 28



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 8/28/2024 2:45 AM, Manu wrote:

 Here's one that I just wrote a short while ago:
 https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c 



```
if (data.length < 4) // unlikely
     return 0;
```

replace with:

```
if (data.length < 4)
     goto Lreturn0;
```



 Aug 29



 next sibling parent reply Manu <turkeyman gmail.com>  writes:


On Fri, 30 Aug 2024 at 04:32, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 8/28/2024 2:45 AM, Manu wrote:

 Here's one that I just wrote a short while ago:
 https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c



 ```
 if (data.length < 4) // unlikely
      return 0;
 ```

 replace with:

 ```
 if (data.length < 4)
      goto Lreturn0;
 ```


How is that any different? The branch prediction hasn't changed.



 Aug 29



  parent reply Dom DiSc <dominikus scherkl.de>  writes:


On Friday, 30 August 2024 at 02:54:28 UTC, Manu wrote:

 On Fri, 30 Aug 2024 at 04:32, Walter Bright via Digitalmars-d < 
 digitalmars-d puremagic.com> wrote:


 On 8/28/2024 2:45 AM, Manu wrote:

 Here's one that I just wrote a short while ago: 
 https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c



 ```
 if (data.length < 4) // unlikely
      return 0;
 ```

 replace with:

 ```
 if (data.length < 4)
      goto Lreturn0;
 ```


 How is that any different? The branch prediction hasn't changed.


I already asked this question.
He said a single break or goto is NOT considered the hot branch 
by the compiler.
But I don't like this, because it's an implementation detail that 
every compiler may implement or not, and it's not documented 
anywhere.
Maybe if the documentation would clearly state at a prominent 
point that a single break or goto has to be considered the cold 
path by the compiler, but a function call is to be considered the 
hot path (and all related queries about branch priorization link 
there), then I would consider this a solution. But is it likely 
this will happen?



 Aug 31



 next sibling parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 8/31/2024 9:11 AM, Dom DiSc wrote:

 I already asked this question.
 He said a single break or goto is NOT considered the hot branch by the
compiler.
 But I don't like this, because it's an implementation detail that every
compiler 
 may implement or not, and it's not documented anywhere.
 Maybe if the documentation would clearly state at a prominent point that a 
 single break or goto has to be considered the cold path by the compiler, but a 
 function call is to be considered the hot path (and all related queries about 
 branch priorization link there), then I would consider this a solution. But is 
 it likely this will happen?


It's the obvious consequence of laying out the code in the same order as the 
programmer laid it out. AFAIK every compiler does this by default.



 Aug 31



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 8/31/2024 5:34 PM, Walter Bright wrote:

 It's the obvious consequence of laying out the code in the same order as the 
 programmer laid it out. AFAIK every compiler does this by default.


Also the consequence of the "forward branch not taken" is assumed to be the hot 
one by the CPU, and the "backwards branch taken" is also assumed to be the hot
one.



 Aug 31



prev sibling  parent reply Manu <turkeyman gmail.com>  writes:


On Sat, 31 Aug 2024 at 17:16, Dom DiSc via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Friday, 30 August 2024 at 02:54:28 UTC, Manu wrote:

 On Fri, 30 Aug 2024 at 04:32, Walter Bright via Digitalmars-d <
 digitalmars-d puremagic.com> wrote:


 On 8/28/2024 2:45 AM, Manu wrote:

 Here's one that I just wrote a short while ago:
 https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c



 ```
 if (data.length < 4) // unlikely
      return 0;
 ```

 replace with:

 ```
 if (data.length < 4)
      goto Lreturn0;
 ```


 How is that any different? The branch prediction hasn't changed.


 I already asked this question.
 He said a single break or goto is NOT considered the hot branch
 by the compiler.


The goto is not a branch at all. The if() is the branch... and it still
predicts the pessimistic case incorrectly.
Replacing the return with a goto hasn't changed the control flow in any
way; goto and return are equivalent; they are not branches.



 But I don't like this, because it's an implementation detail that
 every compiler may implement or not, and it's not documented
 anywhere.
 Maybe if the documentation would clearly state at a prominent
 point that a single break or goto has to be considered the cold
 path by the compiler, but a function call is to be considered the
 hot path (and all related queries about branch priorization link
 there), then I would consider this a solution. But is it likely
 this will happen?





 Sep 10



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


Compile the following with -vasm -O:

```
void bar();

int foo(int i)
{
     if (i)
         return 0;
     bar();
     return 1;
}

int baz(int i)
{
     if (i)
         goto Lreturn0;
     bar();
     return 1;

Lreturn0:
     return 0;
}
```
and you get:
```
_D5test93fooFiZi:
0000:   55                       push      RBP
0001:   48 8B EC                 mov       RBP,RSP
0004:   85 FF                    test      EDI,EDI
0006:   74 04                    je        Lc
0008:   31 C0                    xor       EAX,EAX // hot path
000a:   5D                       pop       RBP
000b:   C3                       ret
000c:   E8 00 00 00 00           call      L0   // cold path
0011:   B8 01 00 00 00           mov       EAX,1
0016:   5D                       pop       RBP
0017:   C3                       ret
_D5test93bazFiZi:
0000:   55                       push      RBP
0001:   48 8B EC                 mov       RBP,RSP
0004:   85 FF                    test      EDI,EDI
0006:   75 0C                    jne       L14
0008:   E8 00 00 00 00           call      L0   // hot path
000d:   B8 01 00 00 00           mov       EAX,1
0012:   5D                       pop       RBP
0013:   C3                       ret
0014:   31 C0                    xor       EAX,EAX // cold path
0016:   5D                       pop       RBP
0017:   C3                       ret
```



 Sep 10



  parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 11 Sept 2024 at 06:21, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 Compile the following with -vasm -O:

 ```
 void bar();

 int foo(int i)
 {
      if (i)
          return 0;
      bar();
      return 1;
 }

 int baz(int i)
 {
      if (i)
          goto Lreturn0;
      bar();
      return 1;

 Lreturn0:
      return 0;
 }
 ```
 and you get:
 ```
 _D5test93fooFiZi:
 0000:   55                       push      RBP
 0001:   48 8B EC                 mov       RBP,RSP
 0004:   85 FF                    test      EDI,EDI
 0006:   74 04                    je        Lc
 0008:   31 C0                    xor       EAX,EAX // hot path
 000a:   5D                       pop       RBP
 000b:   C3                       ret
 000c:   E8 00 00 00 00           call      L0   // cold path
 0011:   B8 01 00 00 00           mov       EAX,1
 0016:   5D                       pop       RBP
 0017:   C3                       ret
 _D5test93bazFiZi:
 0000:   55                       push      RBP
 0001:   48 8B EC                 mov       RBP,RSP
 0004:   85 FF                    test      EDI,EDI
 0006:   75 0C                    jne       L14
 0008:   E8 00 00 00 00           call      L0   // hot path
 000d:   B8 01 00 00 00           mov       EAX,1
 0012:   5D                       pop       RBP
 0013:   C3                       ret
 0014:   31 C0                    xor       EAX,EAX // cold path
 0016:   5D                       pop       RBP
 0017:   C3                       ret
 ```


Okay, I see. You're depending on the optimiser to specifically collapse the
goto into the branch as a simplification.
Surely that's not even remotely reliable. There are several ways to
optimise that function, and I see no reason an optimiser would reliably
choose a construct like you show.

I'm actually a little surprised; a lifetime of experience with this sort of
thing might have lead me to predict that the optimiser would *actually*
shift the `return 0` up into the place of the goto, effectively eliminating
the goto... I'm sure I've seen optimisers do that transformation before,
but I can't recall ever noting an instance of code generation that looks
like what you pasted... I reckon I might have spotted that before.

... and turns out, I'm right. I was so surprised with the codegen you
present that I pulled out compiler explorer and ran some experiments.
I tested GCC and Clang for x86, MIPS, and PPC, all of which I am extremely
familiar with, and all of them optimise the way I predicted. None of them
showed a pattern like you presented here.

If I had to guess; I would actually imagine that GCC and Clang will very
deliberately NOT make a transformation like the one you show, for the
precise reason that such a transformation changes the nature of static
branch prediction which someone might have written code to rely on. It
would be dangerous for the optimiser to transform the code in the way you
show, and so it doesn't.



 Sep 11



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 4:44 AM, Manu wrote:

 Okay, I see. You're depending on the optimiser to specifically collapse the
goto 
 into the branch as a simplification.


Actually, the same code is generated without optimization. All it's doing is 
removing blocks that consist of nothing but "goto". It's a trivial
optimization, 
and was there in the earliest version of the compiler.



 Surely that's not even remotely reliable. There are several ways to optimise 
 that function, and I see no reason an optimiser would reliably choose a 
 construct like you show.


gcc -O does more or less the same thing.



 I'm actually a little surprised; a lifetime of experience with this sort of 
 thing might have lead me to predict that the optimiser would /actually/ shift 
 the `return 0` up into the place of the goto, effectively eliminating the 
 goto... I'm sure I've seen optimisers do that transformation before, but I
can't 
 recall ever noting an instance of code generation that looks like what you 
 pasted... I reckon I might have spotted that before.


The goto remains in the gcc -O version.



 ... and turns out, I'm right. I was so surprised with the codegen you present 
 that I pulled out compiler explorer and ran some experiments.
 I tested GCC and Clang for x86, MIPS, and PPC, all of which I am extremely 
 familiar with, and all of them optimise the way I predicted. None of them
showed 
 a pattern like you presented here.


gcc -O produced:

```
foo:
     mov       EAX,0
     test      EDI,EDI
     jne       L1B
     sub       RSP,8
     call      bar PC32
     mov       EAX,1
     add       RSP,8
L1B:    rep
     ret
baz:
     mov       EAX,0
     test      EDI,EDI
     jne       L38
     sub       RSP,8
     call      bar PC32
     mov       EAX,1
     add       RSP,8
L38:    rep
     ret
```


 If I had to guess; I would actually imagine that GCC and Clang will very 
 deliberately NOT make a transformation like the one you show, for the precise 
 reason that such a transformation changes the nature of static branch
prediction 
 which someone might have written code to rely on. It would be dangerous for
the 
 optimiser to transform the code in the way you show, and so it doesn't.


The transformation is (intermediate code):
```
if (i) goto L2; else goto L4;
L2:
    goto L3;
L4:
    bar();
    return 1;
L3:
    return 0;
```
becomes:
```
if (!i) goto L3; else goto L4;
L4:
     bar();
     return 1;
L3:
     return 0;
```
I.e. the goto->goto was replaced with a single goto.

It's not dangerous or weird at all, nor does it interfere with branch
prediction.



 Sep 11



  parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 11 Sept 2024 at 18:26, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/11/2024 4:44 AM, Manu wrote:

 Okay, I see. You're depending on the optimiser to specifically collapse


 the goto

 into the branch as a simplification.


 Actually, the same code is generated without optimization. All it's doing
 is
 removing blocks that consist of nothing but "goto". It's a trivial
 optimization,
 and was there in the earliest version of the compiler.



 Surely that's not even remotely reliable. There are several ways to


 optimise

 that function, and I see no reason an optimiser would reliably choose a
 construct like you show.


 gcc -O does more or less the same thing.



 I'm actually a little surprised; a lifetime of experience with this sort


 of

 thing might have lead me to predict that the optimiser would /actually/


 shift

 the `return 0` up into the place of the goto, effectively eliminating


 the

 goto... I'm sure I've seen optimisers do that transformation before, but


 I can't

 recall ever noting an instance of code generation that looks like what


 you

 pasted... I reckon I might have spotted that before.


 The goto remains in the gcc -O version.



 ... and turns out, I'm right. I was so surprised with the codegen you


 present

 that I pulled out compiler explorer and ran some experiments.
 I tested GCC and Clang for x86, MIPS, and PPC, all of which I am


 extremely

 familiar with, and all of them optimise the way I predicted. None of


 them showed

 a pattern like you presented here.


 gcc -O produced:

 ```
 foo:
      mov       EAX,0
      test      EDI,EDI
      jne       L1B
      sub       RSP,8
      call      bar PC32
      mov       EAX,1
      add       RSP,8
 L1B:    rep
      ret
 baz:
      mov       EAX,0
      test      EDI,EDI
      jne       L38
      sub       RSP,8
      call      bar PC32
      mov       EAX,1
      add       RSP,8
 L38:    rep
      ret
 ```


 If I had to guess; I would actually imagine that GCC and Clang will very
 deliberately NOT make a transformation like the one you show, for the


 precise

 reason that such a transformation changes the nature of static branch


 prediction

 which someone might have written code to rely on. It would be dangerous


 for the

 optimiser to transform the code in the way you show, and so it doesn't.


 The transformation is (intermediate code):
 ```
 if (i) goto L2; else goto L4;
 L2:
     goto L3;
 L4:
     bar();
     return 1;
 L3:
     return 0;
 ```
 becomes:
 ```
 if (!i) goto L3; else goto L4;
 L4:
      bar();
      return 1;
 L3:
      return 0;
 ```
 I.e. the goto->goto was replaced with a single goto.

 It's not dangerous or weird at all, nor does it interfere with branch
 prediction.


It inverts the condition. In the case on trial, that inverts the branch
prediction.

But that aside, I'm even more confused; I couldn't reproduce that in any of
my tests.
Here's a bunch of my test copiles... they all turn out the same:

gcc:

baz(int):
        test    edi, edi
        je      .L10
        xor     eax, eax
        ret
.L10:
        sub     rsp, 8
        call    bar()
        mov     eax, 1
        add     rsp, 8
        ret

clang:

baz(int):
        xor     eax, eax
        test    edi, edi
        je      .LBB0_1
        ret
.LBB0_1:
        push    rax
        call    bar() PLT
        mov     eax, 1
        add     rsp, 8
        ret

gcc-powerpc:

baz(int):
        cmpwi 0,3,0
        beq- 0,.L9
        li 3,0
        blr
.L9:
        stwu 1,-16(1)
        mflr 0
        stw 0,20(1)
        bl bar()
        lwz 0,20(1)
        li 3,1
        addi 1,1,16
        mtlr 0
        blr

arm64:

baz(int):
        cbz     w0, .L9
        mov     w0, 0
        ret
.L9:
        stp     x29, x30, [sp, -16]!
        mov     x29, sp
        bl      bar()
        mov     w0, 1
        ldp     x29, x30, [sp], 16
        ret

clang-mips:

baz(int):
        beqz    $4, $BB0_2
        addiu   $2, $zero, 0
        jr      $ra
        nop
$BB0_2:
        addiu   $sp, $sp, -24
        sw      $ra, 20($sp)
        sw      $fp, 16($sp)
        move    $fp, $sp
        jal     bar()
        nop
        addiu   $2, $zero, 1
        move    $sp, $fp
        lw      $fp, 16($sp)
        lw      $ra, 20($sp)
        jr      $ra
        addiu   $sp, $sp, 24

Even if you can manage to convince a compiler to write the output you're
alleging, I would never imagine for a second that's a reliable strategy.
The optimiser could do all kinds of things... even though in all my
experiments, it does exactly what I predicted it would.



 Sep 11



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 3:23 PM, Manu wrote:

 Even if you can manage to convince a compiler to write the output you're 
 alleging,


Alleging? I cut and pasted what dmd did and what gcc did. My gcc may behave 
differently than yours, as there are many versions of it.


 I would never imagine for a second that's a reliable strategy. The 
 optimiser could do all kinds of things... even though in all my experiments,
it 
 does exactly what I predicted it would.


Did you use -O?

dmd does what I predicted it would, as it is designed to operate that way. If 
gcc doesn't do what you want, there's nothing I can do about it.



 Sep 11



  parent reply Manu <turkeyman gmail.com>  writes:


On Thu, 12 Sept 2024 at 04:26, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/11/2024 3:23 PM, Manu wrote:

 Even if you can manage to convince a compiler to write the output you're
 alleging,


 Alleging? I cut and pasted what dmd did and what gcc did. My gcc may
 behave
 differently than yours, as there are many versions of it.


This is literally my point...


 I would never imagine for a second that's a reliable strategy. The

 optimiser could do all kinds of things... even though in all my


 experiments, it

 does exactly what I predicted it would.


 Did you use -O?


I used -O2... I don't imagine that would have made a difference though? I
don't think I've ever seen anyone use -O before.

dmd does what I predicted it would, as it is designed to operate that way.

 If
 gcc doesn't do what you want, there's nothing I can do about it.


You're not meant to do anything about it; just accept that your suggestion
to rely on contorting the code and a prayer that the compiler emits the
code you'd like to see (it doesn't) is not a reasonable suggestion.
This needs a proper solution.



 Sep 12



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/12/2024 3:49 PM, Manu wrote:

 You're not meant to do anything about it; just accept that your suggestion to 
 rely on contorting the code and a prayer that the compiler emits the code
you'd 
 like to see (it doesn't) is not a reasonable suggestion.
 This needs a proper solution.


dmd does emit the expected code.

I used -O on gcc, not -O2, and it produced the expected result. -O2 does not,
as 
you discovered.

There's also the do-while solution:

```
void bar();
int gax(int i)
{
     do
     {
         if (i) break;
         bar();
         return 1;
     } while (0);
     return 0;
}
```
which produces the same result with gcc -O:
```
gax:
     mov       EAX,0
     test      EDI,EDI
     jne       L55
     sub       RSP,8
     call      bar PC32
     mov       EAX,1
     add       RSP,8
L55:    rep
     ret
```

I do not know why -O2 behaves differently. I don't know why gcc does not
respect 
the code order given by the programmer.

Expecting these kinds of micro-optimizations to work reliably have a long 
history of becoming pessimizations. Given the complexity of modern optimizers 
and code generators, trying to control the sausage that comes out is going to
be 
frustrating. Since they are "hints", there is no guarantee whatsoever any 
particular compiler will take the hints.

One thing you can try is to ask Iain and Martin to automatically add 
[[likely]]/[[unlikely]] hints to if statements so that code generation order 
mimics dmd's, which does put the code in the order presented.



 Sep 13



prev sibling next sibling parent reply Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Thursday, 29 August 2024 at 18:28:04 UTC, Walter Bright wrote:

 On 8/28/2024 2:45 AM, Manu wrote:

 Here's one that I just wrote a short while ago:
 https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c



 ```
 if (data.length < 4) // unlikely
     return 0;
 ```

 replace with:

 ```
 if (data.length < 4)
     goto Lreturn0;
 ```


Prime example of Hyrum’s Law.

Heuristics in the optimizer: Good.
Pandering to the heuristics of a specific compiler: Bad.



 Sep 06



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/6/2024 3:53 AM, Quirin Schroll wrote:

 Heuristics in the optimizer: Good.
 Pandering to the heuristics of a specific compiler: Bad.


All the compilers I know, by default, lay out the instructions in the same
order 
the expressions are laid out in the source code.



 Sep 06



prev sibling  parent reply Daniel N <no public.email>  writes:


On Thursday, 29 August 2024 at 18:28:04 UTC, Walter Bright wrote:

 On 8/28/2024 2:45 AM, Manu wrote:

 Here's one that I just wrote a short while ago:
 https://gist.github.com/TurkeyMan/0e49da245cc0086f852ac18deed21a9c



 ```
 if (data.length < 4) // unlikely
     return 0;
 ```

 replace with:

 ```
 if (data.length < 4)
     goto Lreturn0;
 ```


This seldom works.
onlineapp.d(4): Error: `goto` skips declaration of variable 
`onlineapp.fun.y`
onlineapp.d(6):        declared here

```
int fun(int x)
{
     if (x < 0)
         goto Lreturn0;

     int y = x * x;

     return y;
Lreturn0:
     return 0;
}
```



 Sep 07



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


```
int fun(int x)
{
      int y;
      if (x < 0)
          goto Lreturn0;

      y = x * x;

      return y;
Lreturn0:
      return 0;
}
```

or:
```
int fun(int x)
{
      if (x < 0)
          goto Lreturn0;

     {
      int y = x * x;

      return y;
     }
Lreturn0:
      return 0;
}
```



 Sep 09



prev sibling  parent reply Manu <turkeyman gmail.com>  writes:


On Fri, 23 Aug 2024, 12:26 Nicholas Wilson via Digitalmars-d, <
digitalmars-d puremagic.com> wrote:


 On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 I'm working on microcontrollers, and many don't have a branch
 predictor. They do "static" prediction, that is, they just
 predict branch-not-taken and it's on you to write your code as
 such, and that's not always possible. (like the loop condition
 in a for loop)

 This leads to a lot of awkward looking if's written in
 unnatural 'backwards' terms, and also, leads to undesirable
 depth of nested scopes.

 The compiler backend can and should re-jig the comparisons, but
 it needs to receive a hint which way is 'likely' from the
 programmer.

 How can we add an attribute to the branch condition that the
 backend can take advantage of? I think it needs to be in the
 language spec...


 For LDC see,

 https://github.com/ldc-developers/ldc/blob/master/runtime/druntime/src/ldc/intrinsics.di#L619
 and see also `llvm_assume` just beneath it.

 GDC probably has something similar too.


Yes exactly, this is my point, we need something in the spec. I think there
might be an opportunity to express branch prediction hints in a more
user-friendly way than assume statements... But a language assume() would
also be very useful!






 Aug 23



  parent reply kinke <noone nowhere.com>  writes:


On Friday, 23 August 2024 at 09:10:34 UTC, Manu wrote:

 On Fri, 23 Aug 2024, 12:26 Nicholas Wilson via Digitalmars-d, < 
 digitalmars-d puremagic.com> wrote:

 For LDC see,

 https://github.com/ldc-developers/ldc/blob/master/runtime/druntime/src/ld
/intrinsics.di#L619 and see also `llvm_assume` just beneath it.

 GDC probably has something similar too.


 Yes exactly, this is my point, we need something in the spec. I 
 think there might be an opportunity to express branch 
 prediction hints in a more user-friendly way than assume 
 statements... But a language assume() would also be very useful!


I suggest adding a `core.builtins.expect()` intrinsic to 
standardize the existing LDC and GDC intrinsics, adding a dummy 
(`pragma(inline, true)`!) identity function for DMD. No need for 
introducing statement-level UDAs, other compiler magic, 
complicating language/spec etc. `core.attribute` already does 
this for magic UDAs.



 Aug 23



  parent reply Nicholas Wilson <iamthewilsonator hotmail.com>  writes:


On Friday, 23 August 2024 at 20:08:53 UTC, kinke wrote:

 I suggest adding a `core.builtins.expect()` intrinsic to 
 standardize the existing LDC and GDC intrinsics, adding a dummy 
 (`pragma(inline, true)`!) identity function for DMD. No need 
 for introducing statement-level UDAs, other compiler magic, 
 complicating language/spec etc. `core.attribute` already does 
 this for magic UDAs.


https://github.com/dlang/dmd/pull/16807



 Aug 23



  parent reply Manu <turkeyman gmail.com>  writes:


On Sat, 24 Aug 2024 at 10:11, Nicholas Wilson via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Friday, 23 August 2024 at 20:08:53 UTC, kinke wrote:

 I suggest adding a `core.builtins.expect()` intrinsic to
 standardize the existing LDC and GDC intrinsics, adding a dummy
 (`pragma(inline, true)`!) identity function for DMD. No need
 for introducing statement-level UDAs, other compiler magic,
 complicating language/spec etc. `core.attribute` already does
 this for magic UDAs.


 https://github.com/dlang/dmd/pull/16807



Thanks Nick! That's good to have.

That said, I still feel using expect() is pretty invasive.
If you have a bunch of existing code, marking it up is a fiddly
transformation, and hurts readability:

if (fails_validation)
  return -1;
if (check_for_lilely_case)
  return v;
return calculate(v);


// invasive and pretty severely damages readibility
if (expect(fails_validation, false))
  return -1;
if (expect(check_for_lilely_case, true))
  return v;
return calculate(v);


// paste token on end of line, doesn't really affect readibility at all
if (fails_validation)  unlikely
  return -1;
if (check_for_lilely_case)  likely
  return v;
return calculate(v);


An attribute attaching to control statements would definitely be nice for
my money...



 Aug 23



 next sibling parent  Nicholas Wilson <iamthewilsonator hotmail.com>  writes:


On Saturday, 24 August 2024 at 01:26:43 UTC, Manu wrote:

 Thanks Nick! That's good to have.

 That said, I still feel using expect() is pretty invasive.
 If you have a bunch of existing code, marking it up is a fiddly
 transformation, and hurts readability:

 if (fails_validation)
   return -1;
 if (check_for_lilely_case)
   return v;
 return calculate(v);


 // invasive and pretty severely damages readibility
 if (expect(fails_validation, false))
   return -1;
 if (expect(check_for_lilely_case, true))
   return v;
 return calculate(v);


 // paste token on end of line, doesn't really affect 
 readibility at all
 if (fails_validation)  unlikely
   return -1;
 if (check_for_lilely_case)  likely
   return v;
 return calculate(v);


 An attribute attaching to control statements would definitely 
 be nice for my money...


note there is nothing stopping you from doing

```d
pragma (inline, true) bool unlikely(bool val) => expect(val, 
false);
pragma (inline, true) bool   likely(bool val) => expect(val, 
true);

if (unlikely(fails_validation))
   return -1;
if (check_for_liklely_case.likely) // if you feel that (ab)using 
UFCS is prettier
   return v;
return calculate(v)
```



 Aug 23



prev sibling  parent  Lance Bachmeier <no spam.net>  writes:


On Saturday, 24 August 2024 at 01:26:43 UTC, Manu wrote:


 An attribute attaching to control statements would definitely 
 be nice for my money...


+1, and it's not obvious what the objection would be to doing 
that.



 Aug 23



prev sibling next sibling parent reply Dom DiSc <dominikus scherkl.de>  writes:


On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 How can we add an attribute to the branch condition that the 
 backend can take advantage of? I think it needs to be in the 
 language spec...


I always arrange it so, that the if-path is the likely one, and 
the else path is the unlikely one. This also makes the code more 
readable, and it is always possible to do so.
The compiler should optimize accordingly. No further indication 
should be necessary.



 Aug 23



  parent reply Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Friday, 23 August 2024 at 07:33:53 UTC, Dom DiSc wrote:

 On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 How can we add an attribute to the branch condition that the 
 backend can take advantage of? I think it needs to be in the 
 language spec...


 I always arrange it so, that the if-path is the likely one, and 
 the else path is the unlikely one.


As if anyone can remember that.


 This also makes the code more readable,


Absolutely not. Early returns for unlikely-but-valid input like 
null pointers makes sense to me. Other than that, there’s `if 
(...) throw ...;`, but basically all optimizers recognize this as 
an unlikely path.


 and it is always possible to do so.


Technically yes, but it makes some code harder to understand.


 The compiler should optimize accordingly. No further indication 
 should be necessary.


This is your style, and IMO it’s a bad style.



 Sep 06



 next sibling parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/6/2024 3:21 AM, Quirin Schroll wrote:

 Early returns for unlikely-but-valid input like null pointers 
 makes sense to me.


I often write code so that the happy path is the first if. Andrei objected to 
this style :-/


 Other than that, there’s `if (...) throw ...;`, but basically 
 all optimizers recognize this as an unlikely path.


Sure, but that's only one case. Manu's functions are all nothrow.


 This is your style, and IMO it’s a bad style.


Since CPU branch prediction for forward branches assumes they are not taken, it 
seems your style is statistically less likely. (As I assume the CPU designers 
did collect statistics on this.)



 Sep 07



  parent reply Manu <turkeyman gmail.com>  writes:


On Sat, 7 Sept 2024 at 21:16, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/6/2024 3:21 AM, Quirin Schroll wrote:

 Early returns for unlikely-but-valid input like null pointers
 makes sense to me.


 I often write code so that the happy path is the first if. Andrei objecte=


d

 to
 this style :-/


 Other than that, there=E2=80=99s `if (...) throw ...;`, but basically
 all optimizers recognize this as an unlikely path.


 Sure, but that's only one case. Manu's functions are all nothrow.


 This is your style, and IMO it=E2=80=99s a bad style.


 Since CPU branch prediction for forward branches assumes they are not
 taken, it
 seems your style is statistically less likely. (As I assume the CPU
 designers
 did collect statistics on this.)


The statistical majority that you allude to is overwhelmingly dominated by
the branch UP and the end of every loop cycle.
Statistically speaking, almost all branches encountered during program flow
are up-branches at the end of loop cycles, which infers the rule that an up
branch should be predicted true, and therefore given a
sign-bit-branch-preiction strategy, down-branch must therefore predict
false. No other statistical realities past the loop continuation branch are
relevant.

I'd also suggest that, other than maybe the statistical probability of a
loop continuation being a good choice to predict in the true case, the
strategy of sign-bit based prediction is more a useful tool for a compiler
than an inherent architectural optimising feature. It gives the compiler
agency that it might not otherwise have, and in the cases where the
compiler can't infer meaningful predictions, we should be able to supply
them...



 Sep 10



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/10/2024 1:48 PM, Manu wrote:

 On Sat, 7 Sept 2024 at 21:16, Walter Bright via Digitalmars-d 
     Since CPU branch prediction for forward branches assumes they are not
taken, it
     seems your style is statistically less likely. (As I assume the CPU
designers
     did collect statistics on this.)
 
 
 The statistical majority that you allude to is overwhelmingly dominated by
the 
 branch UP and the end of every loop cycle.
 Statistically speaking, almost all branches encountered during program flow
are 
 up-branches at the end of loop cycles, which infers the rule that an up
branch 
 should be predicted true, and therefore given a 
 sign-bit-branch-preiction strategy, down-branch must therefore predict false.
No 
 other statistical realities past the loop continuation branch are relevant.


I think that is what I wrote.


 I'd also suggest that, other than maybe the statistical probability of a loop 
 continuation being a good choice to predict in the true case, the strategy of 
 sign-bit based prediction is more a useful tool for a compiler than an
inherent 
 architectural optimising feature. It gives the compiler agency that it might
not 
 otherwise have, and in the cases where the compiler can't infer meaningful 
 predictions, we should be able to supply them...


I did write that forward branches were considered not likely, and backward 
branches likely. We are in agreement on that.



 Sep 10



  parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 11 Sept 2024 at 06:56, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/10/2024 1:48 PM, Manu wrote:

 On Sat, 7 Sept 2024 at 21:16, Walter Bright via Digitalmars-d
     Since CPU branch prediction for forward branches assumes they are


 not taken, it

     seems your style is statistically less likely. (As I assume the CPU


 designers

     did collect statistics on this.)


 The statistical majority that you allude to is overwhelmingly


 dominated by the

 branch UP and the end of every loop cycle.
 Statistically speaking, almost all branches encountered during program


 flow are

 up-branches at the end of loop cycles, which infers the rule that an up


 branch

 should be predicted true, and therefore given a
 sign-bit-branch-preiction strategy, down-branch must therefore predict


 false. No

 other statistical realities past the loop continuation branch are


 relevant.

 I think that is what I wrote.


 I'd also suggest that, other than maybe the statistical probability of a


 loop

 continuation being a good choice to predict in the true case, the


 strategy of

 sign-bit based prediction is more a useful tool for a compiler than an


 inherent

 architectural optimising feature. It gives the compiler agency that it


 might not

 otherwise have, and in the cases where the compiler can't infer


 meaningful

 predictions, we should be able to supply them...


 I did write that forward branches were considered not likely, and backward
 branches likely. We are in agreement on that.


Okay, I lost the signal somewhere... what I'm essentially saying though, is
that it doesn't matter what the rule is or how it came about; the point is,
it's a tool the architecture offers which is most useful at the language
level. Laying out code to match this particular rule is not something
that's appropriate, because some other arch with whatever other primitive
strategy might come along.

Obfuscating the contorting code is not the goal or a reasonable solution;
we just want a mechanism in the language to take advantage of this general
category of support in whatever architecture.



 Sep 11



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 4:18 AM, Manu wrote:

 Okay, I lost the signal somewhere... what I'm essentially saying though, is
that 
 it doesn't matter what the rule is or how it came about; the point is, it's a 
 tool the architecture offers which is most useful at the language level.
Laying 
 out code to match this particular rule is not something that's appropriate, 
 because some other arch with whatever other primitive strategy might come
along.


The rule that the code is laid out in the order the programmer wrote it makes 
the most sense to me. It gives the programmer the control over how it gets 
executed. The same applies to switch statements - put the most visited case 
statements first.


 Obfuscating the contorting code is not the goal or a reasonable solution; we 
 just want a mechanism in the language to take advantage of this general
category 
 of support in whatever architecture.


I tend to agree, but when micro-optimizing one's code, one accepts that its 
elegance is going to decline.

There are at least 3 ways to organize the code to get what you want. I won't 
claim they're beautiful, but they work.



 Sep 11



 next sibling parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 11 Sept 2024 at 19:56, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/11/2024 4:18 AM, Manu wrote:

 Okay, I lost the signal somewhere... what I'm essentially saying though,


 is that

 it doesn't matter what the rule is or how it came about; the point is,


 it's a

 tool the architecture offers which is most useful at the language level.


 Laying

 out code to match this particular rule is not something that's


 appropriate,

 because some other arch with whatever other primitive strategy might


 come along.

 The rule that the code is laid out in the order the programmer wrote it
 makes
 the most sense to me. It gives the programmer the control over how it gets
 executed. The same applies to switch statements - put the most visited
 case
 statements first.


This isn't a matter of opinion. The compilers do what the compilers do, and
that's just the way it is.


 Obfuscating the contorting code is not the goal or a reasonable solution;
 we

 just want a mechanism in the language to take advantage of this general


 category

 of support in whatever architecture.


 I tend to agree, but when micro-optimizing one's code, one accepts that
 its
 elegance is going to decline.

 There are at least 3 ways to organize the code to get what you want. I
 won't
 claim they're beautiful, but they work.


I can't reproduce this claim of yours.
I couldn't reproduce a case where your hack produced the code you say, and
even if I could I would never accept it to be reliable.

...and even if it DID work reliably, I *still* wouldn't accept it, because
mangling and contorting my code like that is just stupid.

...and it's not like we're even talking about a trade-off here! An
otherwise benign and extremely low-impact hint attribute on a control
statement just isn't an edgy or risky move.



 Sep 11



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 3:37 PM, Manu wrote:

     The rule that the code is laid out in the order the programmer wrote it
makes
     the most sense to me. It gives the programmer the control over how it gets
     executed. The same applies to switch statements - put the most visited case
     statements first.
 
 
 This isn't a matter of opinion. The compilers do what the compilers do, and 
 that's just the way it is.


As a matter of fact, not opinion, this is the way dmd works. How gdc/ldc work 
with this is up to Iain and Martin. I don't tell them what to do.



 I can't reproduce this claim of yours.
 I couldn't reproduce a case where your hack produced the code you say, and
even 
 if I could I would never accept it to be reliable.


Use the -O switch as I suggested and verified to work with gcc.



 ...and even if it DID work reliably, I /still/ wouldn't accept it, because 
 mangling and contorting my code like that is just stupid.


I'm sympathetic to that viewpoint, and generally go for writing the clearest 
code as a priority. If I really need to micro-optimize a section, I'll write it 
in inline assembler rather than trying to convince a compiler to do it my way.

There's no guarantee any hints (like `register`) have any effect, either.


 ...and it's not like we're even talking about a trade-off here! An otherwise 
 benign and extremely low-impact hint attribute on a control statement just
isn't 
 an edgy or risky move.


It's a complexity issue. The more complex the language, the fewer people will
be 
interested in learning it. (I'm kind of amazed that newbies are still willing
to 
learn C++ with the heft of its spec that literally nobody understands.) The
more 
complex, the more risk of bugs. It is definitely not a low-impact hint. The 
intermediate code does not support it, such would need to be added in to all
the 
code that deals with the block structure.

I know these things look simple on the surface, but they aren't. As more 
evidence of that, consider the linked article on what a mess happens when 
[[likely]] is used in a non-trivial manner.



 Sep 14



prev sibling  parent reply Johan <j j.nl>  writes:


On Wednesday, 11 September 2024 at 18:54:21 UTC, Walter Bright 
wrote:

 On 9/11/2024 4:18 AM, Manu wrote:

 Obfuscating the contorting code is not the goal or a 
 reasonable solution; we just want a mechanism in the language 
 to take advantage of this general category of support in 
 whatever architecture.


 I tend to agree, but when micro-optimizing one's code, one 
 accepts that its elegance is going to decline.

 There are at least 3 ways to organize the code to get what you 
 want. I won't claim they're beautiful, but they work.


FWIW, I agree with Walter that it is not worth to add a new 
special feature to the language for the problem at hand.

It is rare that you'd want to explicitly tell whether a branch is 
likely or not, and for that case the tool already exist 
(`llvm_expect` for LDC). It think it would hurt D as a whole to 
have special stuff for such a rare thing.

I do agree that it'd be good to have a common interface for all 
compilers, which can be achieved by e.g. introducing a 
`core.micro_optimization` module.
That module could collect more of such micro optimization things, 
like telling the compiler about likely function pointers or class 
types (devirtualization). [1]

Cheers,
   Johan


[1]
```
auto is_likely(alias Likely, Fptr, Args...)(Fptr fptr, Args args) 
{
     return (fptr == &Likely) ? Likely(args) : fptr(args);
}
// ...
void function() fptr = get_function_ptr();
fptr.is_likely!likely_function();
```
See 
https://johanengelen.github.io/ldc/2016/04/13/PGO-in-LDC-virtual-calls.html



 Sep 12



  parent reply Manu <turkeyman gmail.com>  writes:


On Thu, 12 Sept 2024 at 18:21, Johan via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Wednesday, 11 September 2024 at 18:54:21 UTC, Walter Bright
 wrote:

 On 9/11/2024 4:18 AM, Manu wrote:

 Obfuscating the contorting code is not the goal or a
 reasonable solution; we just want a mechanism in the language
 to take advantage of this general category of support in
 whatever architecture.


 I tend to agree, but when micro-optimizing one's code, one
 accepts that its elegance is going to decline.

 There are at least 3 ways to organize the code to get what you
 want. I won't claim they're beautiful, but they work.


 FWIW, I agree with Walter that it is not worth to add a new
 special feature to the language for the problem at hand.

 It is rare that you'd want to explicitly tell whether a branch is
 likely or not, and for that case the tool already exist
 (`llvm_expect` for LDC).



expect() statements are not a good time.
And something portable needs to be added anyway; so I'd seriously suggest
not using expect as an API for this.

It think it would hurt D as a whole to

 have special stuff for such a rare thing.


How?
And it's not 'rare'; it's 'niche'. For a microcontroller with no branch
prediction, it's common and essential.
It's literally unworkable to write code for the platform without this tool;
you can't have branches constantly mispredicting.

I do agree that it'd be good to have a common interface for all

 compilers, which can be achieved by e.g. introducing a
 `core.micro_optimization` module.
 That module could collect more of such micro optimization things,
 like telling the compiler about likely function pointers or class
 types (devirtualization). [1]

 Cheers,
    Johan


 [1]
 ```
 auto is_likely(alias Likely, Fptr, Args...)(Fptr fptr, Args args)
 {
      return (fptr == &Likely) ? Likely(args) : fptr(args);
 }
 // ...
 void function() fptr = get_function_ptr();
 fptr.is_likely!likely_function();
 ```
 See
 https://johanengelen.github.io/ldc/2016/04/13/PGO-in-LDC-virtual-calls.html


We virtually always end up with weird or butchered solutions to almost
everything for no good reason. Why can't we just do the normal and
reasonable thing for once?
Adding an attribute to a control statement is virtually zero impact; it's
such an obvious and elegant solution. This also isn't mutually exclusive
with expect(), or your suggestion above.



 Sep 12



  parent reply Johan <j j.nl>  writes:


On Thursday, 12 September 2024 at 22:59:32 UTC, Manu wrote:

 expect() statements are not a good time.


Why not?
Expect is known from other languages and is more general (can 
work with wider range of values than just true/false, and can 
work with types too), and reduces the problem to the backend 
domain only: no new parsing rules (don't forget editors and other 
tooling), and no AST change, etc.


 I think it would hurt D as a whole to
 have special stuff for such a rare thing.


 How?
 And it's not 'rare'; it's 'niche'. For a microcontroller with 
 no branch
 prediction, it's common and essential.
 It's literally unworkable to write code for the platform 
 without this tool;
 you can't have branches constantly mispredicting.


It would help if your arguments would not use so much hyperbole. 
Obviously it is not unworkable, demonstrated by decades of 
microcontroller programming without it (C does not have it).

The "hurt" I meant is in maintenance of the compiler frontend 
which already is in quite a bad complexity state (subtle bugs 
existing and introduced upon almost every change). Adding yet 
another special case is imo a net loss.

-Johan



 Sep 14



 next sibling parent  Daniel N <no public.email>  writes:


On Saturday, 14 September 2024 at 08:32:53 UTC, Johan wrote:

 On Thursday, 12 September 2024 at 22:59:32 UTC, Manu wrote:

 expect() statements are not a good time.


 Why not?
 Expect is known from other languages and is more general (can 
 work with wider range of values than just true/false, and can 
 work with types too), and reduces the problem to the backend 
 domain only: no new parsing rules (don't forget editors and 
 other tooling), and no AST change, etc.


Statements are not DRY but expressions would be.

```d
void dry(int i)
{
   if(expect!false(i < 0))
     return;
```



 Sep 14



prev sibling  parent reply Manu <turkeyman gmail.com>  writes:


On Sat, 14 Sept 2024, 09:36 Johan via Digitalmars-d, <
digitalmars-d puremagic.com> wrote:


 On Thursday, 12 September 2024 at 22:59:32 UTC, Manu wrote:

 expect() statements are not a good time.


 Why not?
 Expect is known from other languages and is more general (can
 work with wider range of values than just true/false, and can
 work with types too), and reduces the problem to the backend
 domain only: no new parsing rules (don't forget editors and other
 tooling), and no AST change, etc.


It's still ugly and relatively high impact on the code you markup though.
You have to insert additional lines in the flow and write expressions,
which is awkward if it's some long or compound expression, and it's also an
undesirable repetition of an expression; a tweak to some if(expr) may also
need to have a matching tweak to the expect statement, could lose sync, or
if you then suggest to resolve the expression to a local bool somewhere
before the expect() and the if(), then that's ANOTHER pointless line.

It's a bad time all round. We've moved on from expect statements. They have
their place, but it's not for this.


 I think it would hurt D as a whole to

 have special stuff for such a rare thing.


 How?
 And it's not 'rare'; it's 'niche'. For a microcontroller with
 no branch
 prediction, it's common and essential.
 It's literally unworkable to write code for the platform
 without this tool;
 you can't have branches constantly mispredicting.


 It would help if your arguments would not use so much hyperbole.
 Obviously it is not unworkable, demonstrated by decades of
 microcontroller programming without it (C does not have it).



Huh? I've been writing expect statements in C for 20 years or maybe more...
It's always been a useful tool; but the reason it's actually way more
relevant today, is because the nature of static branch prediction in modern
micros where it's much more costly to mispredict in riscv or xtensa than it
used to be. Old arch's with weak (or no) branch prediction also had very
shallow pipelines, or even no pipelines in early micros. More advanced old
arch's did have dynamic branch predictors, but you could still gain some
optimisations from hunting code layout, or signalling an initial
prediction; though the value and applicability of this sort of hint was
MUCH narrower; it was rare to bother.

Modern arch's are pipelined, and a mispredict is relatively more costly.
I don't think there has ever been a time where we have had popular
architectures with meaningfully deep pipelines and without dynamic branch
prediction, where a mispredict is anywhere near as costly.
There's a reason it's been recently added to C++. This situation is new.

Also the nature of code on these micros today; they are hundreds of mhz and
we do a whole lot more with them, including more complex logic and number
crunching. Old micros were conveniently coded in asm, and nobody ever
really expected them to do much of anything.

These micros are comparable to a PlayStation 2 or something of that era;
there's a really great opportunity to write meaningful software for them.
~2004 is back... and it's actually a pretty interesting new domain.

Most micro software even on these modern processors doesn't do anything
particularly interesting (turns a light on or off over wifi); but if you
want to do something interesting with these chips, there's a lot of careful
handling which gives huge advantages. The branch predictor is *by far* the
most significant detail to take care. That's not hyperbole.

The "hurt" I meant is in maintenance of the compiler frontend

 which already is in quite a bad complexity state (subtle bugs
 existing and introduced upon almost every change). Adding yet
 another special case is imo a net loss.


I reckon we're dealing with one pointer to an attribute expression in the
branch node (which will be completely ignored except for by the backend),
and a line in the parser to allow attaching an attribute expression to that
pointer. I'd imagine the patch is less than 10 lines, and not very invasive
at all.

I don't see this is a special case. The grammar tweak would be no more
special case than attaching attributes to other declarations.
I reckon you're exaggerating the complexity.






 Sep 15



  parent reply Johan <j j.nl>  writes:


On Sunday, 15 September 2024 at 12:06:53 UTC, Manu wrote:

 On Sat, 14 Sept 2024, 09:36 Johan via Digitalmars-d, < 
 digitalmars-d puremagic.com> wrote:


 On Thursday, 12 September 2024 at 22:59:32 UTC, Manu wrote:

 How?
 And it's not 'rare'; it's 'niche'. For a microcontroller with
 no branch
 prediction, it's common and essential.
 It's literally unworkable to write code for the platform
 without this tool;
 you can't have branches constantly mispredicting.


 It would help if your arguments would not use so much 
 hyperbole. Obviously it is not unworkable, demonstrated by 
 decades of microcontroller programming without it (C does not 
 have it).



 Huh? I've been writing expect statements in C for 20 years or 
 maybe more...


I meant - of course - something besides `expect`. I was 
responding to your "this tool", thinking that it must refer to 
your new proposal, because otherwise why would there be a 
discussion? But apparently you meant "expect". Then there is no 
debate:
when writing D for microcontrollers today (i.e. you need to use 
GDC or LDC) you have the option to use the equivalent of 
`expect`. Use it.

I'm sorry for entering this discussion and will leave. I do not 
get a sense that the desire is to build a balanced view and come 
to a shared conclusion.

-Johan



 Sep 15



  parent  Manu <turkeyman gmail.com>  writes:


On Sun, 15 Sept 2024, 14:11 Johan via Digitalmars-d, <
digitalmars-d puremagic.com> wrote:


 On Sunday, 15 September 2024 at 12:06:53 UTC, Manu wrote:

 On Sat, 14 Sept 2024, 09:36 Johan via Digitalmars-d, <
 digitalmars-d puremagic.com> wrote:


 On Thursday, 12 September 2024 at 22:59:32 UTC, Manu wrote:

 How?
 And it's not 'rare'; it's 'niche'. For a microcontroller with
 no branch
 prediction, it's common and essential.
 It's literally unworkable to write code for the platform
 without this tool;
 you can't have branches constantly mispredicting.


 It would help if your arguments would not use so much
 hyperbole. Obviously it is not unworkable, demonstrated by
 decades of microcontroller programming without it (C does not
 have it).



 Huh? I've been writing expect statements in C for 20 years or
 maybe more...


 I meant - of course - something besides `expect`. I was
 responding to your "this tool", thinking that it must refer to
 your new proposal, because otherwise why would there be a
 discussion? But apparently you meant "expect". Then there is no
 debate:
 when writing D for microcontrollers today (i.e. you need to use
 GDC or LDC) you have the option to use the equivalent of
 `expect`. Use it.

 I'm sorry for entering this discussion and will leave. I do not
 get a sense that the desire is to build a balanced view and come
 to a shared conclusion.

 -Johan


No I'm not proposing expect; but saying that expect has been the
state-of-the-art forever, and we're done with that now.
Using expect has always been an unsatisfying experience, but at least it's
rare. Now that this particular issue is more relevant than ever, and at
least C++ has acknowledged and accepted this, it's time we fix this too.






 Sep 15



prev sibling  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/6/2024 3:21 AM, Quirin Schroll wrote:

 there’s `if (...) throw ...;`, but basically 
 all optimizers recognize this as an unlikely path.


https://issues.dlang.org/show_bug.cgi?id=24749



 Sep 07



prev sibling next sibling parent reply Nicholas Wilson <iamthewilsonator hotmail.com>  writes:


On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 I'm working on microcontrollers, and many don't have a branch 
 predictor. They do "static" prediction, that is, they just 
 predict branch-not-taken and it's on you to write your code as 
 such, and that's not always possible. (like the loop condition 
 in a for loop)


Stupid questions: does PGO work on the microcontrollers, and  
have you tried PGO?



 Aug 23



  parent  Manu <turkeyman gmail.com>  writes:


On Sat, 24 Aug 2024 at 12:06, Nicholas Wilson via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 I'm working on microcontrollers, and many don't have a branch
 predictor. They do "static" prediction, that is, they just
 predict branch-not-taken and it's on you to write your code as
 such, and that's not always possible. (like the loop condition
 in a for loop)


 Stupid questions: does PGO work on the microcontrollers, and
 have you tried PGO?


Maybe... I'd have to source the profile from an alt architecture though...
I wonder if the profile is at a higher level (like in the LLVM realm), or
if it ends up profiling target-local constructs.
I'm not likely to use it anyway. I've always found tooling like that to add
unsatisfactory complexity to the build and deploy environment, especially
when the build environment is already a bit fiddley with ROM packaging and
stuff.



 Aug 24



prev sibling next sibling parent reply Tejas <notrealemail gmail.com>  writes:


On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 I'm working on microcontrollers, and many don't have a branch 
 predictor. They do "static" prediction, that is, they just 
 predict branch-not-taken and it's on you to write your code as 
 such, and that's not always possible. (like the loop condition 
 in a for loop)

 This leads to a lot of awkward looking if's written in 
 unnatural 'backwards' terms, and also, leads to undesirable 
 depth of nested scopes.

 The compiler backend can and should re-jig the comparisons, but 
 it needs to receive a hint which way is 'likely' from the 
 programmer.

 How can we add an attribute to the branch condition that the 
 backend can take advantage of? I think it needs to be in the 
 language spec...


Hi, what are your views on the article linked below that 
discourages using `[[likely]]` and `[[unlikely]]`?

https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-unlikely-attributes/



 Sep 09



 next sibling parent  Stefan Koch <uplink.coder googlemail.com>  writes:


On Tuesday, 10 September 2024 at 02:18:57 UTC, Tejas wrote:


 Hi, what are your views on the article linked below that 
 discourages using `[[likely]]` and `[[unlikely]]`?

 https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-unlikely-attributes/


Well it does criticize how the likely and unlikely attributes in 
c++ have unintuitive semantics. D would probably have a chance to 
fix that. If D decides to support the attributes.



 Sep 10



prev sibling  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/9/2024 7:18 PM, Tejas wrote:

 Hi, what are your views on the article linked below that discourages using 
 `[[likely]]` and `[[unlikely]]`?
 
 https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-unlikely-attributes/


Wow. The article eviscerates that design.



 Sep 11



  parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 11 Sept 2024 at 09:12, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/9/2024 7:18 PM, Tejas wrote:

 Hi, what are your views on the article linked below that discourages


 using

 `[[likely]]` and `[[unlikely]]`?


 https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-unlikely-attributes/

 Wow. The article eviscerates that design.


Just to be clear; nobody I'm aware of has proposed that design, so I hope
that's not your take-away.

My proposal is to allow a hint attached strictly to control statements.
(ideally as a suffix)
It is easy to read, also easy to ignore (this is important), and extremely
low-impact when marking up existing code: no new lines, no rearranging of
code, purely additive; strictly appends to the end of existing
control statements... these are very nice properties for casually marking
up some code where it proves to be profitable, without interfering with
readability, or even interfering with historic diff's in any meaningful way
that might make it annoying to review.



 Sep 11



 next sibling parent  "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 11/09/2024 11:53 PM, Manu wrote:

 On Wed, 11 Sept 2024 at 09:12, Walter Bright via Digitalmars-d 
 <digitalmars-d puremagic.com <mailto:digitalmars-d puremagic.com>> wrote:
 
     On 9/9/2024 7:18 PM, Tejas wrote:
      > Hi, what are your views on the article linked below that
     discourages using
      > `[[likely]]` and `[[unlikely]]`?
      >
      >
     https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-
nlikely-attributes/ <https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-unlikely-attributes/>
 
     Wow. The article eviscerates that design.
 
 
 Just to be clear; nobody I'm aware of has proposed that design, so I 
 hope that's not your take-away.
 
 My proposal is to allow a hint attached strictly to control statements. 
 (ideally as a suffix)
 It is easy to read, also easy to ignore (this is important), and 
 extremely low-impact when marking up existing code: no new lines, no 
 rearranging of code, purely additive; strictly appends to the end of 
 existing control statements... these are very nice properties for 
 casually marking up some code where it proves to be profitable, without 
 interfering with readability, or even interfering with historic diff's 
 in any meaningful way that might make it annoying to review.


Ideas forum proposal I wrote a little bit ago, based upon this article 
for what it should not do.

https://forum.dlang.org/post/oezbkynwdhfqatsvufdm forum.dlang.org



 Sep 11



prev sibling  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 4:53 AM, Manu wrote:

 Just to be clear; nobody I'm aware of has proposed that design, so I hope
that's 
 not your take-away.


Indeed I thought you were proposing that, glad you're not!


 My proposal is to allow a hint attached strictly to control statements.
(ideally 
 as a suffix)
 It is easy to read, also easy to ignore (this is important), and extremely 
 low-impact when marking up existing code: no new lines, no rearranging of
code, 
 purely additive; strictly appends to the end of existing
control statements... 
 these are very nice properties for casually marking up some code where it
proves 
 to be profitable, without interfering with readability, or even interfering
with 
 historic diff's in any meaningful way that might make it annoying to review.


How is that materially different from [[likely]] annotations?



 Sep 11



 next sibling parent reply Timon Gehr <timon.gehr gmx.ch>  writes:


On 9/11/24 20:55, Walter Bright wrote:

 

 My proposal is to allow a hint attached strictly to control 
 statements. (ideally as a suffix)
 It is easy to read, also easy to ignore (this is important), and 
 extremely low-impact when marking up existing code: no new lines, no 
 rearranging of code, purely additive; strictly appends to the end of 
 existing control statements... these are very nice properties for 
 casually marking up some code where it proves to be profitable, 
 without interfering with readability, or even interfering with 
 historic diff's in any meaningful way that might make it annoying to 
 review.


 
 How is that materially different from [[likely]] annotations?


It's associated with the branch and not with the program path.

(This is assuming the ideas in the blog post about C++ [[likely]] are 
factually correct, I have not sought independent confirmation.)



 Sep 11



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 12:46 PM, Timon Gehr wrote:

 On 9/11/24 20:55, Walter Bright wrote:

 My proposal is to allow a hint attached strictly to control statements. 
 (ideally as a suffix)
 It is easy to read, also easy to ignore (this is important), and extremely 
 low-impact when marking up existing code: no new lines, no rearranging of 
 code, purely additive; strictly appends to the end of existing 
 control statements... these are very nice properties for casually marking up 
 some code where it proves to be profitable, without interfering with 
 readability, or even interfering with historic diff's in any meaningful way 
 that might make it annoying to review.


 How is that materially different from [[likely]] annotations?


 
 It's associated with the branch and not with the program path.


I have no idea what the difference is, as the branch determines the program
path.



 Sep 13



  parent reply Timon Gehr <timon.gehr gmx.ch>  writes:


On 9/13/24 10:19, Walter Bright wrote:

 On 9/11/2024 12:46 PM, Timon Gehr wrote:

 On 9/11/24 20:55, Walter Bright wrote:

 My proposal is to allow a hint attached strictly to control 
 statements. (ideally as a suffix)
 It is easy to read, also easy to ignore (this is important), and 
 extremely low-impact when marking up existing code: no new lines, no 
 rearranging of code, purely additive; strictly appends to the end of 
 existing control statements... these are very nice properties for 
 casually marking up some code where it proves to be profitable, 
 without interfering with readability, or even interfering with 
 historic diff's in any meaningful way that might make it annoying to 
 review.


 How is that materially different from [[likely]] annotations?


 It's associated with the branch and not with the program path.


 
 I have no idea what the difference is, as the branch determines the
 program path.
 


Well, it is the attribute being associated with the program path being 
ill-defined that is being criticized in that blog post. The difference 
is that for path-associated, you are saying that a specific statement is 
likely or unlikely to be executed, for branch-associated, you are saying 
in which direction a specific branch is likely to go.



 Sep 13



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/13/2024 4:56 AM, Timon Gehr wrote:

 Well, it is the attribute being associated with the program path being 
 ill-defined that is being criticized in that blog post. The difference is that 
 for path-associated, you are saying that a specific statement is likely or 
 unlikely to be executed, for branch-associated, you are saying in which 
 direction a specific branch is likely to go.


Ok, thanks for the explanation. The branch predictor on CPUs defaults to a 
forward branch being considered unlikely, and a backwards branch being 
considered likely.

I'm sure the CPU designers collected statistics on this before burning this
into 
the branch predictor hardware.

It's a simple and easily remembered rule, and so why dmd behaves as it does.

As for an attribute, I cannot see it being viable for anything other than the 
`if`, as the undocumented menace of it being applied to anything else is 
apparent in the blog post.

Hence, if D were to support something along those lines, it would be a keyword 
such as:

```
ifrarely (i) return 0;
```

as the least ugly approach. But I've been unable to come up with an obviously 
good keyword for it. And we would need buyin from Iain and Martin.



 Sep 13



 next sibling parent  Daniel N <no public.email>  writes:


On Friday, 13 September 2024 at 18:53:11 UTC, Walter Bright wrote:

 Hence, if D were to support something along those lines, it 
 would be a keyword such as:

 ```
 ifrarely (i) return 0;
 ```

 as the least ugly approach. But I've been unable to come up 
 with an obviously good keyword for it. And we would need buyin 
 from Iain and Martin.


ifrarely is nice, but I prefer swift style guard.


```swift
func ex(maybe : Int?)
{
     guard let val = maybe else {
         // implicitly unlikely
         print("early exit")
         return
     }

     // look ma - val is in scope here!
     print("val = ", val)
}

ex(maybe:1)
ex(maybe:nil)
```



 Sep 13



prev sibling  parent reply claptrap <clap trap.com>  writes:


On Friday, 13 September 2024 at 18:53:11 UTC, Walter Bright wrote:

 On 9/13/2024 4:56 AM, Timon Gehr wrote:

 Well, it is the attribute being associated with the program 
 path being ill-defined that is being criticized in that blog 
 post. The difference is that for path-associated, you are 
 saying that a specific statement is likely or unlikely to be 
 executed, for branch-associated, you are saying in which 
 direction a specific branch is likely to go.


 Ok, thanks for the explanation. The branch predictor on CPUs 
 defaults to a forward branch being considered unlikely, and a 
 backwards branch being considered likely.


That was pretty much only the Pentiums, older AMDs just assumed 
branch not taken if wasn't in the BTB already. Newer CPUs, Core2 
onwards, Zen, nobody seems to know for sure what they do, but the 
Intel SDMs do state that the Core architecture doesn't use static 
prediction. I think Agner Fog says it's essentially random.



 Sep 13



 next sibling parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 14/09/2024 8:50 AM, claptrap wrote:

 On Friday, 13 September 2024 at 18:53:11 UTC, Walter Bright wrote:

 On 9/13/2024 4:56 AM, Timon Gehr wrote:

 Well, it is the attribute being associated with the program path 
 being ill-defined that is being criticized in that blog post. The 
 difference is that for path-associated, you are saying that a 
 specific statement is likely or unlikely to be executed, for 
 branch-associated, you are saying in which direction a specific 
 branch is likely to go.


 Ok, thanks for the explanation. The branch predictor on CPUs defaults 
 to a forward branch being considered unlikely, and a backwards branch 
 being considered likely.


 
 That was pretty much only the Pentiums, older AMDs just assumed branch 
 not taken if wasn't in the BTB already. Newer CPUs, Core2 onwards, Zen, 
 nobody seems to know for sure what they do, but the Intel SDMs do state 
 that the Core architecture doesn't use static prediction. I think Agner 
 Fog says it's essentially random.


https://www.agner.org/optimize/microarchitecture.pdf

Not quite random, but certainly has changed to a significantly more 
complicated design since the 90's.

"
3.8 Branch prediction in Intel Haswell, Broadwell, Skylake, and other Lakes
The branch predictor appears to have been redesigned in the Haswell and 
later Intel processors, but the design is undocumented.
Reverse engineering has revealed that the branch prediction is using 
several tables of local and global histories of taken branches 
[Yavarzadeh, 2023].
The measured throughput for jumps and branches varies between one branch 
per clock cycle and one branch per two clock cycles for jumps and 
predicted taken branches.
Predicted not taken branches have an even higher throughput of up to two 
  branches per clock cycle.
The high throughput for taken branches of one per clock was observed for 
up to 128 branches with no more than one branch per 16 bytes of code.
The throughput is reduced to one jump per two clock cycles if there is 
more than one branch instruction per 16 bytes of code. If there are more 
than 128 branches in the critical part of the code, and if they are 
spaced by at least 16 bytes, then apparently the first 128 branches
have the high throughput and the remaining have the low throughput.
These observations may indicate that there are two branch prediction 
methods: a fast method tied to the µop cache and the instruction cache, 
and a slower method using a branch target buffer.
"



 Sep 13



 next sibling parent  claptrap <clap trap.com>  writes:


On Friday, 13 September 2024 at 20:59:01 UTC, Richard (Rikki) 
Andrew Cattermole wrote:

 On 14/09/2024 8:50 AM, claptrap wrote:

 On Friday, 13 September 2024 at 18:53:11 UTC, Walter Bright 
 wrote:

 On 9/13/2024 4:56 AM, Timon Gehr wrote:

 Well, it is the attribute being associated with the program 
 path being ill-defined that is being criticized in that blog 
 post. The difference is that for path-associated, you are 
 saying that a specific statement is likely or unlikely to be 
 executed, for branch-associated, you are saying in which 
 direction a specific branch is likely to go.


 Ok, thanks for the explanation. The branch predictor on CPUs 
 defaults to a forward branch being considered unlikely, and a 
 backwards branch being considered likely.


 
 That was pretty much only the Pentiums, older AMDs just 
 assumed branch not taken if wasn't in the BTB already. Newer 
 CPUs, Core2 onwards, Zen, nobody seems to know for sure what 
 they do, but the Intel SDMs do state that the Core 
 architecture doesn't use static prediction. I think Agner Fog 
 says it's essentially random.


 https://www.agner.org/optimize/microarchitecture.pdf

 Not quite random, but certainly has changed to a significantly 
 more complicated design since the 90's.


Read 3.7

"Static prediction in PM and Core2
These processors do not use static prediction. The predictor 
simply makes a random prediction the first time a branch is seen, 
depending on what happens to be in the BTB entry that is assigned 
to the new branch. There is simply a 50% chance of making the 
right prediction of jump or no jump, but the predicted target is 
correct."

I mean I assume we're talking about static prediction here, 
because there's no point trying to out think the branch predictor 
once it's got history for the branch.



 Sep 13



prev sibling  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


Thanks for digging this up. I don't see much hope of integrating that into a 
code generator. Even worse, using different schemes for multiple processors
that 
are supposedly implementing the same instruction set.



 Sep 14



  parent  "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 15/09/2024 2:37 PM, Walter Bright wrote:

 Thanks for digging this up. I don't see much hope of integrating that 
 into a code generator.


Agreed, you won't be able to compete with LLVM and GCC, when they have 
the cpu designers contributing.


 Even worse, using different schemes for multiple 
 processors that are supposedly implementing the same instruction set.


The backend does have this knowledge. Normally with GCC and LLVM, you'd 
give it the specific cpu generation you want to target. Or you can use 
the JIT option for LLVM and get it sorted out on execution.

https://github.com/dlang/dmd/blob/0e8e67097df1a367eec1cff2069166843ad53eb3/compiler/src/dmd/backend/cdef.d#L221

https://wiki.dlang.org/LDC-specific_language_changes#.40.28ldc.attributes.dynamicCompile.29

The dmd backend understanding of cpu generations is a little out of date 
though!

Realistically you're going to be relying on user data to optimize this 
for dmd. Either from PGO, or annotation in code.

I can't see PGO being worth your time to implement. If people care about 
performance they are simply not going to be using dmd for it.

But for annotation in code... you can do this in the glue code, a simple 
swap of condition and with that path, should work!

```
test;
jgt True;
False:

goto End;
True:

End:
ret;
```

vs

```
test;
ge False;
True:

goto End;
False:

End:
ret;
```



 Sep 14



prev sibling  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/13/2024 1:50 PM, claptrap wrote:

 That was pretty much only the Pentiums, older AMDs just assumed branch not
taken 
 if wasn't in the BTB already. Newer CPUs, Core2 onwards, Zen, nobody seems to 
 know for sure what they do, but the Intel SDMs do state that the Core 
 architecture doesn't use static prediction. I think Agner Fog says it's 
 essentially random.


You're not wrong, but Manu was interested in this feature on microcontrollers 
which apparently have a more primitive system.



 Sep 14



prev sibling  parent reply Manu <turkeyman gmail.com>  writes:


On Wed, 11 Sept 2024 at 20:01, Walter Bright via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On 9/11/2024 4:53 AM, Manu wrote:

 Just to be clear; nobody I'm aware of has proposed that design, so I


 hope that's

 not your take-away.


 Indeed I thought you were proposing that, glad you're not!


 My proposal is to allow a hint attached strictly to control statements.


 (ideally

 as a suffix)
 It is easy to read, also easy to ignore (this is important), and


 extremely

 low-impact when marking up existing code: no new lines, no rearranging


 of code,

 purely additive; strictly appends to the end of existing


 control statements...

 these are very nice properties for casually marking up some code where


 it proves

 to be profitable, without interfering with readability, or even


 interfering with

 historic diff's in any meaningful way that might make it annoying to


 review.

 How is that materially different from [[likely]] annotations?


The article given above shows why arbitrary hints given as stand-alone
statements in a flow causes nonsense when conflicting annotations appear
within a flow.
Attaching exactly one annotation specifically to a control statement that
describes a branch is not at risk of nonsense cases.



 Sep 11



  parent reply Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 3:44 PM, Manu wrote:

 The article given above shows why arbitrary hints given as stand-alone 
 statements in a flow causes nonsense when conflicting annotations appear
within 
 a flow.


It reminds me of the wretched

__declspec
__attribute__
__pragma
_Pragma
#pragma

additions to C that don't fit in the grammar in any sane manner.



 Sep 13



  parent reply Manu <turkeyman gmail.com>  writes:


On Fri, 13 Sept 2024, 09:31 Walter Bright via Digitalmars-d, <
digitalmars-d puremagic.com> wrote:


 On 9/11/2024 3:44 PM, Manu wrote:

 The article given above shows why arbitrary hints given as stand-alone
 statements in a flow causes nonsense when conflicting annotations appear


 within

 a flow.


 It reminds me of the wretched

 __declspec
 __attribute__
 __pragma
 _Pragma
 #pragma

 additions to C that don't fit in the grammar in any sane manner


Yes, that's exactly why this thread exists. What you describe is the
situation we have in D today...






 Sep 13



  parent  Walter Bright <newshound2 digitalmars.com>  writes:


D's attributes are in the grammar in a sane manner.



 Sep 14



prev sibling next sibling parent reply Andrea Fontana <nospam example.org>  writes:


On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 I'm working on microcontrollers, and many don't have a branch 
 predictor. They do "static" prediction, that is, they just 
 predict branch-not-taken and it's on you to write your code as 
 such, and that's not always possible. (like the loop condition 
 in a for loop)

 This leads to a lot of awkward looking if's written in 
 unnatural 'backwards' terms, and also, leads to undesirable 
 depth of nested scopes.

 The compiler backend can and should re-jig the comparisons, but 
 it needs to receive a hint which way is 'likely' from the 
 programmer.

 How can we add an attribute to the branch condition that the 
 backend can take advantage of? I think it needs to be in the 
 language spec...


unlikely_if(...) ...;
else ...;

:)



 Sep 10



  parent reply Dom DiSc <dominikus scherkl.de>  writes:


On Tuesday, 10 September 2024 at 08:29:49 UTC, Andrea Fontana 
wrote:

 unlikely_if(...) ...;
 else ...;


Cool. That's the first proposal that I can read without getting 
eye-cancer.



 Sep 10



  parent reply Daniel N <no public.email>  writes:


On Tuesday, 10 September 2024 at 08:54:13 UTC, Dom DiSc wrote:

 On Tuesday, 10 September 2024 at 08:29:49 UTC, Andrea Fontana 
 wrote:

 unlikely_if(...) ...;
 else ...;


 Cool. That's the first proposal that I can read without getting 
 eye-cancer.


I had similar thoughts.

unlikely(...) ...;
else ...;



 Sep 10



  parent reply ShadoLight <ettienne.gilbert gmail.com>  writes:


On Tuesday, 10 September 2024 at 11:24:35 UTC, Daniel N wrote:

 On Tuesday, 10 September 2024 at 08:54:13 UTC, Dom DiSc wrote:

 On Tuesday, 10 September 2024 at 08:29:49 UTC, Andrea Fontana 
 wrote:

 unlikely_if(...) ...;
 else ...;


 Cool. That's the first proposal that I can read without 
 getting eye-cancer.


 I had similar thoughts.

 unlikely(...) ...;
 else ...;


Just tongue-in-cheek along these lines ;-)

iffy(...) ...;
else ...;


At least it is shorter!



 Sep 11



  parent reply Dom DiSc <dominikus scherkl.de>  writes:


On Wednesday, 11 September 2024 at 08:53:30 UTC, ShadoLight wrote:

 Just tongue-in-cheek along these lines ;-)

 iffy(...) ...;
 else ...;


 At least it is shorter!


In german it would be easy: "wenn" is the likely path, "falls" is 
the unlikely path.



 Sep 11



 next sibling parent reply Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Wednesday, 11 September 2024 at 11:05:03 UTC, Dom DiSc wrote:

 On Wednesday, 11 September 2024 at 08:53:30 UTC, ShadoLight 
 wrote:

 Just tongue-in-cheek along these lines ;-)

 iffy(...) ...;
 else ...;


 At least it is shorter!


 In german it would be easy: "wenn" is the likely path, "falls" 
 is the unlikely path.


There’s also _when_ in English. Being German myself, I found 
_wenn_ and _falls_ are way more interchangeable than English _if_ 
and _when._ What teachers tell you isn’t that clear cut true. 
Haskell has a `when` function for monads.

Maybe we could add `unless` which is a negated `if`, but 
`unless(cond)` is different from `if (!cond)` in how it’s seen my 
the optimizer. CoffeScript has `unless`. However, I still think 
any optimization hints should be in a form that allows a 
conforming compiler to ignore it, i.e. a `pragma` is ideal:

```d
if (x is null) pragma(unlikely) return 0;
// use *x
```

The best thing about `pragma` is that it allows for additional 
arguments. For example, a `bool` to enable or disable it: 
`pragma(unlikely, false)` could be as if it’s not there. Great 
for meta-programming. For `pragma(likely)`, a numerical 
probability makes sense, too: `pragma(likely, 0)` is equivalent 
to `pragma(unlikely)` and a single `pragma(likely, value)` (with 
`value` > 0) is `pragma(likely)`.

Generally speaking, if there are more than two branches, with two 
or more of them tagged `likely`, they can be given weights, that 
may be derived from abstract reasoning or profiling. That’s 
essentially what GCC has with 
`__builtin_expect_with_probability`, except that it’s with 
weights and not probabilities.



 Sep 13



 next sibling parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 13/09/2024 9:54 PM, Quirin Schroll wrote:

 The best thing about |pragma| is that it allows for additional 
 arguments. For example, a |bool| to enable or disable it: 
 |pragma(unlikely, false)| could be as if it’s not there. Great for 
 meta-programming. For |pragma(likely)|, a numerical probability makes 
 sense, too: |pragma(likely, 0)| is equivalent to |pragma(unlikely)| and 
 a single |pragma(likely, value)| (with |value| > 0) is |pragma(likely)|.


We can do this with a UDA.

```d
struct unlikely {
	bool activate=true;
}

if (...)  unlikely(false) {

}
```


 Generally speaking, if there are more than two branches, with two or 
 more of them tagged |likely|, they can be given weights, that may be 
 derived from abstract reasoning or profiling. That’s essentially what 
 GCC has with |__builtin_expect_with_probability|, except that it’s with 
 weights and not probabilities.


The way it works in D is if-else not if-elseif-else.

So for something like this, you are swapping the assumption from one 
path to another.

I don't think we need probability support, just because of how the IR 
will be laid out to the backend.



 Sep 13



  parent reply Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Friday, 13 September 2024 at 10:02:25 UTC, Richard (Rikki) 
Andrew Cattermole wrote:

 On 13/09/2024 9:54 PM, Quirin Schroll wrote:

 The best thing about |pragma| is that it allows for additional 
 arguments. For example, a |bool| to enable or disable it: 
 |pragma(unlikely, false)| could be as if it’s not there. Great 
 for meta-programming. For |pragma(likely)|, a numerical 
 probability makes sense, too: |pragma(likely, 0)| is 
 equivalent to |pragma(unlikely)| and a single |pragma(likely, 
 value)| (with |value| > 0) is |pragma(likely)|.


 We can do this with a UDA.

 ```d
 struct unlikely {
 	bool activate=true;
 }

 if (...)  unlikely(false) {

 }
 ```


Compiler-recognized UDAs are actually a bad choice in this case. 
We’d need to change the grammar to allow them at this place in a 
very special and weird way and they’re harder to ignore.

Again, the advantage of a pragma is that it’s implementation 
defined and may end up not have any semantics at all, and this is 
already specified out. A compiler-recognized UDA is just the 
wrong tool for the job. The [spec about 
pragmas](https://dlang.org/spec/pragma) is pretty clear about 
that and as a related feature, `inline` is a pragma as well for 
this exact reason.

I just don’t understand why some people are adamant that those 
annotations should be attributes. To me, it makes not the least 
bit of sense.


 Generally speaking, if there are more than two branches, with 
 two or more of them tagged |likely|, they can be given 
 weights, that may be derived from abstract reasoning or 
 profiling. That’s essentially what GCC has with 
 |__builtin_expect_with_probability|, except that it’s with 
 weights and not probabilities.


 The way it works in D is if-else not if-elseif-else.


There is also `switch`.


 So for something like this, you are swapping the assumption 
 from one path to another.

 I don't think we need probability support, just because of how 
 the IR will be laid out to the backend.


GCC supports them, so I thought at least GDC could make use of 
them, LDC probably, too. DMD can just consider weights > 0 as 
equal and likely.



 Sep 13



  parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz>  writes:


On 13/09/2024 10:20 PM, Quirin Schroll wrote:

 On Friday, 13 September 2024 at 10:02:25 UTC, Richard (Rikki) Andrew 
 Cattermole wrote:

 On 13/09/2024 9:54 PM, Quirin Schroll wrote:

 The best thing about |pragma| is that it allows for additional 
 arguments. For example, a |bool| to enable or disable it: 
 |pragma(unlikely, false)| could be as if it’s not there. Great for 
 meta-programming. For |pragma(likely)|, a numerical probability makes 
 sense, too: |pragma(likely, 0)| is equivalent to |pragma(unlikely)| 
 and a single |pragma(likely, value)| (with |value| > 0) is 
 |pragma(likely)|.


 We can do this with a UDA.

 ```d
 struct unlikely {
     bool activate=true;
 }

 if (...)  unlikely(false) {

 }
 ```


 
 Compiler-recognized UDAs are actually a bad choice in this case. We’d 
 need to change the grammar to allow them at this place in a very special 
 and weird way and they’re harder to ignore.
 
 Again, the advantage of a pragma is that it’s implementation defined and 
 may end up not have any semantics at all, and this is already specified 
 out. A compiler-recognized UDA is just the wrong tool for the job. The 
 [spec about pragmas](https://dlang.org/spec/pragma) is pretty clear 
 about that and as a related feature, `inline` is a pragma as well for 
 this exact reason.
 
 I just don’t understand why some people are adamant that those 
 annotations should be attributes. To me, it makes not the least bit of 
 sense.


All the arguments you are making for a pragma equally apply to a UDA.

Except they have the benefit that you can override them, and redefine 
them if they are not supported.

You cannot do that with a pragma.

So there is a transition path for both old and new code with new 
compiler versions with the UDA's that are not present with pragmas and 
that is a major advantage for code maintenance and portability between 
compilers.


 Generally speaking, if there are more than two branches, with two or 
 more of them tagged |likely|, they can be given weights, that may be 
 derived from abstract reasoning or profiling. That’s essentially what 
 GCC has with |__builtin_expect_with_probability|, except that it’s 
 with weights and not probabilities.


 The way it works in D is if-else not if-elseif-else.


 
 There is also `switch`.


Walter has stated this elsewhere, that the order of declaration 
determines likelihood for cases.

https://forum.dlang.org/post/vbspbo$2845$1 digitalmars.com


 So for something like this, you are swapping the assumption from one 
 path to another.

 I don't think we need probability support, just because of how the IR 
 will be laid out to the backend.


 
 GCC supports them, so I thought at least GDC could make use of them, LDC 
 probably, too. DMD can just consider weights > 0 as equal and likely.


So does LLVM.

What I am questioning is the need to offer this in the language, as I 
don't think we can drive it. To drive it you need if-elseif-else, rather 
than if-else.



 Sep 13



  parent reply Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Friday, 13 September 2024 at 10:26:48 UTC, Richard (Rikki) 
Andrew Cattermole wrote:

 On 13/09/2024 10:20 PM, Quirin Schroll wrote:

 On Friday, 13 September 2024 at 10:02:25 UTC, Richard (Rikki) 
 Andrew Cattermole wrote:

 On 13/09/2024 9:54 PM, Quirin Schroll wrote:

 The best thing about |pragma| is that it allows for 
 additional arguments. For example, a |bool| to enable or 
 disable it: |pragma(unlikely, false)| could be as if it’s 
 not there. Great for meta-programming. For |pragma(likely)|, 
 a numerical probability makes sense, too: |pragma(likely, 
 0)| is equivalent to |pragma(unlikely)| and a single 
 |pragma(likely, value)| (with |value| > 0) is 
 |pragma(likely)|.


 We can do this with a UDA.

 ```d
 struct unlikely {
     bool activate=true;
 }

 if (...)  unlikely(false) {

 }
 ```


 
 Compiler-recognized UDAs are actually a bad choice in this 
 case. We’d need to change the grammar to allow them at this 
 place in a very special and weird way and they’re harder to 
 ignore.
 
 Again, the advantage of a pragma is that it’s implementation 
 defined and may end up not have any semantics at all, and this 
 is already specified out. A compiler-recognized UDA is just 
 the wrong tool for the job. The [spec about 
 pragmas](https://dlang.org/spec/pragma) is pretty clear about 
 that and as a related feature, `inline` is a pragma as well 
 for this exact reason.
 
 I just don’t understand why some people are adamant that those 
 annotations should be attributes. To me, it makes not the 
 least bit of sense.


 All the arguments you are making for a pragma equally apply to 
 a UDA.


I don’t see why. Compilers aren’t free to ignore ` safe` and not 
issue an error if you violate its conditions, but every pragma is 
specified to be ignorable.


 Except they have the benefit that you can override them, and 
 redefine them if they are not supported.

 You cannot do that with a pragma.

 So there is a transition path for both old and new code with 
 new compiler versions with the UDA's that are not present with 
 pragmas and that is a major advantage for code maintenance and 
 portability between compilers.


I fail to see why this is the case or even desirable. 
`pragma(likely)` isn’t really likely to be in code bases anyway.


 Generally speaking, if there are more than two branches, 
 with two or more of them tagged |likely|, they can be given 
 weights, that may be derived from abstract reasoning or 
 profiling. That’s essentially what GCC has with 
 |__builtin_expect_with_probability|, except that it’s with 
 weights and not probabilities.


 The way it works in D is if-else not if-elseif-else.


 
 There is also `switch`.


 Walter has stated this elsewhere, that the order of declaration 
 determines likelihood for cases.

 https://forum.dlang.org/post/vbspbo$2845$1 digitalmars.com


Another case of relying on the choice of specific compilers. 
AFAICT, the whole point of likelihood annotations is that you can 
layout the code as you think it’s best to read, but sprinkle in 
some annotations that don’t hurt reading so that the compiler 
emits a better binary.


 So for something like this, you are swapping the assumption 
 from one path to another.

 I don't think we need probability support, just because of 
 how the IR will be laid out to the backend.


 
 GCC supports them, so I thought at least GDC could make use of 
 them, LDC probably, too. DMD can just consider weights > 0 as 
 equal and likely.


 So does LLVM.

 What I am questioning is the need to offer this in the 
 language, as I don't think we can drive it. To drive it you 
 need if-elseif-else, rather than if-else.


Well, we’re in circles here. I already mentioned `switch`, and 
again, the reason for the annotation is that code can be laid out 
to be readable and idiomatic. Let’s say you have a big switch in 
a hot loop. You profiled and now the data tells you how likely 
each branch was. What would you prefer? Reordering the branches 
by likelihood, leading to a diff that’s basically impossible to 
understand or even vet that it’s just a reordering, or the pure 
addition of likelihood annotations, for which in the diff it’s 
absolutely clear nothing else changes. And if there’s a 
fallthrough, you have to jump to the right case now.

You’re arguing as if the compiler couldn’t recognize `else if` as 
a pattern.

The reason a compiler optimizes the non-branch or switch cases by 
ordering (except if it has another clear indication of what’s a 
cold path, e.g. a thrown exception) is because absent any 
information, it has to do something and be deterministic. For 
most cases, it’s fine. Optimization hints are an expert tool.



 Sep 13



  parent reply Zoadian <no no.no>  writes:


On Friday, 13 September 2024 at 10:57:56 UTC, Quirin Schroll 
wrote:

 On Friday, 13 September 2024 at 10:26:48 UTC, Richard (Rikki) 
 Andrew Cattermole wrote:
 Let’s say you have a big switch in a hot loop. You profiled and 
 now the data tells you how likely each branch was. What would 
 you prefer? Reordering the branches by likelihood, leading to a 
 diff that’s basically impossible to understand or even vet that 
 it’s just a reordering, or the pure addition of likelihood 
 annotations, for which in the diff it’s absolutely clear 
 nothing else changes. And if there’s a fallthrough, you have to 
 jump to the right case now.


i'd prefer handing the compiler a profile log, and the compiler 
just optimizing based on that file without the need to do any 
annotations by hand.



 Sep 13



  parent  Quirin Schroll <qs.il.paperinik gmail.com>  writes:


On Friday, 13 September 2024 at 11:18:59 UTC, Zoadian wrote:

 On Friday, 13 September 2024 at 10:57:56 UTC, Quirin Schroll 
 wrote:

 On Friday, 13 September 2024 at 10:26:48 UTC, Richard (Rikki) 
 Andrew Cattermole wrote:
 Let’s say you have a big switch in a hot loop. You profiled 
 and now the data tells you how likely each branch was. What 
 would you prefer? Reordering the branches by likelihood, 
 leading to a diff that’s basically impossible to understand or 
 even vet that it’s just a reordering, or the pure addition of 
 likelihood annotations, for which in the diff it’s absolutely 
 clear nothing else changes. And if there’s a fallthrough, you 
 have to jump to the right case now.


 i'd prefer handing the compiler a profile log, and the compiler 
 just optimizing based on that file without the need to do any 
 annotations by hand.


Sure, that’s way easier for devs. You just can’t do that if you 
also want to distribute the code with the branch hints.



 Sep 18



prev sibling  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/13/2024 2:54 AM, Quirin Schroll wrote:

 That’s essentially what GCC has with `__builtin_expect_with_probability`


No hire.



 Sep 14



prev sibling  parent  Walter Bright <newshound2 digitalmars.com>  writes:


On 9/11/2024 4:05 AM, Dom DiSc wrote:

 In german it would be easy: "wenn" is the likely path, "falls" is the unlikely 
 path.


Hmm. What about in Klingon?



 Sep 14



prev sibling  parent  Guillaume Piolat <guillaume.piolat gmail.com>  writes:


On Friday, 23 August 2024 at 01:47:37 UTC, Manu wrote:

 How can we add an attribute to the branch condition that the 
 backend can take advantage of? I think it needs to be in the 
 language spec...


In case this thread goes nowhere, work-around is:

     version(LDC)
     {
         import ldc.intrinsics;
         bool likely(bool b) { return llvm_expect!bool(b, true); }
         bool unlikely(bool b) { return llvm_expect!bool(b, 
false); }
     }
     else
     {
         bool likely(bool b) { return b; }
         bool unlikely(bool b) { return b; }
     }

Not sure for GDC. This taken from lz4 source.



 Sep 15