search

scroll-tech / ceno

Accelerate Zero-knowledge Virtual Machine by Non-uniform Prover Based on GKR Protocol
Apache License 2.0
53 stars 6 forks source link

Refactor `RowMajorMatrix` with a safe API #600

Open naure opened 3 days ago

naure commented 3 days ago

This type uses MaybeInit with the expectation that assignment code will set values in every cell. Moreover, the matrix is usually larger than requested in new(…) because it is padded to a power-of-two size. All in all that is error-prone and hard to debug (been there, #597).

Rewrite this with a safe and easy API.

One idea is to use Vec::with_capacity and extend. Another way could be based on iterators and use collect_vec.

Regarding padding, the type should take the responsibility to fill the padding rows. It is not actually necessary to allocate that padding space. The padding can be represented with a single value to repeat, and the padding is done at the last possible time in de_interleaving. It could look like a method set_padding_strategy(…), see the existing enum InstancePaddingStrategy.

matthiasgoergens commented 3 days ago

How much time or memory are we actually saving with the uninit shenanigans?

naure commented 2 days ago

The proposed approach should be marginally faster than the current one thanks to postponing the padding, but this issue is more about ease of use.

matthiasgoergens commented 2 days ago

Yes. I'm just curious how much we are gaining from the shenanigans currently in master compared to not doing anything special?

Do you know whether we ever did some benchmarks?

naure commented 2 days ago

There is only the one implementation as far as I know.