5 ms·

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

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.

saghm 5y ago
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).
- dmurray 5y ago
  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.
- lmm 5y ago
  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).
nijave 5y ago
>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)

saghm 5y ago

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).

dmurray 5y ago
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.
lmm 5y ago
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).

nijave 5y ago

>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)