Stream: API design

Topic: statically allocated collections and API design

Richard Feldman (Oct 30 2023 at 23:47):

one interesting thing I've realized about the potential for having statically allocated collections (e.g. if I write the literal ["foo", "bar", baz"], we know that the entire List Str can be allocated in the binary itself because it doesn't rely on any information that changes at runtime) is that it affects API design.

Richard Feldman (Oct 30 2023 at 23:47):

for example, I ran into a use case where having a function like Str.splitAny : Str, List Str -> List Str would be nice, and then I reflexively started thinking about if there would be a way to avoid the List because it's an extra heap allocation

Richard Feldman (Oct 30 2023 at 23:48):

but then I realized it doesn't have to be a heap allocation if we had that optimization, and in fact more often than not (at least the way I expect people would typically use a function like that) it'd be a static allocation, and might optimize all the way into an unrolled loop

Richard Feldman (Oct 30 2023 at 23:48):

which really changes the tradeoffs around APIs taking collections like that!

Brendan Hansknecht (Oct 31 2023 at 02:45):

Currently List Str will allocate even if it is constant

Richard Feldman (Oct 31 2023 at 10:20):

right, but the idea is to change that in the future!!:smiley:

Brendan Hansknecht (Oct 31 2023 at 14:31):

I mean it works for regular lists. The reason it doesn't work for nested lists is just a bug.

Brendan Hansknecht (Oct 31 2023 at 14:32):

It actually used to work a long time ago.

Brendan Hansknecht (Oct 31 2023 at 14:32):

But yeah, definitely a should fix eventually

Bryce Miller (Nov 07 2023 at 16:06):

Is this an optimization that could automatically stack allocate a collection if it’s size is known at compile time and never changes? So if I have a List Foo which is initialized to a given length and I never add or remove elements.

Brendan Hansknecht (Nov 07 2023 at 16:14):

Oh, those should all be in the binary in the read only data sections. (or potentially even the mutable data section). So no need to try and stack allocate or anything of that nature. Also stack allocation generally isn't safe cause you can't return the list from the current function (and it can lead to easily getting stack overflows and lots of duplicate data)

Brendan Hansknecht (Nov 07 2023 at 16:14):

those should all be in the binary in the read only data sections.

We just have some bugs stopping us from having this optimization in all cases currently.

Bryce Miller (Nov 07 2023 at 16:16):

So basically, once the wrinkles are ironed out, I get non-heap allocated collections for free as long as I don’t do anything to change their size after I initialize them?

Bryce Miller (Nov 07 2023 at 16:16):

Even if I only know the type of the members, not the values?

Bryce Miller (Nov 07 2023 at 16:17):

Well I guess I’d have to initialize to something. Nvm.

Brendan Hansknecht (Nov 07 2023 at 16:19):

I get non-heap allocated collections for free as long as I don’t do anything to change their size after I initialize them?

As I think about this more, I am pretty sure that any change will have to heap allocate. Cause each time you load a constant, it must be exactly the same. If we allowed inplace modification, that would break things. So the moment any change happens, it would heap allocate.

Bryce Miller (Nov 07 2023 at 16:22):

Oh, so in order for that to work, you’d have to have a ref count of 1, and be doing opportunistic in-place mutation anyway.

Bryce Miller (Nov 07 2023 at 16:22):

So you’d have to track that, plus whether the size of the collection is changing at all.

Bryce Miller (Nov 07 2023 at 16:23):

That makes sense, I think.

Bryce Miller (Nov 07 2023 at 16:24):

I can see how that would be non-trivial to implement. I just thought it sounded cool to get the performance of a Rust array for free, without having to write different code.

Brendan Hansknecht (Nov 07 2023 at 16:26):

A constant can't have opportunistic mutation at all. If you have:

fn = \{} ->
   x = [1, 2, 3]
   List.set x 0 ((List.get x 0) + 1)

If you do an oppurtunistic inplace mutation, you would change x to [2, 2, 3] and return [2, 2, 3]. The next time the function runs, it would then load [2, 2, 3] and return [3, 2, 3]. So refcounts aren't a valid signal when dealing with constants. Opportunistic mutation is never valid.

Brendan Hansknecht (Nov 07 2023 at 16:28):

I guess ,to be fair, there are technically ways to make this work if we really wanted to. Probably the most reasonable way to make something like this work would be to enable the small list optimization. Then if the constant is under a specific size, it would be on the stack and allowed inplace mutation.

Bryce Miller (Nov 07 2023 at 16:31):

Oh, you’re talking about constants only. I see.

Bryce Miller (Nov 07 2023 at 16:35):

I’m thinking of situations such as maybe a chess game, where the grid is a fixed 64 squares. The values might change, but the size won’t. In Rust we would use an Array for that. But I’m not sure how often this comes up in situations where you wouldn’t want to just use a systems language anyway.

Brendan Hansknecht (Nov 07 2023 at 16:47):

Ah. yes. That use case for arrays. Yeah, I want arrays for the same reason. Currently the Roc approved solution is tuples, but I don't think their ergonomics are good enough for this yet.

Brendan Hansknecht (Nov 07 2023 at 16:50):

That would actually be a super awesome use case to see the pain point of using tuples and if we can make them nice enough to not need arrays of some sort. (that and if someone could write a tuple and list version to compare the perf diff)

Bryce Miller (Nov 07 2023 at 16:56):

I have a Sudoku thingy I wrote in elm. I’ve been thinking about porting it over to Roc for grins. Maybe I could compare tuples and lists if i get around to it.

Last updated: Jul 06 2025 at 12:14 UTC