Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Quadratic duplicate message check #68

Closed
Stebalien opened this issue Oct 17, 2023 · 1 comment · Fixed by #72
Closed

Quadratic duplicate message check #68

Stebalien opened this issue Oct 17, 2023 · 1 comment · Fixed by #72

Comments

@Stebalien
Copy link
Member

Right now, the "fallback" duplicate check (when blst is disabled) is has a n^2 runtime. The blst version is using a red/black tree and has a log(n) runtime.

I'd consider:

  1. At a minimum, making the fallback have a log(n) runtime (e.g., use BTreeSet).
  2. Even better, use a HashSet for both. The rust HashSet is pretty damn fast and avoids hashing entirely for small sets, IIRC, so we shouldn't have any issues there.
@Stebalien
Copy link
Member Author

Motivation: Anything other than a linear runtime will be annoying to charge for in terms of gas.

Stebalien added a commit that referenced this issue Oct 19, 2023
@Stebalien
Replace the quadradic duplicate check logic with a linear version
ffc88ec 
It's ~2% slower with 10 hashes and ~2% faster with 100 hashes (with very
noisy benchmarks). But the important part is that the runtime should
scale linearly with the number of inputs. E.g., this version is 2.5x
faster for 1000 signatures.

fixes #68
@Stebalien Stebalien mentioned this issue Oct 19, 2023
Merged
Stebalien added a commit that referenced this issue Oct 20, 2023
@Stebalien
Replace the quadradic duplicate check logic with a linear version
4989969 
It's ~2% slower with 10 hashes and ~2% faster with 100 hashes (with very
noisy benchmarks). But the important part is that the runtime should
scale linearly with the number of inputs. E.g., this version is 2.5x
faster for 1000 signatures.

fixes #68
Stebalien added a commit that referenced this issue Oct 20, 2023
@Stebalien
Replace the quadradic duplicate check logic with a linear version (#72)
89b6656 
It's ~2% slower with 10 hashes and ~2% faster with 100 hashes (with very
noisy benchmarks). But the important part is that the runtime should
scale linearly with the number of inputs. E.g., this version is 2.5x
faster for 1000 signatures.

fixes #68
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Replace the quadradic duplicate check logic with a linear version filecoin-project/bls-signatures
1 participant
@Stebalien