barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

Trace sorting: Make q_arith boolean

Open ledwards2225 opened this issue 1 year ago • 1 comments

q_arith can currently take arbitrary values. We actively use q_arith = 0,1,2,3. (Comments in code suggest that at one time there was some use for q_arith > 3 but this doesn't seem to be used anywhere). This is an obstacle to representing selectors as boolean and/or as ranges rather than polynomials. I discussed this with Zac and he proposed the following to get rid of this:

  • For q_arith = 3, simply do the less efficient thing and add an additional gate wherever this is used. (Currently only in nnf addition and subraction).
  • For q_arith = 2, add a new selector q_5 that simply scales w_4_shift. This is as opposed to adding a whole new gate selector e.g. q_arith_2 which would require an entirely new "block", which has high cost once blocks are of a large fixed size.

ledwards2225 avatar Mar 18 '24 18:03 ledwards2225

This is likely not worthwhile. Motivation was to have very simple form for gate selectors (boolean, constant over an "active" range) but a) our polynomial class already allows memory efficient storage of these polynomials and b) the hope of nice constant structure is inhibited by "dummy gates" where the selector is zero within a "active range" for the gate type.

ledwards2225 avatar Apr 15 '25 22:04 ledwards2225