www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Performance penalty for using ranges

reply "Paul Jurczak" <pauljurczak yahoo.com> writes:
I wrote a few versions of a palindrome testing function and 
noticed that versions using ranges (isPalindrome1..isPalindrome3) 
are 3 times slower than array indexing one (isPalindrome0). Is 
there a more efficient way of using ranges? Timing was done on 
Windows with DMD 2.063.2 (32-bit) dmd -O -noboundscheck -inline 
-release.

// 6.9ms
bool isPalindrome0(T)(T[] s) {
    auto i = 0;
    for (; i < s.length/2 && s[i] == s[$-i-1]; ++i) {}
    return i == s.length/2;
}

// 21ms
bool isPalindrome1(T)(T[] s) {
    while (s.length > 1 && s.front == s.back) {
       s.popBack();
       s.popFront();
    }

    return s.length <= 1;
}

// 21ms
bool isPalindrome2(T)(T[] s) {
    for (; s.length > 1 && s.front == s.back; s.popBack(), 
s.popFront()) {}
    return s.length <= 1;
}

// 21.4ms
bool isPalindrome3(T)(T s) {
    foreach (i; 0..s.length/2)
       if (s[i] != s[$-i-1])
          return false;

    return true;
}


int test() {
    int a[10];
    int n = 0;

    foreach (i; 0..1_000_000) {
       a[4] = !a[4];
       n += isPalindrome0(a);
    }

    return n;
}


void main()
{
    enum N = 16;
    auto t = benchmark!(test)(N);

    writeln(cast(float)t[0].msecs/N);
    writeln(test);
}
Aug 25 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Paul Jurczak:


 I wrote a few versions of a palindrome testing function and 
 noticed that versions using ranges 
 (isPalindrome1..isPalindrome3) are 3 times slower than array 
 indexing one (isPalindrome0). Is there a more efficient way of 
 using ranges?


I have modified and improved and fixed your code a little:


import std.stdio, std.datetime, std.array, std.typetuple,
        std.range, std.algorithm;

bool isPalindrome0(T)(in T[] s) pure nothrow {
     size_t i = 0;
     for (; i < s.length / 2 && s[i] == s[$ - i - 1]; ++i) {}
     return i == s.length / 2;
}

bool isPalindrome1(T)(T[] s) pure nothrow {
     while (s.length > 1 && s.front == s.back) {
         s.popBack;
         s.popFront;
     }

     return s.length <= 1;
}

bool isPalindrome2(T)(T[] s) pure nothrow {
     for (;
          s.length > 1 && s.front == s.back;
          s.popBack, s.popFront) {}
     return s.length <= 1;
}

bool isPalindrome3(T)(in T[] s) pure nothrow {
     foreach (immutable i; 0 .. s.length / 2)
         if (s[i] != s[$ - i - 1])
             return false;
     return true;
}

/// A high-level version.
bool isPalindrome4(T)(in T[] s) /*pure nothrow*/ {
     return s.retro.equal(s);
}

int test(alias F)(in int nLoops) /*pure nothrow*/ {
     int[10] a;
     typeof(return) n = 0;

     foreach (immutable _; 0 .. nLoops) {
         a[4] = !a[4];
         n += F(a);
     }

     return n;
}

void main() {
     enum size_t nLoops = 60_000_000;
     StopWatch sw;

     foreach (alg; TypeTuple!(isPalindrome0, isPalindrome1,
                              isPalindrome2, isPalindrome3,
                              isPalindrome4)) {
         sw.reset;
         sw.start;
         immutable n = test!alg(nLoops);
         sw.stop;
         writeln(n, " ", sw.peek.msecs);
     }
}


