My opinions about D array bound checks are slowly changing. I still think "-boundscheck=off" is useful and good to have. But now I am giving increasing importance to compiler logic that optimizes away bound checks safely. People more and more want a safe system language, more and more persons don't disable array bound tests. This means that optimizing away bound checks is becoming more and more important in D. And D can't ignore this need any more. Even adding logic to remove 20% of the bound checks in numeric code is going to help D because I think more and more people will not disable bound checks in D.


The following notes are derived from a post by Chris in D.learn:
http://forum.dlang.org/thread/kwkccgdymkpbpyzolumy@forum.dlang.org


Is it possible to optimize away all array bound checks in code like this?

void main() {
    int[5] data;
    foreach (const i; 0 .. 10)
        data[i] = 0;
    foreach (immutable i; 0 .. 10)
        data[i] = 0;
    int[10] big;
    foreach (const i, x; big)
        data[i] = x;
}


But the compiler must recognize this as correct code:


void main() {
    int[5] data;
    foreach (const i; 0 .. 10)
        if (i < 5)
            data[i] = 0;
}


Can this logic be added to D?


More info on the topic:
http://en.wikipedia.org/wiki/Bounds-checking_elimination
http://ssw.jku.at/Research/Papers/Wuerthinger07/Wuerthinger07.pdf

Bye,
bearophile

On 31/05/2014 10:56 p.m., bearophile wrote:
> My opinions about D array bound checks are slowly changing. I still
> think "-boundscheck=off" is useful and good to have. But now I am giving
> increasing importance to compiler logic that optimizes away bound checks
> safely. People more and more want a safe system language, more and more
> persons don't disable array bound tests. This means that optimizing away
> bound checks is becoming more and more important in D. And D can't
> ignore this need any more. Even adding logic to remove 20% of the bound
> checks in numeric code is going to help D because I think more and more
> people will not disable bound checks in D.
>
>
> The following notes are derived from a post by Chris in D.learn:
> http://forum.dlang.org/thread/kwkccgdymkpbpyzolumy@forum.dlang.org
>
>
> Is it possible to optimize away all array bound checks in code like this?
>
> void main() {
>      int[5] data;
>      foreach (const i; 0 .. 10)
>          data[i] = 0;
>      foreach (immutable i; 0 .. 10)
>          data[i] = 0;
>      int[10] big;
>      foreach (const i, x; big)
>          data[i] = x;
> }
>
>
> But the compiler must recognize this as correct code:
>
>
> void main() {
>      int[5] data;
>      foreach (const i; 0 .. 10)
>          if (i < 5)
>              data[i] = 0;
> }
>
>
> Can this logic be added to D?
>
>
> More info on the topic:
> http://en.wikipedia.org/wiki/Bounds-checking_elimination
> http://ssw.jku.at/Research/Papers/Wuerthinger07/Wuerthinger07.pdf
>
> Bye,
> bearophile

The first two foreach statements assignment statements should be compile errors.
I'm actually a little bit surprised that we don't already test for this.
But I spose that would actually be quite hard.
Perhaps if the foreach statement value is ctfe'able we can compare it upon assignment as a value.

Hmm I wonder if there is any more CTFE'able tricks we can do in the compiler.. to improve error checking.

31-May-2014 14:56, bearophile пишет:
> My opinions about D array bound checks are slowly changing. I still
> think "-boundscheck=off" is useful and good to have. But now I am giving
> increasing importance to compiler logic that optimizes away bound checks
> safely.

Cool, I hope it means you are getting ready to try your hand at implementing it!

> People more and more want a safe system language, more and more
> persons don't disable array bound tests. This means that optimizing away
> bound checks is becoming more and more important in D.

All kind of a non-argument. Who are those people that are not disabling bounds checks in system language ? :)

> And D can't
> ignore this need any more.

Surely it can be safely ignored.
It's just a nice to have feature. Say in 2 years from now it may be closer to the top priority, but there are far, far more important problem to solve. Not that I'm going to discourage anybody working on it.

