Optimization: Eliminate List to Coordinate conversion in favor of Tuples

[benjaminpjones]

Background

I ran a CPU profile with Scalene and it shows Coordinate.__init__() taking roughly 31% of CPU time. Related functions like Board.at() and Coordinate.__hash__() are also taking non-negligible time.

This PR attempts to address the performance cost by replacing List and Coordinate representations with Tuples. There are a couple principles at play here:

• User-defined classes use more resources than built-in classes. While user-defined classes are good for readability, they can incur a performance cost. Since Coordinate are on the hot path, it might be worth switching to tuple
• tuple uses less resources than list. Dynamically sized containers like list need to over-allocate memory in case elements are added later. Moreover, tuple are immutable, so a tuple may have some optimizations enabled by the fact that its elements may not be changed.

Proposed Changes

• Update the action maps to be programmatically generated.
  • Main benefit: easier to change the structure of the action map, which we make use of when we change the list to tuple
  • Side benefit: Easier to make different size action maps
• add basic unit test
  • python -m unittest
• Replace Lists and Coordinates in the action maps and elsewhere

Results

Roughly 60% speedup in simulation time

Before:

$ python main.py -l 100
At login page Current URL: http://localhost:5173/login
Logged in. Current URL: http://localhost:5173/
Game created. Current URL: http://localhost:5173/game/66c238baf60d7d0c62bfb991
Simulating ...
Time taken to simulate 363 children 100 times: 73.38 seconds

After:

$ python main.py -l 100
\At login page Current URL: http://localhost:5173/login
Logged in. Current URL: http://localhost:5173/
Game created. Current URL: http://localhost:5173/game/66c23872f60d7d0c62bfb990
Simulating ...
Time taken to simulate 363 children 100 times: 45.11 seconds

[benjaminpjones]

Fixed an off by one error introduced by this PR.

BTW no worries if this isn't a change you'd like to merge. Just let me know!

[SameerDalal]

I would like to merge this change! It's some serious performance boost. I just wanted to take the time to understand the changes that you made before merging so I can improve other code down the line.

[benjaminpjones]

Awesome! No worries and thanks for taking time to understand it :)

Let me know if I can answer any questions too

[SameerDalal]

Looks good!

I was also able to create an action map using modulus and division with only one for loop but it seems those operations take a little bit more time.

[SameerDalal]

Fixed an off by one error introduced by this PR.

I did find an issue with this. By adding one, we are changing the move played on the board. For example, if the best move determined by the engine was action 359, the engine plays some other move like action 360 on the board. By removing the + 1 in switch_19x19.get(action[0] + 1, default_case_19x19)() the engine plays the correct move on the board.

I think the issue is that we changed the index of x and y coordinates of the action map from 0 to 1. The hardcoded action map's first element was [1,1] while this action map's first element is [0,0]

[SameerDalal]

Fixed an off by one error introduced by this PR.

I haven't been able to reproduce this error after removing the + 1. Could you provide some more details?

[benjaminpjones]

I was having trouble with, for example, action == 19 which lead to get_action_offset((0, 1))

The unit test in test_offset_moves.py will fail on (0,0) if the +1 is removed.

I'm not at a computer right now, will try to find where the discrepancy comes from later.

I think the issue is that we changed the index of x and y coordinates of the action map from 0 to 1.

This was by design - the Coordinate class did a conversion to 0-based index. In order to use the same objects in the action map as the Coordinate code, I had to choose between 0-based and 1-based.

If we change it to 1-based, a lot of code that used Coordinate class will break.

[benjaminpjones]

Just tried to repro, not having much luck. Bot played 166, and here I count to 166 it seems right to me:

I checked the white stone in the same way. Is there like a code test that would demonstrate the issue?

[SameerDalal]

Bot played 166, and here I count to 166 it seems right to me:

Is this with or without the +1 in the code?

[SameerDalal]

Fixed the issue! Adding the +1 in the offset_moves file was correct. The error came from the get_sgf_data function which was 1 indexed.

[benjaminpjones]

Oh cheers! Thanks for finding that!