www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - __restrict

reply Manu <turkeyman gmail.com> writes:
--0016368324ec8d6dee04afa2cebc
Content-Type: text/plain; charset=UTF-8

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

--0016368324ec8d6dee04afa2cebc
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

I sent an email about this once before... but there was no real response/di=
scussion on the topic.<div><br></div><div>I just want to emphasise the impo=
rtance of __restrict in optimising hot code, and I&#39;m curious to know if=
 there has already been discussion on the matter? Plans for implementation?=
 Workarounds?</div>
<div>I&#39;d have thought that surely guys like Don would have considered a=
nd care about these details intimately?</div><div><br></div><div>- Manu</di=
v>

--0016368324ec8d6dee04afa2cebc--
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 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
prev sibling next sibling parent reply Manu <turkeyman gmail.com> writes:
--0016364ed99e1c9a3404afa58e7a
Content-Type: text/plain; charset=UTF-8

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

--0016364ed99e1c9a3404afa58e7a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div>I agree, that is certainly more important :)</div><div><br></div><div>= I&#39;m mainly just curious to know about how the main contributors feel ab= out these things,=C2=A0and whether these things will be implemented/planned= , or if they violate some fundamental language principles...</div> <div>Basically, I really want to start some major work in D, but before inv= esting into the language, I want to know that important features are recogn= ised and have a long term plan...</div><div><br></div><div>I&#39;m curious = to know what you mean by &quot;<span class=3D"Apple-style-span" style=3D"fo= nt-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 2= 55, 255); ">maybe also because in D where possible we prefer things that th= e compiler is able to verify/enforce&quot;. I&#39;m not sure how that reall= y applies to __restrict. It&#39;s effectively an optimisation hint to the c= ompiler, giving it explicit instructions... what would there be to verify o= r enforce in this case? Is it that it would be preferred if __restrict-abil= ity could be implied by carefully crafted language rules? I just don&#39;t = think that&#39;s possible.. But it&#39;s still an important keyword.</span>= </div> <div><br></div><div>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 r= andom people coming along and adding things here and there?</div><div><br> </div><div class=3D"gmail_quote">On 19 October 2011 12:36, bearophile <span= dir=3D"ltr">&lt;<a href=3D"mailto:bearophileHUGS lycos.com">bearophileHUGS= lycos.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> Manu:<br> <div class=3D"im"><br> &gt; I sent an email about this once before... but there was no real<br> &gt; response/discussion on the topic.<br> <br> </div>It was discussed a bit in past, and restrict was not appreciated a lo= t, maybe also because in D where possible we prefer things that the compile= r is able to verify/enforce.<br> 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 w= ork on before that. The recently almost-fixed &quot;inout&quot; was more ur= gent than &quot;__restrict&quot;.<br> <br> Bye,<br> <font color=3D"#888888">bearophile<br> </font></blockquote></div><br> --0016364ed99e1c9a3404afa58e7a--
Oct 19 2011
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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent Manu <turkeyman gmail.com> writes:
--0016e648adca46723d04afb96154
Content-Type: text/plain; charset=UTF-8

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.

