www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - AliasSeq seems to compile slightly faster with static foreach

reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
There was a recent PR for Phobos where Seb added static to a bunch of
foreach's that used AliasSeq. It hadn't actually occurred to me that that
was legal (I've basically just been using static foreach where foreach with
AliasSeq doesn't work), but it is legal (which I suppose isn't surprising
when you think about it; I just hadn't). However, that got me to wondering
if such a change was purely aesthetic or whether it might actually have an
impact on build times - particularly since running dub test for one of my
recent projects keeps taking longer and longer. So, I added static to a
bunch of foreach's over AliasSeqs in that project to see if it would have
any effect. The result was that dub test went from about 16.5 seconds on my
system to about 15.8 seconds - and that's just by adding static to the
foreach's over AliasSeqs, not fundamentally changing what any of the code
did. That's not a huge speed up, but it's definitely something and far more
than I was expecting.

Of course, you have to be careful with such a change, because static foreach
doesn't introduce a new scope, and double braces are potentially required
where they weren't before, but given that I'd very much like to streamline
that test build, adding static to those foreach's was surprisingly
worthwhile.

Taking it a step further, I tried switching some of the static foreach's
over to using array literals, since they held values rather than types, and
that seemed to have minimal impact on the time to run dub test. However, by
switching to using std.range.only, it suddenly was taking more like 11.8
seconds. So, with a few small changes, I cut the time to run dub test down
by almost a third.

- Jonathan M Davis
Jan 05
next sibling parent reply Meta <jared771 gmail.com> writes:
On Friday, 5 January 2018 at 13:10:25 UTC, Jonathan M Davis wrote:
 There was a recent PR for Phobos where Seb added static to a 
 bunch of foreach's that used AliasSeq. It hadn't actually 
 occurred to me that that was legal (I've basically just been 
 using static foreach where foreach with AliasSeq doesn't work), 
 but it is legal (which I suppose isn't surprising when you 
 think about it; I just hadn't). However, that got me to 
 wondering if such a change was purely aesthetic or whether it 
 might actually have an impact on build times - particularly 
 since running dub test for one of my recent projects keeps 
 taking longer and longer. So, I added static to a bunch of 
 foreach's over AliasSeqs in that project to see if it would 
 have any effect. The result was that dub test went from about 
 16.5 seconds on my system to about 15.8 seconds - and that's 
 just by adding static to the foreach's over AliasSeqs, not 
 fundamentally changing what any of the code did. That's not a 
 huge speed up, but it's definitely something and far more than 
 I was expecting.

 Of course, you have to be careful with such a change, because 
 static foreach doesn't introduce a new scope, and double braces 
 are potentially required where they weren't before, but given 
 that I'd very much like to streamline that test build, adding 
 static to those foreach's was surprisingly worthwhile.

 Taking it a step further, I tried switching some of the static 
 foreach's over to using array literals, since they held values 
 rather than types, and that seemed to have minimal impact on 
 the time to run dub test. However, by switching to using 
 std.range.only, it suddenly was taking more like 11.8 seconds. 
 So, with a few small changes, I cut the time to run dub test 
 down by almost a third.

 - Jonathan M Davis
It does not make any sense to me as to why using only instead of AliasSeq resulted in a speedup. I would've expected no change or worse performance. Any theories?
Jan 05
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Friday, January 05, 2018 13:16:52 Meta via Digitalmars-d wrote:
 On Friday, 5 January 2018 at 13:10:25 UTC, Jonathan M Davis wrote:
 There was a recent PR for Phobos where Seb added static to a
 bunch of foreach's that used AliasSeq. It hadn't actually
 occurred to me that that was legal (I've basically just been
 using static foreach where foreach with AliasSeq doesn't work),
 but it is legal (which I suppose isn't surprising when you
 think about it; I just hadn't). However, that got me to
 wondering if such a change was purely aesthetic or whether it
 might actually have an impact on build times - particularly
 since running dub test for one of my recent projects keeps
 taking longer and longer. So, I added static to a bunch of
 foreach's over AliasSeqs in that project to see if it would
 have any effect. The result was that dub test went from about
 16.5 seconds on my system to about 15.8 seconds - and that's
 just by adding static to the foreach's over AliasSeqs, not
 fundamentally changing what any of the code did. That's not a
 huge speed up, but it's definitely something and far more than
 I was expecting.

 Of course, you have to be careful with such a change, because
 static foreach doesn't introduce a new scope, and double braces
 are potentially required where they weren't before, but given
 that I'd very much like to streamline that test build, adding
 static to those foreach's was surprisingly worthwhile.

 Taking it a step further, I tried switching some of the static
 foreach's over to using array literals, since they held values
 rather than types, and that seemed to have minimal impact on
 the time to run dub test. However, by switching to using
 std.range.only, it suddenly was taking more like 11.8 seconds.
 So, with a few small changes, I cut the time to run dub test
 down by almost a third.

 - Jonathan M Davis
It does not make any sense to me as to why using only instead of AliasSeq resulted in a speedup. I would've expected no change or worse performance. Any theories?
I don't know. It's probably related to however foreach over an AliasSeq is implemented. The fact that only is faster than using an array literal doesn't surprise me though, since CTFE probably does a bunch of extra, unnecessary allocation when dealing with array literal. Maybe the speed difference between AliasSeq and only is a sign of something that could be improved in the compiler's implementation, or maybe only is just fundamentally faster for one reason or another. I don't know. But from what I can tell, the speed difference is large enough that it's kind of crazy to use AliasSeq with values when static foreach and only will work just as well. - Jonathan M Davis
Jan 05
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05.01.2018 14:10, Jonathan M Davis wrote:
 Taking it a step further, I tried switching some of the static foreach's
 over to using array literals, since they held values rather than types, and
 that seemed to have minimal impact on the time to run dub test. However, by
 switching to using std.range.only, it suddenly was taking more like 11.8
 seconds. So, with a few small changes, I cut the time to run dub test down
 by almost a third.
This is weird, as the compiler will apply the following rewrites: static foreach(i;only(0,1,2,3,4)){} => static foreach(i;{ int[] r=[]; foreach(i;only(0,1,2,3,4)){ r~=i; } return r; }()){} => // (using CTFE) static foreach(i;[0,1,2,3,4]){} => // (uses shortcut; not instantiating the AliasSeq template) static foreach(i;AliasSeq!(0,1,2,3,4)){}
Jan 07
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Sunday, January 07, 2018 09:59:30 Timon Gehr via Digitalmars-d wrote:
 On 05.01.2018 14:10, Jonathan M Davis wrote:
 Taking it a step further, I tried switching some of the static foreach's
 over to using array literals, since they held values rather than types,
 and that seemed to have minimal impact on the time to run dub test.
 However, by switching to using std.range.only, it suddenly was taking
 more like 11.8 seconds. So, with a few small changes, I cut the time to
 run dub test down by almost a third.
This is weird, as the compiler will apply the following rewrites: static foreach(i;only(0,1,2,3,4)){} => static foreach(i;{ int[] r=[]; foreach(i;only(0,1,2,3,4)){ r~=i; } return r; }()){} => // (using CTFE) static foreach(i;[0,1,2,3,4]){} => // (uses shortcut; not instantiating the AliasSeq template) static foreach(i;AliasSeq!(0,1,2,3,4)){}
I don't know. Looking at only's implementation, it uses a static array internally, not a dynamic one, so I would not have expected the lowering that you describe, but I don't know enough about the details of how the compiler works to know what it would really do - especially during CTFE - and I'd expect you to know far more about that than I would. Either way, with my project at least, with the unit tests that I was generating using foreach or static foreach, using static foreach with AliasSeq was slightly faster than using normal foreach, using array literals with static foreach was about the same as using AliasSeq with static foreach, and using only with static foreach was way faster than either - enough so that by switching all of my non-static foreach's over AliasSeqs of values to only (or lockstep with iota and only where I needed indices) resulted in dub test taking a bit over half as long as it did before. Now, I had a lot of unit tests using foreach with AliasSeqs of values, which is why the impact was so great in my case, but anecdotally, it implies that the compiler treats a static foreach over a std.range.only quite differently from one over an array literal or AliasSeq. - Jonathan M Davis
Jan 07