• Brian Myers (23/23) May 21 2008 Hi,
• BCS (4/7) May 21 2008 I think not because the context pointer "this" must be carried somehow a...
• bearophile (20/22) May 21 2008 Do you mean something like this?
• Dee Girl (12/42) May 21 2008 import std.algorithm;
• Brian Myers (5/35) May 22 2008 I think this is exactly what I wanted. I needed to use the address of op...
• Dee Girl (14/17) May 22 2008 In fact it is simpler. It is just bug in dmd. The following code works.
• Brian Myers (30/54) May 22 2008 Hmmm, for some reason this is still not working. It must be because the ...
• Dee Girl (22/23) May 22 2008 This code does not work:
• bearophile (5/10) May 22 2008 I don't exactly know what you are trying to do, but using s1~s2 to merge...
• Brian Myers (5/17) May 22 2008 I'll look into submitting a bug report to Walter. Thanx bearophile.
• lurker (2/25) May 22 2008
• bearophile (85/86) May 24 2008 I am not using D 2.x, but I have performed some benchmarks, with quite i...
• bearophile (22/22) May 24 2008 More versions with more surprises:
• Dee Girl (3/29) May 24 2008 I think you want to measure function call overhead. Then do not put dyna...

Brian Myers <bmyers harryanddavid.com> writes:

Hi,

I send Andrei a suggestion a while back for improving the map! template in
std.algorithm. The change was, when map! is supplied a function alias, its
return type should be a range of the return type of the function. This is much
like Python's map statement and lets you do things like this:

string[] string_list = //integer strings from somewhere
auto intrange = map!(atoi)(split(string_list, ","));

That has worked out well. This time I have a question about both the reduce!
and map! templates. I would like to do something like this:

reduce!(Merge)(/*string[] list of files*/);

but where Merge is a member function of a class. When I try this I get:

c:\dmd\bin\..\src\phobos\std\algorithm.d(185): Error: need 'this' to access
member Merge

When I try

reduce!(this.Merge)(/*same string[]*/);

I get:

d_dedup.d(153): template std.algorithm.reduce(F...) cannot deduce template
function from argument types !(this.Merge)(i
variant(char)[],invariant(char)[][])

Is it possible to map! or reduce! a member function or delegate against a
range? If so how would I do that?

Thanx,

Brian

BCS <ao pathlink.com> writes:

Reply to Brian,


 Is it possible to map! or reduce! a member function or delegate
 against a range? If so how would I do that?
 

I think not because the context pointer "this" must be carried somehow at 
runtime. It might, however, be possible to make a version of map! that takes 
a delegate and uses that.

bearophile <bearophileHUGS lycos.com> writes:

Brian Myers:
 Is it possible to map! or reduce! a member function or delegate against a
 range? If so how would I do that?

Do you mean something like this?

import d.func: map, xrange, putr;

class Foo {
    int sqr(int x) { return x * x; }
}

class Baz {
    float div2(int x) { return x / 2; }
}

void main() {
    auto f1 = new Foo;
    putr( map(&f1.sqr, xrange(10)) );

    auto b1 = new Baz;
    putr( map(&b1.div2, xrange(10)) );
}

Output:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
[0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0]

Bye,
bearophile

Dee Girl <deegirl noreply.com> writes:

bearophile Wrote:

 Brian Myers:
 Is it possible to map! or reduce! a member function or delegate against a
 range? If so how would I do that?

 
 Do you mean something like this?
 
 import d.func: map, xrange, putr;
 
 class Foo {
     int sqr(int x) { return x * x; }
 }
 
 class Baz {
     float div2(int x) { return x / 2; }
 }
 
 void main() {
     auto f1 = new Foo;
     putr( map(&f1.sqr, xrange(10)) );
 
     auto b1 = new Baz;
     putr( map(&b1.div2, xrange(10)) );
 }
 
 Output:
 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
 [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0]
 
 Bye,
 bearophile

import std.algorithm;

struct A
{
    int Merge(int) { return 0; }
}

void main(string[] args)
{
    A a;
    map!((int x) { return a.Merge(x); })([1, 2, 3]);
}

