Fix overflow issue in interpolation search
COLLABORATOR
~~Seems like the CI failure is unrelated to this PR~~ (fixed with the merge). 

@lhoestq Can you please verify that everything is OK in terms of speed? Another solution is to change the offsets array dtype to np.int64 (but this doesn't scale in theory compared to Python integer which is unbound). I'm not sure why on my 64-bit machine the default numpy dtype is np.int32 tho.
2021-05-08T21:17:07Z
https://github.com/huggingface/datasets/pull/2336#issuecomment-835517955
https://api.github.com/repos/huggingface/datasets/issues/2336
MDEyOklzc3VlQ29tbWVudDgzNTUxNzk1NQ==
https://api.github.com/repos/huggingface/datasets/issues/comments/835517955/reactions
2021-05-09T14:39:46Z
https://api.github.com/repos/huggingface/datasets/issues/comments/835517955
https://avatars.githubusercontent.com/u/47462742?v=4
https://api.github.com/users/mariosasko/events{/privacy}
https://api.github.com/users/mariosasko/followers
https://api.github.com/users/mariosasko/following{/other_user}
https://api.github.com/users/mariosasko/gists{/gist_id}
https://github.com/mariosasko
mariosasko
MDQ6VXNlcjQ3NDYyNzQy
https://api.github.com/users/mariosasko/orgs
https://api.github.com/users/mariosasko/received_events
https://api.github.com/users/mariosasko/repos
https://api.github.com/users/mariosasko/starred{/owner}{/repo}
https://api.github.com/users/mariosasko/subscriptions
User
https://api.github.com/users/mariosasko
public
MEMBER
Hi ! Thanks for the fix.
Unfortunately in terms of speed this is not acceptable :/
The `get_batch_of_1024_random_rows` metric or the `benchmark_getitem_100B ` benchmark is almost at 1sec instead of a few milliseconds.

Would it be possible to avoid the overflow by simply passing `dtype=np.int64` to `np.cumsum` ?
On windows machines the default is int32 unfortunately so we have to force the dtype to be int64


2021-05-10T08:52:34Z
https://github.com/huggingface/datasets/pull/2336#issuecomment-836404881
https://api.github.com/repos/huggingface/datasets/issues/2336
MDEyOklzc3VlQ29tbWVudDgzNjQwNDg4MQ==
https://api.github.com/repos/huggingface/datasets/issues/comments/836404881/reactions
2021-05-10T08:52:34Z
https://api.github.com/repos/huggingface/datasets/issues/comments/836404881
https://avatars.githubusercontent.com/u/42851186?v=4
https://api.github.com/users/lhoestq/events{/privacy}
https://api.github.com/users/lhoestq/followers
https://api.github.com/users/lhoestq/following{/other_user}
https://api.github.com/users/lhoestq/gists{/gist_id}
https://github.com/lhoestq
lhoestq
MDQ6VXNlcjQyODUxMTg2
https://api.github.com/users/lhoestq/orgs
https://api.github.com/users/lhoestq/received_events
https://api.github.com/users/lhoestq/repos
https://api.github.com/users/lhoestq/starred{/owner}{/repo}
https://api.github.com/users/lhoestq/subscriptions
User
https://api.github.com/users/lhoestq
public
COLLABORATOR
Yes, casting the array to np.int64 should work as well. Another option would be to cast the array elements (`arr[i], arr[j]`) in interpolation search to Python integers (bound only with memory) before multiplication (the error stems from this part: `(j - i) * (x - arr[i])`) when working with big values. But for now, the first option is OK for the sake of simplicity.
2021-05-10T13:05:01Z
https://github.com/huggingface/datasets/pull/2336#issuecomment-836674706
https://api.github.com/repos/huggingface/datasets/issues/2336
MDEyOklzc3VlQ29tbWVudDgzNjY3NDcwNg==
https://api.github.com/repos/huggingface/datasets/issues/comments/836674706/reactions
2021-05-10T13:05:01Z
https://api.github.com/repos/huggingface/datasets/issues/comments/836674706
https://avatars.githubusercontent.com/u/47462742?v=4
https://api.github.com/users/mariosasko/events{/privacy}
https://api.github.com/users/mariosasko/followers
https://api.github.com/users/mariosasko/following{/other_user}
https://api.github.com/users/mariosasko/gists{/gist_id}
https://github.com/mariosasko
mariosasko
MDQ6VXNlcjQ3NDYyNzQy
https://api.github.com/users/mariosasko/orgs
https://api.github.com/users/mariosasko/received_events
https://api.github.com/users/mariosasko/repos
https://api.github.com/users/mariosasko/starred{/owner}{/repo}
https://api.github.com/users/mariosasko/subscriptions
User
https://api.github.com/users/mariosasko
public
Fixes #2335 

More info about this error can be found [here](https://stackoverflow.com/questions/53239890/why-do-i-keep-getting-this-error-runtimewarning-overflow-encountered-in-int-sc/53240100). 