Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Zero alloc pathfinding

Zero alloc pathfinding

Iskander (Alex) Sharipov

September 26, 2023
Tweet

More Decks by Iskander (Alex) Sharipov

Other Decks in Programming

Transcript

  1. A dive into specialized data structures and micro-optimizations Something that

    you would easily use in your job What this talk is …but not this
  2. Agenda 1. A very short intro 2. Existing libraries 3.

    Why my library is so fast 4. How to overcome some of its limitations
  3. Image source: www.redblobgames.com/pathfinding/a-star Pathfinding finds some way to get from

    point A to point B. Depending on the algorithm, the paths can have different properties.
  4. Roboden & pathfinding • Can have large maps (scrollable, several

    screens) • Maps are generated, there are no key waypoints • Different kinds of landscape (mountains, lava, forests, …) • Hundreds of units that are active in the real-time • Fixed 60 ticks per second
  5. Let’s benchmark libraries! Tests: • no_walls - the trivial solution

    is the best one • simple_wall - go around a simple wall • multi_wall - several simple walls 50x50 grid map
  6. Benchmark details (for nerds) Sources: github.com/quasilyte/pathing/_bench OS: Linux Mint 21.1

    CPU: x86-64 12th Gen Intel(R) Core(TM) i5-1235U Tools used: “go test -bench”, benchstat Turbo boost: disabled (intel_pstate/no_turbo=1) Go version: devel go1.21-c30faf9c54
  7. Pathfinding benchmarks: CPU time (ns/op) LIBRARY no_walls simple_wall multi_wall pathing

    3525 2084 2688 astar (x268) 948367 (x745) 1554290 (x685) 1842812 go-astar grid paths Read as “X times slower”
  8. Pathfinding benchmarks: CPU time (ns/op) LIBRARY no_walls simple_wall multi_wall pathing

    3525 2084 2688 astar (x268) 948367 (x745) 1554290 (x685) 1842812 go-astar (x128) 453939 (x450) 939300 (x343) 1032581 grid (x514) 1816039 (x553) 1154117 (x442) 1189989 paths (x1868) 6588751 (x2474) 5158604 (x2274) 6114856
  9. Pathfinding benchmarks: allocations LIBRARY no_walls simple_wall multi_wall pathing 0 0

    0 astar 337336 B 2008 511908 B 3677 722690 B 3600 go-astar 43653 B 529 93122 B 1347 130731 B 1557 grid 996889 B 2976 551976 B 1900 740523 B 1759 paths 235168 B 7199 194768 B 6368 230416 B 7001
  10. quasilyte/pathing • x128-2474 times faster than the alternatives • Does

    no heap allocations to build a path • Optimized for very big grid maps (thousands of cells) • Simple and zero-cost layers system • Works out of the box, no need to implement an interface
  11. Why other libraries are so much slower? Why pathing is

    so fast? Instead of talking about this… …we’ll focus on this
  12. Greedy BFS performance-critical parts • Matrix to store cell information

    (the grid) • Result path representation • Priority queue for “frontier” • Map to store the visited cells
  13. Greedy BFS performance-critical parts • Matrix to store cell information

    (the grid) • Result path representation • Priority queue for “frontier” • Map to store the visited cells
  14. {0,0} {1,0} {2,0} {3,0} {0,1} {1,1} {2,1} {3,1} {0,2} {1,2}

    {2,2} {3,3} Grid map Plains Sand Lava Map legend
  15. {0,0} {1,0} {2,0} {3,0} {0,1} {1,1} {2,1} {3,1} {0,2} {1,2}

    {2,2} {3,3} Grid map Some units can only traverse the plains.
  16. {0,0} {1,0} {2,0} Grid map {0,1} {1,1} {2,1} {3,1} {0,2}

    {1,2} {2,2} {3,3} Other units can traverse sand as well {3,0}
  17. {0,0} {1,0} {2,0} {3,0} {0,1} {1,1} {2,1} {3,1} {0,2} {1,2}

    {2,2} {3,3} Grid map Flying units can probably cross lava too
  18. Defining the grid cell types type CellType int const (

    CellPlain CellType = iota // 0 CellSand // 1 CellLava // 2 )
  19. Storing the grid cell data • We have only 3

    tile types => • 2 bits per cell are enough
  20. Choosing a grid cell data size (in bits) SIZE (bits)

    VALUE RANGE MAP SIZE (3600 CELLS) 2 0-3 (2^2) 900 bytes 3 0-7 (2^3) 1350 bytes 4 0-15 (2^4) 1800 bytes 5 0-31 (2^5) 2250 bytes 6 0-63 (2^6) 2700 bytes A typical cache line size is only 64 bytes
  21. Flat array storage (2 bits / cell) 0 1 2

    3 4 5 6 7 Bytes[0] Bytes[1] i := y*g.numCols + x byteIndex := i / 4 shift := (i % 4) * 2 cell := g.bytes[byteIndex] >> shift & 0b11 Array memory
  22. Grid access patterns {x,y} {x+1,y} {x,y-1} {x-1,y} {x,y+1} These cells

    may be inside the same byte => good cache locality
  23. Grid access patterns {x,y} {x+1,y} {x,y-1} {x-1,y} {x,y+1} These cells

    may not even fit into the same cache line (64 byte)
  24. Cache lines vs flat array storage SIZE (bits) MAX WIDTH

    (cells, 32x32 pixels) 2 256 cells (8192 pixels) 3 ~170 cells (5440 pixels) 4 128 cells (4096 pixels) 5 ~102 cells (3264 pixels) 6 ~85 cells (2720 pixels)
  25. Querying the grid cell value 1. Get a raw value

    from the grid at {x,y} (0-3 for 2 bits)
  26. Querying the grid cell value 1. Get a raw value

    from the grid at {x,y} (0-3 for 2 bits) 2. Map that through the cell mapper (get a 0-255 value)
  27. Querying the grid cell value 1. Get a raw value

    from the grid at {x,y} (0-3 for 2 bits) 2. Map that through the cell mapper (get a 0-255 value) 3. Use that value during the pathfinding
  28. Interpreting the cell value • After the mapping, cell value

    is in [0,255] range • 0 means that this cell can’t be traversed • Any other value specifies the traversal cost For the simplest cases, 0 and 1 are enough.
  29. A better way to define the layer type GridLayer uint32

    func (l GridLayer) Get(i int) byte { return byte(l >> (uint32(i) * 8)) }
  30. Greedy BFS performance-critical parts • Matrix to store cell information

    (the grid) • Result path representation • Priority queue for “frontier” • Map to store the visited cells
  31. {0,0} {1,0} {2,0} {2,1} A path with points {2,2} {2,3}

    Up Right Right Down A path with deltas (“steps”) Down Down 0,0 1,0 2,0 S 2,1 2,2 F Map
  32. Defining cardinal directions (no diagonals for now) type Direction int

    // Just 4 values, so 2 bits per direction will suffice! const ( DirRight Direction = iota // 0 DirDown // 1 DirLeft // 2 DirUp // 3 )
  33. 1 2 3 4 5 6 7 8 9 10

    11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 We could store up to 64 “steps” in just 16 bytes (2 registers) Second 8 bytes First 8 bytes
  34. 1 2 3 4 5 6 7 8 9 10

    11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 But we also need pos+len to iterate over the path pos len
  35. Defining the Path structure const gridPathBytes = (16 - 2)

    // 14 const gridPathMaxLen = gridPathBytes * 4 // 56 type GridPath struct { bytes [gridPathBytes]byte len byte pos byte }
  36. Our Path type advantages • Value semantics - just pass

    it without a pointer • Copying is trivial - a pair of 64-bit MOVQ instructions • No need to do a heap allocations • Requires no real memory fetching, unlike dynamic arrays
  37. Our Path type disadvantages • Limited max path length SIZE

    (bytes) MAX PATH LENGTH (steps) 16 56 24 88 32 120 There is an advantage in keeping it under 64
  38. Greedy BFS performance-critical parts • Matrix to store cell information

    (the grid) • Result path representation • Priority queue for “frontier” • Map to store the visited cells
  39. Frontier & priority queue • Push(coord, score) • Pop( )

    -> (coord, score) • Reset( ) - to re-use the memory Score is a Manhattan distance from coord to the destination. (*) The exact score calculation depends on the algorithm.
  40. How do we use priority queue here? • Push all

    current possible moves to pqueue • Investigate all tempting routes first If some move brings us closer to the finish, we’ll check that route first. This is needed to reduce the average computation steps performed by the algorithm.
  41. 5 x 4 3 2 2 2: {2,1}, {1,2} 4:

    {0,1} 5: {0,0} Step 2.3
  42. 5 x 4 3 2 2 2: {2,1}, {1,2} 4:

    {0,1} 5: {0,0} Step 3 - pop min
  43. 5 x 4 3 2 1 2 1: {3,1} 2:

    {1,2} 4: {0,1} 5: {0,0} Step 3.1
  44. 5 x 4 3 2 1 2 1 1: {3,1}

    {2,2} 2: {1,2} 4: {0,1} 5: {0,0} Step 3.2
  45. func (q *PriorityQueue[T]) Push(priority int, value T) { i :=

    uint(priority) & 0b111111 q.buckets[i] = append(q.buckets[i], value) q.mask |= 1 << i } This masking removes the bound check
  46. Push(1, "foo") Push(4, "bar") Push(1, "baz") mask: 0b10010 buckets: {

    1: {"foo", "baz"}, 4: {"bar"}, } Actions Queue state Unchanged!
  47. func (q *PriorityQueue[T]) Pop() T { i := uint(bits.TrailingZeros64(q.mask)) if

    i < uint(len(q.buckets)) { e := q.buckets[i][len(q.buckets[i])-1] q.buckets[i] = q.buckets[i][:len(q.buckets[i])-1] if len(q.buckets[i]) == 0 { q.mask &^= 1 << i } return e } return T{} } TrailingZeros is basically a BSF+CMOV instructions on x86-64
  48. Push(1, "foo") Push(4, "bar") Push(1, "baz") mask: 0b10010 buckets: {

    1: {"foo", "baz"}, 4: {"bar"}, } Actions Queue state
  49. Push(1, "foo") Push(4, "bar") Push(1, "baz") Pop() // => "baz"

    mask: 0b10010 buckets: { 1: {"foo"}, 4: {"bar"}, } Actions Queue state Unchanged!
  50. Push(1, "foo") Push(4, "bar") Push(1, "baz") Pop() // => "baz"

    Pop() // => "foo" mask: 0b10000 buckets: { 4: {"bar"}, } Actions Queue state Becomes zero!
  51. Push(1, "foo") Push(4, "bar") Push(1, "baz") Pop() // => "baz"

    Pop() // => "foo" Pop() // => "bar" mask: 0b00000 buckets: <all empty> Actions Queue state All bits are 0
  52. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 1 0 1 0 mask uint8 bucket elements
  53. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 1 0 1 0 mask uint8 Pop#1 bits.TrailingZeros(0b00101010) => 1
  54. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 1 0 1 0 mask uint8 Pop#2 bits.TrailingZeros(0b00101010) => 1
  55. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 1 0 1 0 mask uint8 Pop#3 bits.TrailingZeros(0b00101010) => 1
  56. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 1 0 0 0 mask uint8 Became zero
  57. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 1 0 0 0 mask uint8 Pop#4 bits.TrailingZeros(0b00101000) => 3
  58. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 0 0 0 0 mask uint8 Became zero
  59. How Pop( ) calculates the bucket in O(1) 0 0

    1 0 0 0 0 0 mask uint8 Pop#5 bits.TrailingZeros(0b00100000) => 5
  60. func (q *PriorityQueue[T]) Reset() { offset := uint(bits.TrailingZeros64(q.mask)) q.mask >>=

    offset i := offset for q.mask != 0 { if i < uint(len(q.buckets)) { q.buckets[i] = q.buckets[i][:0] } q.mask >>= 1 i++ } q.mask = 0 } 100% memory re-use
  61. Bucket64 properties • Push( ) - O(1) • Pop( )

    - O(1) • Reset( ) - O(1)* Reset is constant to the number of buckets. Note that we’re using the mask to skip reslicing batches of buckets, so it’s quite fast.
  62. Greedy BFS performance-critical parts • Matrix to store cell information

    (the grid) • Result path representation • Priority queue for “frontier” • Map to store the visited cells
  63. 2D (or 1D) array properties • Get(coord) - O(1) •

    Set(coord, value) - O(1) • Reset( ) - O(n) Re-using a big array is an expensive memset(0). It makes them impractical for us.
  64. CoordMap benchmarks, size=96*96 (ns/op) CONTAINER SET GET RESET array 10

    4 7200 Reset( ) for an array can be quite slow
  65. CoordMap benchmarks, size=96*96 (ns/op) CONTAINER SET GET RESET array 10

    4 7200 sparse-dense (+25) 35 (+13) 17 1 sparse-dense Set( ) & Get( ) have some extra overhead
  66. 0 0 0 0 0 0 Elements 1 Gen value

    gen The zero-value container gen is 1, element gens are 0
  67. 0 0 A 1 0 0 0 Elements 1 Gen

    Set( ) assigns the value & updates the gen counter value gen
  68. 0 0 A 1 0 0 0 Elements 1 Gen

    Get( ) compares the elem and container gen values value gen Gen mismatch => not found
  69. 0 0 A 1 0 0 0 Elements 1 Gen

    Get( ) compares the elem and container gen values value gen Gen match => return A
  70. 0 0 A 1 0 0 0 Elements 2 Gen

    No memory reset is needed, Get( ) will work correctly right away value gen gen++
  71. Generation map properties • Get(coord) - O(1) • Set(coord, value)

    - O(1) • Reset( ) - O(1) minimal overhead
  72. CoordMap benchmarks, size=96*96 (ns/op) CONTAINER SET GET RESET array 10

    4 7200 sparse-dense (+25) 35 (+13) 17 1 gen-map (+4) 14 (+6) 10 1 Generations-based map is ~2 times faster than sparse-dense map
  73. CoordMap size estimations • Grid stores 1 cell for 2

    bits • CoordMap needs ~8 bytes per cell We’re paying x32 times more memory for the CoordMap! Can we still have an ~unlimited Grid size after that?
  74. CoordMap max size • Max search area is N=((56*2)^2)+2 =>

    12546 • The max size is 12546 * 8 => 100368 bytes (0,1 MB) After that, you can increase the Grid size for as much as you want; the CoordMap won’t get bigger.
  75. Defining coord map element type mapElem struct { value uint8

    // Direction stored as uint8 gen uint32 // Generation counter } // Sizeof(mapElem) => 8 (due to padding)
  76. Defining coord map element type mapElem struct { value uint8

    // Direction stored as uint8 gen uint16 // Generation counter } // Sizeof(mapElem) => 4 (1 byte wasted)
  77. Handling the overflow type mapElem struct { value uint8 //

    Direction stored as uint8 gen uint8 // Generation counter } // Sizeof(mapElem) => 2 (no bytes wasted)
  78. Defining coord map element func (m *CoordMap) Reset() { //

    Use a constant to match the gen type. if m.gen == math.MaxUint16 { m.clear() // A real memclr; happens very rarely } else { m.gen++ } }
  79. Defining coord map element func (m *CoordMap) clear() { m.gen

    = 1 clear(m.elems) // Sets elem.gen to 0 }
  80. Gen counter size Smaller counter => less memory overhead per

    element, but real memory clears will happen more often. Counters like uint32-uint64 make real memory clears almost impossible, but they will consume more memory per element.
  81. More than 4 tile types in a game? Use per-biome

    layer sets! 0 Plains 1 Forest 2 Water 3 Mountains 0 Sand 1 Lava 2 Volcano 3 Mountains Jungle biome Inferno biome
  82. When you see an L-shaped turn, a diagonal move is

    possible (hint: use a Peek2 function)
  83. Zero allocs? • Paths are just an on-stack value (16

    bytes) • Unlike builtin maps, sparse maps allows 100% re-use
  84. Zero allocs? • Paths are just an on-stack value (16

    bytes) • Unlike builtin maps, sparse maps allows 100% re-use • Priority queue is also re-use friendly
  85. A* vs Greedy BFS A* pros: • Optimal paths •

    Always finds the path A* cons: • More expensive to compute • Requires more memory
  86. Useful links • My library source code • Sparse set/map

    explained • Generations map explained • Great A* and greedy BFS introduction • Morton space-filling curve • Roboden game source code • Awesome Ebitengine list