I did not install bearophile library. It would be interesting to see what the
speed is of std.algorithm and d.func. Dee Girl

Brian Myers <bmyers harryanddavid.com> writes:

I think this is exactly what I wanted. I needed to use the address of operator
along with the instance reference.

Wow some of the things you can do in D (like Dee Girl's post) are almost as
esoteric and obscure as Felix!

Thanx everyone,

Brian

bearophile Wrote:

 Brian Myers:
 Is it possible to map! or reduce! a member function or delegate against a
 range? If so how would I do that?

 
 Do you mean something like this?
 
 import d.func: map, xrange, putr;
 
 class Foo {
     int sqr(int x) { return x * x; }
 }
 
 class Baz {
     float div2(int x) { return x / 2; }
 }
 
 void main() {
     auto f1 = new Foo;
     putr( map(&f1.sqr, xrange(10)) );
 
     auto b1 = new Baz;
     putr( map(&b1.div2, xrange(10)) );
 }
 
 Output:
 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
 [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0]
 
 Bye,
 bearophile

Dee Girl <deegirl noreply.com> writes:

Brian Myers Wrote:

 I think this is exactly what I wanted. I needed to use the address of operator
along with the instance reference.
 
 Wow some of the things you can do in D (like Dee Girl's post) are almost as
esoteric and obscure as Felix!

In fact it is simpler. It is just bug in dmd. The following code works.

import std.algorithm;

struct A
{
    int Merge(int) { return 0; }
}

void main(string[] args)
{
    A a;
    auto fun = &a.Merge;
    map!(fun)([1, 2, 3]);
}

It is a problem that compiler can work with fun but not direct with &a.Merge.
It is good idea to report bug to Walter. Such bug limits power of higher order
functions. Thank you, Dee Girl

Brian Myers <bmyers harryanddavid.com> writes:

Hmmm, for some reason this is still not working. It must be because the reduce
statement is itself within a method of the same class as Merge. Here's what
I've got.

class ExternalSorter : Sorter {
.
.
.

    string Merge(string f1, string f2) {
    .
    .
    .
    }

    override void Sort() {
    .
    .
    .
        auto mrg = &Merge;
        retfile = (chunk_list.length == 1 ? chunk_list[0] :
                   reduce!(mrg)(chunk_list[0], chunk_list[1..$]));
    .
    .
    .
    }

And here's the error message:
c:\dmd\bin\..\src\phobos\std\algorithm.d(283): template
std.algorithm.reduce(F...) is not a function template
d_dedup.d(191): template std.algorithm.reduce(F...) cannot deduce template
function from argument types !(&this.Merge)(i
nvariant(char)[],invariant(char)[][])
d_dedup.d(191): Error: incompatible types for ((this.chunk_list[cast(uint)0]) ?
((reduce(F...))((this.chunk_list[cast(ui
nt)0]),this.chunk_list[cast(uint)1..__dollar]))): 'invariant(char)[]' and 'int'

This is the closest I've gotten yet. I've tried a number of other ways with the
address of operator, etc...

Brian



Dee Girl Wrote:

 Brian Myers Wrote:
 
 I think this is exactly what I wanted. I needed to use the address of operator
along with the instance reference.
 
 Wow some of the things you can do in D (like Dee Girl's post) are almost as
esoteric and obscure as Felix!

 
 In fact it is simpler. It is just bug in dmd. The following code works.
 
 import std.algorithm;
 
 struct A
 {
     int Merge(int) { return 0; }
 }
 
 void main(string[] args)
 {
     A a;
     auto fun = &a.Merge;
     map!(fun)([1, 2, 3]);
 }
 
 It is a problem that compiler can work with fun but not direct with &a.Merge.
It is good idea to report bug to Walter. Such bug limits power of higher order
functions. Thank you, Dee Girl
 

Dee Girl <deegirl noreply.com> writes:

Brian Myers Wrote:

 Hmmm, for some reason this is still not working. It must be because the reduce
statement is itself within a method of the same class as Merge. Here's what
I've got.

This code does not work:


import std.algorithm;

class Sorter {}

class ExternalSorter : Sorter {
    string Merge(string f1, string f2) {
        return f1 ~ f2;
    }

    void Sort() {
        string[] chunk_list = [ "a", "b" ];
        auto mrg = &Merge;
        auto retfile = reduce!(mrg)(chunk_list[0], chunk_list[1..$]);
    }
}

void main(string[] args)
{
    auto s = new ExternalSorter;
    s.Sort;
}

But I know how to make it work because I look at the error message. You go to
std.algorithm and make NxNHelper from private to public. Then inside NxNHelper
also make For from private to public. Then code works.

Maybe bug report to Walter is necessary. Private should work because lookup is
in correct module. It is bug in compiler not library. Can you please? Thank
you, Dee Girl

bearophile <bearophileHUGS lycos.com> writes:

Brian Myers:
     string Merge(string f1, string f2) {
     .
     .
     .
     }

I don't exactly know what you are trying to do, but using s1~s2 to merge an
array of strings is probably O(n^2) if the higher order functions you use (or
the compiler) aren't smart enough.
There is a join() function in std.string that is O(1), and there's a faster
version of it in my libs (and probably in Tango too).

Bye,
bearophile

Brian Myers <bmyers harryanddavid.com> writes:

I'll look into submitting a bug report to Walter. Thanx bearophile.

Dee Girl, I'm actually not merging strings. The strings are file names. Merge
is the merge phase for an external sort. In my next project I'll use map to do
something like what you're talking about. I'll have to test the difference
between map!-ing a custom function and doing join, and using reduce and a
custom function.

Thanx to both of you.

Brian

bearophile Wrote:

 Brian Myers:
     string Merge(string f1, string f2) {
     .
     .
     .
     }

 
 I don't exactly know what you are trying to do, but using s1~s2 to merge an
array of strings is probably O(n^2) if the higher order functions you use (or
the compiler) aren't smart enough.
 There is a join() function in std.string that is O(1), and there's a faster
version of it in my libs (and probably in Tango too).
 
 Bye,
 bearophile

lurker <lurker lurk.com> writes:

dood u got ur credits crossed. d chick not bearophile said u should submit a
bug report. then bearophile not d chick said merging strings is bad. afaiu d
chick prolly put string concat in there as an example. peace

Brian Myers Wrote:

 I'll look into submitting a bug report to Walter. Thanx bearophile.
 
 Dee Girl, I'm actually not merging strings. The strings are file names. Merge
is the merge phase for an external sort. In my next project I'll use map to do
something like what you're talking about. I'll have to test the difference
between map!-ing a custom function and doing join, and using reduce and a
custom function.
 
 Thanx to both of you.
 
 Brian
 
 bearophile Wrote:
 
 Brian Myers:
     string Merge(string f1, string f2) {
     .
     .
     .
     }

 
 I don't exactly know what you are trying to do, but using s1~s2 to merge an
array of strings is probably O(n^2) if the higher order functions you use (or
the compiler) aren't smart enough.
 There is a join() function in std.string that is O(1), and there's a faster
version of it in my libs (and probably in Tango too).
 
 Bye,
 bearophile

 

bearophile <bearophileHUGS lycos.com> writes:

Dee Girl:
 I did not install bearophile library. It would be interesting to see what the
speed is of std.algorithm and d.func.

I am not using D 2.x, but I have performed some benchmarks, with quite
interesting results (DMD 1.029 because my libs don't work at all with DMD
1.030, on a Core Duo, using 1 core only):

import std.stdio: put = writef, putr = writefln;
import d.func: map, range;
import d.time: clock;
import std.traits: ReturnType;
import d.extra: NewVoidCArray, delVoidC, NewVoidGCArray;
import std.c.stdlib: alloca;

static int inv(int x) { return -x; }

ReturnType!(f)[] Map2(alias f)(int[] arr) {
    auto result = new ReturnType!(f)[arr.length];
    foreach (i, el; arr)
        result[i] = f(el);
    return result;
}

ReturnType!(f)[] Map3(alias f)(int[] arr) {
    auto result = NewVoidGCArray!(int)(arr.length);
    foreach (i, el; arr)
        result[i] = f(el);
    return result;
}

void Map4(alias f)(int[] arr) {
    auto result = (cast(int*)alloca(arr.length * int.sizeof))[0 .. arr.length];
    if (result.ptr is null)
        throw new Exception("Not enough free stack");

    foreach (i, el; arr)
        result[i] = f(el);
    return result;
}

void main() {
    auto data = range(6_000_000);
    double t;
    typeof(data) r;

    t = clock();
    for (uint i; i < 100U; ++i) {
        r = new int[data.length];
        foreach (pos, el; data)
            r[pos] = -el;
    }
    putr("inline: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = map(&inv, data);
    putr("map global func: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = map((int x) {return -x;}, data);
    putr("map locally defined delegate: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = map(function(int x) {return -x;}, data);
    putr("map locally defined function: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = Map2!(inv)(data);
    putr("Map2 with global function: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i) {
        auto r2 = NewVoidCArray!(int)(data.length);
        foreach (pos, el; data)
            r2[pos] = -el;
        delVoidC(r2);
    }
    putr("inline C malloc: ", clock() - t);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = Map3!(inv)(data);
    putr("Map3 with global function: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        Map4!(inv)(data);
    putr("Map4 with global function: ", clock() - t);
}



Timings results, n = 6_000_000 of ints:
  inline: 4.59
  map global func: 4.95
  map locally defined delegate: 4.73
  map locally defined function: 4.31
  Map2 with global function: 3.97
  inline C malloc: 2.01
  Map3 with global function: 2.53
  Map4 with global function: 2.0

I can see two surprises there, one is that putting "function" in the map avoids
it to become a delegate, speeding up the code a little. The other bigger
surprise is the first version (inlined) being slower than the version "map
locally defined function".

Bye,
bearophile

bearophile <bearophileHUGS lycos.com> writes:

More versions with more surprises:

    t = clock();
    for (uint i; i < 100U; ++i)
        r = Map2!((int x) {return -x;})(data);
    putr("Map2 with locally defined delegate: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = Map2!(function(int x) {return -x;})(data);
    putr("Map2 with locally defined function: ", clock() - t, " ", r[$-1]);
}

/*

Timings:
    inline: 4.61 -5999999
    map global func: 4.968 -5999999
    map locally defined delegate: 4.782 -5999999
    map locally defined function: 4.328 -5999999
    Map2 with global function: 4 -5999999
    inline C malloc: 2.015
    Map3 with global function: 2.531 -5999999
    Map4 with global function: 1.969
    Map2 with locally defined delegate: 4.297 -5999999
    Map2 with locally defined function: 4.156 -5999999

Dee Girl <deegirl noreply.com> writes:

bearophile Wrote:

 More versions with more surprises:
 
     t = clock();
     for (uint i; i < 100U; ++i)
         r = Map2!((int x) {return -x;})(data);
     putr("Map2 with locally defined delegate: ", clock() - t, " ", r[$-1]);
 
     t = clock();
     for (uint i; i < 100U; ++i)
         r = Map2!(function(int x) {return -x;})(data);
     putr("Map2 with locally defined function: ", clock() - t, " ", r[$-1]);
 }
 
 /*
 
 Timings:
     inline: 4.61 -5999999
     map global func: 4.968 -5999999
     map locally defined delegate: 4.782 -5999999
     map locally defined function: 4.328 -5999999
     Map2 with global function: 4 -5999999
     inline C malloc: 2.015
     Map3 with global function: 2.531 -5999999
     Map4 with global function: 1.969
     Map2 with locally defined delegate: 4.297 -5999999
     Map2 with locally defined function: 4.156 -5999999

I think you want to measure function call overhead. Then do not put dynamic
allocation in function. Otherwise you measure allocate speed. That is why
results are odd. Maybe if you change order results will change.

Would help to put static allocation inside function, never dynamic. Then you
measure loop and call overhead. Also tests should be in separate runs of
program and averaged over few runs. Dee Girl