I know that no one is working on BigInts right now, so where should I post my suggestions for optimizations so that someone will see them when they start on BigInt optimizations?
I have been doing a lot of work with BigInts recently, and I have quite a few ideas of how to massively optimize BigInts. I looked through the Chromium source code, and there does not seem to be much in the way of compilation optimizations right now. Some of my ideas are simple and effectives, while others may be a lot more complicated and questionable. I even have some controversial suggestions. Without further ado, here are my suggestions. Simple optimizations are given below. None of the simple optimizations below should require JIST dynamic type-prediction before the optimization can be inserted because if `x` turns out not to be a BigInt, then an error is simply be thrown. However, one could extend the optimizations below to utilize dynamic type-prediction so that situations in which the compiler cannot be certain whether the optimization can be applied do not have to be immediately rejected. None of the optimizations below should slow down general compilation because one can conditionally apply passes for the below optimizations only if the compiler sees BigInt literals in the source code. 1. Do not create a copy with assignment-operators against constants. For example, `x += 15n` should add 15n to x, not add 15n to a copy of x. 2. Convert multiplication and division into bit shifting where the number involved is a power of two. For example, `x * 8n` and `x / 4n` becomes `x << 3n` and `x >> 2n` respectively. 3. Optimize shift-right&and-field into array-like memory access. For example, `(x >> 256n) & 0xffffn` becomes something like `((int *) x)[ 8 ] & 0xffff` (I apologize for my egregious attempt to mimic C). 4. Optimize bitwise-assignment followed by a number left-shifted up a certain number of bits into array-like memory access. For example, `x |= 103n << 256;` becomes something like `((int *) x)[ 8 ] |= 103`. For example, `x ^= 27n << 192n;` becomes something like `((int *) x)[ 6 ] ^= 103`. Controversial and medium-difficulty optimizations are given below. 1. Allow us to preallocate the size of a BigInt stored initially in a variable at the `var` where the variable is scoped via `0n << allocationBits`. For example, `var x=0n << 65536n` would pre-allocate 65536 bits of memory or 8192 bytes. However, `var x=0n; x <<= 65536n;` would not pre-allocate any memory. For this optimization to be effective, one must also install the deduplication optimization (simple optimization #1). 2. Optimize for true unsigned 64-bit integer optimizations via and-masks instead of trying something over-complicated like `BigInt.asUint64`, where one would need all sorts of complex hooks incase if the function gets overridden or whatever else might happen. For example, `var k=2n; k=(2n << 5n) & 0xffffffffffffffffn; k = k * k & 0xffffffffffffffffn; k = (k - (k * k & 0xffffffffffffffffn)) & 0xffffffffffffffffn; k = k / 71n & 0xffffffffffffffffn;` becomes entirely fast unsigned 64-bit operations. It looks ugly, but it's not half as bad as it looks: Gzip would minimize the impact on file size. I would imagine that doing these optimizations in this manner might simply be as simple as just copy-paste-and-tweak all the almost-asm integer optimizations: `i = i + 1|0` with almost-asm integer optimizations becomes `i = i + 1n & 0xffffffffffffffffn` with unsigned 64-bit optimizations. This would not have to be the permanent way that 64-bit operations are done. Instead, think of it like a piece of candy being freely giving to us performance-enthusiasts. Advanced, complex, and difficult optimizations are given below. 1. Use reference-counting to further reduce unnecessary copying, which sucks up a great deal more of the execution time than it should because memory not in the cache is sooooo slow. Each BigInt is a pointer to the space where it is actually stored. At the stored data, add an extra field which we shall call bnReferenceCount. When a BigInt variable appears on the left side of an assignment, its reference count goes down by one. For each reference on the right side of the assignment, increment bnReferenceCount by one. When a BigInt variable is used, its bnReferenceCount is checked. If bnReferenceCount <= 1, then it is OKAY for the operator to modify the original contents of the BigInt variable without creating a copy. If bnReferenceCount > 1, then create a copy of the variable (the copy has a bnReferenceCount of 1) and decrement the value of the bnReferenceCount field on the original. Let us examine `x = x ** 5n + x`. Prior to the statement, the bnReferenceCount of the BigInt pointed to by `x` is 1. The compiler statically asserts that the assignment to x on the left decrements bnReferenceCount to 0 and the next two uses of x increment bnReferenceCount by 2, resulting in a net value of 2 for the bnReferenceCount of `x`. Right before the statement is executed at runtime, we subtract 1 and add 2 to the bnReferenceCount field of the object pointed to by `x`, yielding a bnReferenceCount of 2 for `x`. Then, the first occurance of `x`, where x is exponentiated, creates a copy of `x` and decrements the bnReferenceCount of the original because there is one less thing pointing to the original. Then, the copy is raised to the power of five without further copying because copies, by default, have a bnReferenceCount of 1. The next occurance of x does not initiate a copy-operation because its bnReferenceCount is 1. During the final addition, both the copy (left) and the original (right) are candidates for storing the result of the addition because they both have a bnReferenceCount of 1. So, the longer one--copy--is chosen as the final holder. the copy and the original are added and the result is stored in copy. Then, because the original is no longer used, its bnReferenceCount is decremented to 0. Because its bnReferenceCount reaches 0, the original can be submitted to the garbage collector for the next cycle. Finally, the copy is assigned to the variable x, thus incrementing the copy's bnReferenceCount to 2. The statement has finished and the last BigInt to be used was the copy, so the copy's bnReferenceCount is decremented down to 1. After the statement, `x` holds a new BigInt whose bnReferenceCount is 1. -- -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev --- You received this message because you are subscribed to the Google Groups "v8-dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/a72abe92-9617-4e0c-9b6d-32cd2ea275bc%40googlegroups.com.