Using a compiler with a better optimizing back-end (especially 
with a better inlining), the timings show that the faster 
versions are the second and third, but all of them have a very 
similar performance (the last one reads the whole array twice, so 
it's a little slower, as expected):


...>ldmd2 -O -release -inline -noboundscheck -run test2.d
30000000 1150
30000000 1073
30000000 1038
30000000 1215
30000000 1621


Someday a function like isPalindrome4 will be pure & nothrow.

Bye,
bearophile
Aug 25 2013
parent reply "Paul Jurczak" <pauljurczak yahoo.com> writes:
On Sunday, 25 August 2013 at 14:54:04 UTC, bearophile wrote:

 I have modified and improved and fixed your code a little:


[..]
Thank you for your analysis. I've run it on Linux with DMD64 
2.063.2: dmd -O -noboundscheck -inline -release and relative 
timings are different than on Windows:

500000 7160
500000 18588
500000 18592
500000 14466
500000 28368

I'm also running it with LDC, but it reports timings too good to 
be true - something meaningful is getting optimized away and I'm 
trying to find out why. I have a few newbie questions below:


 int test(alias F)(in int nLoops) /*pure nothrow*/ {
     int[10] a;
     typeof(return) n = 0;

     foreach (immutable _; 0 .. nLoops) {
         a[4] = !a[4];
         n += F(a);
     }

     return n;
 }


What is the purpose of "immutable _;" above? Why not "i;"?


 void main() {
     enum size_t nLoops = 60_000_000;
     StopWatch sw;

     foreach (alg; TypeTuple!(isPalindrome0, isPalindrome1,
                              isPalindrome2, isPalindrome3,
                              isPalindrome4)) {
         sw.reset;
         sw.start;
         immutable n = test!alg(nLoops);
         sw.stop;
         writeln(n, " ", sw.peek.msecs);
     }
 }


Same question here: why immutable?

I wanted to get more stable run-to-run results, so I'm looking 
for minimums:

void main()
{
    enum      N = 100;
    enum      M = 1_000_000;
    StopWatch sw;

    foreach (alg; TypeTuple!(isPalindrome0, isPalindrome1, 
isPalindrome2,
	                          isPalindrome3, isPalindrome4)) {
       int [N] results;
       long[N] timings;

       foreach (i; 0..N) {
          sw.reset;
          sw.start;
          results[i] = test!alg(M);
          sw.stop;
          timings[i] = sw.peek.usecs;
       }

       writeln(results.reduce!min, "  ", timings.reduce!min);
    }
}
Aug 25 2013
next sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 25/08/13 20:07, Paul Jurczak wrote:

 What is the purpose of "immutable _;" above? Why not "i;"?


It's never used, so notating it like this means you'll never clash with another 
variable name by accident (e.g. if somewhere else in the function you declare
an 
int i).

Had never thought of that before but it's a handy trick, I'll have to make use 
of it in my own code ...
Aug 25 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 25 August 2013 at 18:13:39 UTC, Joseph Rushton 
Wakeling wrote:

 On 25/08/13 20:07, Paul Jurczak wrote:

 What is the purpose of "immutable _;" above? Why not "i;"?


 It's never used, so notating it like this means you'll never 
 clash with another variable name by accident (e.g. if somewhere 
 else in the function you declare an int i).

 Had never thought of that before but it's a handy trick, I'll 
 have to make use of it in my own code ...


It never clashes untill you nest two foreach, and then you have 
to use __ ...

foreach( _ ; 0 .. M)
     foreach( __ ; 0 .. N)
         ...

I have an enhancement request to simply allow anonymous iteration:
foreach( ; 0 .. N)

http://d.puremagic.com/issues/show_bug.cgi?id=9009
Aug 25 2013
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 25/08/13 21:10, monarch_dodra wrote:

 It never clashes untill you nest two foreach, and then you have to use __ ...

 foreach( _ ; 0 .. M)
      foreach( __ ; 0 .. N)
          ...

 I have an enhancement request to simply allow anonymous iteration:
 foreach( ; 0 .. N)

 http://d.puremagic.com/issues/show_bug.cgi?id=9009


Good call. :-)
Aug 25 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/25/13 12:46 PM, Joseph Rushton Wakeling wrote:

 On 25/08/13 21:10, monarch_dodra wrote:

 It never clashes untill you nest two foreach, and then you have to use
 __ ...

 foreach( _ ; 0 .. M)
      foreach( __ ; 0 .. N)
          ...

 I have an enhancement request to simply allow anonymous iteration:
 foreach( ; 0 .. N)

 http://d.puremagic.com/issues/show_bug.cgi?id=9009


 Good call. :-)


I don't see why the excitement around anonymous bindings. It's a rare 
case and it's not like we're running out of symbols, particularly given 
they're by definition written only once :o).

Andrei
Aug 25 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 I don't see why the excitement around anonymous bindings. It's 
 a rare case and it's not like we're running out of symbols, 
 particularly given they're by definition written only once :o).


It's not a rare case, I can test this searching in my code for 
"foreach (_;".

And while not essential, anonymous loops are useful because 
adding an useless variable to your code increases its complexity 
a little without giving something back. It's just like adding an 
useless variable inside one of your functions. In C/C++ I look 
for the "unused variable" warnings (a warning that is currently 
missing in D).

When you define a function, and you don't want to use its second 
argument, D allows you to not give it a name, despite you are not 
running out of symbols:

void foo(int x, int) {}

