Skip to content

fix: fft domain precompute thread safety#46

Merged
ThomasPiellard merged 1 commit intodevelopfrom
fix/domain_precompute
Apr 28, 2021
Merged

fix: fft domain precompute thread safety#46
ThomasPiellard merged 1 commit intodevelopfrom
fix/domain_precompute

Conversation

@gbotrel
Copy link
Copy Markdown
Collaborator

@gbotrel gbotrel commented Apr 28, 2021

Missed that in my review of #45 .

The pattern

BitReverse(domain.CosetTableInv[coset-1])
// ...  scale by coset
BitReverse(domain.CosetTableInv[coset-1])

is not thread safe, and quite wasteful.

Replaced by dynamically computing the correct index in the coset table:

parallel.Execute(len(a), func(start, end int) {
	for i := start; i < end; i++ {
		irev := bits.Reverse64(uint64(i)) >> nn
		a[i].Mul(&a[i], &domain.CosetTable[coset-1][int(irev)])
	}
})

Benchmark:

BenchmarkFFT/fft_2**19bits_(cosets_without_precomputations)-8     63984013      43923680      -31.35%

Also did few style adjustment with less if -> if -> else -> if statements.

@gbotrel gbotrel requested a review from ThomasPiellard April 28, 2021 00:54
@CLAassistant
Copy link
Copy Markdown

CLAassistant commented Apr 28, 2021

CLA assistant check
All committers have signed the CLA.

@gbotrel gbotrel changed the base branch from master to develop April 28, 2021 00:54
@ThomasPiellard ThomasPiellard merged commit 6bd055b into develop Apr 28, 2021
@gbotrel gbotrel deleted the fix/domain_precompute branch April 28, 2021 15:21
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