On Tuesday, 19 May 2015 at 20:41:58 UTC, Brian Schott wrote:
> On Tuesday, 19 May 2015 at 20:01:29 UTC, deadalnix wrote:
>> Have you tried things like :
>>
>> (x >> bsr(x)) == 1 ?
>>
>> I have no idea if this is faster or not, but worth trying.
>
> https://issues.dlang.org/show_bug.cgi?id=14380
>
> "If the content source operand is 0, the content of the destination operand is undefined" - This applies to both the bsf and bsr instructions.

Why ain't we generating a tzcnt ?

On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote:
> On 5/19/15 4:01 PM, deadalnix wrote:
>> Have you tried things like :
>>
>> (x >> bsr(x)) == 1 ?
>>
>> I have no idea if this is faster or not, but worth trying.
>
> Hm.. I think this would always succeed. Perhaps you mean:
>
> 1 << bsr(x) == x;
>

Both work as long as you use a fully defined instruction, like tzcnt.

On 5/19/15 5:32 PM, deadalnix wrote:
> On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote:
>> On 5/19/15 4:01 PM, deadalnix wrote:
>>> Have you tried things like :
>>>
>>> (x >> bsr(x)) == 1 ?
>>>
>>> I have no idea if this is faster or not, but worth trying.
>>
>> Hm.. I think this would always succeed. Perhaps you mean:
>>
>> 1 << bsr(x) == x;
>>
>
> Both work as long as you use a fully defined instruction, like tzcnt.

Hm... I messed up, (x >> bsr(x)) is always zero. I think you meant to write:

x >> (bsr(x) - 1)

which always is 1.

Either way, it doesn't work.

-Steve

On Tuesday, 19 May 2015 at 22:43:46 UTC, Steven Schveighoffer wrote:
> On 5/19/15 5:32 PM, deadalnix wrote:
>> On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote:
>>> On 5/19/15 4:01 PM, deadalnix wrote:
>>>> Have you tried things like :
>>>>
>>>> (x >> bsr(x)) == 1 ?
>>>>
>>>> I have no idea if this is faster or not, but worth trying.
>>>
>>> Hm.. I think this would always succeed. Perhaps you mean:
>>>
>>> 1 << bsr(x) == x;
>>>
>>
>> Both work as long as you use a fully defined instruction, like tzcnt.
>
> Hm... I messed up, (x >> bsr(x)) is always zero. I think you meant to write:
>
> x >> (bsr(x) - 1)
>
> which always is 1.
>
> Either way, it doesn't work.
>
> -Steve

No.

bsr(1) is 0.
1 >> bsr(1) is 1.
0 >> anything is 0.

So it doesn't matter if bsr is defined or not for 0.

On Tuesday, 19 May 2015 at 20:46:09 UTC, Matthias Bentrup wrote:
> I think you can make the over/underflow at zero work in your favor:
>
> bool isPowerOf2(uint x)
> {
>   return (x & -x) > (x - 1);
> }

Very nice

First version isn't any slow. It's clear and can be optimized with gdc:

http://goo.gl/Q7HKcU

And if you matter about dmd - it generates shit all the time.

On Wednesday, 20 May 2015 at 09:49:06 UTC, Temtaime wrote:
> First version isn't any slow. It's clear and can be optimized with gdc:
>
> http://goo.gl/Q7HKcU

Yes, and besides, if one cares about these minor performance issues, that most likely will disappear in the pipeline if you are a little bit careful about how you arrange your code, then one one would be better off letting the compiler take advantage of statically available information about size:

@always_inline
... allocate(ulong size){
   if(size==0) return _my_alloc_zero();
   if(is_log2_or_zero(size)) return _my_alloc_log2size(size);
   return _my_alloc_nonlog2size(size);
 }

So basically a version that preserves the tests that the compiler most easily can get rid of can lead to faster code even if it in isolation has a few extra instructions.

On 5/19/15 1:46 PM, Matthias Bentrup wrote:
> I think you can make the over/underflow at zero work in your favor:
>
> bool isPowerOf2(uint x)
> {
>    return (x & -x) > (x - 1);
> }

Nice code with dmd and gdc. Thanks! https://github.com/andralex/phobos/commit/ec197ecd203b0ea25201acfeb4fbbb13b2fabb7f -- Andrei

On 5/19/15 7:41 PM, deadalnix wrote:
> On Tuesday, 19 May 2015 at 22:43:46 UTC, Steven Schveighoffer wrote:
>> On 5/19/15 5:32 PM, deadalnix wrote:
>>> On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote:
>>>> On 5/19/15 4:01 PM, deadalnix wrote:
>>>>> Have you tried things like :
>>>>>
>>>>> (x >> bsr(x)) == 1 ?
>>>>>
>>>>> I have no idea if this is faster or not, but worth trying.
>>>>
>>>> Hm.. I think this would always succeed. Perhaps you mean:
>>>>
>>>> 1 << bsr(x) == x;
>>>>
>>>
>>> Both work as long as you use a fully defined instruction, like tzcnt.
>>
>> Hm... I messed up, (x >> bsr(x)) is always zero. I think you meant to
>> write:
>>
>> x >> (bsr(x) - 1)
>>
>> which always is 1.
>>
>> Either way, it doesn't work.
>>
>
> No.
>
> bsr(1) is 0.
> 1 >> bsr(1) is 1.

Gah, I messed up, used output from old code that wasn't doing what I thought it was. You are right about that.

But my whole point there was that x >> bsr(x) is ALWAYS 1.

2 >> bsr(2) == 1
3 >> bsr(3) == 1
4 >> bsr(4) == 1
17 >> bsr(17) == 1

So really, your test checks to see if a value is zero or not, not whether it's a power of 2.

BUT, the opposite mechanism would work:

1 << bsr(x) == x;

> 0 >> anything is 0.

Hah, good point :) Even if bsr(0) is undefined it doesn't matter. Didn't think of that.

But that means the opposite solution I mentioned above, doesn't work, still back to square one.

-Steve

On Tuesday, 19 May 2015 at 20:46:09 UTC, Matthias Bentrup wrote:
> I think you can make the over/underflow at zero work in your favor:
>
> bool isPowerOf2(uint x)
> {
>   return (x & -x) > (x - 1);
> }

The cool thing is that also the over/underflow of "-" at 0x8000_0000 works. But that is really a weird calculation! Wouldn't pass any Polyspace or other code checker tool and need some special comments on why it works...