• via Digitalmars-d-bugs (66/66) Dec 09 2016 https://issues.dlang.org/show_bug.cgi?id=16961

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=16961

          Issue ID: 16961
           Summary: Fix Algorithms to Account for ref Value Front and
                    Avoid Copying Where Unnecessary.
           Product: D
           Version: D2
          Hardware: x86
                OS: Windows
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: sprink.noreply gmail.com

Some algorithms make copies of range's "front", where a copy could be expensive
and unneeded.

For example, there is absolutely no reason to be creating a copy if front
returns by references for a comparison function "cmp()":

https://github.com/dlang/phobos/blob/v2.072.1/std/algorithm/comparison.d#L595

/////////////////////////////////////////////////////////////////////

int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2)
if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 &&
isSomeString!R2))
{
    for (;; r1.popFront(), r2.popFront())
    {
        if (r1.empty) return -cast(int)!r2.empty;
        if (r2.empty) return !r1.empty;
        auto a = r1.front, b = r2.front;
        if (binaryFun!pred(a, b)) return -1;
        if (binaryFun!pred(b, a)) return 1;
    }
}

/////////////////////////////////////////////////////////////////////

D doesn't allow generic code to be written in a way to account for both (by
value and references) so a simple wrapper would need to be used to fix this:

/////////////////////////////////////////////////////////////////////

struct Value(T)
{
    T value;
    ref T get() { return value; }
}

struct ValueRef(T)
{
    T* value;
    ref T get() { return *value; }
}

auto makeValue(T)(T v)     { return Value!T(v);    }
auto makeValue(T)(ref T v) { return ValueRef!T(&v); }


// in cmp() now:

auto a = r1.front.makeValue;
auto b = r2.front.makeValue;

if (binaryFun!pred(a.get(), b.get())) return -1;
if (binaryFun!pred(b.get(), a.get())) return 1;

/////////////////////////////////////////////////////////////////////


Not pretty but we are not likely to see an alternative fix for this using a
language feature, which would involve "ref" variables and rvalue references.

"Just use Pointers": This doesn't actually solve the problem of writing generic
code, it just shifts the burden of writing duplicate code from the library
maintainer to the user.

Implementing this will allow for truer generic functions, reducing copying
where unneeded. No need to write two separate functions to use pointers for
expensive to copy objects. As a side effect this will also allow objects which
cannot be copied to work, for algorithms which do no copying, or should not do
any copying of objects.

--