When I see code with a loop with a variable, to understand the 
loop I first of all search how such variable is used inside the 
loop. If the loop variable is anonymous this tells me something 
important about the loop, and reduces the noise.

Bye,
bearophile
Aug 25 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
 It's not a rare case, I can test this searching in my code for 
 "foreach (_;".


Beside my code, if you want I can show 16 URLs to use cases of 
"anonymous iteration" in D code.

Bye,
bearophile
Aug 25 2013
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 25/08/13 23:17, Andrei Alexandrescu wrote:

 I don't see why the excitement around anonymous bindings. It's a rare case and
 it's not like we're running out of symbols, particularly given they're by
 definition written only once :o).


Every little helps. :-)

(Don't know if you get the cultural reference on that, it probably helps to be 
British...:-)
Aug 25 2013
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 25 August 2013 at 21:17:43 UTC, Andrei Alexandrescu 
wrote:

 On 8/25/13 12:46 PM, Joseph Rushton Wakeling wrote:

 On 25/08/13 21:10, monarch_dodra wrote:

 It never clashes untill you nest two foreach, and then you 
 have to use
 __ ...

 foreach( _ ; 0 .. M)
     foreach( __ ; 0 .. N)
         ...

 I have an enhancement request to simply allow anonymous 
 iteration:
 foreach( ; 0 .. N)

 http://d.puremagic.com/issues/show_bug.cgi?id=9009


 Good call. :-)


 I don't see why the excitement around anonymous bindings. It's 
 a rare case and it's not like we're running out of symbols, 
 particularly given they're by definition written only once :o).

 Andrei


I think "the excitement" is an overstatement. The subject comes 
up every now and then. The "foreach(_)" semantic is getting a bit 
more common, but it tends to confuse newbies, that ask about it. 
At that point, I simply point out that there is this ER, and 
people tend to agree it would be a nice addition.

I agree it's not like its a real problem or anything, but it 
would be nice to have. Is all.
Aug 26 2013
prev sibling next sibling parent "Paul Jurczak" <pauljurczak yahoo.com> writes:
On Sunday, 25 August 2013 at 18:07:33 UTC, Paul Jurczak wrote:
[..]

 I'm also running it with LDC, but it reports timings too good 
 to be true - something meaningful is getting optimized away and 
 I'm trying to find out why.


[..]

It seems that LDC optimizer is smarter than I expected and it was 
able to optimize away comparison on constant elements of array a 
in my test:

int test(alias F)(int N) {
    int a[10];
    int n = 0;

    foreach (immutable _; 0..N) {
       a[4] = !a[4];
       n += F(a);
    }

    return n;
}

I modified it, so there is no constant elements and all cases of 
pairwise comparison are exercised:

int test(alias F)(int N) {
    enum L = 10;
    int  a[L];
    int  n = 0;

    foreach (int i; 0..N) {
       auto j = (i%L + L/2)%L;
       a[j] = !a[j];
       n += F(a);
    }

    return n;
}

Here are the results:

Xubuntu 13.04 64-bit Core i5 3450S 2.8GHz (3.5GHz turbo):
LDC 0.11.0: ldmd2 -m64 -O -noboundscheck -inline -release
100000  5284
100000  4265
100000  4268
100000  5717
100000  4265

GDC 4.8.1: gdc -m64 -march=native -fno-bounds-check 
-frename-registers -frelease -O3
100000  4612
100000  5717
100000  5718
100000  4984
100000  11546

DMD64 2.063.2: dmd -O -noboundscheck -inline -release
100000  8350
100000  14615
100000  14597
100000  14270
100000  18509

Windows 7 64-bit Core i5 2500 3.4GHz turbo:
DMD 2.063.2 (32-bit) dmd -O -noboundscheck -inline -release
100000  9803
100000  17050
100000  17031
100000  20851
100000  20283

I'm stunned by LDC ability to optimize isPalindrome4 to the best 
performance level of the whole group. Other compilers placed it 
at the bottom of performance rank.
Aug 25 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Paul Jurczak:


 int test(alias F)(in int nLoops) /*pure nothrow*/ {
    int[10] a;
    typeof(return) n = 0;

    foreach (immutable _; 0 .. nLoops) {
        a[4] = !a[4];
        n += F(a);
    }

    return n;
 }


 What is the purpose of "immutable _;" above? Why not "i;"?


I have used _ as variable iteration name to remind the person 
that is reading the code that loop variable name is not used 
inside the loop itself. When you have more of those variables you 
can number them as _1, _2, or use no more than two underscores __.

