Improve performance of rotate function

[becheran]

See discussion in #32

[Shir0kamii]

We were thinking that a better implementation would probably need to reorder the grid, rather than creating a new one. The problem is that it implies an in-place transpose.

We already tried the "follow-the-cycle" algorithm, but while it is O(n) in time and memory just like the currently implemented transpose, it is also half as fast.

The other option we can explore would be to support column-major grids. Indeed, a transposed row-major grid is the same grid in column-major order. I see two ways of doing that, but they share some issues.

The first way would be to include a GridOrder enum inside the grid. The implementation would be simple, but it would slow access to the grid's cells because we would need to dispatch the transform from 2d to 1d.

The second way would be to add a second generic type on the grid. I think a snippet will be more understandable than a long description:

trait GridOrder {
    type Counterpart: GridOrder;

    fn counterpart_order(self) -> Self::Counterpart;
    fn index_in_grid<T>(grid: &Grid<T, Self>, row: usize, col: usize) -> usize;
}

struct RowMajor;
struct ColumnMajor;
enum DynamicOrder {
    RowMajor,
    ColumnMajor,
}

impl GridOrder for RowMajor { ... }
impl GridOrder for ColumnMajor { ... }
impl GridOrder for DynamicOrder { ... }

struct Grid<T, O = RowMajor> { ... }

The signature for transpose would then look like fn transpose(self) -> Grid<T, <O as GridOrder>::Counterpart>. The change of grid type could be problematic if the grid is embedded in another data structure, that's why I would include an option for dynamic order, akin to the first solution. The good part would be that it shouldn't slow things down for users not using the grid transforms.

In both solutions, it would introduce an issue with the grid[x][y] syntax since grid[x] wouldn't be able to return &[T] while in column-major order, and I don't see any way to solve this.

I can take the time to experiment with either or both solutions, but I would like your input before I commit to this effort. Does this make any sense to you ? Is it worthwhile to pursue ?

[becheran]

Thanks for taking the time. Interesting that transpose is a change in row to column major order. Didn't know that.

I think it would be great if grid would be flexible in the sense that one can initiate a row-major or a column-major one depending on what is better for a given situation and switch between both types if needed using the transpose method. Though, it would be quite some effort to update all existing functions.

What I don't understand is what you mean with?

, but it would slow access to the grid's cells because we would need to dispatch the transform from 2d to 1d.

Right now all operations are alraedy performed on a 1D datastruct internaly. That is also the reason why push_row is a lot faster than push_column.

Loosing the grid[x][y] syntaxt might also not be necessary. It is just a matter of what x is. So if we update the docs to explain that x is either the row or the column depending on the Order, it would still make sense to have such an implementation I guess.

So it does make a lot of sense to me to also support column-major orders for the grid. Though, it will be quite some effort to implement that I guess.

[Shir0kamii]

Yes, it will be quite the task, but I'm willing to give it a shot! Luckily I have time on my hands this summer.

Right now all operations are alraedy performed on a 1D datastruct internaly.

Yes I know, but the methods do take 2D coordinates, and you have to transform them to a 1D index. If we embed a GridOrder enum inside the grid, you'd have to dispatch between the two formulas. It wouldn't be much slower, but this kind of access is probably done a lot, which is why I see it as an issue.

Loosing the grid[x][y] syntaxt might also not be necessary. It is just a matter of what x is.

In my opinion, the exposed API should be as independent from the grid order as possible. Switching from grid[row][col] to grid[col][row] based on internal ordering does strikes me as odd.

I will start with the simple solution, and start a MR in the following days, on which we will be able to discuss specifics.

[antonmarsden]

@Shir0kamii @becheran Not wanting to blow my own trumpet, but I have written performant flip_rows() and flow_cols() functions in my TooDee library. Also, my insert_col() and insert_row() impls are both quick. Feel free to repurpose the code for your needs - see https://github.com/antonmarsden/toodee