the tower12() -> calcFrobeniusCoefficients() calls on the top level of modules freeze and slow down application start up #229
Description
see: https://github.com/paulmillr/noble-curves/blob/main/src/bls12-381.ts#L156
since the parameters for calcFrobeniusCoefficients() are always the same on startup, the return values should be pre-memoized to avoid unnecessary computation on app startup, below is a quick hack to memoise the return value, and it improves our react native based app startup by at least 1 second:
diff --git a/abstract/tower.js b/abstract/tower.js
index 5fccbe282c9945380d08f301f491ed98952916d0..0bb72412eda066bf43e9904922a42aab7d4fb369 100644
--- a/abstract/tower.js
+++ b/abstract/tower.js
@@ -19,7 +19,167 @@ const utils_ts_1 = require("./utils.js");
// Be friendly to bad ECMAScript parsers by not using bigint literals
// prettier-ignore
const _0n = BigInt(0), _1n = BigInt(1), _2n = BigInt(2), _3n = BigInt(3);
+
+
+// Fp -> nonResidue -> modulus -> degree -> num -> divsor
+const prebuiltMemoMap = {
+ '{"ORDER":"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787n","isLE":false,"BITS":381,"BYTES":48,"MASK":"4925250774549309901534880012517951725634967408808180833493536675530715221437151326426783281860614455100828498788351n","ZERO":"0n","ONE":"1n"}':
+ {
+ '"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n"':
+ {
+ '"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787n"':
+ {
+ '2': {
+ '1': {
+ undefined: [
+ [
+ 1n,
+ 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n,
+ ],
+ ],
+ },
+ },
+ },
+ },
+ },
+ '{"ORDER":"16019282247729705411943748644318972617695120099330552659862384536985976748491357143400656079302193429974954385540170730531103884539706905936200202421036435811093013034271812758016407969496331661418541023677774899971425993489485369n","isLE":false,"NONRESIDUE":{"c0":"1n","c1":"1n"},"BITS":762,"BYTES":96,"MASK":"24258095192198577111702804507226602425888844017448384549047688094157046135724638848919975137947601217976370792142673018846430938189293974866316988672518455300069609000325779774222895087993725700394734362401819824232700732090875903n","ZERO":{"c0":"0n","c1":"0n"},"ONE":{"c0":"1n","c1":"0n"}}':
+ {
+ '{"c0":"1n","c1":"1n"}': {
+ '"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787n"':
+ {
+ '12': {
+ '1': {
+ '6': [
+ [
+ { c0: 1n, c1: 0n },
+ {
+ c0: 3850754370037169011952147076051364057158807420970682438676050522613628423219637725072182697113062777891589506424760n,
+ c1: 151655185184498381465642749684540099398075398968325446656007613510403227271200139370504932015952886146304766135027n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620351n,
+ c1: 0n,
+ },
+ {
+ c0: 2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530n,
+ c1: 1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ c1: 0n,
+ },
+ {
+ c0: 3125332594171059424908108096204648978570118281977575435832422631601824034463382777937621250592425535493320683825557n,
+ c1: 877076961050607968509681729531255177986764537961432449499635504522207616027455086505066378536590128544573588734230n,
+ },
+ {
+ c0: 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n,
+ c1: 0n,
+ },
+ {
+ c0: 151655185184498381465642749684540099398075398968325446656007613510403227271200139370504932015952886146304766135027n,
+ c1: 3850754370037169011952147076051364057158807420970682438676050522613628423219637725072182697113062777891589506424760n,
+ },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ c1: 0n,
+ },
+ {
+ c0: 1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257n,
+ c1: 2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530n,
+ },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437n,
+ c1: 0n,
+ },
+ {
+ c0: 877076961050607968509681729531255177986764537961432449499635504522207616027455086505066378536590128544573588734230n,
+ c1: 3125332594171059424908108096204648978570118281977575435832422631601824034463382777937621250592425535493320683825557n,
+ },
+ ],
+ ],
+ },
+ },
+ '6': {
+ '2': {
+ '3': [
+ [
+ { c0: 1n, c1: 0n },
+ {
+ c0: 0n,
+ c1: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ c1: 0n,
+ },
+ { c0: 0n, c1: 1n },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ c1: 0n,
+ },
+ {
+ c0: 0n,
+ c1: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ },
+ ],
+ [
+ { c0: 1n, c1: 0n },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437n,
+ c1: 0n,
+ },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ c1: 0n,
+ },
+ {
+ c0: 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n,
+ c1: 0n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ c1: 0n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620351n,
+ c1: 0n,
+ },
+ ],
+ ],
+ },
+ },
+ },
+ },
+ },
+};
+
+function bigintReplacer(_, value) {
+ if (typeof value === 'bigint') {
+ return value.toString() + 'n';
+ }
+ return value;
+}
+
+function strf(anything) {
+ if (anything === undefined) {
+ return 'undefined';
+ }
+ return JSON.stringify(anything, bigintReplacer);
+}
+
function calcFrobeniusCoefficients(Fp, nonResidue, modulus, degree, num = 1, divisor) {
+ const t = performance.now();
+ const memoizedRet =
+ prebuiltMemoMap[strf(Fp)]?.[strf(nonResidue)]?.[strf(modulus)]?.[strf(degree)]?.[
+ strf(num)
+ ]?.[strf(divisor)];
+
+ if (memoizedRet) {
+ console.log('[hacked `@noble/curves` tower.js:] hit memo cache', performance.now() - t);
+ return memoizedRet;
+ }
+
const _divisor = BigInt(divisor === undefined ? degree : divisor);
const towerModulus = modulus ** BigInt(degree);
const res = [];
@@ -33,8 +193,14 @@ function calcFrobeniusCoefficients(Fp, nonResidue, modulus, degree, num = 1, div
}
res.push(powers);
}
+
+ console.log('calcFrobeniusCoefficients::');
+ console.log(' input::', Fp, nonResidue, modulus, degree, num, divisor);
+ console.log(' output::', res);
+
return res;
}
+
// This works same at least for bls12-381, bn254 and bls12-377
function psiFrobenius(Fp, Fp2, base) {
// GLV endomorphism Ψ(P)
diff --git a/esm/abstract/tower.js b/esm/abstract/tower.js
index bc6761c527ba18eb5e8e85931336508925a6a50b..443c1fd7fe2e65a30a338d7e808a3d16f3da26bc 100644
--- a/esm/abstract/tower.js
+++ b/esm/abstract/tower.js
@@ -15,7 +15,166 @@ import { bitLen, bitMask, concatBytes, notImplemented } from "./utils.js";
// Be friendly to bad ECMAScript parsers by not using bigint literals
// prettier-ignore
const _0n = BigInt(0), _1n = BigInt(1), _2n = BigInt(2), _3n = BigInt(3);
+
+// Fp -> nonResidue -> modulus -> degree -> num -> divsor
+const prebuiltMemoMap = {
+ '{"ORDER":"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787n","isLE":false,"BITS":381,"BYTES":48,"MASK":"4925250774549309901534880012517951725634967408808180833493536675530715221437151326426783281860614455100828498788351n","ZERO":"0n","ONE":"1n"}':
+ {
+ '"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n"':
+ {
+ '"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787n"':
+ {
+ '2': {
+ '1': {
+ undefined: [
+ [
+ 1n,
+ 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n,
+ ],
+ ],
+ },
+ },
+ },
+ },
+ },
+ '{"ORDER":"16019282247729705411943748644318972617695120099330552659862384536985976748491357143400656079302193429974954385540170730531103884539706905936200202421036435811093013034271812758016407969496331661418541023677774899971425993489485369n","isLE":false,"NONRESIDUE":{"c0":"1n","c1":"1n"},"BITS":762,"BYTES":96,"MASK":"24258095192198577111702804507226602425888844017448384549047688094157046135724638848919975137947601217976370792142673018846430938189293974866316988672518455300069609000325779774222895087993725700394734362401819824232700732090875903n","ZERO":{"c0":"0n","c1":"0n"},"ONE":{"c0":"1n","c1":"0n"}}':
+ {
+ '{"c0":"1n","c1":"1n"}': {
+ '"4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787n"':
+ {
+ '12': {
+ '1': {
+ '6': [
+ [
+ { c0: 1n, c1: 0n },
+ {
+ c0: 3850754370037169011952147076051364057158807420970682438676050522613628423219637725072182697113062777891589506424760n,
+ c1: 151655185184498381465642749684540099398075398968325446656007613510403227271200139370504932015952886146304766135027n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620351n,
+ c1: 0n,
+ },
+ {
+ c0: 2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530n,
+ c1: 1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ c1: 0n,
+ },
+ {
+ c0: 3125332594171059424908108096204648978570118281977575435832422631601824034463382777937621250592425535493320683825557n,
+ c1: 877076961050607968509681729531255177986764537961432449499635504522207616027455086505066378536590128544573588734230n,
+ },
+ {
+ c0: 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n,
+ c1: 0n,
+ },
+ {
+ c0: 151655185184498381465642749684540099398075398968325446656007613510403227271200139370504932015952886146304766135027n,
+ c1: 3850754370037169011952147076051364057158807420970682438676050522613628423219637725072182697113062777891589506424760n,
+ },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ c1: 0n,
+ },
+ {
+ c0: 1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257n,
+ c1: 2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530n,
+ },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437n,
+ c1: 0n,
+ },
+ {
+ c0: 877076961050607968509681729531255177986764537961432449499635504522207616027455086505066378536590128544573588734230n,
+ c1: 3125332594171059424908108096204648978570118281977575435832422631601824034463382777937621250592425535493320683825557n,
+ },
+ ],
+ ],
+ },
+ },
+ '6': {
+ '2': {
+ '3': [
+ [
+ { c0: 1n, c1: 0n },
+ {
+ c0: 0n,
+ c1: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ c1: 0n,
+ },
+ { c0: 0n, c1: 1n },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ c1: 0n,
+ },
+ {
+ c0: 0n,
+ c1: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ },
+ ],
+ [
+ { c0: 1n, c1: 0n },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437n,
+ c1: 0n,
+ },
+ {
+ c0: 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436n,
+ c1: 0n,
+ },
+ {
+ c0: 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786n,
+ c1: 0n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350n,
+ c1: 0n,
+ },
+ {
+ c0: 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620351n,
+ c1: 0n,
+ },
+ ],
+ ],
+ },
+ },
+ },
+ },
+ },
+};
+
+function bigintReplacer(_, value) {
+ if (typeof value === 'bigint') {
+ return value.toString() + 'n';
+ }
+ return value;
+}
+
+function strf(anything) {
+ if (anything === undefined) {
+ return 'undefined';
+ }
+ return JSON.stringify(anything, bigintReplacer);
+}
+
function calcFrobeniusCoefficients(Fp, nonResidue, modulus, degree, num = 1, divisor) {
+ const t = performance.now();
+ const memoizedRet =
+ prebuiltMemoMap[strf(Fp)]?.[strf(nonResidue)]?.[strf(modulus)]?.[strf(degree)]?.[
+ strf(num)
+ ]?.[strf(divisor)];
+
+ if (memoizedRet) {
+ console.log('[hacked `@noble/curves` tower.js:] hit memo cache', performance.now() - t);
+ return memoizedRet;
+ }
+
const _divisor = BigInt(divisor === undefined ? degree : divisor);
const towerModulus = modulus ** BigInt(degree);
const res = [];
@@ -29,6 +188,11 @@ function calcFrobeniusCoefficients(Fp, nonResidue, modulus, degree, num = 1, div
}
res.push(powers);
}
+
+ console.log('calcFrobeniusCoefficients::');
+ console.log(' input::', Fp, nonResidue, modulus, degree, num, divisor);
+ console.log(' output::', res);
+
return res;
}
// This works same at least for bls12-381, bn254 and bls12-377