tree 1d52c5df881a7fb35d2b8d08b2233a1eba6cfec3
parent 2671da30afade456249fe4a8c73ed4115278b984
author Nick Wellnhofer <wellnhofer@aevum.de> 1481125442 +0100
committer Nick Wellnhofer <wellnhofer@aevum.de> 1481128133 +0100

Fix IndexManager with many small segments

IxManager_Choose_Sparse would throw when handling more than about 40
segments because of the integer overflow test in S_fibonacci.

Also, the naive recursive implementation of S_fibonacci had abysmal
performance. After all, the result was created by adding only 0s and
1s. The number of calls to S_fibonacci when computing fib(n) was
fib(n+1), resulting in more than a billion of iterations with n ~ 45.
On my (heavily loaded and low-end) test machine, Choose_Sparse could
take up to 40 seconds to complete.

On the positive side, if anyone was hit by this performance problem,
it's likely they also saw the "index n too large" exception and we
only had two reports so far.

Use a precomputed lookup table and fix the test for large values of n.

Fixes LUCY-318.