Stream: ideas

Topic: segmented builtin `List` under the hood?

Richard Feldman (Aug 07 2025 at 16:35):

just saw https://danielchasehooper.com/posts/segment_array/ and I wonder whether this is the design we should be using for our builtin List :thinking:

Richard Feldman (Aug 07 2025 at 16:36):

it kinda reminds me of seamless slices, in terms of avoiding expensive operations (in this case realloc+copy when capacity is exceeded) at the expense of a few extra CPU instructions that are probably never going to make a difference

Richard Feldman (Aug 07 2025 at 16:37):

seems like it could be quite a big deal for hosts using arena allocation, and probably be neutral to positive on other hosts...but I'm not sure what the downside scenarios might be!

Richard Feldman (Aug 07 2025 at 16:39):

(separately, seems like a potentially good idea to have SafeList in the compiler be backed by SegmentedList and then try arena allocators in the compiler?)

Brendan Hansknecht (Aug 07 2025 at 19:06):

Hmmm :thinking:

Brendan Hansknecht (Aug 07 2025 at 19:07):

Definitely need to think about this more. My gut feeling is that it would have bad tradeoffs in a number of common scenarios. But obviously it's very nice with arenas specifically

Richard Feldman (Aug 07 2025 at 19:13):

it seems like it would have no real tradeoffs in the case where it doesn't resize

Richard Feldman (Aug 07 2025 at 19:13):

other than maybe capacity being a power of 2 resulting in some wasted memory if the allocator wasn't already rounding up to powers of 2 for bucketing anyway?

Brendan Hansknecht (Aug 07 2025 at 19:28):

Default costs would be:

1. More expensive walking
2. More complex logic for handling edges between two buckets.
3. Wasted memory (especially cause large arrays tend to grow a lot slower). This is probably one of the biggest costs in many cases. You also have limitations around shrinking arrays.

Brendan Hansknecht (Aug 07 2025 at 19:28):

But yeah, nothing too crazy most likely. I think memory usage likely would be the biggest issue. Oh, and one extra indirection on every access. That might add up.

Brendan Hansknecht (Aug 07 2025 at 19:29):

Growing list bigger than 3 usizes and make is store all pointers to segments on the stack, that also almost certainly has some solid cost in a number of cases.

Brendan Hansknecht (Aug 07 2025 at 19:30):

I assume we also apply this to strings

Brendan Hansknecht (Aug 07 2025 at 19:30):

Side note, it would allow for some crazy large small strings.

Brendan Hansknecht (Aug 07 2025 at 19:32):

Like lists would be 28 usizes instead of 3. That definitely must have a cost.

Richard Feldman (Aug 07 2025 at 19:47):

oh I assumed it would be possible to put those on the heap in the first allocation

Richard Feldman (Aug 07 2025 at 19:47):

instead of on the stack

Brendan Hansknecht (Aug 07 2025 at 20:16):

Ok sure. Means near empty lists are a lot larger. Also means you have an extra pointer indirection on all list interactions

Brendan Hansknecht (Aug 07 2025 at 20:17):

Anyway, all this to say, I'm not sold the tradeoffs are so simple. I would guess in many cases this is slower.

Richard Feldman (Aug 07 2025 at 21:06):

yeah that's fair, maybe doesn't make sense after all

Brendan Hansknecht (Aug 07 2025 at 21:34):

I do definitely agree that it is super nice for arenas though. So maybe we can make it opt in somehow? At least in the long run.

Brendan Hansknecht (Aug 07 2025 at 21:35):

And definitely feels worth messing with at some point to get a rough idea of perf in practice

Last updated: Jun 16 2026 at 16:19 UTC