Comments (12)
Tracking down stack overflows is difficult and they have a tendency to happen in production since that's when the program deals with largest amounts of data
Stack safety vs Performance.
- I do agree that it's much easier to track down performance issues as opposed to runtime stack overflows.
- I rather have slow lib, and optimize when necessary, as opposed to TCO unsafe.
Actually I am concerned about these functions; iterate
and unfold
.
- they crash on 5000+ element list
- On search I found this issue,
- Let me know if I should open another issue for the same.
from list-extra.
This is unfoldr
currently:
unfoldr : (b -> Maybe ( a, b )) -> b -> List a
unfoldr f seed =
case f seed of
Nothing ->
[]
Just ( a, b ) ->
a :: unfoldr f b
I think this is a stack safe version (untested):
unfoldr : (b -> Maybe ( a, b )) -> b -> List a
unfoldr f seed =
unfoldrHelp f seed [] |> List.reverse
unfoldrHelp : (b -> Maybe ( a, b )) -> b -> List a -> List a
unfoldrHelp f seed acc =
case f seed of
Just ( a, b ) ->
unfoldrHelp f b (a :: acc)
Nothing ->
acc
from list-extra.
This is an interesting discussion to have. Ultimately, the decision comes down to whether we want to prioritize making the implementations 100% safe or if we want them to be as fast as possible.
On the one hand, having a guarantee that this library will never cause your app to crash is a strong statement, particularly in Elm. It is also very unlikely that whatever performance degradation this may cause would have any noticeable impact on real-world apps due to overwhelming cost of DOM manipulations.
On the other hand, most non-TCO functions will only break for lists of more than 5k-10k elements, which is quite a lot. I can't remember ever needing a list that large in Elm (although I'm sure other folks have their use-cases). An argument could be made that if you are using lists that are that large then you should consider using a more appropriate data structure.
Note that there is a middle-ground. It is possible to start off with the faster, non-TCO implementation and then switch to the TCO implementation after processing X elements (for some constant X around 3k). This is how take
(see elm-lang/core#668) and likely the v0.19 foldr
(see elm-lang/core#872) are implemented in core. I tried this approach for a few functions in this library, like updateAt
and removeAt
, but they actually performed worse than the current implementations 🤷♂️.
from list-extra.
I think the elm ecosystem should prefer working and stable implementations. If this library is not meant to be very stable there should be a warning and it probably can't be used in production.
This commit is interesting. It solves the same potential problem in elm-lang/core
.
from list-extra.
Personally, I agree with you that everything should be stack-safe, but I do not think it is as simple a decision as you are making it out to be.
Let me play devil's advocate for a minute. Saying that "the library is not stable" or that "it can't be used in production" for this reason is a pretty gross exaggeration. OCaml's standard library, for example, is not entirely stack-safe, yet people still use it! (Obviously, this is a bit different for Elm, which prioritizes no runtime exceptions.) I estimate that we would be harming performance in over 99% of use-cases just for the handful of cases where people are using lists of several thousand items. At the very least, I agree that if we choose to leave things as they are, we should add warnings to the documentation on all of the non-TCO functions.
Again, my vote is in favor of making everything stack-safe, but I do think it is important to consider the consequences of this decision. @Chadtech Would you like to weigh in?
from list-extra.
I agree with @pzp1997 's devil's advocate point. JavaScript isnt stack safe, and I am not ready to concede that production ready code isnt possible in JavaScript.
I dont have a general opinion on the priority of stack safety, and I dont see making that a priority ex-ante to be a practical approach.
Anyway, @andys8, if you make PRs with stack safe versions of these functions, and you can demonstrate that they perform at least as well in other regards, then I think we should accept those changes. If there is a trade-off, we should have a discussion about it, and I think the answer to that discussion would come from contrasting real examples of how we use these functions and whether or not stack safety or speed are really beneficial.
from list-extra.
I get the point. It bring's us to the interesting question: If we want to find a compromise - how much better has the performance to be to accept this kind of possible runtime crashes?
The other question is what's the chance of it to occur. But this one is even harder to find an answer ;)
from list-extra.
Yeah exactly. I think things will turn out much better if we wait for someone to have a problem, and then try and solve that problem in the least drastic way. We dont even need to ask general questions like "How important is speed compared to stack safety?". Answering the much narrower question of "Is stack safety necessary in this case? And can it be implemented in such a way that doesnt interfere with any other plausible use case?"
from list-extra.
I'm hoping for a fixed version because the project I'm working on is actually suffering from this problem (#61). It's not "theoretical". And that's why I was contributing the changes back to the library ;)
from list-extra.
Relevant: https://ellie-app.com/426Lc2q5nkba1/0
and https://elmlang.slackarchive.io/help/page-93/ts-1502598591356555
(Worth rewriting the group functions in this way?)
from list-extra.
Yeah exactly. I think things will turn out much better if we wait for someone to have a problem
I'm using jxxcarlson/hex
which converts hex strings into bytes. I noticed that long strings cause a stack overflow. I narrowed down the problem to a List.Extra.groupsOf 2
call within the hex package. Long strings aren't uncommon when dealing with binary data so this is definitely an issue.
Edit: I rewrote that part of the code to not depend on List.Extra.groupsOf and it works again. I personally don't think the default should be fast but not stack safe. Tracking down stack overflows is difficult and they have a tendency to happen in production since that's when the program deals with largest amounts of data. In this specific case I lost a lot of time finding it because it was happening in a constant value. All constants are computed when the app is created so the search space for where the stack overflow could be coming from was pretty large.
from list-extra.
@jigargosar #137 was merged 10 days ago to make iterate
stack safe but I guess @Chadtech is holding off on cutting a new release to batch more changes with it. I think it would be great if someone could do some benchmarking to determine the performance impact of making unfoldr
stack safe. Even if we decide that unfoldr
should be stack safe no matter what, it is important to quantify the performance degradation (if any) for the purposes of release notes.
from list-extra.
Related Issues (20)
- Next release HOT 1
- Proposal for more context in `groupWhile` HOT 3
- MIT LICENSE file does not match "BSD-3-Clause" in elm.json HOT 1
- Proposal for `combinations` HOT 2
- Argument order of `andMap` HOT 1
- proposal: Add findMap HOT 2
- isInfixOf returns incorrect result when a partial match is found before a complete match HOT 2
- groupByWhile seems unintuitive HOT 2
- Proposal for `windows` function(s) HOT 5
- code design thought HOT 1
- `groupWhen` and `groupWhenWithAcc` proposal/design question HOT 1
- Cycle 0 list = [] ? HOT 1
- Tail call optimiziations
- `groupsOfVarying` behaves inconsistently with groups of length `0`
- I downloaded the source code for elm-community/list-extra But it looks like the hash of the archive has changed since publication HOT 3
- groupsOf and friends can exceed maximum call stack size HOT 1
- Add a pad functions HOT 1
- Proposal for `toMaybeList` function HOT 2
- `unconsLast`
- Proposal: `(a -> Result x b) -> List a -> Result (List x) (List b)` HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from list-extra.