Allow in-place encoding

[nazar-pc]

Right now encoder allocates a vector for shards, where it copied the original data and eventually allows to read recovery data.

It wold be really nice if it was possible to provide correctly allocated slice of bytes right away and encode things in-place or at least a way to provide both input and output memory explicitly.

This would cut peak memory usage substantially in the use case I have.

Similar request is for decoder, though decoding is less frequent for me, so lower priority.

[AndersTrier]

Agree that it would be really nice to have.

It is not obvious how to do it though, as I do some shuffling around of bytes in the final chunk, if the shard length is not a multiple of 64:

reed-solomon-simd/src/engine/shards.rs

Lines 49 to 72 in 243f4ce

	// Last chunk is special if shard.len() % 64 != 0.
	// See src/algorithm.md for an explanation.
	if tail_len > 0 {
	let (src_lo, src_hi) = src_tail.split_at(tail_len / 2);
	let (dst_lo, dst_hi) = dst[whole_chunk_count].split_at_mut(32);
	dst_lo[..src_lo.len()].copy_from_slice(src_lo);
	dst_hi[..src_hi.len()].copy_from_slice(src_hi);
	}
	}
	// Undoes the encoding of the last chunk for the given range of shards
	pub(crate) fn undo_last_chunk_encoding(&mut self, shard_bytes: usize, range: Range<usize>) {
	let whole_chunk_count = shard_bytes / 64;
	let tail_len = shard_bytes % 64;
	if tail_len == 0 {
	return;
	};
	for idx in range {
	let last_chunk = &mut self[idx][whole_chunk_count];
	last_chunk.copy_within(32..32 + tail_len / 2, tail_len / 2);
	}
	}

One option could be to only support shard.len() % 64 == 0 with this new API.

Another solution could be to handle the last non-64-chunk by copying the bytes to a 64 byte stack buffer.

Or just handle the final bytes in rust without SIMD. This might actually be the best option.

Any suggestions on what the API could look like?

[nazar-pc]

Both of the suggested options make sense to me. For the use case I had in mind multiple of 64 would work just as well.

Now since I reported this, I actually discovered that in many places it is actually more convenient to deal with iterators since the eventual data structure has some stuff interleaved between shards. Not I'm wondering if that could also be represented in the API that wouldn't require extra allocation.

Details

I essentially have a large-ish allocation, which contains source shards followed by recovery shards, but each individual shard has a placeholder for some proofs to be inserted later rather than having all shards concatenated next to each other:

source_shard_0 proof_0 source_shard_1 proof_1 recovery_shard_0 proof_2 recovery_shard_1 proof_3

Source shards together are around 128M and the same number of recovery shards is used, so all this results in a decent amount of extra heap allocations during erasure coding and this happens to be a time-sensitive part of the workflow.

For example rayon has IndexedParallelIterator that I think may be closely related to the needs of this library. Something like that with an additional constraint that a shard must be a multiple of 64 bytes would mean I could avoid all extra allocations.