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