[Issue 4725] std.algorithm.sum()
https://issues.dlang.org/show_bug.cgi?id=4725 Orvid King blah38...@gmail.com changed: What|Removed |Added CC||blah38...@gmail.com --- Comment #34 from Orvid King blah38...@gmail.com --- I'll assume that the fact that the only version of sum that this supported is an array specialized version is one of the known issues? --
[Issue 4725] std.algorithm.sum()
https://issues.dlang.org/show_bug.cgi?id=4725 --- Comment #35 from Andrei Alexandrescu and...@erdani.com --- sum should work with all ranges, and get specialized only for specific kinds of ranges. Is that not the case? --
[Issue 4725] std.algorithm.sum()
https://issues.dlang.org/show_bug.cgi?id=4725 --- Comment #36 from Orvid King blah38...@gmail.com --- Ack, woops, sorry, was thinking of the wrong function, it was max that I had an issue with, as it didn't work when I chained it after a map!(). --
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 bearophile_h...@eml.cc changed: What|Removed |Added Status|ASSIGNED|RESOLVED Resolution||FIXED --- Comment #32 from bearophile_h...@eml.cc 2014-02-25 14:30:48 PST --- The main request is now addressed. There are numerous enhancements/bugs related, but they all have their own issue number. Ready to close? Currently sum is not listed in this page: http://dlang.org/phobos/std_algorithm.html -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #33 from Andrei Alexandrescu and...@erdani.com 2014-02-25 15:16:08 PST --- Yah. For the record, this sux :o). -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #24 from bearophile_h...@eml.cc 2014-02-15 01:44:42 PST --- See Issue 12169 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #25 from bearophile_h...@eml.cc 2014-02-15 01:48:32 PST --- See Issue 12170 for another problem -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #26 from bearophile_h...@eml.cc 2014-02-15 01:53:08 PST --- See also Issue 12171 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #27 from bearophile_h...@eml.cc 2014-02-15 02:01:58 PST --- Another problem is in Issue 12172 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #28 from bearophile_h...@eml.cc 2014-02-15 02:35:00 PST --- See also Issue 12173 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #30 from bearophile_h...@eml.cc 2014-02-15 02:53:59 PST --- See also Issue 12175 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #31 from bearophile_h...@eml.cc 2014-02-15 03:12:07 PST --- See also Issue 12176 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
https://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #23 from github-bugzi...@puremagic.com 2014-02-14 23:20:08 PST --- Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/1564671acef88478a8eec7e0ecfcf794023c58d6 Fix Issue 4725 - std.algorithm.sum() https://github.com/D-Programming-Language/phobos/commit/acdb1d0a9ae9ce2b40ee16b3d45c42817cd00b7e Merge pull request #1205 from andralex/4725 Fix Issue 4725 - std.algorithm.sum() -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #21 from bearophile_h...@eml.cc 2013-06-08 15:15:10 PDT --- Fortran has a built in sum() that supports a second useful optional argument, that specifies the dimension along to compute the sum, it's useful for 2D or nD arrays: ke = 0.5d0 * dot_product(mass, sum(v ** 2, dim=1)) See: http://gcc.gnu.org/onlinedocs/gfortran/SUM.html -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #22 from Andrei Alexandrescu and...@erdani.com 2013-06-08 15:24:12 PDT --- Time to merge the pull request that's rotting in there... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #20 from bearophile_h...@eml.cc 2013-05-04 13:27:36 PDT ---
An use case. Given some permutations of the chars ABCD this program finds the
missing one:
import std.stdio, std.string, std.algorithm, std.conv, std.range;
void main() {
const perms = ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC
BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD
BADC BDAC CBDA DBCA DCAB.split;
immutable rowSum = perms[0].reduce!q{a + b};
foreach (immutable i; 0 .. perms[0].length) {
immutable sumColumns = reduce!q{a + b}(0, perms.transversal(i));
write(cast(char)(rowSum - sumColumns % rowSum));
}
writeln;
}
Output: DBAC
Using a sum() function:
import std.stdio, std.string, std.algorithm, std.conv, std.range;
void main() {
const perms = ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC
BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD
BADC BDAC CBDA DBCA DCAB.split;
immutable rowSum = perms[0].sum(0);
foreach (immutable i; 0 .. perms[0].length) {
immutable sumColumns = perms.transversal(i).sum(0);
write(cast(char)(rowSum - sumColumns % rowSum));
}
writeln;
}
As in the Python sum() I have added a seed value, in this case the 0 int.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #19 from bearophile_h...@eml.cc 2013-03-25 10:49:55 PDT ---
Is it worth adding to sum() an optional argument with the start value, as in
the Python sum()?
In this program in the first case there is an array of floats and you want to
use a real sum for max precision. In the second example there is an array of
ints, and the programmer wants to sum inside a long to avoid overflow:
import std.stdio, std.algorithm;
void main() {
float[] a1 = [1.21, 1.3, 1.4];
real s1 = reduce!q{a + b}(0.0L, a1);
writefln(%.19f, s1);
writefln(%.19f, a1.sum);
int[] a2 = [int.max, int.max, int.max];
real s2 = reduce!q{a + b}(0L, a2);
writeln(s2);
writeln(a2.sum);
}
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #17 from Andrei Alexandrescu and...@erdani.com 2013-03-12 22:14:45 PDT --- https://github.com/D-Programming-Language/phobos/pull/1205 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #16 from bearophile_h...@eml.cc 2012-04-17 14:14:24 PDT --- See also Issue 7934 for an extra improvement. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #15 from bearophile_h...@eml.cc 2011-11-25 01:04:35 PST --- A good signature for sum(): sum(sequence[, dim=0[, start]]) In Fortran's sum() 'dim' is an optional value that defaults to 0 (well to the first index of an array, that is 0 in D), it specifies what dimension to perfom the sum to. On default it acts like the Python sum(). In Fortran you often have arrays of vectors (or arrays of tuples in D), and Fortran supports vector operations similar to D ones, so: VA = [[1,2,3], [4,5,6]] sum(VA)== [5, 7, 9] sum(VA, 0) == [5, 7, 9] sum(VA, 1) == [6, 15] sum(VA, x) == Error if x 1 Example usage, points is an array of double[3] that represent 3D points: totalDistance = sqrt(sum(points[] ^^ 2, dim=0)); -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #14 from bearophile_h...@eml.cc 2011-11-24 02:39:05 PST --- In Fortran 90+ c'e' una sum(): http://www.nsc.liu.se/~boein/f77to90/a5.html#section14 I think sum() needs a specialization for things like float[4], int[4], double[4], ecc. If a float[4] is represented in a SSE register then sum(float[4]) needs just 2 sums. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #6 from bearophile_h...@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: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #7 from Andrei Alexandrescu and...@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: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #8 from bearophile_h...@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: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
David Simcha dsim...@yahoo.com changed:
What|Removed |Added
CC||dsim...@yahoo.com
--- Comment #9 from David Simcha dsim...@yahoo.com 2011-05-15 09:33:10 PDT ---
I'm going to have to agree with Bearophile on this one. Using multiple
summation variables is both faster (because it breaks some dependency chains
and uses instruction level parallelism better) and more accurate (because you
effectively have more precision). Here's a test program:
import std.stdio, std.datetime, std.random, std.range, std.traits;
// Adapted from dstats.summary.sum().
auto ilpSum(T)(T data) if(isRandomAccessRange!T) {
enum nILP = 8; // Empirically optimal on Athlon 64 X2.
Unqual!(ElementType!T)[nILP] sum = 0;
size_t i = 0;
if(data.length 2 * nILP) {
for(; i + nILP data.length; i += nILP) {
foreach(j; 0..nILP) {
sum[j] += data[i + j];
}
}
foreach(j; 1..nILP) {
sum[0] += sum[j];
}
}
for(; i data.length; i++) {
sum[0] += data[i];
}
return sum[0];
}
auto naiveSum(T)(T data) if(isRandomAccessRange!T) {
Unqual!(ElementType!T) ret = 0;
foreach(elem; data) {
ret += elem;
}
return ret;
}
void main() {
auto nums = new double[10_000_000];
foreach(ref x; nums) x = uniform(0.0, 1.0);
auto sw = StopWatch(AutoStart.yes);
auto s = naiveSum(nums);
immutable naiveTime = sw.peek.msecs;
// Printing out s to make sure the compiler doesn't optimize away the
// whole function.
writefln(naive: Sum = %s, %s milliseconds., s, naiveTime);
sw.reset();
s = ilpSum(nums);
immutable ilpTime = sw.peek.msecs;
writefln(ilp: Sum = %s, %s milliseconds., s, ilpTime);
}
Results:
naive: Sum = 4.9988e+06, 51 milliseconds.
ilp: Sum = 4.9988e+06, 33 milliseconds.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #10 from Andrei Alexandrescu and...@metalanguage.com 2011-05-15 11:36:24 PDT --- No need to teach or convince me of the virtues of ILP. We've long discussed in the newsgroup how associative operations can be significantly accelerated. I was simply replying to the implementation shown, which is a duplication of reduce. Ideally we'd capture more operation than summation in e.g. assoc_reduce. Then sum would become a simple alias. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #11 from David Simcha dsim...@yahoo.com 2011-05-15 11:53:59 PDT --- (In reply to comment #10) No need to teach or convince me of the virtues of ILP. We've long discussed in the newsgroup how associative operations can be significantly accelerated. I was simply replying to the implementation shown, which is a duplication of reduce. Ideally we'd capture more operation than summation in e.g. assoc_reduce. Then sum would become a simple alias. Great idea! When we figure hot how we want to do this, I should probably incorporate it into std.parallelism, too, since std.parallelism already assumes associativity anyhow. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #12 from Andrei Alexandrescu and...@metalanguage.com 2011-05-15 12:05:38 PDT --- Probably we need two more reduce primitives, both of which assume associativity. One uses ILP and simple loop unrolling whereas the other uses full-blown threads. There are definitely needs for each. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #13 from David Simcha dsim...@yahoo.com 2011-05-15 12:15:45 PDT --- (In reply to comment #12) Probably we need two more reduce primitives, both of which assume associativity. One uses ILP and simple loop unrolling whereas the other uses full-blown threads. There are definitely needs for each. Right. We already have the full blown threads one in std.parallelism. What I'm saying is that, if you're using threads, you're already assuming associativity. Therefore, you may as well use ILP and loop unrolling, too. std.parallelism currently doesn't do this and once we work out the details and create an assocReduce in std.algorithm, these techniques should be ported to std.parallelism.reduce, too. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 Andrei Alexandrescu and...@metalanguage.com changed: What|Removed |Added Status|NEW |ASSIGNED CC||and...@metalanguage.com AssignedTo|nob...@puremagic.com|and...@metalanguage.com -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 Denis Derman denis.s...@gmail.com changed: What|Removed |Added CC||denis.s...@gmail.com --- Comment #3 from Denis Derman denis.s...@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: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #4 from Denis Derman denis.s...@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: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725 --- Comment #5 from bearophile_h...@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: ---
[Issue 4725] std.algorithm.sum()
http://d.puremagic.com/issues/show_bug.cgi?id=4725
--- Comment #1 from bearophile_h...@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: ---
