> this means the number of players in the current lobby is counted every time a player is added
> that counting is O(N), where N is the number of players
> simply displaying the the player list turns out to be O(N^2)
Perhaps this is the real issue?
Not a chance.
Complexity theory matters when you're dealing with large N. These are tiny N, miniscule even. At this scale, the time for one operation is way more important than how quickly the number of operations grows with N. Some operations take a single processor flop while others take quadrillions. Are we talking about N^2 integer comparisons or N^2 renders for a 3D movie? And is that N^2 operations per hour or per millisecond?
Goko needs to send information every time a player logs on or off, starts/finishes a game, or joins/creates/changes a table. I probably create a table once every 20-ish minutes, then I auto-kick a couple joiners, then I get an opp and I start a game. So I'm generating about 15 events an hour. Sometimes I chat in the lobby or change rooms too, and maybe I'm underestimating... let's call it 60 events per hour, so each of
N clients is receiving
60N messages per hour, which is a total of
N2/60 per second that the server has to send. If that seems off, you can test it with the attached GM script, which listens to the Goko server and outputs every message they send you to the JS console.
But wait! I'm not actually receiving lobby events most of the time I'm logged in. When I'm playing a game, I don't care what's happening in the lobby and Goko isn't telling me. When I come back, they send me one "big" message that gives me the whole current state of the room. That one big message doesn't cost much more than any of the small ones do. So if I'm in games 90% of the time I'm connected, then Goko really only has 1/10th the obligation we calculated before. You can check that estimate by counting the number of running games vs connected players in the lobby at any given moment.
So now we're down to
N2/600 messages per second. If there are N=200 people in a lobby, then Goko will need to send about
2002/600 = 67 messages per second. Is that realistic?
Why not try it out? Ask my server to send you some websocket messages and see how long it takes. If it can send 67 in less than a second, then my $500 computer is ready to handle a unified Goko lobby.
Ok, ok... Sending 67 messages per second is so easy it's not even worth testing. Let's try a bigger N.... leverage that O(N^2) running time. Maybe Goko grows by a factor of 10 so that N=2,000. Is my server capable of sending (2,000^2)/600 = 6,667 websocket messages in less than a second?This was my result:
Server sent 6667 messages.
Server clock time elapsed: 0.1139 secEdit: Ok, looking back at the original conversation, I see that I missed the point. We're not talking about the time to send messages but the time to read an array. Same argument applies though, rather more so in fact.