May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Monday, 25 May 2020 at 18:33:13 UTC, Andrei Alexandrescu wrote:
> On 5/25/20 12:07 PM, Stefan Koch wrote:
>> On Monday, 25 May 2020 at 16:04:24 UTC, Andrei Alexandrescu wrote:
>>> On 5/25/20 3:15 AM, Max Samukha wrote:
>>>> On Monday, 25 May 2020 at 06:18:13 UTC, FeepingCreature wrote:
>>>>
>>>>> static foreach and stringof were used so I didn't have to pull in `format` or `to!string`, which had issues in std.meta.
>>>>>
>>>>> I'm seeing some improvement over 2.086 at least; it should be about equivalent to the hand-unrolled version in master.
>>>>
>>>> How could you miss the state-of-the-art?) Preallocate the result string and use the string counter hack!
>>>> http://dpldocs.info/this-week-in-d/Blog.Posted_2020_05_11.html#dmd-and-static-foreach
>>>>
>>>
>>> static foreach is quadratic? Is this a matter of principle, or QoI?
>>
>> Yes it is.
>> I did present this fact at the pre-event to Dconf 2018.
>>
>> As for your other question it's both. The QoI is not stellar.
>> But it is fundamentally limited by having to create independent scopes.
>
> How do you mean that? static foreach does not create a scope.
The scope I am talking about is what dmd calls Scope.
This has to do with compiler internals.
static foreach has a manifest variable as IV.
That means it introduces a static name.
That name for example I has to resolve to a different value on every iteration.
This violates the rules of the language outside of static foreach.
Therefore the a construct has to be introduces which allows special behavior
inside a foreach body.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On Monday, 25 May 2020 at 17:34:36 UTC, Timon Gehr wrote:
> On 25.05.20 19:25, Stefan Koch wrote:
>> On Monday, 25 May 2020 at 17:23:50 UTC, Timon Gehr wrote:
>>> [...]
>>
>> Since Forwarding scopes where not in the language before you introduced static if.
>> Could you give a quick explanation how they work?
>>
>
> It's a scope that forwards new symbols to its parent scope on insertion. This way, each iteration of the `static foreach` will have its own local scope with distinct loop variables, but any declarations that are generated in the `static foreach` body will skip this scope and instead populate the parent scope. (As an experiment, the original implementation also had `__local` declarations to insert symbols into the local scope without forwarding.)
Thank a lot for the explanation!
I was wondering about this for a while.
That's a clever solution.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On Monday, 25 May 2020 at 17:34:36 UTC, Timon Gehr wrote:
> (As an experiment, the original implementation also had `__local` declarations to insert symbols into the local scope without forwarding.)
That would actually be really useful in some places. Like
static foreach(memberName; __traits(allMembers, f)) {
__local alias member = __traits(getMember, f, memberName);
}
Though of course it is also possible to do such with staticMap in places.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Max Samukha | On Monday, 25 May 2020 at 17:08:32 UTC, Max Samukha wrote:
> Precalculated length is Adam's
I stole it from Stefan too IIRC.
The way I see it, it is all just D community knowledge. A lot of the things I know just come from helping other users through their problems too - they point out something that is cool or is broken and by working on it together we both learn.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Stefan Koch | On Monday, 25 May 2020 at 15:59:43 UTC, Stefan Koch wrote:
> The dmd used is at commit 2f23e3348e9a927c025637a4852d4d77beb997d3
> which is on manu's fork of the compiler.
Does that include the other shortcut prs? I wonder if they would further open or close the gap
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Adam D. Ruppe | On Monday, 25 May 2020 at 20:47:42 UTC, Adam D. Ruppe wrote:
> On Monday, 25 May 2020 at 17:34:36 UTC, Timon Gehr wrote:
>> (As an experiment, the original implementation also had `__local` declarations to insert symbols into the local scope without forwarding.)
>
> That would actually be really useful in some places. Like
>
> static foreach(memberName; __traits(allMembers, f)) {
> __local alias member = __traits(getMember, f, memberName);
> }
>
> Though of course it is also possible to do such with staticMap in places.
you want type functions :)
What you are doing there works by default since declarations are temporary.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Adam D. Ruppe | On Monday, 25 May 2020 at 20:57:07 UTC, Adam D. Ruppe wrote:
> On Monday, 25 May 2020 at 15:59:43 UTC, Stefan Koch wrote:
>> The dmd used is at commit 2f23e3348e9a927c025637a4852d4d77beb997d3
>> which is on manu's fork of the compiler.
>
> Does that include the other shortcut prs? I wonder if they would further open or close the gap
Open it I suspect.
The `...` version would be around 20x faster if it could create the new sequence as one thing.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Adam D. Ruppe | On 5/25/2020 6:27 AM, Adam D. Ruppe wrote:
> Using dmd master: 1.8s 1.2G
> Using released dmd: 2.1s, 1.1G
A 15% speed win is a big deal! Especially for such a simple change.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 5/25/2020 9:46 AM, Timon Gehr wrote:
> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
>
> The implementation of `static foreach` in DMD is based on lowering, and the existing "tuple" foreach implementation. I suspect the culprit for bad performance for very large `static foreach` is a slow expression "tuple" implementation, but I am not sure.
> Therefore, maybe performance could be improved by modifying the foreach expansion code such that it can accept a CTFE array instead of an expression tuple. One could also add a special-case implementation for range `static foreach` to work around inefficient CTFE.
This is worth looking in to. I've had customers tell me they don't use static foreach due to performance problems.
|
May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | On Monday, 25 May 2020 at 21:25:33 UTC, Walter Bright wrote:
> On 5/25/2020 6:27 AM, Adam D. Ruppe wrote:
>> Using dmd master: 1.8s 1.2G
>> Using released dmd: 2.1s, 1.1G
>
> A 15% speed win is a big deal! Especially for such a simple change.
How much of a deal is 100% ? Enough to talk about including ... ?
|
Copyright © 1999-2021 by the D Language Foundation