)]}'
{
  "commit": "98e1227cb7bfe4b845c7fc5136e83f8d368065b2",
  "tree": "f3e9a1725c08f756b0d24c2bbf401921d13697ec",
  "parents": [
    "acfb1062f4c3f08cdfeb7fef496121d4f5edfc3f"
  ],
  "author": {
    "name": "David Benjamin",
    "email": "davidben@google.com",
    "time": "Sat Jun 10 00:29:28 2023 -0400"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Tue Jun 13 21:42:15 2023 +0000"
  },
  "message": "Make bn_mod_lshift_consttime faster\n\nbn_mod_lshift_consttime currently calls bn_mod_lshift1_consttime in a\nloop, but between needing a temporary value and having to guard against\nsome complications in our fixed-width BIGNUM convention, it\u0027s actually\npicking up a lot of overhead.\n\nThis function is currently called to setup Montgomery contexts with\nsecret moduli (RSA primes). The setup operation is not\nperformance-sensitive in our benchmarks, because it is amortized away in\nRSA private key signing. However, as part of reducing thread contention\nwith the RSA object, I\u0027m planning to make RSA creation, which we do\nbenchmark, eagerly fill in the Montgomery context.\n\nWe do benchmark RSA parsing, so adding a slow Montgomery setup would\nshow up in benchmarks. This distinction is mostly artificial. Work done\non creation and work done on first use is still work done once per RSA\nkey. However, work done on key creation may slow server startup, while\nwork deferred to first use is amortized but less predictable.\n\nEither way, from this CL, and especially the one to follow it, we have\nplenty of low-hanging fruit in this function. As a bonus, this should\nhelp single-use RSA private keys, but that\u0027s not something we currently\nbenchmark.\n\nModulus sizes below chosen based on:\n\n- Common curve sizes (moot because we use a variable-time setup anyway)\n\n- Common RSA modulus sizes (also variable-time setup)\n\n- Half of common RSA modulus sizes (the secret primes involved)\n\nOf these, only the third category matters. The others can use the\ndivision-based path where it\u0027s faster anyway. However, by the end of\nthis patch series, they\u0027ll get a bit closer, so I benchmarked them all\nto compare. (Though division still wins in the end.)\n\nBenchmarks on an M1 Max:\n\nBefore:\nDid 528000 256-bit mont (constime) operations in 2000993us (263869.0 ops/sec)\nDid 312000 384-bit mont (constime) operations in 2001281us (155900.1 ops/sec)\nDid 246000 512-bit mont (constime) operations in 2001521us (122906.5 ops/sec)\nDid 191000 521-bit mont (constime) operations in 2006336us (95198.4 ops/sec)\nDid 98000 1024-bit mont (constime) operations in 2001438us (48964.8 ops/sec)\nDid 55000 1536-bit mont (constime) operations in 2025306us (27156.4 ops/sec)\nDid 35000 2048-bit mont (constime) operations in 2022714us (17303.5 ops/sec)\nDid 17640 3072-bit mont (constime) operations in 2028352us (8696.7 ops/sec)\nDid 10290 4096-bit mont (constime) operations in 2065529us (4981.8 ops/sec)\n\nAfter:\nDid 712000 256-bit mont (constime) operations in 2000454us (355919.2 ops/sec) [+34.9%]\nDid 440000 384-bit mont (constime) operations in 2001121us (219876.8 ops/sec) [+41.0%]\nDid 259000 512-bit mont (constime) operations in 2003709us (129260.3 ops/sec) [+5.2%]\nDid 212000 521-bit mont (constime) operations in 2007033us (105628.6 ops/sec) [+11.0%]\nDid 107000 1024-bit mont (constime) operations in 2018551us (53008.3 ops/sec) [+8.3%]\nDid 57000 1536-bit mont (constime) operations in 2001027us (28485.4 ops/sec) [+4.9%]\nDid 37000 2048-bit mont (constime) operations in 2039631us (18140.5 ops/sec) [+4.8%]\nDid 20000 3072-bit mont (constime) operations in 2041163us (9798.3 ops/sec) [+12.7%]\nDid 11760 4096-bit mont (constime) operations in 2007195us (5858.9 ops/sec) [+17.6%]\n\nBug: 316\nChange-Id: I06f4a065fdecc1aec3160fe32a41e200538d1ee3\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/60685\nAuto-Submit: David Benjamin \u003cdavidben@google.com\u003e\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\nCommit-Queue: Adam Langley \u003cagl@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "6de5a4303ae41c49dc803d3a206865b517358bf5",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/div.c",
      "new_id": "6c13716920172aa08b09a7d7a728d968fccd5c6d",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/div.c"
    }
  ]
}