www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - ranges

reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Hello.

I'm muddling over the following code, which compares an array/take 
composition with the analogous imperative code. For medium-large values 
of n, I'm seeing a fivefold degradation in performance, which blows up 
to 30 times worse at n=50000000.

Any ideas on why this is or better ways to accomplish the same?

import std.range;
import std.date;
import std.random;
import std.array;
import std.stdio;

void main(){
     for(int n = 500; n <= 500000000; n *= 10){
         writeln(n);
         auto r = rndGen();
         auto tz = getUTCtime();
         auto a = new int[n];
         foreach(ref aa; a){
             aa = r.front();
             r.popFront();
         }
         auto tz2 = getUTCtime();
         auto a2 = array(take(r,n));
         auto tz3 = getUTCtime();
         writeln("\tarr: ",tz2-tz);
         writeln("\trange: ",tz3-tz2);
     }
}
~
Apr 29 2010
next sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Oh I get it. hasLength is broken.

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

Kyle Foley's patch brings my program to a more respectable 1.6 times 
slower or thereabouts.

On 04/29/2010 01:52 PM, Ellery Newcomer wrote:

 Hello.

 I'm muddling over the following code, which compares an array/take
 composition with the analogous imperative code. For medium-large values
 of n, I'm seeing a fivefold degradation in performance, which blows up
 to 30 times worse at n=50000000.

 Any ideas on why this is or better ways to accomplish the same?

 import std.range;
 import std.date;
 import std.random;
 import std.array;
 import std.stdio;

 void main(){
 for(int n = 500; n <= 500000000; n *= 10){
 writeln(n);
 auto r = rndGen();
 auto tz = getUTCtime();
 auto a = new int[n];
 foreach(ref aa; a){
 aa = r.front();
 r.popFront();
 }
 auto tz2 = getUTCtime();
 auto a2 = array(take(r,n));
 auto tz3 = getUTCtime();
 writeln("\tarr: ",tz2-tz);
 writeln("\trange: ",tz3-tz2);
 }
 }
 ~
Apr 29 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:

 http://d.puremagic.com/issues/show_bug.cgi?id=3508
 Kyle Foley's patch brings my program to a more respectable 1.6 times 
 slower or thereabouts.


No need to write another bug report then.

Bye,
bearophile
Apr 29 2010
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:


 I'm muddling over the following code, which compares an array/take 
 composition with the analogous imperative code. For medium-large values 
 of n, I'm seeing a fivefold degradation in performance, which blows up 
 to 30 times worse at n=50000000.


Some of the code written by Andrei can be bad. I have modified your code like
this:

import std.range: front, popFront, array, take;
import std.date: getUTCtime;
import std.random: rndGen;
import std.stdio: writeln;

void main() {
    for (int n = 500; n <= 500_000_000; n *= 10) {
        writeln(n, ":");
        auto rnd = rndGen();

        auto t0 = getUTCtime();
        auto rnd_arr1 = new int[n];
        foreach (ref el; rnd_arr1) {
            el = rnd.front();
            rnd.popFront();
        }

        auto t1 = getUTCtime();
        auto rnd_arr2 = new int[n];
        int i;
        foreach (r; take(rnd, n))
            rnd_arr2[i++] = r;

        auto t2 = getUTCtime();
        auto rnd_arr3 = array(take(rnd, n));

        auto t3 = getUTCtime();

        writeln("  arr:   ", t1 - t0);
        writeln("  take:  ", t2 - t1);
        writeln("  range: ", t3 - t2);
    }
}


It shows that most of the time is spent by array().
After some experiments I have found that the Appender() is very slow. But the
direct cause of this problem, beside the slowness of Appender() is that the
hasLength is buggy and doesn't find the length of the take, using the Appender.

If you replace the hasLenght with the equivalent from my dlibs1:

template hasLength(R) {
    enum bool hasLength = is(typeof(R.length)) || is(typeof(R.init.length))
                          && !isNarrowString!R;
}

The problem essentially vanishes. The root of the problem is that Phobos has
not enough unittests and it not battle-tested yet.
I will probably write a bug report.

Bye,
bearophile
Apr 29 2010