Skip to content

Added optional precompute parameter in FFT domain initialization#45

Merged
gbotrel merged 6 commits intodevelopfrom
hotfix/issue_36
Apr 27, 2021
Merged

Added optional precompute parameter in FFT domain initialization#45
gbotrel merged 6 commits intodevelopfrom
hotfix/issue_36

Conversation

@ThomasPiellard
Copy link
Copy Markdown
Contributor

@ThomasPiellard ThomasPiellard commented Apr 27, 2021

This PR fixes #36 a performance loss of the FFT which occurred when the support of arbitrary cosets was added.

Description

When creating an FFT domain, a boolean value is now passed as parameter to force some pre computations, namely the BitReverse of the coset table. Forcing the pre computing or not is a time/memory trade off. Forcing the pre computations doubles the memory needed to stored a domain.

API breaking changes

func NewDomain(m, depth uint64, precomputeReversedTable bool) *Domain
instead of:
func NewDomain(m, depth uint64) *Domain

Benchmarks

MBP 2.2GHz 6-core i7 - 16GB RAM

BenchmarkFFT/fft_2**18bits_(cosets_without_precomputations)-12                48          20933738 ns/op
BenchmarkFFT/fft_2**18bits_(cosets_with_precomputations)-12                   96          12964353 ns/op

@CLAassistant
Copy link
Copy Markdown

CLAassistant commented Apr 27, 2021

CLA assistant check
All committers have signed the CLA.

@ThomasPiellard ThomasPiellard requested a review from gbotrel April 27, 2021 20:54
@gbotrel gbotrel changed the title Hotfix/issue 36 Added optional precompute parameter in FFT domain initialization Apr 27, 2021
@gbotrel
Copy link
Copy Markdown
Collaborator

gbotrel commented Apr 27, 2021

Looks good to me, merging. May revisit with optimization work on Consensys/gnark/issues/69

@gbotrel gbotrel merged commit 128e75d into develop Apr 27, 2021
@gbotrel gbotrel deleted the hotfix/issue_36 branch April 27, 2021 21:32
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants