Incredibly slow type-level Nub

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Incredibly slow type-level Nub

Nickolay Kudasov
Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Incredibly slow type-level Nub

Richard Eisenberg-2
If you have a practical example of where GHC's current type-level reduction machinery is too slow, please post a bug report. We have only a few real examples of this, and so GHC's implementation is tuned for those examples. With more examples, we can tune more widely.

Thanks!
Richard

On Feb 7, 2016, at 8:37 AM, Nickolay Kudasov <[hidden email]> wrote:

Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Incredibly slow type-level Nub

Roel van Dijk-3
In reply to this post by Nickolay Kudasov
Hi Nickolay,

I'm not sure why your version was *that* slow. But the algorithm was not optimal. I translated the Haskell Report prelude version of nub to the type level. That version compiles instantly with the long list. I tested with GHC 7.10.2.

https://gist.github.com/roelvandijk/f115c6b85a3961e1b689

Regards,
Roel

2016-02-07 14:37 GMT+01:00 Nickolay Kudasov <[hidden email]>:
Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Incredibly slow type-level Nub

Nickolay Kudasov
Roel, thanks, your solution works perfectly for me! I should've checked that implementation myself.

Richard, since Roel's solution works for me, I think I should not file this.

I think type-list [1] is the place on Hackage for list-related type-level functions.
I probably should send a PR adding Roel's Nub there.

Thanks for your help!
Nick


On Sun, 7 Feb 2016 at 18:24 Roel van Dijk <[hidden email]> wrote:
Hi Nickolay,

I'm not sure why your version was *that* slow. But the algorithm was not optimal. I translated the Haskell Report prelude version of nub to the type level. That version compiles instantly with the long list. I tested with GHC 7.10.2.

https://gist.github.com/roelvandijk/f115c6b85a3961e1b689

Regards,
Roel


2016-02-07 14:37 GMT+01:00 Nickolay Kudasov <[hidden email]>:
Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Incredibly slow type-level Nub

Dmitry Olshansky
In reply to this post by Nickolay Kudasov
I suppose that a problem is with "non-lazy type-level If". 
This was discussed here. And there is a ticket with workaround.

Best regards,
Dmitry

2016-02-07 16:37 GMT+03:00 Nickolay Kudasov <[hidden email]>:
Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Incredibly slow type-level Nub

Dmitry Olshansky
In reply to this post by Nickolay Kudasov
Hello,

I wonder if singletons library doesn't satisfy your requrements? Did you look at this opportunity? Here is a Nub implementation.

I am particulary interested in this because I am checking now this library for usung it in my project. Had you some reasons to refuse it?

Best regards,
Dmitry

2016-02-07 16:37 GMT+03:00 Nickolay Kudasov <[hidden email]>:
Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Incredibly slow type-level Nub

Nickolay Kudasov
Dmitry,

Well, actually, I was not aware that singletons provide this functionality!

From what I see singletons seem to be an overkill for my use case.

Thanks for the hint though, I will look into singletons more to see if it fits the bill.

Kind regards,
Nick

On Mon, 8 Feb 2016 at 13:21 Dmitry Olshansky <[hidden email]> wrote:
Hello,

I wonder if singletons library doesn't satisfy your requrements? Did you look at this opportunity? Here is a Nub implementation.

I am particulary interested in this because I am checking now this library for usung it in my project. Had you some reasons to refuse it?

Best regards,
Dmitry

2016-02-07 16:37 GMT+03:00 Nickolay Kudasov <[hidden email]>:
Dear Cafe,

I have faced a type-level performance problem (with GHC 7.10.3).
I am trying to implement type-level Nub which removes duplicates from a type-level list.

My implementation [1] with an example of a list of length 20 takes forever to compile. If you reduce the size of the example list (e.g. to 15 items), it will compile faster. Also, if you remove the Nub application from exampleVals, it compiles instantly (this is how I know the problem is in Nub).

My question is how can I speed up type-level Nub?
And less importantly why exactly is it this slow?

The practical application for this is building automatic tests [2] for servant-swagger. There I am interested in generating exactly one test for each distinct type.

Kind regards,
Nick


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe