Memory efficient way to move items from one arraylist to another?

[sudden rain]

I have a loop where I walk over the items of one arraylist and gather additional items that I need to walk over (think of exploring a graph). At the end of each loop I want to move the discovered_items to the items_to_explore arraylist and "reset" or "clear" the discovered_items arraylist. But not sure how to do this effectively?

for (items_to_explore.items) |item| {
  ...
  try discovered_items.append(new_item);
  ... 
}
items_to_explore = discovered_items;
discovered_items.clearRetainingCapacity();

[untold rock]

do you want to replace items_to_explore with discovered_items?

[sudden rain]

Yes, the old items are not needed anymore at this point, yet I would like to prevent allocating a new arraylist each itteration.

[untold rock]

items_to_explore.clearRetainingCapacity();
items_to_explore.appendSliceAssumeCapacity(discovered_items.items);
discovered_items.clearRetainingCapacity();

[sudden rain]

Memory efficient way to move items from one arraylist to another?

Ok... That doesn't seem to difficult. I thought I maybe needed to use some std.mem copy stuff, but if this is super performand as well, this looks pretty nice.

[untold rock]

If you only need the discovered_items to filter out the items_to_explore, then you could do this all inplace as well without discovered_items at all

[sudden rain]

Its not really filtering I think... New ones are found/added, but they are quaranteed to be new and should be explored in the next itteration.

[untold rock]

okay, then you might want to use appendSlice instead of appendSliceAssumeCapacity

in case there are more discovered items than last time

[sudden rain]

Using appendSliceAssumeCapacity does require me to do a len check in between right?

Yeah I was just typing that 😊

Well this should get me going. Thanks @untold rock!

[alpine scaffold]

what about swapping them

mem.swap(ArrayList(T), &items_to_explore, &discovered_items);
discovered_items.clearRetainingCapacity();

[sudden rain]

Now we're talking 😉 But I would like to understand how this actually works...

pub fn swap(comptime T: type, a: *T, b: *T) void {
    const tmp = a.*;
    a.* = b.*;
    b.* = tmp;
}

So is tmp the address of the starting point of the bytes in memory? Or...?

[untold rock]

It's same as struct assignment

state and pointers swap over, so it should just work

[sudden rain]

I think I get it... tmp is the address of ArrayList a (I guess a fat pointer) then a is set to the address of ArrayList b and lastly b is set to tmp.

So how is this different then (or isn't it different and is this just a conveniens method (I guess not, but..)):

const tmp = items_to_explore;
items_to_explore = discovered_items;
discovered_items = tmp;

[untold rock]

it's not different from that indeed

[median current]

I think I get it... tmp is the address of ArrayList a (I guess a fat pointer) then a is set to the address of ArrayList b and lastly b is set to tmp.
to be suuuuper pedantic, tmp is the value pointed to by a, so a shallow copy of the arraylist. this is because .* is the dereferencing operator. you're copying whatever a is pointing at into tmp

the value at a (a.*) is then set to the value at b (b.*)
ie copying over the thing b is pointing to into the spot a is pointing to.

the value at b (b.*) is then set to the value of tmp
and this is again copying the value tmp holds into the spot b is pointing to.

nothing really to do with fat pointers here

[sudden rain]

Yes, clear... And this is a shallow copy as you said, which is why this is probably more performant, right? I don't know the internals of an ArrayList, but I assume it's a type with some meta data and a pointer to a backing array in memory? Hence I mentioned the term "fat pointer", but I guess that is something else 😊 Thanks for giving some more details! All helps to get a better understanding of how things work together!

[median current]

i guess it could be called a fat pointer in that sense 😅 i guess i usually think of those as a pointer and a vtable but it makes sense. and youre pretty close, an arraylist is just a slice (pointer + length) and a capacity. the managed variant holds an allocator too but its not integral to the structure

and yes a shallow copy is a lot more performant than a deep copy, if you dont need a deep copy, just by virtue of copying less stuff

[sudden rain]

Thanks!

[sudden rain]

Hmm.. So for ArrayLists this seems to work fine, but for the next version I'm using a HashMap instead of an ArrayList and now I get errors about memory leaks...

The HashMap has values that are initialised as well and it looks like they are not free'd. So is this pattern not suited for HashMaps (I guess not)? And if so, what would be an alternative efficient way to achieve this with maps?

@median current any ideas on why this is different for maps?

[alpine scaffold]

depends on what the items are being held

[sudden rain]

They are allocated items as well

[alpine scaffold]

wouldnt that issue also show up with ArrayList given clearRetainingCapacity() doesnt free the intermediary items?

[sudden rain]

I would indeed expect that, but in the arraylist case is was ArrayList(u32). So maybe it would indeed also give the same issue there.

Funny as I expected the bits that are getting copied contain the info to the backing data....

Ooooooh... Never mind I get it!

It's not the "moved" map that gives the issue, its the one I call clearRetainingCapacity on. I need to loop open its values and deinit them as well. Of course... 🙈

Thanks again @alpine scaffold! Learned a lot this weekend 😏

Hmm... I spoke too soon... Changed it, but still gives the same error.

So i now do:

mem.swap(std.HashMap(u32, std.HashMap(u32, void)), &items_to_explore, &discovered_items);
var iterator = discovered_items.iterator();
while (iterator.next()) |kv| {
    kv.value_ptr.clearRetainingCapacity();
}
discovered_items.clearRetainingCapacity();

But its still leaking...