I wrote about this a couple days ago, but I accidently cut out part of the explanation. Oops, my bad. This is my second shot at this.
There’s an inefficiency in insertSlice of std.ArrayList. This is the current implementation:
pub fn insertSlice(self: *Self, i: usize, items: []const T) Allocator.Error!void {
try self.ensureUnusedCapacity(items.len);
self.items.len += items.len;
mem.copyBackwards(T, self.items[i + items.len .. self.items.len], self.items[i .. self.items.len - items.len]);
@memcpy(self.items[i..][0..items.len], items);
}
The problem is that if ensureUnusedCapacity triggers a resize, it will copy all the elements to the new allocation. inserSlice will then copy a slice of these same items to the end of the allocation, to make space for the insertion. It’s better to copy everything to their final place at once. Here’s my implementation:
/// Insert slice `items` at index `i` by moving `list[i .. list.len]` to make room.
/// This operation is O(N).
/// Invalidates pointers if additional memory is needed.
pub fn insertSlice(
self: *Self,
index: usize,
items: []const T,
) Allocator.Error!void {
const dst = try self.addManyAtIndex(
index,
items.len,
);
@memcpy(dst, items);
}
/// Resize the array, adding `count` new elements at position `index`, which have `undefined` values.
/// The return value is a slice pointing to the newly allocated elements. The returned pointer
/// becomes invalid when the list is resized. Resizes list if self.capacity is not large enough.
pub fn addManyAtIndex(
self: *Self,
index: usize,
count: usize,
) Allocator.Error![]T {
const new_len = self.items.len + count;
const to_move = self.items[index..];
if (self.capacity >= new_len) {
//There is enough space
self.items.len = new_len;
mem.copyBackwards(
T,
self.items[index + count ..],
to_move,
);
return self.items[index..][0..count];
} else {
// Here we avoid copying allocated but unused bytes by
// attempting a resize in place, and falling back to allocating
// a new buffer and doing our own copy. With a realloc() call,
// the allocator implementation would pointlessly copy our
// extra capacity.
const old_memory = self.allocatedSlice();
if (self.allocator.resize(old_memory, new_len)) {
self.capacity = new_len;
self.items.len = new_len;
mem.copyBackwards(
T,
self.items[index + count ..],
to_move,
);
return self.items[index..][0..count];
} else {
// Need a new allocation. Calculate allocation size as
// ensureTotalCapacity. We don't call ensureTotalCapacity because there
// would be an unnecessary check if the capacity is enough (we already
// know it's not).
var better_capacity = new_len;
while (true) {
better_capacity +|= better_capacity / 2 + 8;
if (better_capacity >= new_len) break;
}
const new_memory = try self.allocator.alignedAlloc(
T,
alignment,
better_capacity,
);
@memcpy(
new_memory[0..index],
self.items[0..index],
);
@memcpy(
new_memory[index + count ..][0..to_move.len],
to_move,
);
self.allocator.free(old_memory);
self.items.ptr = new_memory.ptr;
self.items.len = new_len;
self.capacity = new_memory.len;
return new_memory[index..][0..count];
}
}
}
The comment about realloc was copied straight from ensureTotalCapacityPrecise. It’s curious that the problem they alluded there is the same problem in the current implementation of insertSlice.
Also, while implementing my own version, I noticed the tests for insertSlice don’t cover the case where the ArrayList needs to resize. If you comment out the entire else branch of the first “if” (“if (self.capacity >= new_len)”), all tests still pass.
