Needlessly large instantiation depth in std.typetuple algorithms

[dlangBugzillaToGithub]

khurshid.normuradov reported this on 2013-04-21T22:25:01Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=9976

CC List

• andrej.mitrovich (@AndrejMitrovic)
• code (@MartinNowak)
• greensunny12
• zorael

Description

Created attachment 1210
test staticMap algorithm

More compile time algorithms (as, staticIndexOf, staticMap, EraseAll,
NoDuplicates, etc) - implemented as recursion. But this implementation need
deep recursion. So I had test  staticMap with more 500 arguments. It's not
compiled with normal configuration of dmd . After that I rewrite own staticMap2
with little change:

template staticMap2(alias F, T...)
{
   static if (T.length == 0)
   {
       alias TypeTuple!() staticMap2;
   } else static if (T.length == 1)
   {
       alias TypeTuple!(F!(T[0])) staticMap2;
   } else {
      alias TypeTuple!( staticMap2!(F, T[0..$/2]), staticMap2!(F,T[$/2..$]))
staticMap2 ;
}


And this variant compiled more than 32768 arguments.

For small arguments both version compiled almost the same time.

Which opinion is on this matter?


-------------------------------
test program is attachment.
---------------------------------

!!!There are attachements in the bugzilla issue that have not been copied over!!!

[dlangBugzillaToGithub]

k.hara.pg commented on 2013-04-21T23:25:56Z

https://github.com/D-Programming-Language/phobos/pull/1271

[dlangBugzillaToGithub]

github-bugzilla commented on 2013-04-22T10:18:48Z

Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/43d1196c0701103f3e666ec4282055d7ed407be9
fix Issue 9976 - more compile time algorithms implementation used deep recursion

Reduce instantiation depth in staticMap, allSatisfy, anySatisfy, and Filter.

https://github.com/D-Programming-Language/phobos/commit/cf3a3ee0a5cc7f7ed3f9e6ced31ea5d004f8df14
Merge pull request #1271 from 9rnsr/fix9976

Issue 9976 - more compile time algorithms implementation used deep recursion

[dlangBugzillaToGithub]

code (@MartinNowak) commented on 2013-04-22T10:24:03Z

I hope you didn't work on a pull request as well; Kenji was fast(er), as usual.

If you have additional suggestions, feel free to reopen the issue or post a new one.

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-04-23T00:27:06Z

(In reply to comment #3)
> I hope you didn't work on a pull request as well; Kenji was fast(er), as usual.
> 
> If you have additional suggestions, feel free to reopen the issue or post a new
> one.

Yes, I am first time here.

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-04-23T00:36:32Z

And this :))

template Reverse(TList...)
{
    static if (TList.length <= 1 )
		alias TList Reverse;
    else 
        alias TypeTuple!( TList[$-1], Reverse!(TList[1..$-1]), TList[0]) Reverse;
    
}

:)))

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-04-23T01:05:52Z

(In reply to comment #5)
> And this :))
> 
> template Reverse(TList...)
> {
>     static if (TList.length <= 1 )
>         alias TList Reverse;
>     else 
>         alias TypeTuple!( TList[$-1], Reverse!(TList[1..$-1]), TList[0])
> Reverse;
> 
> }
> 
> :)))

or 

template Reverse (TList...)
{
	static if (TList.length <= 1 )
	{
		alias Reverse  = TList;
	} else {
		alias Reverse  = TypeTuple!( Reverse !(TList[$/2..$]) , Reverse!(TList[0..$/2]));
	}
}

[dlangBugzillaToGithub]

k.hara.pg commented on 2013-04-23T22:42:50Z

(In reply to comment #5)
> And this :))
> 
> template Reverse(TList...)
[snip]

https://github.com/D-Programming-Language/phobos/pull/1274

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-04-23T23:18:33Z

(In reply to comment #7)
> (In reply to comment #5)
> > And this :))
> > 
> > template Reverse(TList...)
> [snip]
> 
> https://github.com/D-Programming-Language/phobos/pull/1274

Thanks, Kenji Hara.

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-04-24T01:18:55Z

I'm not sure, but, is this right?

template MostDerived(T, TList...)
{
    static if (TList.length == 0)
    {
       alias MostDerived = T;
    }
    else static if (TList.length == 1 )
    {
         static if (is (TList[0] : T) )
         { 
             alias  MostDerived = TList[0];
         }
         else
         {
             alias MostDerived = T;
         }
    }
    else
    {
       alias Half = MostDerived!(T, TList[0..$/2]);
       alias MostDerived = MostDerived!(Half, TList[$/2..$]);
    }
}

[dlangBugzillaToGithub]

github-bugzilla commented on 2013-05-31T18:55:57Z

Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/d3df489171890ccdd73708a3edfa047efa01c4d2
fix Issue 9976 - Needlessly large instantiation depth in std.typetuple algorithms

https://github.com/D-Programming-Language/phobos/commit/69f5377acd873301fd9f7cd742e9229050bb4342
Merge pull request #1274 from 9rnsr/fix9976

Apply ddoc-ed unittest feature in std.typetuple, and fix issue 9976

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2013-05-31T18:57:43Z

(In reply to comment #9)
> I'm not sure, but, is this right?
> 
> template MostDerived(T, TList...)

Is this the last one left? Someone should make a pull for it.

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-06-14T06:30:59Z

(In reply to comment #11)
> (In reply to comment #9)
> > I'm not sure, but, is this right?
> > 
> > template MostDerived(T, TList...)
> 
> Is this the last one left? Someone should make a pull for it.

Not only this, I think that all following algorithms can easily change, too:
1. DerivedToFront
2. MostDerived
3. ReplaceAll        which used GenericReplaseAll
4. Replace           which used GenericReplace
5. NoDuplicates     
6. EraseAll          which used GenericEraseAll
7. Erase             which used GenericErase
8. staticIndexOf     which used genericIndexOf

Need only little think :-)

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2013-06-14T08:32:01Z

(In reply to comment #12)
> 8. staticIndexOf     which used genericIndexOf

I've reported about this before:
http://forum.dlang.org/thread/mailman.1418.1346015010.31962.digitalmars-d@puremagic.com

http://forum.dlang.org/thread/CAJ85NXA3F5se9hv3iA80hyQbwXBuP-ffon6ay=AXG+E11sicdw@mail.gmail.com

A speedup would be very welcome.

[dlangBugzillaToGithub]

khurshid.normuradov commented on 2013-06-14T11:22:03Z

(In reply to comment #13)
> (In reply to comment #12)
> > 8. staticIndexOf     which used genericIndexOf
> 
> I've reported about this before:
> http://forum.dlang.org/thread/mailman.1418.1346015010.31962.digitalmars-d@puremagic.com
> 
> http://forum.dlang.org/thread/CAJ85NXA3F5se9hv3iA80hyQbwXBuP-ffon6ay=AXG+E11sicdw@mail.gmail.com
> 
> A speedup would be very welcome.

I've reported also, today :-). 

http://forum.dlang.org/thread/xwzivolcokzulonslkbq@forum.dlang.org

I think that need implement all linear algorithms   with "bisection" principle  as above , instead of "head/tail" principle.