www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - __restrict

reply Manu <turkeyman gmail.com> writes:
I sent an email about this once before... but there was no real
response/discussion on the topic.

I just want to emphasise the importance of __restrict in optimising hot
code, and I'm curious to know if there has already been discussion on the
matter? Plans for implementation? Workarounds?
I'd have thought that surely guys like Don would have considered and care
about these details intimately?

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


 I sent an email about this once before... but there was no real
 response/discussion on the topic.


It was discussed a bit in past, and restrict was not appreciated a lot, maybe
also because in D where possible we prefer things that the compiler is able to
verify/enforce.
And I think D/DMD is not yet in a development stage where it cares for max
performance details. I think there are plenty of more important things to work
on before that. The recently almost-fixed "inout" was more urgent than
"__restrict".

Bye,
bearophile
Oct 19 2011
parent reply Manu <turkeyman gmail.com> writes:
I agree, that is certainly more important :)

I'm mainly just curious to know about how the main contributors feel about
these things, and whether these things will be implemented/planned, or if
they violate some fundamental language principles...
Basically, I really want to start some major work in D, but before investing
into the language, I want to know that important features are recognised and
have a long term plan...

I'm curious to know what you mean by "maybe also because in D where possible
we prefer things that the compiler is able to verify/enforce". I'm not sure
how that really applies to __restrict. It's effectively an optimisation hint
to the compiler, giving it explicit instructions... what would there be to
verify or enforce in this case? Is it that it would be preferred if
__restrict-ability could be implied by carefully crafted language rules? I
just don't think that's possible.. But it's still an important keyword.

How difficult is it to contribute to D in these areas? Is that something
that is encouraged, or is D still too embryonic to have random people coming
along and adding things here and there?

On 19 October 2011 12:36, bearophile <bearophileHUGS lycos.com> wrote:


 Manu:


 I sent an email about this once before... but there was no real
 response/discussion on the topic.


 It was discussed a bit in past, and restrict was not appreciated a lot,
 maybe also because in D where possible we prefer things that the compiler is
 able to verify/enforce.
 And I think D/DMD is not yet in a development stage where it cares for max
 performance details. I think there are plenty of more important things to
 work on before that. The recently almost-fixed "inout" was more urgent than
 "__restrict".

 Bye,
 bearophile
Oct 19 2011
next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 19 Oct 2011 07:58:15 -0400, Manu <turkeyman gmail.com> wrote:

 I agree, that is certainly more important :)

 I'm mainly just curious to know about how the main contributors feel about
 these things, and whether these things will be implemented/planned, or if
 they violate some fundamental language principles...
 Basically, I really want to start some major work in D, but before investing
 into the language, I want to know that important features are recognised and
 have a long term plan...


Well, __restrict was mainly added to C (IIRC), to allow loop vectorization. In
D, we have explicit array operations, which carry a lot of the same caveats as
__restrict, except are checkable.


 I'm curious to know what you mean by "maybe also because in D where possible
 we prefer things that the compiler is able to verify/enforce". I'm not sure
 how that really applies to __restrict. It's effectively an optimisation hint
 to the compiler, giving it explicit instructions... what would there be to
 verify or enforce in this case?


That's the point, the compiler can't verify or enforce the assumptions of
__restrict. Think of array indexing in C. The compiler has no way of verifying
or enforcing that ptr[10_000] is a valid memory location. And this has lead to
undefined behavior and a large number of security exploits. In D, the arrays
always carry around their lengths, so indexes can be checked. No more undefined
behavior and less exploits. Similarly, C's const provides no actual guarantees.
But compilers used it to optimize code anyways, which has lead many a
programmer to long hours debugging.


 Is it that it would be preferred if
 __restrict-ability could be implied by carefully crafted language rules?


Yes, and it is for array operations.


 I
 just don't think that's possible.. But it's still an important keyword.

 How difficult is it to contribute to D in these areas? Is that something
 that is encouraged, or is D still too embryonic to have random people coming
 along and adding things here and there?


It's very easy to contribute. The source code for DMD, LDC, GDC is all
available and patches are regularly submitted and accepted. Check out D's
github repositories and the mailing lists for more.


 On 19 October 2011 12:36, bearophile <bearophileHUGS lycos.com> wrote:


 Manu:


 I sent an email about this once before... but there was no real
 response/discussion on the topic.


 It was discussed a bit in past, and restrict was not appreciated a lot,
 maybe also because in D where possible we prefer things that the compiler is
 able to verify/enforce.
 And I think D/DMD is not yet in a development stage where it cares for max
 performance details. I think there are plenty of more important things to
 work on before that. The recently almost-fixed "inout" was more urgent than
 "__restrict".

 Bye,
 bearophile
Oct 19 2011
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 19/10/11 3:08 PM, Robert Jacques wrote:

 On Wed, 19 Oct 2011 07:58:15 -0400, Manu <turkeyman gmail.com> wrote:

 I agree, that is certainly more important :)

 I'm mainly just curious to know about how the main contributors feel
 about
 these things, and whether these things will be implemented/planned, or if
 they violate some fundamental language principles...
 Basically, I really want to start some major work in D, but before
 investing
 into the language, I want to know that important features are
 recognised and
 have a long term plan...


 Well, __restrict was mainly added to C (IIRC), to allow loop
 vectorization. In D, we have explicit array operations, which carry a
 lot of the same caveats as __restrict, except are checkable.


It's for far more than vectorization. Any place that has redundant loads 
can benefit from __restrict.

I recommend this presentation on the subject: 
http://www.slideshare.net/guest3eed30/memory-optimization

It's about memory optimizations. Aliasing issues start at slide 35.
Oct 19 2011
parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 19 Oct 2011 17:10:55 -0400, Peter Alexander
<peter.alexander.au gmail.com> wrote:


 On 19/10/11 3:08 PM, Robert Jacques wrote:

 On Wed, 19 Oct 2011 07:58:15 -0400, Manu <turkeyman gmail.com> wrote:

 I agree, that is certainly more important :)

 I'm mainly just curious to know about how the main contributors feel
 about
 these things, and whether these things will be implemented/planned, or if
 they violate some fundamental language principles...
 Basically, I really want to start some major work in D, but before
 investing
 into the language, I want to know that important features are
 recognised and
 have a long term plan...


 Well, __restrict was mainly added to C (IIRC), to allow loop
 vectorization. In D, we have explicit array operations, which carry a
 lot of the same caveats as __restrict, except are checkable.


 It's for far more than vectorization. Any place that has redundant loads
 can benefit from __restrict.

 I recommend this presentation on the subject:
 http://www.slideshare.net/guest3eed30/memory-optimization

 It's about memory optimizations. Aliasing issues start at slide 35.


Thanks. I've seen most of that before. And even in those slide, the major
(though not only) use-case for __restrict is with array and matrix processing.
Most other use-cases can be cached manually or are really, really unsafe.
Oct 19 2011
parent reply Manu <turkeyman gmail.com> writes:
Caching results manually is very tedious work, and makes a mess of your
code.. If you've had to do that yourself you'd understand how annoying it
can be.
Placing restrict on sensible pointers is much cleaner and saves a lot of
time, and also results in optimisation everywhere it is used, rather than
just the 1-2 places that you happened to notice it was a problem...

On 20 October 2011 05:25, Robert Jacques <sandford jhu.edu> wrote:


 On Wed, 19 Oct 2011 17:10:55 -0400, Peter Alexander <
 peter.alexander.au gmail.com> wrote:

  On 19/10/11 3:08 PM, Robert Jacques wrote:

 On Wed, 19 Oct 2011 07:58:15 -0400, Manu <turkeyman gmail.com> wrote:


 I agree, that is certainly more important :)

 I'm mainly just curious to know about how the main contributors feel
 about
 these things, and whether these things will be implemented/planned, or
 if
 they violate some fundamental language principles...
 Basically, I really want to start some major work in D, but before
 investing
 into the language, I want to know that important features are
 recognised and
 have a long term plan...


 Well, __restrict was mainly added to C (IIRC), to allow loop
 vectorization. In D, we have explicit array operations, which carry a
 lot of the same caveats as __restrict, except are checkable.


 It's for far more than vectorization. Any place that has redundant loads
 can benefit from __restrict.

 I recommend this presentation on the subject:
 http://www.slideshare.net/**guest3eed30/memory-**optimization<http://www.slideshare.net/guest3eed30/memory-optimization>

 It's about memory optimizations. Aliasing issues start at slide 35.


 Thanks. I've seen most of that before. And even in those slide, the major
 (though not only) use-case for __restrict is with array and matrix
 processing. Most other use-cases can be cached manually or are really,
 really unsafe.
Oct 20 2011
parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Thu, 20 Oct 2011 07:37:22 -0400, Manu <turkeyman gmail.com> wrote:

 Caching results manually is very tedious work, and makes a mess of your
 code.. If you've had to do that yourself you'd understand how annoying it
 can be.


I do do it all the time and I've never found it that tedious. Especially
compared to all the loop invariant divisions, expressions, function calls, etc
you have to excise from the loop anyways... I mean, L1 cache has a latency of ~
1 cycle, division is ~50-150 cycles.


 Placing restrict on sensible pointers is much cleaner and saves a lot of
 time, and also results in optimisation everywhere it is used, rather than
 just the 1-2 places that you happened to notice it was a problem...


Except that you should only use __restrict where you notice a problem. In case
you didn't know, C++ compilers do (did?) all the __restrict optimizations for
const variables. And the systematic use of const on these compilers is a well
known source of Heisen-bugs. I haven't heard that this 'feature' has been
disabled, but its been a while since I checked.
Oct 20 2011
parent reply Manu <turkeyman gmail.com> writes:
Naturally, as with all my posts, I'm not referring to x86 :)
L1 is rarely ~1 cycle access, there are even a few architectures that can't
write to L1 at all, and I've never come in contact with a compiler that can
do anything useful with the const keyword in C. That said __restrict is
fundamentally different than const, const suggests I can't change the
memory pointed at, when that is often exactly what I intend to do.

It seems to be very hard to convince people who have never had to work on
these platforms that it's really important :/

On 21 October 2011 06:49, Robert Jacques <sandford jhu.edu> wrote:


 On Thu, 20 Oct 2011 07:37:22 -0400, Manu <turkeyman gmail.com> wrote:


 Caching results manually is very tedious work, and makes a mess of your
 code.. If you've had to do that yourself you'd understand how annoying it
 can be.


 I do do it all the time and I've never found it that tedious. Especially
 compared to all the loop invariant divisions, expressions, function calls,
 etc you have to excise from the loop anyways... I mean, L1 cache has a
 latency of ~ 1 cycle, division is ~50-150 cycles.


  Placing restrict on sensible pointers is much cleaner and saves a lot of

 time, and also results in optimisation everywhere it is used, rather than
 just the 1-2 places that you happened to notice it was a problem...


 Except that you should only use __restrict where you notice a problem. In
 case you didn't know, C++ compilers do (did?) all the __restrict
 optimizations for const variables. And the systematic use of const on these
 compilers is a well known source of Heisen-bugs. I haven't heard that this
 'feature' has been disabled, but its been a while since I checked.
Oct 20 2011
parent "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 21 Oct 2011 02:19:03 -0400, Manu <turkeyman gmail.com> wrote:

 Naturally, as with all my posts, I'm not referring to x86 :)


