There’s an inefficiency in insertSlice of std.ArrayList.
/// 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,
allocator: Allocator,
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 (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 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,
);
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];
}
}
}
/// 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,
allocator: Allocator,
index: usize,
items: []const T,
) Allocator.Error!void {
const dst = try self.addManyAtIndex(
allocator,
index,
items.len,
);
@memcpy(dst, items);
}
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.