[Issue 19705] Static foreach slow for numeric ranges

d-bugmail at puremagic.com d-bugmail at puremagic.com
Wed Feb 27 13:50:24 UTC 2019


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

Stefan Koch <uplink.coder at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |uplink.coder at gmail.com

--- Comment #1 from Stefan Koch <uplink.coder at gmail.com> ---
I can shed light on the reason, at least.
So static foreach is conceptually just syntactic sugar over tuple foreach.
As such it works in two steps 

1. Create a type-tuple from the numeric range.
2. Iterate the type-tuple.

To iterate a tuple we need to expand tuples which may be elements of the tuple
such that: tuple(1,2,3,tuple(4,5,6)) becomes tuple(1,2,3,4,5,6);
that process has to be done lazily since a tuple could be generated on the fly
to model infinite sequences.

therefore iteration over three elements would go like this 
(ResultElems[] elems;
elem[0] = iterateTuple(t); resetTuple(t);
iterateTuple(t); elems[1] = iterateTuple(t); resetTuple(t);
iterateTuple(t); iterateTuple(t); elems[2] = iterateTuple(t); resetTuple(t);
)
as you can this O(n!) (factorial)
and that's why it's slow.

Templates suffer from the same problem, and the compiler does some work to
memorize previous instances which effectively diminishes the factorial term
(it's technically still there though and can dominate if N gets large enough!)

One way to slove this is to keep tuple_expansion state when iterating/expanding
the tuple which would effectively diminish the factorial term rather well.

--


More information about the Digitalmars-d-bugs mailing list