search

lsalzman / enet

ENet reliable UDP networking library
MIT License
2.78k stars 675 forks source link

Prevent iteration over inactive peers #266

Open dimage1 opened 2 months ago

dimage1 commented 2 months ago

Improves enet_protocol_send_outgoing_commands by iterating over active peers only.

bjorn commented 2 months ago

Seems like a good idea. But I'm just wondering, what kind of performance improvement are you seeing with this patch? It seems to me that the maximum number of peers would have to be rather high for this to matter.

mman commented 2 months ago

@bjorn @dimage1 sorry to hijack the discussion, I did some extensive profiling in the past months and send_outgoing_commands is indeed super expensive operation as it walks all peers, and all outgoing commands for each peer to see what is confirmed and what needs to be resent so it is essentially O(N*M). (N being number of peers and M average number of reliable outgoing commands in a queue for peer).

My proposal to fix this would be to introduce a proper C implementation of a hash table to track active peers and to track outgoing commands for each peer for faster lookup, and solve the problem once and for all.

This fix is a partial way forward in that it walks the list of all peers to derive list of active peers on any peer state change. So it reduces number N. But it still walks the list of sent outgoing commands in a linear fashion (number M) to see what to confirm and what to resend. Depending on what type of app you have it may or may not actually help. I for example have an app where peers come and go rather frequently, so in my case this fix will not actually help, only will it shift load elsewhere.

dimage1 commented 2 months ago

@bjorn I considered this for 256 - 4096 peers per 1 instance, e.g. on a relay / proxy / dedicated server with several simultaneous sessions and a short frame time (1 - 20ms, which equals to 1000 - 50 FPS). @mman the change indeed more helps on rather long lasting connections (e.g. 1 - 60 minutes), where a server himself is underpopulated, leaving quite some empty peer slots. Your M number concern looks reasonable and the hash table idea could be a good fix / improvement! I'm not sure when I will have time to try it though.

mman commented 2 months ago

@dimage1 The hash table thingy is something I have in mind for a long time, but have not got around to implement. It's is trickier than it looks on the first thought. I just wanted to confirm your observation that...

  1. Storage of the peers / tracking of active peers
  2. Storage of outgoing reliable commands, and their retransmissions

are indeed the main source of performance problems in enet and are worth working on improving...

mman commented 2 months ago

@dimage1 @bjorn Dropping this here for when I get around to implementing it: https://benhoyt.com/writings/hash-table-in-c/