search

elm-community / list-extra

Convenience functions for working with List.
http://package.elm-lang.org/packages/elm-community/list-extra/latest
MIT License
135 stars 58 forks source link

Optimize List.Extra#last #90

Closed zwilias closed 6 years ago

zwilias commented 6 years ago

While the foldl1 solution was clever, it was also relatively slow. A simple, obvious and recursive solution is a bunch faster (same time complexity, but less overhead).

In my mind, since list-extra is such an extremely widely used package, it should never be too clever nor slow. Since depending on this package in a library is also a pretty risky affair, since the risk of dependency conflicts is pretty high, it seems like a good idea to try and have functions that are self-contained for easier extraction.

https://ellie-app.com/dVhMTzvGda1/0 for benchmarks against the current implementation.

On my machine, that's 470% increase for empty list, 1350% increase for 100 elements and 1266% increase for 10000 elements.

Chadtech commented 6 years ago

Awesome! I just ran the bench marks and I am seeing similar gains. Its really cool seeing how this optimizations work. Thanks for PRing.

Chadtech commented 6 years ago

Also, what do you mean by "it seems like a good idea to try and have functions that are self-contained"? I dont understand that part.

zwilias commented 6 years ago

If someone is writing a package, depending on list-extra is a risk. The most common dependency conflict I see is 2 dependencies requiring different version of list-extra. Most packages only need one or 2 functions from this package, in my experience, so in that case it pays off to either write an implementation from scratch or copy paste it from this library.

So, with self-contained, I mean that making it easy to copy paste just a single function from this library, makes life of package writers a bunch easier. It's somewhat counterintuitive to try and write a package like this without internal function reuse, but I do believe it is valuable. Does that make sense?