www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Simple features that I've always missed from C...

reply Manu <turkeyman gmail.com> writes:
Some trivial binary operations that never had an expression in C/C++, I'd
love consideration for an operator or some sort of intrinsic for these.

*Roll/Rotate:* I'm loving the '>>>' operator, but I could often really do
with a rotate operator useful in many situations... '>>|' perhaps...
something like that?
  This is ugly: a = (a << x) | ((unsigned)a >> (sizeof(a)/8 - x)); ... and
I'm yet to see a compiler that will interpret that correctly.
  Additionally, if a vector type is every added, a rotate operator will
become even more useful.

*Count leading/trailing zeroes:* I don't know of any even slightly recent
architecture that doesn't have opcodes to count loading/trailing zeroes,
although they do exist, so perhaps this is a little dubious. I'm sure this
could be emulated for such architectures, but it might be unreasonably slow
if used...

*Min/Max operators:* GCC has the lovely <? and >? operators... a <? b ==
min(a, b) .. Why this hasn't been adopted by all C compilers is beyond me.
Surely this couldn't be much trouble to add? Again, super useful in
vector/maths heavy code too.

*Predecated selection:* Float, vector, and often enough even int math can
really benefit from using hardware select opcodes to avoid loads/stores. In
C there is no way to express this short of vendor specific intrinsics again.
'a > b ? a : b' seems like a simple enough expression for the compiler to
detect potential for a predecated select opcode (but in my experience, it
NEVER does), however, when considering vector types, the logic isn't so
clear in that format. Since hardware vectors implement component-wise
selection, the logical nature of the ?: operator doesn't really make sense.
  This could easily be considered an expansion of min/max... 'a <? b', 'a >?
b', 'a ==? b', 'a !=? b', etc. seems pretty natural if you're happy to
accept GCC's '<?' operators, and give the code generator the opportunity to
implement these things using hardware support.


C is terrible at expressing these concepts, resulting in
architecture/compiler specific intrinsics for each of them. Every time I've
ever written a maths library, or even just optimised some maths heavy
routines, these things come up, and I end up with code full of
architecture/platform/compiler ifdef's. I'd like to think they should be
standardised intrinsic features of the language (not implemented in the
standard library), so the code generator/back end has the most information
to generate proper code...

Cheers guys
- Manu
Oct 17 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Manu:


 *Roll/Rotate:* I'm loving the '>>>' operator, but I could often really do
 with a rotate operator useful in many situations... '>>|' perhaps...
 something like that?
   This is ugly: a = (a << x) | ((unsigned)a >> (sizeof(a)/8 - x));


I have asked for a rotate intrinsic in Phobos, but Walter has added a rewrite
rule instead, that turns D code to a rot.
Personal experience has shown me that it's easy to write the operation in a
slightly different way (like with signed instead of unsigned values) that
causes a missed optimization. So I prefer still something specific, like a
Phobos intrinsic, to explicitly ask for this operation to every present and
future D compiler, with no risk of mistakes.



 *Min/Max operators:* GCC has the lovely <? and >? operators... a <? b ==
 min(a, b) .. Why this hasn't been adopted by all C compilers is beyond me.
 Surely this couldn't be much trouble to add? Again, super useful in
 vector/maths heavy code too.


This is cute. Surely max/min is a common operation to do, but often I have to
find a max or min of a collection, where I think this operator can't be used. I
don't think this operator is necessary, and it makes D code a bit less readable
for people that don't know D.




 *Predecated selection:* Float, vector, and often enough even int math can
 really benefit from using hardware select opcodes to avoid loads/stores. In
 C there is no way to express this short of vendor specific intrinsics again.


I don't understand what you are asking here. Please show an example.

There is an enhancement request that asks to support vector operations like
this too (some CPUs support something like this in hardware):
int[] a = [1,2,3,4];
int[] b = [4,3,2,1];
auto c = a[] > b[];
assert(c == [false, false, true, true]);

Are operations like this what you are asking for here?

