- 15 Jul, 2021 1 commit
-
-
Jakob Kummerow authored
Dividing by first computing a multiplicative inverse is faster than Burnikel-Ziegler division for very large inputs. Bug: v8:11515 Change-Id: Ice45690c3fa4eef7102d418cdd3d82a942a076c5 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3015573 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Maya Lekova <mslekova@chromium.org> Cr-Commit-Position: refs/heads/master@{#75743}
-
- 02 Jul, 2021 1 commit
-
-
Jakob Kummerow authored
Bug: v8:11515 Change-Id: I598e57de1c7d6219096dd2306fa206faf7247bb5 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2999869 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Maya Lekova <mslekova@chromium.org> Cr-Commit-Position: refs/heads/master@{#75526}
-
- 01 Jul, 2021 1 commit
-
-
Jakob Kummerow authored
When adding up the results of the recursive steps, the Karatsuba algorithm can temporarily have intermediate results that are one bit bigger than the final result. This patch makes sure we handle that case correctly. Since that extra bit would always get subtracted again, the old code would not have caused incorrect results or memory corruption, but it did run into DCHECK-failures, and potentially could have caused segfaults. Bug: v8:11515, chromium:1223724 Change-Id: I3592835d01cc36def8f0a9bae625e9249864ef78 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2988758Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Cr-Commit-Position: refs/heads/master@{#75509}
-
- 25 Jun, 2021 1 commit
-
-
Jakob Kummerow authored
This just moves the existing algorithm, and translates it from Handle<BigInt> to Digits as underlying data format. Bug: v8:11515 Change-Id: Ieefee4e953e14f4c574aebab94d825ddb7c31f8c Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2975304 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Maya Lekova <mslekova@chromium.org> Cr-Commit-Position: refs/heads/master@{#75391}
-
- 22 Jun, 2021 1 commit
-
-
Jakob Kummerow authored
The Burnikel-Ziegler division algorithm is used for divisors with 57 or more internal digits. It has better asymptotic complexity than "schoolbook" division because it can make use of fast multiplication under the hood. Bug: v8:11515 Change-Id: Ib5d573a0afa560d42972c4ae06aff810a8b9cadb Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2960221 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Maya Lekova <mslekova@chromium.org> Cr-Commit-Position: refs/heads/master@{#75310}
-
- 15 Jun, 2021 1 commit
-
-
Jakob Kummerow authored
No changes to the algorithm; minor speedup due to the move from Handle<BigInt> to Digits. Bug: v8:11515 Change-Id: Id85fe4f0c276d3ad826fee79205719092d0e0715 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2947412 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Maya Lekova <mslekova@chromium.org> Cr-Commit-Position: refs/heads/master@{#75158}
-
- 07 Jun, 2021 1 commit
-
-
Jakob Kummerow authored
This is a reland of 81dd3f42, which was a reland of 59eff3bf Original change's description: > [bigint] Karatsuba multiplication > > The Karatsuba algorithm is used for BigInts with 34 or more internal > digits, and thanks to better asymptotic complexity provides greater > speedups the bigger the inputs. > > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283 > Reviewed-by: Michael Achenbach <machenbach@chromium.org> > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > Cr-Commit-Position: refs/heads/master@{#74916} Bug: v8:11515 Change-Id: I08f7d59dfa39fb3b532684685afd9fa750e0e84e Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933666Reviewed-by: Clemens Backes <clemensb@chromium.org> Reviewed-by: Michael Achenbach <machenbach@chromium.org> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Cr-Commit-Position: refs/heads/master@{#74969}
-
- 02 Jun, 2021 4 commits
-
-
Clemens Backes authored
This reverts commit 81dd3f42. Reason for revert: Does not compile on MSVC: https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Win64%20-%20msvc/18017/overview Original change's description: > Reland "[bigint] Karatsuba multiplication" > > This is a reland of 59eff3bf > > Original change's description: > > [bigint] Karatsuba multiplication > > > > The Karatsuba algorithm is used for BigInts with 34 or more internal > > digits, and thanks to better asymptotic complexity provides greater > > speedups the bigger the inputs. > > > > Bug: v8:11515 > > Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036 > > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283 > > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> > > Reviewed-by: Michael Achenbach <machenbach@chromium.org> > > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > > Cr-Commit-Position: refs/heads/master@{#74916} > > Bug: v8:11515 > Change-Id: I5ece2ff29ef11ea304980c053887d9746cfc80bc > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933497 > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> > Cr-Commit-Position: refs/heads/master@{#74922} Bug: v8:11515 Change-Id: Ie4a80256174fc8d9f714c01f012ac2dc6247a220 No-Presubmit: true No-Tree-Checks: true No-Try: true Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933665 Auto-Submit: Clemens Backes <clemensb@chromium.org> Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com> Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com> Cr-Commit-Position: refs/heads/master@{#74926}
-
Jakob Kummerow authored
This is a reland of 59eff3bf Original change's description: > [bigint] Karatsuba multiplication > > The Karatsuba algorithm is used for BigInts with 34 or more internal > digits, and thanks to better asymptotic complexity provides greater > speedups the bigger the inputs. > > Bug: v8:11515 > Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036 > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283 > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> > Reviewed-by: Michael Achenbach <machenbach@chromium.org> > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > Cr-Commit-Position: refs/heads/master@{#74916} Bug: v8:11515 Change-Id: I5ece2ff29ef11ea304980c053887d9746cfc80bc Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933497Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Cr-Commit-Position: refs/heads/master@{#74922}
-
Maya Lekova authored
This reverts commit 59eff3bf. Reason for revert: Breaks UBSan - https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Linux64%20UBSan/16697/overview Original change's description: > [bigint] Karatsuba multiplication > > The Karatsuba algorithm is used for BigInts with 34 or more internal > digits, and thanks to better asymptotic complexity provides greater > speedups the bigger the inputs. > > Bug: v8:11515 > Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036 > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283 > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> > Reviewed-by: Michael Achenbach <machenbach@chromium.org> > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > Cr-Commit-Position: refs/heads/master@{#74916} Bug: v8:11515 Change-Id: Ifd3d651a26441ba36a23724c6eb1a9915f6e41a8 No-Presubmit: true No-Tree-Checks: true No-Try: true Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2933496 Auto-Submit: Maya Lekova <mslekova@chromium.org> Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com> Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com> Cr-Commit-Position: refs/heads/master@{#74918}
-
Jakob Kummerow authored
The Karatsuba algorithm is used for BigInts with 34 or more internal digits, and thanks to better asymptotic complexity provides greater speedups the bigger the inputs. Bug: v8:11515 Change-Id: I5ab0e318173ea4a02ced3f156d3c17e0259c5036 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782283 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Michael Achenbach <machenbach@chromium.org> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> Cr-Commit-Position: refs/heads/master@{#74916}
-
- 19 Apr, 2021 1 commit
-
-
Jakob Kummerow authored
Also replace the schoolbook algorithm with an optimized version that runs about twice as fast. This also adds infrastructure to support interrupt checks from BigInt library code. Bug: v8:11515 Change-Id: I5f812913697384afca98937e1fb7361b4ec22d62 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2773043 Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Reviewed-by: Michael Achenbach <machenbach@chromium.org> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> Cr-Commit-Position: refs/heads/master@{#74045}
-
- 23 Mar, 2021 1 commit
-
-
Jakob Kummerow authored
This is a reland of c4b44d5d Original change's description: > [bigint] Begin src/bigint refactoring > > This patch moves a first function, Compare, from src/objects/bigint.cc > to src/bigint/, to blaze the trail. More to follow! > > Bug: v8:11515 > Change-Id: Id7fa0b40ea852dbed1360f7ab439cb32d0c15762 > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2737295 > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > Reviewed-by: Hannes Payer <hpayer@chromium.org> > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> > Cr-Commit-Position: refs/heads/master@{#73511} Bug: v8:11515 Change-Id: I50a81593a8acaa91161bb01a445bddbb8e6315c4 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2773804Reviewed-by: Hannes Payer <hpayer@chromium.org> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Cr-Commit-Position: refs/heads/master@{#73610}
-
- 18 Mar, 2021 2 commits
-
-
Leszek Swirski authored
This reverts commit c4b44d5d. Reason for revert: UBSan failures (https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Linux64%20UBSan/15621/overview) Original change's description: > [bigint] Begin src/bigint refactoring > > This patch moves a first function, Compare, from src/objects/bigint.cc > to src/bigint/, to blaze the trail. More to follow! > > Bug: v8:11515 > Change-Id: Id7fa0b40ea852dbed1360f7ab439cb32d0c15762 > Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2737295 > Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> > Reviewed-by: Hannes Payer <hpayer@chromium.org> > Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> > Cr-Commit-Position: refs/heads/master@{#73511} Bug: v8:11515 Change-Id: I98f3e385c785297b1b71de07fc4835da2bbe816c No-Presubmit: true No-Tree-Checks: true No-Try: true Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2773048 Auto-Submit: Leszek Swirski <leszeks@chromium.org> Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com> Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com> Cr-Commit-Position: refs/heads/master@{#73515}
-
Jakob Kummerow authored
This patch moves a first function, Compare, from src/objects/bigint.cc to src/bigint/, to blaze the trail. More to follow! Bug: v8:11515 Change-Id: Id7fa0b40ea852dbed1360f7ab439cb32d0c15762 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2737295Reviewed-by: Thibaud Michaud <thibaudm@chromium.org> Reviewed-by: Hannes Payer <hpayer@chromium.org> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org> Cr-Commit-Position: refs/heads/master@{#73511}
-