Stream: ideas

Topic: in-place iteration

Richard Feldman (Oct 07 2023 at 16:59):

I forget if we ever discussed this, but we could totally have certain iteration operations work in-place, for example:

• map could mutate each element in-place if the list is unique and the closure's return type is the same size as the list elements
• keepIf on a unique list could track the first and second deletions it encounters, and if there were any keeps in between those, memmove them in-place and repeat
• some of these could work for Set and Dict too, plus I'm sure there are more of them out there!

Brendan Hansknecht (Oct 07 2023 at 17:36):

I think that already happens for at least map

Brendan Hansknecht (Oct 07 2023 at 17:36):

Assuming input and output type are the same size and list is unique

Kevin Gillette (Oct 07 2023 at 19:00):

Why does the result value need the same size? If the input is not used after the operation, the result only needs to be "no larger than the input" in order to reuse the allocation.

Ayaz Hafiz (Oct 07 2023 at 19:03):

That's a really good point. I guess you could compact the list as needed to accomodate the smaller elements

Richard Feldman (Oct 07 2023 at 19:19):

wow, yeah I never thought of that!

Kevin Gillette (Oct 07 2023 at 19:22):

if list allocations have or can be given a "capacity" concept, typically a number of elements, then a lot of runtime optimizations get unlocked

Brendan Hansknecht (Oct 07 2023 at 19:23):

You also have to do some more checks around alignment

Brendan Hansknecht (Oct 07 2023 at 19:23):

but yeah, that could be done as well.

Brendan Hansknecht (Oct 07 2023 at 19:24):

Hmm, also for allocation systems where you are required to specify the number of bytes when deallocating, you also need to make sure that you track that as well.

Kevin Gillette (Oct 07 2023 at 19:26):

if you're asked to create a list of 2049 U8 values, the allocation probably should be for 4096 bytes, at which point you've got 2047 bytes of spare capacity. Then if you do a take 512, and then map that result into U32, you still can reuse the capacity of that same allocation

Kevin Gillette (Oct 07 2023 at 19:27):

since even though the result is larger, it still fits within available capacity

Kevin Gillette (Oct 07 2023 at 19:29):

so generally by treating capacity as distinct from length (albeit with capacity being unexposed to the programmer), operations can declare how much space they may need, and that can be checked against capacity.

Kevin Gillette (Oct 07 2023 at 19:30):

That said, to make the U8 -> U32 map reuse the same capacity, you'd need to reverse-iterate

Kevin Gillette (Oct 07 2023 at 19:31):

or you'd first need to memcpy the input to the end of its capacity in order to forward iterate

Kevin Gillette (Oct 07 2023 at 19:31):

without doing either of these, you'd clobber input elements before reading them

Brian Carroll (Oct 07 2023 at 20:15):

Yeah we have a separate capacity field on List and Str since last year. We have added a few tricks to take advantage of that, but there are plenty more tricks left that we haven't done.

Brendan Hansknecht (Oct 07 2023 at 21:28):

Kevin Gillette said:

if you're asked to create a list of 2049 U8 values, the allocation probably should be for 4096 bytes, at which point you've got 2047 bytes of spare capacity. Then if you do a take 512, and then map that result into U32, you still can reuse the capacity of that same allocation

Technically, this isn't guaranteed to be valid (depends on the exact case, almost certainly would work with u8 and u32, but with types with more complex sizes and alignment that may not be the case).

The u8 array could start at an index that would be unaligned for u32s.

Brendan Hansknecht (Oct 07 2023 at 21:28):

But yeah, overall agree there are optimizations to be had, just have to be very careful especially with making them general over all type combinations

Richard Feldman (Oct 07 2023 at 21:33):

actually for those particular examples we'd be fine because our lowest alignment is usize due to the refcount at the beginning

Richard Feldman (Oct 07 2023 at 21:33):

but in theory in the future (with simd) we could have alignments where that would come up!

Brendan Hansknecht (Oct 07 2023 at 21:34):

I know, that is why I depends on the exact case. Didn't want to dive into that, just wanted to clarify the general concern

Last updated: Jun 16 2026 at 16:19 UTC