Poor performance of SocketSet::add

[Steanky]

Description of issue Adding a large number of sockets (~40000) to a SocketSet is very inefficient, taking about 10 seconds on my machine (4.2Ghz AMD processor).

Steps to reproduce Run the following code:

let mut sockets = SocketSet::new(Owned(Vec::with_capacity(40000)));
for _ in 0..40000 {
    sockets.add(Socket::new(Owned(vec![0; 4096]), Owned(vec![0; 4096])));
}

Cause I suspect the cause is the following loop (@ line 76 in socket_set.rs):

for (index, slot) in self.sockets.iter_mut().enumerate() {
    if slot.inner.is_none() {
        return put(index, slot, socket);
    }
}

SocketSet does not keep an internal index, so it needs to do a full search of the backing storage vector to find where to insert. However, this makes the common use case of adding a large number of sockets very slow.

Potential fix Add a new field to SocketSet, ex. first_empty_index: usize. When add is called, just run put(self.first_empty_index, &mut self.sockets[self.first_empty_index], socket), then search for the new lowest free space, starting from first_empty_index + 1 rather than 0. When removing a socket, if the removal index is less than first_empty_index, set first_empty_index equal to the removal index.

This should provide better performance for repeated calls to add without needing to make any radical changes to the data structure.

[thvdveld]

SocketSet does not keep an internal index, so it needs to do a full search of the backing storage vector to find where to insert. However, this makes the common use case of adding a large number of sockets very slow.

I think that smoltcp is used a lot in a no_std embedded context, where adding a lot of sockets is not really the most common thing. However, if the solution is simple and does not add too much complexity, a PR would be very welcome!

[Steanky]

I've got no problem creating a PR for this, as I've already implemented the changes on a personal fork.