scroll-tech / halo2

Other
43 stars 39 forks source link

will this optimisation improve a little bit performace? #60

Closed lightsing closed 3 months ago

lightsing commented 1 year ago

This demo pr add some in-place simplify of Expression and can collapse some certain case expressions. The simplification is best-effort, it cannot simplify to the simplest representation since it's a undecidable problem. And it's not worth to simplify it to simplest since it MUST introduce more cost.

Especially the case of rw_counter_offset, every lookup with condition will cause it adds the condition expo to rw_counter_offset, like:

// rw_counter_offset = some_expr
cb.condition(condition_expr, |cb| {
  cb.rw_lookup(...) // rw_counter_offset = some_expr + condition_expr
  cb.rw_lookup(...) // rw_counter_offset = some_expr + condition_expr + condition_expr
  ...
})

by apply following rule, it can fold expressions like that:

introduce complex (this one is not that complex) optimisation to basic building blocks which code usually don't change could be ok