Accidental Copies · ideas · Zulip Chat Archive

This is paired with github issue #4198. I thought it would be useful to post for general discussion. So sharing it on here directly. Please comment here if you have any thoughts.

I don't really have a solution here, but I thought this would be worth having a more formal discussion topic (I will open a paired zulip thread for discussion). The general question is: how can we help users that introduce accidental copies of large data structures?

An example that was recently hit in Advent of code, can be seen in this function:

cover = \grid, x, y ->
    index = grid.width * x + y

    when List.replace grid.data index One is
        { value: None, list } -> { grid & data: list }
        { value: One, list } -> { grid & data: List.set list index TwoOrMore }
        { value: TwoOrMore, list: _ } -> grid

Due to keeping grid around after the call to List.replace, the ~1MB grid is cloned on every call to this function (which there are tons). Correcting this issue leads to ~650x speed up on my machine (fast function at end of issue for reference). A bug like this can be the difference between Roc being a practical language and it being totally unusable.

This may require a much more long term solution, but I think it is worth thinking about.
My immediate thought is something like scalene where they can show you how much copying is done per line of code. That way you could see a heatmap of allocation.

Theoretically, we could add a flag to the roc compiler to make it print the line of code and size of an allocation to a file with every call to roc_alloc and roc_realloc. Or just add a debug version of the api to the platform to also pass in a string so the platform can handle this. That would at least be a good start. Though we probably really need the call stack or a way to bubble the information up to the original caller. I guess potentially without adding a debug api, the platform should be able to dump the call stack and all of this information (Though might require more debug info from Roc).

cover = \{ width, data }, x, y ->
    index = width * x + y

    # branch prediction (lol)
    when List.replace data index One is
        # If it was previously None, we guessed right
        { value: None, list } -> { width, data: list }
        # If it was One or TwoOrMore, set it to TwoOrMore
        { value: _, list } -> { width, data: List.set list index TwoOrMore }

Brendan Hansknecht (Oct 04 2022 at 15:39):

I am open to any and all ideas. Any other tools people have seen that solve this well? Any general thoughts/comments/questions?

Qqwy / Marten (Oct 04 2022 at 17:23):

Anton (Oct 04 2022 at 17:30):

Eventually we probably want to integrate an allocation heatmap in the editor. The visualization would be quite easy to implement in the editor right now assuming the data is available. I think it would also be good to automatically notify the user (in the editor) if a lot of copying is being done.

Kevin Gillette (Nov 04 2022 at 15:52):

Wouldn't this be something that the compiler reasonably be expected to optimize? Although semantically List.set and List.replace are returning copies of the list, only the element at one index is varying in value, and so I'd imagine that the series of checks and updates updates could occur in a register before being written to main memory.

Brendan Hansknecht (Nov 04 2022 at 16:11):

If a list item is unique, yes. Then the compiler should be able to act exactly as you specified. Generally speaking, at compile time, we are not sure if a value is unique and have to instert a conditional to find out.

The issue is that lists and their elements can have multiple references. Once you have multiple references, that can't be done. You might update in a local register, only for the underlying value in the list to be changed leading to an incorrect final result.

The copies arise with non-unique lists. The main problem is that it is easy to accidentally keep around a reference of a list, leading to a copy. This copy is what we are trying to help users avoid. By associating allocations with lines of code, it should be possible to see where a list is being copied that should actually be unique, pinpointing where to correct the code and avoid a copy.

Kevin Gillette (Nov 04 2022 at 16:17):

Also, out of interest, would either code solution be typical? It took me a while to figure out what the function is attempting to do (List.replace isn't named all that distinctly from List.set, for example). It seems a bit abstract to do a whole-of-list blind replace followed by a check and fixup, especially since (especially in Roc) there's semantically no concurrent access and thus no "better to ask forgiveness than permission" aspect to this.

cover = \grid, x, y ->
    index = grid.width * x + y

    when List.get grid.data index is
        Ok None -> { grid & data: List.set grid.data index One }
        Ok One -> { grid & data: List.set grid.data index TwoOrMore }
        _ -> grid

This is also one element read and a write in the worst case, rather than one read and two writes.

Technically it can be done in fewer cases, but it's probably less readable and may rely on smart optimizations to be as performant...

cover = \grid, x, y ->
    index = grid.width * x + y

    when List.get grid.data index is
        Ok None -> { grid & data: List.set grid.data index One }
        # Either the element was One (this has an effect)
        # Or this is a no-op because it's already TwoOrMore
        # or the index was OutOfBounds
        _ -> { grid & data: List.set grid.data index TwoOrMore }

Brendan Hansknecht (Nov 04 2022 at 16:22):

The function was just an example that someone wrote for advent of code. I think that set vs replace shouldn't make much of a difference here. But yeah, your functions should be valid as well.

Brendan Hansknecht (Nov 04 2022 at 16:22):

As a note, with current roc, your functions would also lead to a copy like the original function.

Kevin Gillette (Nov 04 2022 at 16:46):

Brendan Hansknecht (Nov 04 2022 at 16:47):

Brendan Hansknecht (Nov 04 2022 at 16:48):

Brendan Hansknecht (Nov 04 2022 at 16:49):

The issue is in keeping around a reference to grid which keeps around a reference to the old data list. So it can no longer be updated in place.

Brendan Hansknecht (Nov 04 2022 at 16:50):

I think you example should get fixed as a roc bug. The other example with list.replace will likely be much harder to fix in general