Naturally, stating that upfront would drastically improve our understanding and
weighting of your arguments. :)


 L1 is rarely ~1 cycle access, there are even a few architectures that can't
 write to L1 at all,


And I work on GPU, so I can understand that pain. Then again, I'm so much more
conscious of my code in those situations. For example, the following are not
all created equal:

for(uint i = 0;        i <  length; i++)
for( int i = 0;        i <  length; i++)
for(uint i = length-1; i >= 0;      i--)
for( int i = length-1; i >= 0;      i--)


 and I've never come in contact with a compiler that can
 do anything useful with the const keyword in C. That said __restrict is
 fundamentally different than const, const suggests I can't change the
 memory pointed at, when that is often exactly what I intend to do.


My point, was that there are C++ compilers that do do things (not) useful with
const, that are in principal the exact same things that would happen to a
__restrict object. And it caused lots of hard to find bugs. So I feel safe in
saying that usage of __restrict should never be wide spread. It should only be
used in well understood and controlled code hot spots.


 It seems to be very hard to convince people who have never had to work on
 these platforms that it's really important :/


One of the best ways to do that it to prove it with numbers, with real code
that a consciousness embedded developer could be expected to write.
Oct 21 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Manu:


 what would there be to verify or enforce in this case?


There are type system features like memory zones, linear types, uniqueness
typing, and so on, that are able to enforce similar invariants. D lacks those
type system features, so it can't enforce that a restricted pointer is actually
unique. D Zen seems to not appreciate annotations that can't be enforced (this
is not a hard rule). This is one of the possible explanations for the lack of
 restrict.



 How difficult is it to contribute to D in these areas?


There are contributors that write more than one compiler patch (pull requests
in GitHut) every week, and they often get merged in the main compiler,
especially when they are good, and their need is "obvious" or it was already
discussed in the D newsgroups and accepted. It's not easy to write good
compiler patches, but it's clearly doable if you are good.



 Is that something
 that is encouraged, or is D still too embryonic to have random people coming
 along and adding things here and there?


There are a large number of open bugs in Bugzilla, front-end bugs too, so
creating pull requests/patches that fix them is encouraged. Even some small
enhancement requests, when they are clearly good and they are backwards
compatible, are often accepted. Breaking changes are less easily accepted, they
probably require a precedent discussion in D newsgroups. Regarding significant
enhancement pull requests (like adding a  restrict, or like this one:
https://github.com/D-Programming-Language/dmd/pull/3  that is sleeping there
for a lot of time), they need discussion first, and are accepted slowly, and
not surely.

Bye,
bearophile
Oct 19 2011
prev sibling parent Don <nospam nospam.com> writes:
On 19.10.2011 10:41, Manu wrote:

 I sent an email about this once before... but there was no real
 response/discussion on the topic.

 I just want to emphasise the importance of __restrict in optimising hot
 code, and I'm curious to know if there has already been discussion on
 the matter? Plans for implementation? Workarounds?
 I'd have thought that surely guys like Don would have considered and
 care about these details intimately?

 - Manu


In addition to what others have said, __restrict is not very low-hanging 
fruit for D.

The main reason for this is that D's arrays always know their length.
(Somebody mentioned array operations, but I don't think they are 
terribly important for __restrict; rather, it's the fact that arrays 
retain their length information).
Many operations which would be done with pointers in C, are done with 
arrays in D, and it's very easy to check for aliasing of arrays. 
Pointers aren't even allowed in  safe code.

A secondary reason is that D has immutable. Unlike C++'s const, this 
*can* be used for optimisation. And we also have the guarantee that 
memory is not shared between threads.

In view of this, it's not at all clear to me that the C __restrict 
concept is immediately applicable to D without modification.

Thus:
(1) __restrict is more important (has wider applicability) in C than in D;
(2) some very important array and immutable optimisations haven't been 
done yet; it is believed that they will have a far bigger impact than 
__restrict.

So __restrict is a low priority at this stage.
Oct 23 2011