filecoin-project / builtin-actors

The Filecoin built-in actors
Other
82 stars 79 forks source link

fix: make util::stack run in polynomial time #1492

Closed Stebalien closed 10 months ago

Stebalien commented 10 months ago

~Make it run in C*N time instead of N^C (where C is the number of batches and N is the length of the batch).~

This is hardly the most important code to optimize, but...

Stebalien commented 10 months ago

Ok, I though this was N^C which would usually be N^3. It's not, it's CN^2, which isn't nearly as bad. I.e.:

A*B + (A+B)*C + (A+B+C)*D + ...
Stebalien commented 10 months ago

Actually, I'm completely wrong. The old logic is CN as well.

Stebalien commented 10 months ago

I.e.:

  1. For each batch.
  2. Iterate over the next batch and the base concurrently (plus not times).