Optimization problem: bulk Boolean operations on vectors

Johan Engelen via Digitalmars-d digitalmars-d at puremagic.com
Sat Dec 24 02:28:08 PST 2016


On Saturday, 24 December 2016 at 00:04:48 UTC, Walter Bright 
wrote:
> On 12/23/2016 3:35 PM, Johan Engelen wrote:
>> On Friday, 23 December 2016 at 22:11:31 UTC, Walter Bright 
>> wrote:
>>>
>>> enum SIZE = 100000000;
>>>
>>> void foo(int* a, int* b) {
>>>     int* atop = a + 1000; // should be `a + SIZE`, right?
>>>     ptrdiff_t offset = b - a;
>>>     for (; a < atop; ++a)
>>>     *a &= *(a + offset);
>>> }
>>
>> This code is not equivalent with the plain foreach loop. 
>> Execution is different
>> when a > (size_t.max-SIZE).
>
> The assumption is that 'a' points to the start of an array 
> [0..SIZE], so there's no overflow.

Of course, but it's not codified in the source and thus the 
function is different from the foreach version.

More importantly, I think it is broken. I find it very hard to 
reason about the ptrdiff_t version, because of all the potential 
overflows and the mixing of unsigned and signed math. So I wrote 
a little helper program to print out pointer values.
```
// file a.d
import std.stdio;
void main()
{
     int* a = cast(int*) (size_t.max - 4000000LU + 2000000LU);
     int* b = cast(int*) (1000000LU);
     // ptrdiff_t cannot represent the large difference between
     //arrays at the start and end of memory.
     ptrdiff_t offset = b - a;

     writeln("a          = ", a);
     writeln("b          = ", b);
     writeln("a + offset = ", a + offset);
}
```
Then:
```
❯ dmd -run a.d
a          = FFFFFFFFFFC2F6FF
b          = F4240
a + offset = F423F
```
a+offset is not equal to b for the given pointer values. Whoops.

I find it amazing that the GCC backend manages to come up with a 
bunch of checks for different overflow cases and creates a 
vectorized inner loop.

-Johan



More information about the Digitalmars-d mailing list