mozilla/rust — pull request #12209 by pnkfelix (2014-02-12 10:30:45+00:00)
Title: Remove a source of O(n^2) running time in bigints.

::num::bigint, Remove a source of O(n^2) running time in `fn shr_bits`.

I'll cut to the chase: On my laptop, this brings the running time on
`pidigits 2000` (from src/test/bench/shootout-pidigits.rs) from this:
```
% time ./pidigits 2000 > /dev/null

real	0m7.695s
user	0m7.690s
sys	0m0.005s
```
to this:
```
% time ./pidigits 2000 > /dev/null

real	0m0.322s
user	0m0.318s
sys	0m0.004s
```

The previous code was building up a vector by repeatedly making a
fresh copy for each element that was unshifted onto the front,
yielding quadratic running time. This fixes that by building up the
vector in reverse order (pushing elements onto the end) and then
reversing it.

(Another option would be to build up a zero-initialized vector of the
desired length and then installing all of the shifted result elements
into their target index, but this was easier to hack up quickly, and
yields the desired asymptotic improvement. I have been thinking of
adding a `vec::from_fn_rev` to handle this case, maybe I will try that
this weekend.)