refactor: Use a single list instead of a big one

[ClementBeal]

It would improve the performance by a factor 10 when the code is compile (AOT) but when we use the JIT option, it's 2x slower. So it would be slower in dev but faster in prod .

void main() {
  const dimension = 100;
  const maxCells = dimension * dimension;
  final grid = List<List<int?>>.generate(
    dimension,
    (index) => List.filled(dimension, null),
    growable: false,
  );

  final simpleGrid = List<int?>.filled(maxCells, null);

  final gridStopwatch = Stopwatch();
  final simpleGridStopwatch = Stopwatch();

  gridStopwatch.start();

  for (var i = 0; i < dimension; i++) {
    for (var j = 0; j < dimension; j++) {
      grid[i][j] = 3;
    }
  }
  gridStopwatch.stop();

  simpleGridStopwatch.start();
  for (var i = 0; i < maxCells; i++) {
    simpleGrid[i] = 3;
  }
  simpleGridStopwatch.stop();

  print("Grid : ${gridStopwatch.elapsed}");
  print("Simple grid : ${simpleGridStopwatch.elapsed}");
}

[ClementBeal]

I tested with some "complex" code and it's faster in dev and prof by a factor 4 at least

void main() {
  const dimension = 100;
  const maxCells = dimension * dimension;
  final grid = List<List<int?>>.generate(
    dimension,
    (index) => List.filled(dimension, null),
    growable: false,
  );

  final simpleGrid = List<int?>.filled(maxCells, null);

  final gridStopwatch = Stopwatch();
  final simpleGridStopwatch = Stopwatch();

  gridStopwatch.start();

  for (var i = 0; i < dimension; i++) {
    for (var j = 0; j < dimension; j++) {
      if (i % 4 == 1) {
        grid[i][j] = 3;
      } else {
        grid[i][j] = 2 * i;
      }
    }
  }
  gridStopwatch.stop();

  simpleGridStopwatch.start();
  for (var i = 0; i < maxCells; i++) {
    if (i % 4 == 1) {
      simpleGrid[i] = 3;
    } else {
      simpleGrid[i] = 2 * i;
    }
  }
  simpleGridStopwatch.stop();

  print("Grid : ${gridStopwatch.elapsed}");
  print("Simple grid : ${simpleGridStopwatch.elapsed}");
}

[Luckey-Elijah]

This improvement is on my radar.. It would require some type of migration for the back-end or, backwards compatibility for the List<List<int?>> data structure. I can look into migrating the backend data by hand since it's not a lot of data right now

[ClementBeal]

Another code like the falling sand but only in dart. 50% faster

import 'dart:math';
import 'dart:typed_data';

class FallingSandGrid {
  FallingSandGrid({required this.width, required this.cells}) {
    height = cells.length ~/ width;
  }
  final int width;
  final List<int> cells;
  late int height;

  // Set the value at the given (x, y) coordinates
  void setPixel(int x, int y, int value) {
    if (isInBounds(x, y)) {
      cells[y * width + x] = value;
    }
  }

  // Get the value at the given (x, y) coordinates
  int getPixel(int x, int y) {
    if (isInBounds(x, y)) {
      return cells[y * width + x];
    } else {
      return -1; // Or any value representing "out of bounds"
    }
  }

  // Check if the given (x, y) coordinates are within the grid bounds
  bool isInBounds(int x, int y) {
    return x >= 0 && x < width && y >= 0 && y < height;
  }

  void update() {
    for (var i = cells.length - 1; i >= 0; i--) {
      final y = i ~/ width; // Calculate y coordinate from index

      if (y == height - 1) continue; // Skip bottom row

      final currentPixel = cells[i];
      if (currentPixel == 0) continue;

      final pixelBelow = cells[i + width];

      if (pixelBelow == 0) {
        cells[i + width] = currentPixel;
        cells[i] = 0;
      }
    }
  }
}

class FallingSandGridNested {
  FallingSandGridNested({required this.width, required this.cells});
  final int width;
  final List<List<int>> cells;

  void setPixel(int x, int y, int value) {
    if (isInBounds(x, y)) {
      cells[y][x] = value;
    }
  }

  int getPixel(int x, int y) {
    if (isInBounds(x, y)) {
      return cells[y][x];
    } else {
      return -1;
    }
  }

  bool isInBounds(int x, int y) {
    return x >= 0 && x < width && y >= 0 && y < cells.length;
  }

  void update() {
    for (var x = 0; x < width; x++) {
      for (var y = cells.length - 2; y >= 0; y--) {
        final currentPixel = cells[y][x];
        if (currentPixel == 0) continue;

        final pixelBelow = getPixel(x, y + 1);

        if (pixelBelow == 0) {
          cells[y + 1][x] = currentPixel;
          cells[y][x] = 0;
        }
      }
    }
  }
}

void main() {
  const gridWidth = 700;
  const gridHeight = 700;
  const numTicks = 500;

  // Create grids and initialize randomly
  final random = Random();
  final flatGrid = FallingSandGrid(
    width: gridWidth,
    cells: Uint8List.fromList(List.filled(gridWidth * gridHeight, 0)),
  );
  final nestedGrid = FallingSandGridNested(
    width: gridWidth,
    cells: List.generate(
      gridHeight,
      (y) => Uint8List.fromList(List.filled(gridWidth, 0)),
      growable: false,
    ),
  );

  for (var i = 0; i < 2300; i++) {
    final x = random.nextInt(gridWidth);
    final y = random.nextInt(gridHeight);
    flatGrid.setPixel(x, y, 1);
    nestedGrid.setPixel(x, y, 1);
  }

  // Benchmark flat grid
  final flatGridStopwatch = Stopwatch()..start();
  for (var i = 0; i < numTicks; i++) {
    flatGrid.update();
  }
  flatGridStopwatch.stop();

  // Benchmark nested grid
  final nestedGridStopwatch = Stopwatch()..start();
  for (var i = 0; i < numTicks; i++) {
    nestedGrid.update();
  }
  nestedGridStopwatch.stop();

  final flatTime = flatGridStopwatch.elapsedMicroseconds.toDouble();
  final nestedTime = nestedGridStopwatch.elapsedMicroseconds.toDouble();

  print('Flat Grid Time: ${flatTime / 1000} ms');
  print('Nested Grid Time: ${nestedTime / 1000} ms');

  final speedup = ((nestedTime - flatTime) / nestedTime) * 100;
  print('The flat list is ${speedup.toStringAsFixed(2)}% faster');
}