digitalmars.D - Making recursively-defined traits iterative using `static foreach`
- =?UTF-8?B?Tm9yZGzDtnc=?= (46/46) Mar 10 2018 Now that we have `static foreach` I just realized we can start
- =?UTF-8?B?Tm9yZGzDtnc=?= (8/12) Mar 10 2018 Perhaps even better to do
- =?UTF-8?B?Tm9yZGzDtnc=?= (30/32) Mar 10 2018 My recent definition now looks like
- =?UTF-8?B?Tm9yZGzDtnc=?= (15/47) Mar 10 2018 After benchmarking using
- Simen =?UTF-8?B?S2rDpnLDpXM=?= (14/46) Mar 10 2018 Sure:
- =?UTF-8?B?Tm9yZGzDtnc=?= (2/17) Mar 10 2018 That will trigger CTFE, but I'm trying to avoid that.
Now that we have `static foreach` I just realized we can start
making recursive implementations of traits such as
template allSame(V...)
if (isExpressions!V)
{
static if (V.length <= 1)
{
enum allSame = true;
}
else static if (V.length & 1) // odd count
{
enum allSame = (V[0] == V[$ - 1] &&
V[0 .. $/2] == V[$/2 .. $-1]
allSame!(V[0 .. $/2]));
}
else // event count
{
enum allSame = (V[0 .. $/2] == V[$/2 .. $]
allSame!(V[0 .. $/2]));
}
}
iterative as
template allSameIterative(V...)
{
static if (V.length <= 1)
{
enum allSameIterative = true;
}
else
{
static foreach (Vi; V[1 .. $])
{
static if (V[0] != Vi)
{
enum allSameIterative = false;
}
}
static if (!is(typeof(allSameIterative) == bool)) // if
not yet defined
{
enum allSameIterative = true;
}
}
}
Is this preferred, typically in terms of compile-time memory
usage and speed?
Mar 10 2018
=?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com>
On Saturday, 10 March 2018 at 09:47:55 UTC, Nordlöw wrote:
static if (V[0] != Vi)
{
enum allSameIterative = false;
}
Perhaps even better to do
static if (!is(typeof(allSameIterative) == bool) &&
// not yet defined
V[0] != Vi)
{
enum allSameIterative = false;
}
Mar 10 2018
On Saturday, 10 March 2018 at 09:47:55 UTC, Nordlöw wrote:Now that we have `static foreach` I just realized we can start...My recent definition now looks like template allSameTypeIterative(V...) // TODO restrict `V` to types only { static if (V.length <= 1) { enum allSameTypeIterative = true; } else { static foreach (Vi; V[1 .. $]) { static if (!is(typeof(allSameTypeIterative) == bool) && // not yet defined !is(V[0] == Vi)) // 10% faster than `!isSame(V[0], Vi)` { enum allSameTypeIterative = false; } } static if (!is(typeof(allSameTypeIterative) == bool)) // if not yet defined { enum allSameTypeIterative = true; } } } Is there a way to break the `static foreach` loop prematurely as quickly as `allSameTypeIterative` becomes false?
Mar 10 2018
On Saturday, 10 March 2018 at 13:30:18 UTC, Nordlöw wrote:On Saturday, 10 March 2018 at 09:47:55 UTC, Nordlöw wrote:After benchmarking using https://github.com/nordlow/phobos-next/blob/master/benchmarks/iterative-traits/source/app.d the iterative-version speed-up ranges from 1.1 to 10x for my specific sets of input. The higher speed-up is thanks to - reducing the template instantiation count from log(n), in the recursive case, to 1 in iterative case and - a static if loop that prevents successive calls when, for instance, - predicate is true in `anySatisfyIterative and - predicate is false in `allSatisfyIterative and At https://github.com/nordlow/phobos-next/blob/master/benchmarks/iterative-traits/source/app.d the compilation-times are written in the comments for each kind of benchmark.Now that we have `static foreach` I just realized we can start...My recent definition now looks like template allSameTypeIterative(V...) // TODO restrict `V` to types only { static if (V.length <= 1) { enum allSameTypeIterative = true; } else { static foreach (Vi; V[1 .. $]) { static if (!is(typeof(allSameTypeIterative) == bool) && // not yet defined !is(V[0] == Vi)) // 10% faster than `!isSame(V[0], Vi)` { enum allSameTypeIterative = false; } } static if (!is(typeof(allSameTypeIterative) == bool)) // if not yet defined { enum allSameTypeIterative = true; } } } Is there a way to break the `static foreach` loop prematurely as quickly as `allSameTypeIterative` becomes false?
Mar 10 2018
On Saturday, 10 March 2018 at 13:30:18 UTC, Nordlöw wrote:On Saturday, 10 March 2018 at 09:47:55 UTC, Nordlöw wrote:Sure: property bool allSameTypeIterative(V...)() //if (allSatisfy!(isType, V)) { foreach (Vi; V) if (Vi != V[0]) return false; return true; } No, it's not quite the same, but it's easier to read and gives the same result. -- SimenNow that we have `static foreach` I just realized we can start...My recent definition now looks like template allSameTypeIterative(V...) // TODO restrict `V` to types only { static if (V.length <= 1) { enum allSameTypeIterative = true; } else { static foreach (Vi; V[1 .. $]) { static if (!is(typeof(allSameTypeIterative) == bool) && // not yet defined !is(V[0] == Vi)) // 10% faster than `!isSame(V[0], Vi)` { enum allSameTypeIterative = false; } } static if (!is(typeof(allSameTypeIterative) == bool)) // if not yet defined { enum allSameTypeIterative = true; } } } Is there a way to break the `static foreach` loop prematurely as quickly as `allSameTypeIterative` becomes false?
Mar 10 2018
On Saturday, 10 March 2018 at 18:26:48 UTC, Simen Kjærås wrote:That will trigger CTFE, but I'm trying to avoid that.Is there a way to break the `static foreach` loop prematurely as quickly as `allSameTypeIterative` becomes false?Sure: property bool allSameTypeIterative(V...)() //if (allSatisfy!(isType, V)) { foreach (Vi; V) if (Vi != V[0]) return false; return true; } No, it's not quite the same, but it's easier to read and gives the same result. -- Simen
Mar 10 2018