CellManager is inefficient

[jonathanpwang]

Currently CellManager.get_position is doing a for loop over all columns to get the minimum row count each time. This actually takes a good amount of time when the circuit is wide and witness generation time starts becoming a concern.

I am not familiar with all the cases of CellManager. If it's possible to know the total number of usable rows by the CellManager beforehand, then it is more efficient to assign one column at a time for O(1) search time. But since the circuits are mostly written with a row-by-row framework, this is probably not possible. However then at least one could keep the minimum row counts in a heap data structure for O(log num_columns) performance?

[Brechtpd]

Maybe best to specify you're talking about the CellManager in the keccak implementation right? (I don't think this is done in the EVM circuit, also sorry Carlos! ;)

Not sure about specifics about this specifically, but yeah I'm sure there are still many inefficiencies in the keccak witness generation as I (and others I believe) haven't really spend any time optimizing that part yet.

[jonathanpwang]

Ah yes, I assumed the CellManagers were all similar, but I guess not!