Suggestion: enhance performance by implementing recv_buf by skip list or red-black tree

[Banyc]

trafficstars

The counterpart of recv_buf in linux kernel is called out-of-order queue, which is often shortened as ofo queue. That queue is implemented by a red-black tree so that every time the insertion into the queue can be guaranteed to complete in O(logN) time. The main entry for this logic can be learned from here https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_input.c#L5112 and also pulling data from the ofo queue to receive queue here https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_input.c#L4694. In the KCP version, the equivalent queue is a linked list in nature, which might exceed the time complexity to O(N). It could be a potential issue when the receive window is too large by reaching 65535. The main routine is shown here https://github.com/skywind3000/kcp/blob/master/ikcp.c#L683. It is true that each KCP segment is attached by a sequence number that describes or is based on the segment number other than the data size, saving the efforts from packet merging. Having said that though the sorting itself is a common topic in both protocols.

I prefer to skip lists more than red-black trees since the former is relatively practical, suitable for code in single file only, and easier to maintain.

[mklifo]

@Banyc just curious, did you ever implement & benchmark your solution?

[Banyc]

@mklifo I haven't implemented it yet.