Should lists always have a minimum capacity of 64? · platform development

Stream: platform development

Topic: Should lists always have a minimum capacity of 64?

Eli Dowling (Dec 24 2024 at 12:21):

I have been working again on re-integrating the file reading changes I made to basic cli and I was seeing some errors that really confused me.
One thing I noticed is, if I make a list with capacity 1 in roc, when I log the internal capacity value in rust it's 64. Is this to be expected?

Sam Mohr (Dec 24 2024 at 13:15):

Here's the impl for that function: https://github.com/roc-lang/roc/blob/a58b1013e756749da5c35431efde834a70a29717/crates/compiler/builtins/bitcode/src/list.zig#L353

Sam Mohr (Dec 24 2024 at 13:15):

I think it's not working the way it's supposed to.

Sam Mohr (Dec 24 2024 at 13:15):

It has an arg called capacity that's passed to a listReserve function as spare

Sam Mohr (Dec 24 2024 at 13:17):

And then we unconditionally increase our "desired capacity" by spare

Sam Mohr (Dec 24 2024 at 13:18):

So at least that is wrong. There's some casting stuff going on, which might explain how 1 (or 2?) gets to 64, but I'm not seeing

Eli Dowling (Dec 24 2024 at 13:20):

Sam Mohr said:

And then we unconditionally increase our "desired capacity" by spare

That shouldn't matter because later we use a min for the reserve size with the maxint. No issues

Eli Dowling (Dec 24 2024 at 13:20):

Yeah I don't get it either

Sam Mohr (Dec 24 2024 at 13:21):

https://github.com/roc-lang/roc/blob/a58b1013e756749da5c35431efde834a70a29717/crates/compiler/test_gen/src/gen_list.rs#L3703

Sam Mohr (Dec 24 2024 at 13:21):

This tests that withCapacity reserves correctly

Sam Mohr (Dec 24 2024 at 13:22):

So it sounds like something may be wrong in the FFI interaction for you?

Eli Dowling (Dec 24 2024 at 13:22):

I just did a quick test, any number less than 64 comes out as 64

Eli Dowling (Dec 24 2024 at 13:22):

65 works fine

Sam Mohr (Dec 24 2024 at 13:22):

66?

Eli Dowling (Dec 24 2024 at 13:22):

I'm wondering if this is some small list optimisation trickery

Sam Mohr (Dec 24 2024 at 13:23):

I don't believe we do small list yet, only small str

Eli Dowling (Dec 24 2024 at 13:23):

Sam Mohr said:

66?

66 and 128 is 128

Sam Mohr (Dec 24 2024 at 13:24):

Haha, so 64n + 1 is correct, and anything else is 64(n + 1)

Eli Dowling (Dec 24 2024 at 13:25):

Well 64 is also correct

Sam Mohr (Dec 24 2024 at 13:25):

Yeah

Sam Mohr (Dec 24 2024 at 13:25):

It'd probably be good to get a minimal repro in this channel so we can report a bug

Eli Dowling (Dec 24 2024 at 13:32):

found it.
The calculateCapacity function has a bug

Eli Dowling (Dec 24 2024 at 13:32):

Or, well I guess it has a strange choice to always make it a minimum of 64

Eli Dowling (Dec 24 2024 at 13:33):

But maybe people are smarter than I have good reasons for deciding that 64 bytes is the smallest an array should be.

Eli Dowling (Dec 24 2024 at 13:44):

Anyway, I guess this doesn't matter much, but it's a little confusing for people using small buffers... not that they really should be using a tiny buffer. but still, having it always read 64 bytes when I was only expecting 2, was... unexpected

Brendan Hansknecht (Dec 24 2024 at 19:19):

Should be a minimum of 64 bytes, not 64 items

Brendan Hansknecht (Dec 24 2024 at 19:20):

Also, we should definitely have a way to request a specific size and not over allocate

Brendan Hansknecht (Dec 24 2024 at 19:20):

These numbers where chosen by roughly following what Facebook does for strings that leads to best overall perf/memory use tradeoff for their fleet

Brendan Hansknecht (Dec 24 2024 at 19:21):

That said, that has small string optimization for 0 to 24 bytes

Brendan Hansknecht (Dec 24 2024 at 19:21):

We don't have small list for 0 to 24 bytes. That may shift the tradeoff some.

Brendan Hansknecht (Dec 24 2024 at 19:21):

Though I don't recall if Facebook as small list or not....they may not

Brendan Hansknecht (Dec 24 2024 at 19:22):

Anyway, it is meant to be a reasonable default, but may not be the best choice for all cases.

Brendan Hansknecht (Dec 24 2024 at 19:22):

I'll make sure to double check the original source to see if we mixed something up.

Brendan Hansknecht (Dec 24 2024 at 19:28):

On a really quick skim (so might be off):

They don't have small lists, so they use a slightly different allocation capacity tradeoff
For the first capacity request, they always just round to the allocator bucket size, never do bigger jumps

Brendan Hansknecht (Dec 24 2024 at 19:30):

Oh actually they still do the 64 byte thing

Brendan Hansknecht (Dec 24 2024 at 19:33):

So I think our core differences are:

Not rounding to the allocator size (cause we don't know the allocator)
On calls to reserve or with capacity, they trust the user knows exactly how many elements they want. Instead of using the growth function, they allocate exactly the required amount (rounded to the allocator bucket size)

Brendan Hansknecht (Dec 24 2024 at 19:34):

So we probably should update our code to do both of those things. Even without knowing the allocator size, we probably know rough bucket sizes based on alignment and blocks.

Last updated: Jul 06 2025 at 12:14 UTC