And there the usage of immutable is to disallow the mutation the 
iteration variable inside the loop. In my opinion, to keep code 
clean and less bug-prone D should on make foreach indexes 
immutable on default. This saves you from bugs when you iterate 
on struct items:

struct Foo { int x; }
auto foos = [Foo(10), Foo(20)];
foreach (f; foos)
     f.x++;

It's not uncommon in those cases to forget a "ref" and think foos 

you from this class of bugs.

I have asked this in past, but D lacks a "mutable" keyword for 
the situations when you want to actually mutate the foreach 
variable, and generally Walter didn't sound very interested on 
this.

So as workaround for this language design problem, it's a good 
habit to always put a const/immutable on foreach variables, 
unless you don't wait it, and unless something forces you to not 
use a const.



 void main() {
    enum size_t nLoops = 60_000_000;
    StopWatch sw;

    foreach (alg; TypeTuple!(isPalindrome0, isPalindrome1,
                             isPalindrome2, isPalindrome3,
                             isPalindrome4)) {
        sw.reset;
        sw.start;
        immutable n = test!alg(nLoops);
        sw.stop;
        writeln(n, " ", sw.peek.msecs);
    }
 }


 Same question here: why immutable?


It's explained here:
http://blog.knatten.org/2011/11/11/disempower-every-variable/

In short all your variables/function arguments should be tagged 
as const/immutable unless the semantics of your algorithm needs 
them to mutate, or unless some limit in D/Phobos forbids you to 
(like when you have created a lazy range, currently you can't 
assign it to const and then use it).

