Hacker News Reader

Comment by nijave | Hacker News Reader

Anyone take a look into the code and see why it can't be parallelized? The bottom of the FAQ mentions that but I'd think at least certain aspects should be parallelizable or at least be prioritizable (like maybe forgoing leaderboard updates to focus on more important events?)

View on HN

Good idea. Tho in the code itself (from a cursory glance) in L141 Sequencing(...) I see a bunch of nested maps - I don't know Scala but I think this may be a performance issue? Rather than hyperfocusing on parallelism or event systems etc since that stuff is comparitively hard to solve maybe refactoring this function/algo at the core of the pairing would have more bang for buck

https://github.com/ornicar/lila/blob/98691c8901cc0e7d0f338f4...

If you think about it, you can't really generate pairings in parallel because each thread would need write access to the entire pool to ensure no one is paired twice and that you have a consistent view of all the results to that point before creating a new pair. You could maybe create a lock for each participant but that might actually be slower, and would definitely be more difficult to reason about and can lead towards bugs just as serious under load.

I'm not sure exactly what the algorithm is for choosing pairs, but naively it seems like it should be possible to bucket the players in some way, at which point the pairings within each bucket can be generated in parallel, with buckets getting merged if they get too small. The tricky part is coming up with a way to bucket them that's both efficient and will lead to enough pairings, and I'm not sure what the criteria is. If it's completely random, then ideally any bucketing should work fine. If it's based on ratings or existing records, it seems like starting by grouping players within certain ranges of that stat should work (assuming the boundaries can be picked based on the distribution of the players). I don't know enough to know for sure that bucket grouping would work here, but it doesn't seem like knowing the entire set of results beforehand should be necessary (unless there's some standard algorithm for choosing pairings that's very prescriptive).

The pairing is based on ratings and existing records, and happily isn't dependent on a standard prescriptive algorithm, unlike traditional Swiss tournaments. It would be fine to accept some reordering of game-finishing events.

I'm certain the process can be parallelized - it just hadn't been considered necessary before.

If they're doing tournament pairing the traditional way then you can't do that kind of bucketing because it's always possible that someone will "spill" down if they can't be matched in their bucket, and that would completely change the pairing in each lower bucket (if you add one more person at the top of a bucket you would zig-zag down all the pairings below them, except the new pairings have nothing in common with the previous pairings and so you have to redo things like whether they've played each other before).

>During this tournament, for the first time, players were inputting events faster than Lichess could process them. The queue grew larger, causing delays in pairings.

Mostly interested in what these other events were and how they interact with pairing. Don't really know what pairing involves but seems that should go fairly fast even on a single CPU core (unless it's doing some kind of lookup or calculation but that part should be parallelizable)

Reply on news.ycombinator.com