Group methods will crash if used with a large list

[andys8]

Several methods are implemented in a way that is not tail recursive. I'm not sure what's the current state in elm and in js regarding tail call optimization (see https://lisplog.org/elm_converts_tail_calls_to_loops.html) or if elm-lang/trampoline could help. Open for discussion :)

Reproduce issue

list : List (List Int)
list =
    List.range 0 100000
    |> List.Extra.group

https://ellie-app.com/3MxzbGDZdNSa1/1

Related issues

61

[pzp1997]

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 :man_shrugging:.

[andys8]

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.

https://github.com/elm-lang/core/commit/decbc93025ba38ee9c5613d311e5b979452dfcd3

[pzp1997]

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?

[Chadtech]

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.

[andys8]

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 ;)

[Chadtech]

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?"

[andys8]

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 ;)

[Janiczek]

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?)

[MartinSStewart]

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.

[jigargosar]

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.

[pzp1997]

@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.

[harrysarson]

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