(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.

--0016e648adca46723d04afb96154 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Caching results manually is very tedious work, and makes a mess of your cod= e.. If you&#39;ve had to do that yourself you&#39;d understand how annoying= it can be.<div>Placing restrict on sensible pointers is much cleaner and s= aves 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 probl= em...<br> <br><div class=3D"gmail_quote">On 20 October 2011 05:25, Robert Jacques <sp= an dir=3D"ltr">&lt;<a href=3D"mailto:sandford jhu.edu">sandford jhu.edu</a>= &gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0= 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div><div></div><div class=3D"h5">On Wed, 19 Oct 2011 17:10:55 -0400, Peter= Alexander &lt;<a href=3D"mailto:peter.alexander.au gmail.com" target=3D"_b= lank">peter.alexander.au gmail.com</a>&gt; wrote:<br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> On 19/10/11 3:08 PM, Robert Jacques wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> On Wed, 19 Oct 2011 07:58:15 -0400, Manu &lt;<a href=3D"mailto:turkeyman gm= ail.com" target=3D"_blank">turkeyman gmail.com</a>&gt; wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> I agree, that is certainly more important :)<br> <br> I&#39;m mainly just curious to know about how the main contributors feel<br=

these things, and whether these things will be implemented/planned, or if<b= r> they violate some fundamental language principles...<br> Basically, I really want to start some major work in D, but before<br> investing<br> into the language, I want to know that important features are<br> recognised and<br> have a long term plan...<br> </blockquote> <br> Well, __restrict was mainly added to C (IIRC), to allow loop<br> vectorization. In D, we have explicit array operations, which carry a<br> lot of the same caveats as __restrict, except are checkable.<br> </blockquote> <br> It&#39;s for far more than vectorization. Any place that has redundant load= s<br> can benefit from __restrict.<br> <br> I recommend this presentation on the subject:<br> <a href=3D"http://www.slideshare.net/guest3eed30/memory-optimization" targe= t=3D"_blank">http://www.slideshare.net/<u></u>guest3eed30/memory-<u></u>opt= imization</a><br> <br> It&#39;s about memory optimizations. Aliasing issues start at slide 35.<br> <br> </blockquote> <br></div></div> Thanks. I&#39;ve seen most of that before. And even in those slide, the maj= or (though not only) use-case for __restrict is with array and matrix proce= ssing. Most other use-cases can be cached manually or are really, really un= safe.<br> </blockquote></div><br></div> --0016e648adca46723d04afb96154--
Oct 20 2011
prev sibling next sibling parent "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
prev sibling next sibling parent Manu <turkeyman gmail.com> writes:
--0016364ee67abdcabf04afc90c22
Content-Type: text/plain; charset=UTF-8

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.

--0016364ee67abdcabf04afc90c22 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Naturally, as with all my posts, I&#39;m not referring to x86 :)<div>L1 is = rarely ~1 cycle access, there are even a few architectures that can&#39;t w= rite to L1 at all, and I&#39;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&#39;t change the = memory pointed at, when that is often exactly what I intend to do.</div> <div><br></div><div>It seems to be very hard to convince people who have ne= ver had to work on these platforms that it&#39;s really important :/</div><= div><br></div><div><div class=3D"gmail_quote">On 21 October 2011 06:49, Rob= ert Jacques <span dir=3D"ltr">&lt;<a href=3D"mailto:sandford jhu.edu">sandf= ord jhu.edu</a>&gt;</span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex;"><div class=3D"im">On Thu, 20 Oct 2011 07:37= :22 -0400, Manu &lt;<a href=3D"mailto:turkeyman gmail.com" target=3D"_blank= ">turkeyman gmail.com</a>&gt; wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> Caching results manually is very tedious work, and makes a mess of your<br> code.. If you&#39;ve had to do that yourself you&#39;d understand how annoy= ing it<br> can be.<br> </blockquote> <br></div> I do do it all the time and I&#39;ve never found it that tedious. Especiall= y 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 la= tency of ~ 1 cycle, division is ~50-150 cycles.<div class=3D"im"> <br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> Placing restrict on sensible pointers is much cleaner and saves a lot of<br=

r> just the 1-2 places that you happened to notice it was a problem...<br> </blockquote> <br></div> Except that you should only use __restrict where you notice a problem. In c= ase you didn&#39;t know, C++ compilers do (did?) all the __restrict optimiz= ations for const variables. And the systematic use of const on these compil= ers is a well known source of Heisen-bugs. I haven&#39;t heard that this &#= 39;feature&#39; has been disabled, but its been a while since I checked.<br=

</blockquote></div><br></div> --0016364ee67abdcabf04afc90c22--
Oct 20 2011
prev sibling next sibling 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 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