Bye,
bearophile
Oct 17 2011
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 10/17/2011 4:45 PM, bearophile wrote:

 Manu:


 *Roll/Rotate:* I'm loving the '>>>' operator, but I could often really do
 with a rotate operator useful in many situations... '>>|' perhaps...
 something like that? This is ugly: a = (a<<  x) | ((unsigned)a>>
 (sizeof(a)/8 - x));


 I have asked for a rotate intrinsic in Phobos, but Walter has added a rewrite
 rule instead, that turns D code to a rot. Personal experience has shown me
 that it's easy to write the operation in a slightly different way (like with
 signed instead of unsigned values) that causes a missed optimization. So I
 prefer still something specific, like a Phobos intrinsic, to explicitly ask
 for this operation to every present and future D compiler, with no risk of
 mistakes.


There's no need for a compiler intrinsic. Just write a function that does do
the 
optimization, and call it.

The signed versions "don't work" because a signed right shift is not the same 
thing as an unsigned right shift.

For reference:

void test236()
{
     uint a;
     int shift;
     a = 7;
     shift = 1;
     int r;
     r = (a >> shift) | (a << (int.sizeof * 8 - shift));
     assert(r == 0x8000_0003);
     r = (a << shift) | (a >> (int.sizeof * 8 - shift));
     assert(a == 7);
}
Oct 17 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Walter Bright:


 There's no need for a compiler intrinsic. Just write a function that does do
the 
 optimization, and call it.


Right. Two functions like this are worth putting somewhere in Phobos.



 The signed versions "don't work" because a signed right shift is not the same 
 thing as an unsigned right shift.


It was a mistake in my code.

Thank you, bye,
bearophile
Oct 18 2011
prev sibling parent Manu <turkeyman gmail.com> writes:
On 18 October 2011 02:45, bearophile <bearophileHUGS lycos.com> wrote:


 I have asked for a rotate intrinsic in Phobos, but Walter has added a
 rewrite rule instead, that turns D code to a rot.
 Personal experience has shown me that it's easy to write the operation in a
 slightly different way (like with signed instead of unsigned values) that
 causes a missed optimization. So I prefer still something specific, like a
 Phobos intrinsic, to explicitly ask for this operation to every present and
 future D compiler, with no risk of mistakes.


I agree, an intrinsic that guarantees compiler support, or even an
operator... ;)


 *Predecated selection:* Float, vector, and often enough even int math can

 really benefit from using hardware select opcodes to avoid loads/stores.


 In

 C there is no way to express this short of vendor specific intrinsics


 again.

 I don't understand what you are asking here. Please show an example.

 There is an enhancement request that asks to support vector operations like
 this too (some CPUs support something like this in hardware):
 int[] a = [1,2,3,4];
 int[] b = [4,3,2,1];
 auto c = a[] > b[];
 assert(c == [false, false, true, true]);

 Are operations like this what you are asking for here?


by predicated selection, I mean, code that will select from 2 values based
on some predicate... code that looks like this: float c = (some comparison)
? x : z; .. This has hardware support on many modern architectures to
perform it branch free, particularly important on PowerPC and other RISC
chips.

The vector equivalent depends on generating mask vectors from various
comparisons (essentially the same as the scalar versions, but it would be
nice to standardise that detail with a strict api).
Working something like this:
a = {1,2,3,4}
b = {4,3,2,1}
m = maskLessThan(a, b);  -> m == { true, true, false, false }; (usually
expressed by integer 0 or -1)
c = select(m, a, b); -> c == {1, 2, 2, 1}

Now this is effectively identical to: float c = a < b ? a : b; but in SIMD,
but there's no nice expression in the language to do this. The details are
occasionally slightly different on different architectures, hence I'd like
to see a standard predecated selection API of some form, which will allow
use of hardware opcodes for float/int, and also mapping to SIMD cleanly.

This might possibly branch off into another topic about SIMD support in D,
which appears to be basically non-existent.
One of the real problems is lack of definition of SIMD types and behaviours.
Also, this construct requires the concept of a mask vector (in essence a
SIMD bool), which should be a concept factored into the SIMD design...

On a side note, I've seen murmurings of support for syntax like you
illustrate a few times (interpreting D arrays as candidates for hardware
SIMD usage). While that MIGHT be a nice optimisation in isolated cases, I
have very serious concerns about standardising that as the language mechanic
for dealing with SIMD data types.
I wrote a couple of emails about that in the past though.
Oct 18 2011
prev sibling next sibling parent reply kennytm <kennytm gmail.com> writes:
Manu <turkeyman gmail.com> wrote:

 
 *Min/Max operators:* GCC has the lovely <? and >? operators... a <? b ==
 min(a, b) .. Why this hasn't been adopted by all C compilers is beyond me.
 Surely this couldn't be much trouble to add? Again, super useful in
 vector/maths heavy code too.