Bye,
bearophile
Aug 25 2013
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 25/08/13 22:22, bearophile wrote:

 In short all your variables/function arguments should be tagged as
 const/immutable unless the semantics of your algorithm needs them to mutate, or
 unless some limit in D/Phobos forbids you to (like when you have created a lazy
 range, currently you can't assign it to const and then use it).


It's slightly annoying that one can't readily get immutability to play nice
with 
more general iterations than i .. j.

For example if you consider the loop,

     for (i = 10; i > 0; --i) { ... }

You can't make i immutable for obvious reasons but it's not clear to me how you 
can get a performant version of that with immutable i.

You could do something like [*],

     foreach (immutable i; iota(1, 11).retro) { ... }

... but that will be slow and inefficient.

Ditto for cases like

     for (i = 0; i < n; i += 2) { ... }

which you could write as

     foreach (immutable i; iota(0, n, 2)) { ... }

... but again, that will be slow compared to the for loop or a foreach across
an 
interval.


[* Hijacking of discussion: a while back I think I floated the idea of 
generalizing iota() with closed/open boundary conditions similar to those found 
in std.random.uniform; so e.g. you could do iota!"[]"(0, 10) and the upper
bound 
would be included in the values returned.  Would be useful for cases like
these.]
Aug 25 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 It's slightly annoying that one can't readily get immutability 
 to play nice with more general iterations than i .. j.

 For example if you consider the loop,

     for (i = 10; i > 0; --i) { ... }


Thankfully foreach_reverse was not deprecated:

void main() {
     import std.stdio;

     for (auto i = 10; i > 0; --i)
         write(i, " ");
     writeln;

     foreach_reverse (immutable i; 1 .. 11)
         write(i, " ");
     writeln;
}



 [* Hijacking of discussion: a while back I think I floated the 
 idea of generalizing iota() with closed/open boundary 
 conditions similar to those found in std.random.uniform; so 
 e.g. you could do iota!"[]"(0, 10) and the upper bound would be 
 included in the values returned.  Would be useful for cases 
 like these.]


Yes, it's a kind of necessary enhancement:
http://d.puremagic.com/issues/show_bug.cgi?id=10466

Bye,
bearophile
Aug 25 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 25 August 2013 at 21:01:54 UTC, bearophile wrote:

 [* Hijacking of discussion: a while back I think I floated the 
 idea of generalizing iota() with closed/open boundary 
 conditions similar to those found in std.random.uniform; so 
 e.g. you could do iota!"[]"(0, 10) and the upper bound would 
 be included in the values returned.  Would be useful for cases 
 like these.]


 Yes, it's a kind of necessary enhancement:
 http://d.puremagic.com/issues/show_bug.cgi?id=10466

 Bye,
 bearophile


If somebody were to implement this, I would *love* to review it.
Aug 25 2013
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sun, Aug 25, 2013 at 11:10:39PM +0200, monarch_dodra wrote:

 On Sunday, 25 August 2013 at 21:01:54 UTC, bearophile wrote:

[* Hijacking of discussion: a while back I think I floated the
idea of generalizing iota() with closed/open boundary conditions
similar to those found in std.random.uniform; so e.g. you could
do iota!"[]"(0, 10) and the upper bound would be included in the
values returned.  Would be useful for cases like these.]


Yes, it's a kind of necessary enhancement:
http://d.puremagic.com/issues/show_bug.cgi?id=10466

Bye,
bearophile


 
 If somebody were to implement this, I would *love* to review it.


If somebody were to attempt to implement this, I'd recommend taking this
issue into account as well:

	http://d.puremagic.com/issues/show_bug.cgi?id=10762

	(which is a generalization of:
	http://d.puremagic.com/issues/show_bug.cgi?id=6447)

I don't know if the total amount of changes would warrant rewriting iota
entirely in order to keep the complexity of the implementation minimal.

(The nice thing about D unittests is that rewriting code is much less
scary because if the unittests are complete enough, they will catch any
regressions right off the bat.)


T

-- 
WINDOWS = Will Install Needless Data On Whole System -- CompuMan
Aug 25 2013
prev sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 25/08/13 23:01, bearophile wrote:

 Thankfully foreach_reverse was not deprecated:


Really?  I thought it was viewed these days as some kind of awful abomination 
that should never have been in the language.  (I'm not sure I understand why, 
but equally I'm not sure I care to open the can of worms of finding out why...)
Aug 25 2013
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/25/2013 10:42 PM, Joseph Rushton Wakeling wrote:

      foreach (immutable i; iota(0, n, 2)) { ... }

 ... but again, that will be slow compared to the for loop or a foreach
 across an interval.


Why would that be the case?
Aug 25 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Timon Gehr:


 ... but again, that will be slow compared to the for loop or a 
 foreach
 across an interval.


 Why would that be the case?


In the real world, where we live, there is a thing named 
"abstraction penalty", it's something that asks you to pay 
something when there is an interface between separated 
subsystems. To avoid paying that penalty at run-time in your 
programs you need a smarter compiler, that usually requires more 
time to be developed, and usually requires more time to do its 
work (this means slower compilations, see the LDC2 compiler 
compared to DMD. LDC2 was able to remove most of the run-time 
penalty, but when it compiles it's slower than DMD). So in the 
real life we have to take compromises all the time.

Bye,
bearophile
Aug 25 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/25/2013 11:45 PM, bearophile wrote:

 Timon Gehr:


 ... but again, that will be slow compared to the for loop or a foreach
 across an interval.


 Why would that be the case?


 In the real world, where we live,  ...


This is uncalled for.
Aug 25 2013
next sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 26/08/13 00:36, Timon Gehr wrote:

 This is uncalled for.


I'm sure you didn't mean it, but your original remark, "Why would that be the 
case?", came across as flip and dismissive about a serious practical problem of 
working with D, that anyone caring about performance has run into.

I don't mean to defend or attack anyone, but I'm not surprised you got a 
sarcastic response.
Aug 25 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 08/26/2013 12:46 AM, Joseph Rushton Wakeling wrote:

 On 26/08/13 00:36, Timon Gehr wrote:

 This is uncalled for.


 I'm sure you didn't mean it, but your original remark, "Why would that
 be the case?", came across as flip and dismissive about a serious
 practical problem


It was a genuine question. I assumed that the inliner actually works. 
But you are right, DMD does not even seem to inline iota, and gdc 
appears to fail to vectorize some iota-loops even though it vectorizes 
the range-foreach equivalent.
Aug 25 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Timon Gehr:


 This is uncalled for.


I didn't mean to offend, sorry for the unneeded (light) sarcasm. 
While generally you seem expert in computer science and many 
other things, in several of your post you seem to dismiss a 
little too much practical considerations.

Bye,
bearophile
Aug 25 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 08/26/2013 01:18 AM, bearophile wrote:

 Timon Gehr:


 This is uncalled for.


 I didn't mean to offend,


No offence taken.


 sorry for the unneeded (light) sarcasm.


Well, this kind of thing does not propagate too well over the Internet.
Aug 25 2013
prev sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 25/08/13 23:11, Timon Gehr wrote:

 Why would that be the case?


I don't know why it _need_ be the case, but it _is_ the case in practice right
now.

The precise example I cited of a for() loop with decreasing value, I tried 
replacing using retro and iota -- and it was significantly slower.

Ditto foreach's over iota() -- even though in principle there is no conceptual 
difference between foreach(i; m .. n) and foreach(i; iota(m, n)), and it ought 
to be possible for the two to reduce to the same machine code, there is right 
now a performance hit.
Aug 25 2013