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

           Summary: std.algorithm.sum()
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2010-08-25 18:10:40 PDT ---
Writing Python code shows that computing the sum of a sequence of int/FP values is a very common operation. In D you may write it as:

import std.stdio: writeln;
import std.algorithm: reduce;
void main() {
    auto arr = new double[10];
    arr[] = 1.0;
    auto t = reduce!q{a + b}(arr);
    writeln(t);
}



But I suggest to create std.algorithm.sum() as shorthand, because reduce requires a bit of cognitive burden that is out of place for this so common and basic operation:

import std.stdio: writeln;
import std.algorithm: sum;
void main() {
    auto arr = new double[10];
    arr[] = 1.0;
    auto t = sum(arr);
    writeln(t);
}


As second optional argument sum() may accept the starting value:
auto total = sum(range, 0.0);

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #1 from bearophile_hugs@eml.cc 2010-10-11 13:33:52 PDT ---
One test case for sum():


import std.algorithm: sum;
void main() {
    bool[] array = [true, false, true, true];
    assert(sum(array) == 3);
}



Currently this doesn't compile:
reduce!q{a + b}(array)

You need to add a 0 start:
reduce!q{a + b}(0, array)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #2 from bearophile_hugs@eml.cc 2010-12-12 23:41:50 PST ---
sum() may be implemented better than just using reduce() because a smarter
sum() may keep inside two variables and sum them in parallel each loop. And
then sum the two partial sums at the end and return them. Experiments (and
theory) show that on modern CPUs this is more efficient than a normal loop with
a single accumulation variable.

I mean code like (specialized for random access ranges, that's a very common
case worth specializing for, because sum() is a very common operation that
needs to be fast):


switch (array.length) {
    case 0:
        break;
    case 1:
        total = array[0];
        break;
    default:
        total = array[0];
        auto total2 = cast(typeof(total))array[1];
        int stop = array.length & (~1);
        for (int i = 2; i < stop; i += 2) {
            total += array[i];
            total2 += array[i + 1];
        }
        total += (array.length % 2 ? (total2 + array[$-1]) : total2);
        break;
}
// return total here

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Denis Derman <denis.spir@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |denis.spir@gmail.com


--- Comment #3 from Denis Derman <denis.spir@gmail.com> 2010-12-24 11:18:19 PST ---
See comment to issue 4705 http://d.puremagic.com/issues/show_bug.cgi?id=4705

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #4 from Denis Derman <denis.spir@gmail.com> 2010-12-24 11:23:28 PST ---
(In reply to comment #2)
> sum() may be implemented better than just using reduce() because a smarter
> sum() may keep inside two variables and sum them in parallel each loop. And
> then sum the two partial sums at the end and return them. Experiments (and
> theory) show that on modern CPUs this is more efficient than a normal loop with
> a single accumulation variable.
> 
> I mean code like (specialized for random access ranges, that's a very common
> case worth specializing for, because sum() is a very common operation that
> needs to be fast):
> 
> 
> switch (array.length) {
>     case 0:
>         break;
>     case 1:
>         total = array[0];
>         break;
>     default:
>         total = array[0];
>         auto total2 = cast(typeof(total))array[1];
>         int stop = array.length & (~1);
>         for (int i = 2; i < stop; i += 2) {
>             total += array[i];
>             total2 += array[i + 1];
>         }
>         total += (array.length % 2 ? (total2 + array[$-1]) : total2);
>         break;
> }
> // return total here

You should add a 'case 2:' to avoid complication of a simple and common case. Maybe also avoid // computation under a given number of elements (to be defined).

denis

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #5 from bearophile_hugs@eml.cc 2010-12-24 22:55:05 PST ---
(In reply to comment #4)

> You should add a 'case 2:' to avoid complication of a simple and common case. Maybe also avoid // computation under a given number of elements (to be defined).

The code I have shown is tuned with timing experiments.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei@metalanguage.com
         AssignedTo|nobody@puremagic.com        |andrei@metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #6 from bearophile_hugs@eml.cc 2011-05-15 07:53:34 PDT ---
A first slow and not much tested implementation:


import std.stdio, std.traits, std.range;

template IsSummable(T) {
    enum bool IsSummable = __traits(compiles, {return T.init + T.init;});
}

auto sum(R, T)(R items, T start) if (IsSummable!T) {
    foreach (item; items)
        start += item;
    return start;
}

auto sum(R)(R items) if (IsSummable!(ForeachType!R)) {
    alias ForeachType!R T;
    static if (is(T == cfloat) || is(T == cdouble) || is(T == creal))
        T result = 0+0i;
    else static if (is(T == bool))
        int result;
    else static if (isSomeChar!T)
        uint result;
    else
        T result = 0;

    foreach (item; items)
        result += item;
    return result;
}

void main() {
    //assert(sum([]) == 0);
    assert(sum(new int[0]) == 0);
    assert(sum([1, 2, 3]) == 6);
    assert(sum([1.5L, 2.5L, 3.5L]) == 7.5L);
    assert(sum(iota(0)) == 0);
    assert(sum(iota(10)) == 45);
    assert(sum(iota(10)) == 45);
    assert(sum([true, false, true]) == 2);
    assert(sum([1+0i, 2+1i]) == 3+1i);
    ubyte[] a1 = [100, 200];
    assert(sum(a1, 0) == 300);
    assert(sum(a1) == 44); // overflow!
    assert(sum("hello") == 532);
    assert(sum([1:10, 2:20]) == 30);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #7 from Andrei Alexandrescu <andrei@metalanguage.com> 2011-05-15 08:13:20 PDT ---
Hm, I don't get why we should start from scratch instead of reusing reduce.

auto sum(R)(R range)
if(is(typeof(ElementType!(R).init + ElementType!(R).init)))
{
    return reduce!"a + b"(0, range);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

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



--- Comment #8 from bearophile_hugs@eml.cc 2011-05-15 09:10:38 PDT ---
(In reply to comment #7)
> Hm, I don't get why we should start from scratch instead of reusing reduce.
> 
> auto sum(R)(R range)
> if(is(typeof(ElementType!(R).init + ElementType!(R).init)))
> {
>     return reduce!"a + b"(0, range);
> }

I suggest to avoid using reduce here to allow a more efficient implementation
of sum() (keeping two summing values in parallel), see Comment #2.

Note1: I have shown two versions of sum() here, one accepts a starting value
too.

Note2: I think your code doesn't work with the little unittest (main) I have
added, even if you comment out this line sum(a1,0).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------