FYI, g++ has deprecated these operators long time ago (since 4.0). 

http://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Deprecated-Features.html
Oct 17 2011
parent Manu <turkeyman gmail.com> writes:
On 18 October 2011 05:11, kennytm <kennytm gmail.com> wrote:


 FYI, g++ has deprecated these operators long time ago (since 4.0).

 http://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Deprecated-Features.html


Nooo! .. Removed in favour of the STL instead... well I for one thought they
were a great idea, but apparently trumped by the standards mob.
Doesn't mean they couldn't be considered for D though :)
Oct 18 2011
prev sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 17 Oct 2011 16:53:42 -0400, Manu <turkeyman gmail.com> wrote:
[snip]

 *Count leading/trailing zeroes:* I don't know of any even slightly recent
 architecture that doesn't have opcodes to count loading/trailing zeroes,
 although they do exist, so perhaps this is a little dubious. I'm sure this
 could be emulated for such architectures, but it might be unreasonably slow
 if used...


D has this: check out std.intrinsic's bsr and bsl.
Oct 17 2011
parent reply Don <nospam nospam.com> writes:
On 18.10.2011 06:25, Robert Jacques wrote:

 On Mon, 17 Oct 2011 16:53:42 -0400, Manu <turkeyman gmail.com> wrote:
 [snip]

 *Count leading/trailing zeroes:* I don't know of any even slightly recent
 architecture that doesn't have opcodes to count loading/trailing zeroes,
 although they do exist, so perhaps this is a little dubious. I'm sure
 this
 could be emulated for such architectures, but it might be unreasonably
 slow
 if used...


 D has this: check out std.intrinsic's bsr and bsl.


You mean bsr and bsf.
Unfortunately, there are some big problems with them. What is bsr(0) ?
Oct 18 2011
parent reply Manu <turkeyman gmail.com> writes:
On 18 October 2011 12:12, Don <nospam nospam.com> wrote:


 You mean bsr and bsf.
 Unfortunately, there are some big problems with them. What is bsr(0) ?


True ;) .. but that's why the API needs to be defined and standardised.
On PowerPC it returns 32 (or 64), and the x86 version returns 2 values, the
position, and also a bool telling you if it was zero or not (useful for loop
termination)
I think all hardware that I've seen is easy to factor into the win32
intrinsic api.
Oct 18 2011
parent reply Don <nospam nospam.com> writes:
On 18.10.2011 11:43, Manu wrote:

 On 18 October 2011 12:12, Don <nospam nospam.com
 <mailto:nospam nospam.com>> wrote:

     You mean bsr and bsf.
     Unfortunately, there are some big problems with them. What is bsr(0) ?


 True ;) .. but that's why the API needs to be defined and standardised.
 On PowerPC it returns 32 (or 64), and the x86 version returns 2 values,
 the position, and also a bool telling you if it was zero or not (useful
 for loop termination)


Even worse -- Intel says that the position value of bsr(0) is undefined. 
But AMD does define it, they say it's what was in the register before.



 I think all hardware that I've seen is easy to factor into the win32
 intrinsic api.


That would be nice. What do you think it should do for the zero case?
Note that on x86, one possibility is to do a bsr followed by a cmov, to 
get the PowerPC semantics.
Oct 18 2011
parent reply Manu <turkeyman gmail.com> writes:
Nicely spotted, I didn't realise the intel/amd distinction ;)

Unless I'm mistaken, it is possible for D to return 'out' parameters by
value right? (in additional return registers, no touching the stack?) ..
Assuming that's the case you would surely standardise something more like
the win32 intrinsic rather than one resembling the PPC opcode.
If the function returns a bool that the value was zero or not, then I think
it's fair to say the position is undefined (which supports the intel
assertion).
PPC's approach is more cleanly factored into the win32 model than the other
way around I think, in terms of allowing the optimiser to trim the unused
code. If the intrinsic generates implicit code to produce a bool from the
value, it will surely be trimmed by the optimiser if that result is not
used.

