www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9582] New: std.algorithm.map!(T) cause CT error for fixed size arrays

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582

           Summary: std.algorithm.map!(T) cause CT error for fixed size
                    arrays
           Product: D
           Version: D2
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: marmyst gmail.com


--- Comment #0 from Marcin Mstowski <marmyst gmail.com> 2013-02-24 06:43:45 PST
---
void main() {
  float[5] smt = [0, 1, 2, 4, 100];
  auto ms = map!"a*a"(smt);
}

DMD 2.062 gives: 

dmd test.d
test.d(5): Error: template std.algorithm.map!("a*a").map does not match any
function template declaration. Candidates are:
..\..\src\phobos\std\algorithm.d(379):       
std.algorithm.map!("a*a").map(Range)(Range r) if
(isInputRange!(Unqual!(Range)))
test.d(5): Error: template std.algorithm.map!("a*a").map(Range)(Range r) if
(isInputRange!(Unqual!(Range))) cannot deduce template function from argument
types!()(float[5u])

Dynamic arrays for map!T and reduce!T with static arrays (not tested for others
functions) compile without problem.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 24 2013
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc


--- Comment #1 from bearophile_hugs eml.cc 2013-02-24 07:31:48 PST ---
(In reply to comment #0)

 void main() {
   float[5] smt = [0, 1, 2, 4, 100];
   auto ms = map!"a*a"(smt);
 }

Only certain higher order functions of Phobos work with fixed-sized arrays: import std.algorithm: reduce; void main() { float[5] smt = [0, 1, 2, 4, 100]; assert(reduce!"a+b"(smt) == 107); // OK. } So probably this bug report should be closed. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582


Peter Alexander <peter.alexander.au gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au gmail.co
                   |                            |m


--- Comment #2 from Peter Alexander <peter.alexander.au gmail.com> 2013-02-24
08:08:11 PST ---
This is by design. map expects an input range. Static arrays are not input
ranges. You have to take a slice.

auto ms = map!"a*a"(smt[]); // note additional []

reduce only requires an iterable, which includes static arrays.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra gmail.com


--- Comment #3 from monarchdodra gmail.com 2013-02-24 08:11:52 PST ---
(In reply to comment #2)
 This is by design. map expects an input range. Static arrays are not input
 ranges. You have to take a slice.
 
 auto ms = map!"a*a"(smt[]); // note additional []
 
 reduce only requires an iterable, which includes static arrays.

...and this is good example of why accepting an "iterable" as a function argument, as opposed to a range, is usually a bad idea. As for reduce accepting iterable, Andrei asked me to remove it in one of my open requests, so don't expect it keep working for too long. https://github.com/D-Programming-Language/phobos/pull/861#discussion_r2024457 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #4 from Peter Alexander <peter.alexander.au gmail.com> 2013-02-24
08:16:44 PST ---
(In reply to comment #3)
 ...and this is good example of why accepting an "iterable" as a function
 argument, as opposed to a range, is usually a bad idea.
 
 As for reduce accepting iterable, Andrei asked me to remove it in one of my
 open requests, so don't expect it keep working for too long.
 
 https://github.com/D-Programming-Language/phobos/pull/861#discussion_r2024457

std.array.array also accepts iterables. I think array and reduce are the only two. Removing these is going to break a lot of code though. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #5 from monarchdodra gmail.com 2013-02-24 08:21:49 PST ---
(In reply to comment #4)
 (In reply to comment #3)
 ...and this is good example of why accepting an "iterable" as a function
 argument, as opposed to a range, is usually a bad idea.
 
 As for reduce accepting iterable, Andrei asked me to remove it in one of my
 open requests, so don't expect it keep working for too long.
 
 https://github.com/D-Programming-Language/phobos/pull/861#discussion_r2024457

std.array.array also accepts iterables. I think array and reduce are the only two. Removing these is going to break a lot of code though.

For array, probably. For reduce, probably much less. I think ideally, we should accept "isNonStaticArrayItterable": The idea of "isIterable" is to accept stuff that is either a range, or has opApply. Static arrays, while being iterable, shouldn't be passed around by value to functions. I think there'd be gains in the long run to such a scheme. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #6 from bearophile_hugs eml.cc 2013-02-24 08:52:34 PST ---
(In reply to comment #3)

 As for reduce accepting iterable, Andrei asked me to remove it in one of my
 open requests, so don't expect it keep working for too long.

I am strongly against this breaking change. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #7 from bearophile_hugs eml.cc 2013-02-24 13:49:05 PST ---
(In reply to comment #6)

 I am strongly against this breaking change.

Sorry, that came out too much strong... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #8 from monarchdodra gmail.com 2013-02-24 13:59:12 PST ---
(In reply to comment #7)
 (In reply to comment #6)
 
 I am strongly against this breaking change.

Sorry, that came out too much strong...

Don't worry about it, I didn't even perceive anything that could be offensive. Can you elaborate on the "why" though? Is it just because it would be "breaking change", or do you have a use case that warrants its being in there in the first place (more so than any algorithm I mean)? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #9 from bearophile_hugs eml.cc 2013-02-24 14:40:31 PST ---
(In reply to comment #8)

 Can you elaborate on the "why" though? Is it just because it would be "breaking
 change", or do you have a use case that warrants its being in there in the
 first place (more so than any algorithm I mean)?

I have a good amount of functional-style D2 code with hundreds of usages of reduce. And in D I use fixed-sized arrays all the time to reduce heap activity, so probably this change will require me some fixes in my code, to add the []. I don't like this change in principle, because I like fixed-size arrays, I use them all the time, and I think they should be more first class in Phobos. I'd like more Phobos functions to work with fixed size arrays, not less functions. Also, reduce() doesn't return part of the input, it creates a new output, so it the code that uses the result of reduce() doesn't need to care what reduce() was fed with. The same is true for array(). I think reduce() and array() should also work on opApply, for maximum flexibility. The higher order functions of my D1 nonstandard library accepted both kinds of arrays, and even associative arrays as inputs. I prefer more flexibility. And I think that forcing everything inside the mindframe of Ranges is a not a good idea. Iteration life is more complex: http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/ In past I have asked one small changes in Phobos that was closed down because despite it being handy and useful, it was a small breaking change. Forbidding fixed size arrays as reduce inputs _reduces_ flexibility, and it's a larger breaking change. In the end I am probably able to add the missing [] to my D2 code in a matter of one or two hours (or less) so for me this change doesn't require me a lot of work to fix. So I leave the decision to you. ---------------
 Static arrays, while being iterable, shouldn't be passed around by

Let's say I have this fixed-sized array: int[3] items = [1, 2, 3]; and I want to compute its sum: reduce!q{a + b}(items) In this case ideally I'd like the D compiler to replace that call to reduce with the same ASM as items[0] + items[1] + items[2] This means the compiler has some compile-time information (the array length) that in theory (and in practice too if the code is well written and you are using a GCC back-end that is able to unroll small loops) is usable to produce full optimized code. If I have to write: reduce!q{a + b}(items[]) Then we have lost something, the reduce() can't know at compile-time the length of the array, so performing loop unrolling becomes harder (the JavaVM is able to partially unroll the loop in this case too, but LLVM was not able to do it since the latest version, and even now it's not perfect). Throwing away some compile-time information seems a bad idea to me. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #10 from monarchdodra gmail.com 2013-02-24 15:41:59 PST ---
(In reply to comment #9)
 In the end I am probably able to add the missing [] to my D2 code in a matter
 of one or two hours (or less) so for me this change doesn't require me a lot of
 work to fix. So I leave the decision to you.

I'm not that passionate on the issue. I think treating static arrays as ranges in the first place wasn't the best idea. I mean, if your code didn't compile in the first place, you would have probably called it with arr[] and not have though about it much more. I also agree that working on things with opApply adds useability, such as for std.array.array. How ever, I don't think it warrants passing a static array by value, and creating a template instance per array size.
 Static arrays, while being iterable, shouldn't be passed around by

Let's say I have this fixed-sized array: int[3] items = [1, 2, 3]; and I want to compute its sum: reduce!q{a + b}(items) In this case ideally I'd like the D compiler to replace that call to reduce with the same ASM as items[0] + items[1] + items[2] This means the compiler has some compile-time information (the array length) that in theory (and in practice too if the code is well written and you are using a GCC back-end that is able to unroll small loops) is usable to produce full optimized code. If I have to write: reduce!q{a + b}(items[]) Then we have lost something, the reduce() can't know at compile-time the length of the array, so performing loop unrolling becomes harder (the JavaVM is able to partially unroll the loop in this case too, but LLVM was not able to do it since the latest version, and even now it's not perfect). Throwing away some compile-time information seems a bad idea to me.

But the way I see it, your argument is that loop unrolling justifies copying an entire array. I'm not really sure it is. Can you honestly tell me that when you wrote "reduce(myArray)", you realized you were passing it by value? Furthermore, is the performance gain *also* worth the template bloat, since you are instantiating 1 reduce algorithm per array *size*. C++ could do this, but it doesn't. Ever. And C++ is dead serious about squeezing every last ounce of performance it can, algorithm wise. The ideal solution would be one akin to cycle: A specialized overload that takes static arrays by reference. You get your cheap pass by ref, but also keep your compile time info. But still, that is a *very* specific use case, with a code deployment cost, and shouldn't be used many other things. So my conclusion is that: Yes, for useability reason, taking an iterable is good. However, for the sake of arguments accepted, I don't think a static array should be considered an iterable, and the caller should be expected to slice it. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 24 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9582



--- Comment #11 from bearophile_hugs eml.cc 2013-02-24 16:11:10 PST ---
(In reply to comment #10)

 But the way I see it, your argument is that loop unrolling justifies copying an
 entire array.

If your array is a ubyte[6] then I think copying it is OK, otherwise it's better to take the fixed size array by reference.
 Furthermore, is the performance gain *also* worth the template bloat,
 since you are instantiating 1 reduce algorithm per array *size*.

The compile-time knowledge of the array length gives a performance advantage for small arrays only, that's why I have used a items int[3] in my example. A way to keep the template bloat low is to introduce a limit of the length with a template constraint: import std.stdio; void foo(T, size_t N)(ref T[N] items) if (N < 10) { writeln("foo 1"); } void foo(T)(T[] items) { writeln("foo 2"); } void main() { int[3] a1; int[20] a2; int[] a3; foo(a1); foo(a2); foo(a3); } Prints: foo 1 foo 2 foo 2 (There is another way to solve this problem, but I think it requires a small improvement of D language (it's an idea to help reduce the template bloat in some situations, like with fixed size arrays), but while you design reduce() you can't assume such change, that currently is not even written in a bugzilla enhancement request entry.)
 The ideal solution would be one akin to cycle: A specialized overload that
 takes static arrays by reference. You get your cheap pass by ref, but also keep
 your compile time info.
 
 But still, that is a *very* specific use case, with a code deployment cost, and
 shouldn't be used many other things.

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