> Even adding logic to remove 20% of the bound
> checks in numeric code is going to help D because I think more and more
> people will not disable bound checks in D.


-- 
Dmitry Olshansky

Rikki Cattermole:

> The first two foreach statements assignment statements should be compile errors.
> I'm actually a little bit surprised that we don't already test for this.
> But I spose that would actually be quite hard.

I don't know how hard it is. One purpose of this post is to ask how much hard that is.

Bye,
bearophile

On 1/06/2014 12:04 a.m., bearophile wrote:
> Rikki Cattermole:
>
>> The first two foreach statements assignment statements should be
>> compile errors.
>> I'm actually a little bit surprised that we don't already test for this.
>> But I spose that would actually be quite hard.
>
> I don't know how hard it is. One purpose of this post is to ask how much
> hard that is.
>
> Bye,
> bearophile

I know, this is just my thought on it though.

> void main() {
>     int[5] data;
>     foreach (const i; 0 .. 10)
>         data[i] = 0;
>     foreach (immutable i; 0 .. 10)
>         data[i] = 0;
>     int[10] big;
>     foreach (const i, x; big)
>         data[i] = x;
> }

I'm not sure if bound checks should be removed here. Before removal, this code gives safe runtime exception, or, as suggested above, compile-time error. After removal, this code might cause access violation - which, unlike runtime exception, would leave program/kernel in corrupted state.

>
>
> But the compiler must recognize this as correct code:
>
>
> void main() {
>     int[5] data;
>     foreach (const i; 0 .. 10)
>         if (i < 5)
>             data[i] = 0;
> }

My personal opinion is that code like this should remain inefficient, to stimulate programmers to use simpler, easier to understand idioms, like foreach (i; data). If bound checks get removed in this case, that already covers 90% of loops under question. :-)

Wanderer:

>> void main() {
>>    int[5] data;
>>    foreach (const i; 0 .. 10)
>>        data[i] = 0;
>>    foreach (immutable i; 0 .. 10)
>>        data[i] = 0;
>>    int[10] big;
>>    foreach (const i, x; big)
>>        data[i] = x;
>> }
>
> I'm not sure if bound checks should be removed here. Before removal, this code gives safe runtime exception, or, as suggested above, compile-time error.

The compiler should catch all those cases at compile-time :-)


>> But the compiler must recognize this as correct code:
>>
>>
>> void main() {
>>    int[5] data;
>>    foreach (const i; 0 .. 10)
>>        if (i < 5)
>>            data[i] = 0;
>> }
>
> My personal opinion is that code like this should remain inefficient, to stimulate programmers to use simpler, easier to understand idioms, like foreach (i; data).

Java already removes several bound checks but this only increases the array access performance, so it's not easy to see, unless you do benchmarks (or in D compare the run-time with the run-time with disabled array bound tests). So I don't think this compiler improvement is going to worsen the D code you will see around :-)

Bye,
bearophile

> bound tests. This means that optimizing away bound checks is becoming more and more important in D. And D can't ignore this

Expressions like

x[0 .. $/n]

and

x[$/n .. $]

are important in many divide and conquer (recursive) algorithms such as quick-sort and shall not need bounds check simply because

0 <= $/n <= $, when n >=1

I've looked around in DMD for a suitable place to add checks for this but haven't found the spot where range-check is injected. Help anyone?

On 5/31/2014 4:06 PM, "Nordlöw" wrote:
> I've looked around in DMD for a suitable place to add checks for this but
> haven't found the spot where range-check is injected. Help anyone?

There isn't a suitable place. To make it work, data flow analysis would have to be added to the front end. While doable, this is not a simple addition. Eventually, we'll have to do it as a lot of things become possible & better with data flow analysis, not just bounds check elimination.

> as a lot of things become possible & better with data flow analysis, not just bounds check elimination.

Great. Now I know.

Btw:

Could you elaborate a bit on what data flow optimizations mean?

What other kinds of optimizations will become possible?

Is this something that other langs/compilers offer?