While cmov might work nicely (although I really don't trust that opcode
anyway, an intrinsic like bsr shouldn't be producing a hidden branch) on x86
to produce the PPC result, I'm not sure other architectures would have such
a simple solution. Again, I think the win32 approach is easier for all
architectures to produce and for the optimiser to truncate if the calculated
result is unused.

bool bsf/bsr(int value, out int position); // this assumes that position
will cleanly return in a second return register...


On 18 October 2011 22:50, Don <nospam nospam.com> wrote:


 On 18.10.2011 11:43, Manu wrote:


 On 18 October 2011 12:12, Don <nospam nospam.com
 <mailto:nospam nospam.com>> wrote:

    You mean bsr and bsf.
    Unfortunately, there are some big problems with them. What is bsr(0) ?


 True ;) .. but that's why the API needs to be defined and standardised.
 On PowerPC it returns 32 (or 64), and the x86 version returns 2 values,
 the position, and also a bool telling you if it was zero or not (useful
 for loop termination)


 Even worse -- Intel says that the position value of bsr(0) is undefined.
 But AMD does define it, they say it's what was in the register before.



  I think all hardware that I've seen is easy to factor into the win32

 intrinsic api.


 That would be nice. What do you think it should do for the zero case?
 Note that on x86, one possibility is to do a bsr followed by a cmov, to get
 the PowerPC semantics.
Oct 19 2011
parent Don <nospam nospam.com> writes:
On 19.10.2011 10:13, Manu wrote:

 Nicely spotted, I didn't realise the intel/amd distinction ;)

 Unless I'm mistaken, it is possible for D to return 'out' parameters by
 value right? (in additional return registers, no touching the stack?) ..
 Assuming that's the case you would surely standardise something more
 like the win32 intrinsic rather than one resembling the PPC opcode.
 If the function returns a bool that the value was zero or not, then I
 think it's fair to say the position is undefined (which supports the
 intel assertion).

 PPC's approach is more cleanly factored into the win32 model than the
 other way around I think, in terms of allowing the optimiser to trim the
 unused code. If the intrinsic generates implicit code to produce a bool
 from the value, it will surely be trimmed by the optimiser if that
 result is not used.

 While cmov might work nicely (although I really don't trust that opcode
 anyway, an intrinsic like bsr shouldn't be producing a hidden branch) on
 x86 to produce the PPC result, I'm not sure other architectures would
 have such a simple solution.


Most other architectures that I know of, use lzcnt instead.

On AMD64 (not Intel) and on ARM, there's an LZCNT resp. CLZ instruction, 
which gives:
lzcnt(x) = x? 63-bsr(x) : 64;

Here's how it could be done:

RAX lzcnt(EBX)
{
   bsr RAX, RBX;
   cmovz RAX, -1
   xor RAX, 63;
}



 Again, I think the win32 approach is easier
 for all architectures to produce and for the optimiser to truncate if
 the calculated result is unused.

 bool bsf/bsr(int value, out int position); // this assumes that position
 will cleanly return in a second return register...


Seems to be equivalent to replacing the bsr with a comma expression:

(position = native_bsr(value), value == 0)

Do we really gain much by this?
The more painful signature of the function somewhat discourages users 
from calling it with a zero value, but the undefined position is still 
exposed. So the original problem of undefined behaviour remains.
There's maybe a performance improvement in the fairly rare case where 
there's a branch on zero value. Although theoretically, in existing code 
the optimizer could check for the sequence:
bsr dest, src
cmp src, 0   where only Z flag is required

and remove the cmp, so I don't think the performance aspect should be 
rated very highly.

It's a bit of a problem that AMD's bsf and bsr are so slow. They're 
really slow on Pentium 4 and Atom as well.

Interestingly AMD's lzcnt is faster than their bsr. But since Intel 
doesn't support it, it's pretty useless outside of inline asm.



I think we need to do a survey of as many architectures as possible, 
before we can decide what to do. As far as I know, bsr/bsf is unique to 
x86. If this is true, then bsf/bsr should probably be wrapped in 
version(x86), and discouraged from general use. A portable function 
(perhaps leadz, trailz) would need to provided as well, and recommended 
for general use.
Oct 20 2011