Clone without unnecessary allocations

[hbgl]

For my use case I have a worker thread that periodically updates a thread local HashMap and then copies it to another thread. For most iterations no entries are added or removed, only the values change.

I would like to efficiently synchronize the two HashMaps by copying the arrays of control bytes and elements directly to the already allocated arrays of the other HashMap. Basically it would be the same thing that's done in RawTable's clone function without the extra allocations.

hashbrown/src/raw/mod.rs

Lines 978 to 1028 in bacb169

	impl<T: Clone> Clone for RawTable<T> {
	fn clone(&self) -> Self {
	if self.is_empty_singleton() {
	Self::new()
	} else {
	unsafe {
	let mut new_table = ManuallyDrop::new(
	Self::new_uninitialized(self.buckets(), Fallibility::Infallible)
	.unwrap_or_else(|_| hint::unreachable_unchecked()),
	);
	// Copy the control bytes unchanged. We do this in a single pass
	self.ctrl(0)
	.copy_to_nonoverlapping(new_table.ctrl(0), self.num_ctrl_bytes());
	{
	// The cloning of elements may panic, in which case we need
	// to make sure we drop only the elements that have been
	// cloned so far.
	let mut guard = guard((0, &mut new_table), |(index, new_table)| {
	if mem::needs_drop::<T>() {
	for i in 0..=*index {
	if is_full(*new_table.ctrl(i)) {
	new_table.bucket(i).drop();
	}
	}
	}
	new_table.free_buckets();
	});
	for from in self.iter() {
	let index = self.bucket_index(&from);
	let to = guard.1.bucket(index);
	to.write(from.as_ref().clone());
	// Update the index in case we need to unwind.
	guard.0 = index;
	}
	// Successfully cloned all items, no need to clean up.
	mem::forget(guard);
	}
	// Return the newly created table.
	new_table.items = self.items;
	new_table.growth_left = self.growth_left;
	ManuallyDrop::into_inner(new_table)
	}
	}
	}
	}

I saw that the RawTable was recently exposed in #104 but unless I missed something it is not enough to copy the contents from one map into another. Do you think it would be a good idea to implement clone_from on RawTable which reuses the arrays if possible?

[Amanieu]

Note that you can somewhat already do this:

dest.clear();
dest.extend(src.iter().map(|(k, v)| (k.clone(), v.clone())));

This should avoid any unnecessary allocations in most cases.

[hbgl]

I thought that copying the underlying buffer would be more efficient especially since my keys are very small (i64). Do you think that implementing clone_from makes sense for a HashMap at all? I feel that not being able to copy the underlying buffer wastes one of the main advantages of the Swiss Table.

[Amanieu]

Copying the buffer only works if both tables have the exact same allocation size. We could resize the destination table to match the source table, but that feels wasteful when the destination table is larger than the source.

[hbgl]

Okay I didn't think about that one. I think that an implementation of clone_from can be a best effort approach to avoid unnecessary allocations.

1. If it is possible to copy the buffer, great.
2. Else if the destination table is larger, erase and insert.
3. Else fallback to *self = source.clone().

[itamarst]

I am in similar situation, I have two hashmaps A and B, A gets inserts and removals, and every once in a while A is cloned into B. So B is usually fairly similar to A.

For now I'm using an immutable hashmap (from im) where clone() is cheap, but that has its own costs of additional overhead for inserts and removals.