BUG: Check for overflow in TimedeltaIndex addition.
State: closed

Title is self-explanatory.  Closes #14068.


Labels:
name: Bug
name: Timedelta
description: Timedelta data type

Comments:
There is a similar bug for adding `TimedeltaIndex` and similar time delta objects with each other.  I will add this as a separate commit but wanted to make sure my patch for the original issue passes.

The slightly tricky part for this patch is how we check for overflow.  For example, if we look at this function <a href="https://github.com/pydata/pandas/blob/37f95cef85834207db0930e863341efb285e38a2/pandas/tseries/base.py#L686">here</a>, we replace certain elements with `tslib.iNaT`.  Should we check for overflow in the locations where they are supposed to be `tslib.iNaT`?  Or ignore them?

## [Current coverage](https://codecov.io/gh/pydata/pandas/pull/14237?src=pr) is 85.26% (diff: 100%)

> Merging [#14237](https://codecov.io/gh/pydata/pandas/pull/14237?src=pr) into [master](https://codecov.io/gh/pydata/pandas/branch/master?src=pr) will increase coverage by **<.01%**

``` diff
@@             master     #14237   diff @@
==========================================
  Files           140        140          
  Lines         50579      50584     +5   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43121      43128     +7   
+ Misses         7458       7456     -2   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [7dedbed...77effde](https://codecov.io/gh/pydata/pandas/compare/7dedbed8988db9dc6453320383202bf97deaf14a...77effde12797cd11642ed7e70b30b15164e18076?src=pr)

Yes, `Period`, `Timedelta` and `Timestamp` are always backed by a `int64_t`
value.

On Mon, Sep 19, 2016 at 9:43 AM, gfyoung notifications@github.com wrote:

> ## _@gfyoung_ commented on this pull request.
> 
> In pandas/tseries/tdi.py https://github.com/pydata/pandas/pull/14237:
> 
> > @@ -344,6 +344,17 @@ def _add_datelike(self, other):
> >              other = Timestamp(other)
> >              i8 = self.asi8
> >              result = i8 + other.value
> > -            # gh-14068: there is the possibility of addition overflow,
> > -            # which occurs when we add two very large positive numbers,
> > -            # resulting in a negative number.
> > -            #
> > -            # Since Timestamp objects can never have a negative value,
> > -            # we just need to check that the elements in result are also
> > -            # nonnegative when their corresponding elements in i8 are.
> > -            for x, y in zip(i8, result):
> 
> Ah, fair enough. BTW, is it fair to assume that all integers are int64_t
> and just check for int64 overflow?
> 
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> https://github.com/pydata/pandas/pull/14237, or mute the thread
> https://github.com/notifications/unsubscribe-auth/AB1b_KjV1qiCg6QPdGQt65b3AayiTozxks5qrp-LgaJpZM4J_QBW
> .

@chris-b1 : Added the `algos` implementation for `_checked_add`, and Travis + Appveyor are happy.

@gfyoung It seems to me that in your test you are only checking Timedelta + Timestamp, but those already error on overflow now. Shouldn't you check for the TimedeltaIndex case ? EDIT: Ah, I think you forgot the `[...]` in the third and fourth case ?

Further, can you show a perf comparison?

I don't think cython is needed here

```
In [11]: arr = pd.to_datetime([0,np.iinfo(np.int64).max-1,pd.lib.iNaT])

In [12]: arr
Out[12]: DatetimeIndex(['1970-01-01 00:00:00', '2262-04-11 23:47:16.854775806', 'NaT'], dtype='datetime64[ns]', freq=None)

In [13]: arr = pd.to_datetime([0,np.iinfo(np.int64).max-1,pd.lib.iNaT]).asi8

In [14]: arr
Out[14]: array([                   0,  9223372036854775806, -9223372036854775808])

In [15]: arr+10
Out[15]: array([                  10, -9223372036854775800, -9223372036854775798])

In [16]: ((arr+10) < 0) & (arr != pd.lib.iNaT)
Out[16]: array([False,  True, False], dtype=bool)
```

@jreback IIUC `[15]` is technically undefined behavior  (sign int overflow in C) - although maybe all the compilers python is built on wrap like that?

@chris-b1 I am not sure.

cc @charris
@shoyer 

any idea if [this](https://github.com/pydata/pandas/pull/14237#issuecomment-248260442) is always true?

This is safe here

```
In [25]: ((np.iinfo(np.int64).max-arr+10) > 0) & (arr != pd.lib.iNaT)
Out[25]: array([False,  True, False], dtype=bool)
```

@jorisvandenbossche : Perf comparison of what exactly?

> Perf comparison of what exactly?

Before/after of such a TimedeltaIndex addition (as the checking will give a certain overhead)

@jreback : BTW, I think @chris-b1 suggested Cython for perf reasons, not for correctness (that was assumed) IIUC.

I think the check that you do in the cython code (`np.iinfo(np.int64).max - b < a`) can also be done vectorized in plain numpy? (instead of the looping you had initially) In that case cython is maybe indeed not needed.

@jorisvandenbossche : Writing it in Cython should provide a perf boost (we know the data types).  However, your point about vectorization is well taken and would take care of some of the issues addressed by @chris-b1 .

@jorisvandenbossche : 

``` python
In [1]: import pandas as pd
In [2]: import numpy as np
In [3]: arr = np.arange(1000000)
In [4]: td = pd.to_timedelta(arr)
In [5]: ts = pd.Timestamp('2000')
In [6]: %timeit -n 1000 ts + td
```

`master`: 1000 loops, best of 3: 1.92 ms per loop
`PR`: 1000 loops, best of 3: 2.09 ms per loop

Cython doesn't really make sense with the current implementation, because you can do this with vectorized NumPy functions already. In the current implementation it's entirely pointless because you're just calling Python methods/functions. If you need the loop, then yes, you should go for Cython.

@shoyer : IIUC, I think your understanding of "current implementation" is a little dated.  I made changes in the meantime.  Also, implementing in Cython as I said makes sense because we know the data types with which we will be operating.

@gfyoung Nope, every line in your current Cython code is calling back to Python in order to use NumPy:

``` python
def _checked_add_arr_scalar(ndarray[int64_t] arr, int64_t b):
    if (np.iinfo(np.int64).max - b < arr).any():  # vectorized arithmetic, numpy.ndarray.any
         raise OverflowError("Python int too large to "  # python error
                            "convert to C long")
     return arr + b  # more vectorized arithmetic
```

You _could_ do most of this from NumPy's C-API by calling functions like `PyArray_Any` but that would be pretty pointless.

@shoyer :  Fair enough.  But then again, placing it in `algos.pyx` seems logical for the time being.  Also, the speed-up from using types couldn't hurt as I said.

Why don't you benchmark the function written in Cython vs pure Python so you can see for yourself?

Using Cython makes code harder to debug/introspect/maintain. We should only use it when it makes a meaningful difference for performance (this is a subjective standard).

@shoyer : Fair enough.  But in the meantime, a suggestion of where to this function would be useful then if you disagree with placing it in `algos.pyx`.

@gfyoung as I have said several times, just use the simple numpy construct from above. no reason to code bloat this by doing it in cython. If there is a demonstrated perf gain, then pls show it. but I don't think you can beat numpy here.

@jreback : I would like to abstract the checking into a separate function because there are other places that patching too as I mentioned <a href="https://github.com/pydata/pandas/pull/14237#issuecomment-247683373">above</a>.  @chris-b1 suggested I put the code in `algos.pyx`, so where would you put it then if not there?

@gfyoung sure make a function. But it should doesn't need to be in cython. prob in `core/nanops`

Sorry, if I sent you down a wrong path, I only meant that to the extent this was impl using an explicit loop that would benefit from cython.  

Can you double check your timings (maybe didn't rebuild?) - that overhead seems too small and some local timing suggests so too.

```
arr = np.arange(1000000)
td = pd.to_timedelta(arr)
ts = pd.Timestamp('2000')

%%timeit
td + ts
100 loops, best of 3: 2.71 ms per loop

%%timeit
(np.iinfo(np.int64).max - ts.value < td.asi8).any()
td + ts
100 loops, best of 3: 3.52 ms per loop

```

Moved the checked add method to `nanops` as @jreback suggested.  Travis and Appveyor seem to be happy with this change.

@gfyoung IIRC there was _another_ place in the code where this was needed? (or at least that's what you said)?

@jreback : You are correct (see <a href="https://github.com/pydata/pandas/pull/14237#issuecomment-247683373">here</a>).  However, I think I would prefer to submit those changes in a separate PR just because the actual fix for this one hasn't been fully agreed upon and would impact how I fix the other one.

> We don't need to do TDI or DTI specifically
> why is this ?

```
In [8]: m = np.iinfo(np.int64).max

In [10]: pd.to_datetime(np.arange(m-5,m-1))
Out[10]: DatetimeIndex(['2262-04-11 23:47:16.854775802', '2262-04-11 23:47:16.854775803', '2262-04-11 23:47:16.854775804', '2262-04-11 23:47:16.854775805'], dtype='datetime64[ns]', freq=None)

In [11]: pd.to_datetime(np.arange(m-5,m-1)) + pd.to_timedelta([10]*4,unit='ns')
Out[11]: DatetimeIndex(['2262-04-10 00:12:43.145224196', '2262-04-10 00:12:43.145224197', '2262-04-10 00:12:43.145224198', '2262-04-10 00:12:43.145224199'], dtype='datetime64[ns]', freq='N')
```

doesn't seem correct to me

@jreback : The add handling varies from data type to data type as you can see <a href="https://github.com/pydata/pandas/blob/master/pandas/tseries/base.py#L618">here</a>.  This PR only addresses this branch <a href="https://github.com/pydata/pandas/blob/master/pandas/tseries/base.py#L639">here</a>.  Once this PR is merged, I can then use the `nanops` changes (if that's what they end up being) to patch the other overflow issues.