search

cambrian / accumulator

Cryptographic accumulators in Rust.
https://cambrian.github.io/accumulator
MIT License
133 stars 34 forks source link

WIP: Speeding up accumulators. #24

Closed whaatt closed 5 years ago

whaatt commented 5 years ago

Definitely more stuff to look into here, but delete on 50 elements is made about 4x faster if the ShamirTrick is applied in a MergeSort-fashion (as opposed to iteratively), since the average size of the inputs to ShamirTrick should go down.

eddiew commented 5 years ago

good idea to use the merge sort technique, and to make it general. 3 changes to make

  1. Why bother with the Never thing if we have to re-derive anyway? Experienced rust devs should recognize the empty enum pattern.
  2. The merge sort technique is called divide-and-conquer. let's rename try_merge_reduce to divide_and_conquer, as well as rename the related fns/vars to reflect this.
  3. Let's reimplement try_merge_reduce to not operate over a mutable slice, since the cost of cloning which is required in delete and merge_product is non-trivial. I would use the common recursive form. This should also make it much cleaner.
whaatt commented 5 years ago

  1. Yeah, not super attached to this; made the change since the future preferred way to write an uninhabited struct is Type(!) once the ! (Never) type lands in stable. Will defer to you on whether we should just keep the empty enum pattern until that happens.

  2. tru

  3. Agreed that recursion is cleaner (and internally requires the same N allocations). Motivation behind the iterative version (should've added this in a comment) is that in general we might get away with just consuming elem_witnesses in delete rather than borrowing. In which case the iterative solution would require no extra allocations.

Still looking into (3) though.

eddiew commented 5 years ago

re 1. let's keep the empty enums for the time being re 3, yeah, see if it's true whether or not we can consume the elem_witnesses. if all of our use-cases turn out to require clones, we may as well use the cleaner recursive implementation

whaatt commented 5 years ago

changed (1) and (2)

also changed to recursive impl; I benchmarked the no-allocation version without the cloning and it wasn't appreciably faster (runtime is dominated by Shamir it seems)

eddiew commented 5 years ago

Looks good now. Why don't we also make shamir_trick return a Result<> instead of an Option? Should save a few lines

Edit: nevermind, since the error has to be converted to an AccError anyway