On Fri, Aug 2, 2013 at 12:26 PM, David Jeske <[email protected]> wrote:
> I think I now better understand why you are trying to solve this with > regions. However, I don't understand what the static-region-scoping > boundary is. The carry may be used in a successive loop-iteration, which > may itself also produce a carry in the process of using the previous carry. > Is there a form of static scope analysis which will allow this to be > possible while also promptly reclaiming the first carry before the second > is handed in to generate a third? > There are basically two implementations of BigNum addition. The first is optimistic, but regions don't help. The second is more conservative, but it's region friendly. The optimistic one goes: - Allocate a result word-vector whose size is the larger of the input sizes, with no extra word for potential carry-out - Do the word-wise addition. - If you get to the end and have a non-zero carry out, curse the gods, allocate a new output vector that is one word larger, copy the result, and propagate the carry into the top word, and return that, leaving the interim vector to be GC'd. - Otherwise return the initially allocated result word-vector. That one isn't region friendly, but it only leaves garbage behind in a rare case. The pessimistic one goes: - Allocate a result word-vector whose size is the larger of the input sizes, plus an extra word for potential carry-out - Do the word-wise addition. - Copy the interim result (which is in a vanishing region) into a newly allocated output vector that is an exact fit for size. - Return that newly allocated vector. That one is region friendly, but involves a copy-on-return pattern. For addition, it seems to me that the first algorithm is strictly better. For subtraction, multiplication, and division, where we are quite likely to shrink the return vector in any case, the second version may make more sense. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
