Expand `impl Encode for Vec<String>` to `impl Encode for Vec<E: Encode>`

[Eugeny]

Would be useful for Vec<&str> and key exchange Vec<Algorithm> lists for example.

[tarcieri]

@Eugeny can you open a PR?

[Eugeny]

I would but my PRs from November are still hanging open :(

[tarcieri]

I will get to them soon, I am just going through a very, very large backlog

[tsurdevson]

I had a go at implementing this, adding a very slightly modified version of the Vec<String> impl like so:

#[cfg(feature = "alloc")]
impl<E: Encode> Encode for Vec<E> {
    fn encoded_len(&self) -> Result<usize, Error> {
        self.iter().try_fold(4usize, |acc, e| {
            acc.checked_add(e.encoded_len()?).ok_or(Error::Length)
        })
    }

    fn encode(&self, writer: &mut impl Writer) -> Result<(), Error> {
        self.encoded_len()?
            .checked_sub(4)
            .ok_or(Error::Length)?
            .encode(writer)?;

        for entry in self {
            entry.encode(writer)?;
        }

        Ok(())
    }
}

Seems straight forward. However, this collides with the Vec<u8> impl, so adding this would require removing the spesific impl for Vec<u8>. I set up a very small benchmark to see if this would significantly impact the performance of encoding Vec<u8>:

use criterion::{Criterion, criterion_group, criterion_main};
use ssh_encoding::Encode;
use std::hint::black_box;

fn encode_to_vec(bytes: &Vec<u8>, vec: &mut Vec<u8>) {
    bytes.encode(vec).unwrap();
}

fn criterion_benchmark(c: &mut Criterion) {
    let mut buf = Vec::new();
    let bytes = vec![0u8; 1024];
    c.bench_function("encode byte slice", |b| {
        b.iter(|| encode_to_vec(black_box(&bytes), black_box(&mut buf)));
    });
}

Running this benchmark before and after applying the patch results in a very significant difference.

encode byte slice       time:   [4.3553 µs 4.3709 µs 4.3887 µs]
                        change: [+308.72% +433.12% +589.52%] (p = 0.00 < 0.05)
                        Performance has regressed.

Unless the generic implementation can be made much smarter than what I did, I don't think it would be sensible to make this change.

Perhaps the correct thing to do is instead to add more impls, and/or slightly less generic ones that don't collide with the basic ones that are already there.

[tarcieri]

I think some marker trait which denotes that encoding a message this way is actually valid for a given type would be helpful, and may even get rid of the impl conflicts