BUG: Patch Checked Add Method
State: closed

Title is self-explanatory.  Follow-up to #14237.

Merged in PR #14453


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

Comments:
## [Current coverage](https://codecov.io/gh/pandas-dev/pandas/pull/14324?src=pr) is 85.25% (diff: 90.47%)

> Merging [#14324](https://codecov.io/gh/pandas-dev/pandas/pull/14324?src=pr) into [master](https://codecov.io/gh/pandas-dev/pandas/branch/master?src=pr) will decrease coverage by **0.01%**

``` diff
@@             master     #14324   diff @@
==========================================
  Files           140        140          
  Lines         50634      50645    +11   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43173      43175     +2   
- Misses         7461       7470     +9   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [d98e982...85ca49d](https://codecov.io/gh/pandas-dev/pandas/compare/d98e982ecb0f6b7f3478a63caac34e0be238895c...85ca49d5eb226f007fa10b024c2de7192ce4d166?src=pr)

Although this is probably more correct, I don't think the performance degradation is allowable:

```
# master

In [1]: arr = np.arange(1000000)
   ...: td = pd.to_timedelta(arr)
   ...: ts = pd.Timestamp('2000')
   ...: 

In [2]: %timeit td + ts
100 loops, best of 3: 2.51 ms per loop
```

```
# PR

In [2]: %timeit td + ts
10 loops, best of 3: 41.1 ms per loop
```

The problem is in `np.iinfo(np.int64).min - b > arr` when `b` is positive (and probably in the other check of `b` is negative)

@jorisvandenbossche : I draw a hard line on correctness.  This is impeding my ability to patch the other TDI overflow issues because there are tests that fail because of this bug.  Perhaps it would instead be worthwhile to break the check up into two separate statements, though not sure that would help too much given that it's Python.

try this. The key to this expression is lazy evaluation as its a compound expression. `numexpr` does this for free.

```
In [5]: arr = np.arange(1000000)
   ...: td = pd.to_timedelta(arr)
   ...: ts = pd.Timestamp('2000')
   ...: a = td.view('i8')
   ...: b = ts.value
   ...: 

In [7]: nmax = np.iinfo(np.int64).max 

In [8]: nmin = np.iinfo(np.int64).min

n [11]: ((b > 0) & (np.iinfo(np.int64).max - b < arr)).any() or((b < 0) & (np.iinfo(np.int64).min - b > arr)).any()
Out[11]: False

In [12]: %timeit ((b > 0) & (np.iinfo(np.int64).max - b < arr)).any() or((b < 0) & (np.iinfo(np.int64).min - b > arr)).any()
10 loops, best of 3: 57.7 ms per loop

In [14]: %timeit pd.eval('((b > 0) & (nmax - b < arr)) | ((b < 0) & (nmin - b > arr))').any()
100 loops, best of 3: 6.24 ms per loop

In [15]: pd.eval('((b > 0) & (nmax - b < arr)) | ((b < 0) & (nmin - b > arr))').any()
Out[15]: False

```

numba can do even better (but we don't have this in the quiver atm)

```
In [17]: def f(a,b,arr,nmax,nmin):
    ...:     return np.any((b > 0) & (nmax - b < arr)) | ((b < 0) & (nmin - b > arr))

In [18]: f = numba.jit(f,nopython=True)

In [19]: %timeit f(a,b,arr,nmax,nmin).any()
The slowest run took 59.62 times longer than the fastest. This could mean that an intermediate result is being cached.
100 loops, best of 3: 2.28 ms per loop

In [20]: f(a,b,arr,nmax,nmin).any()
Out[20]: False
```

Something like this is quite convoluted, but is a bit faster as the eval approach:

```
In [62]: %%timeit
    ...: b2 = np.broadcast_to(b, arr.shape)
    ...: mask1 = b2 > 0
    ...: mask2 = b2 < 0
    ...: if not mask1.any():
    ...:     to_raise = (np.iinfo(np.int64).min - b2 > arr).any()
    ...: elif not mask2.any():
    ...:     to_raise = (np.iinfo(np.int64).max - b2 < arr).any()
    ...: else:
    ...:     to_raise = (np.iinfo(np.int64).max - b2[mask1] < arr[mask1]).any() or (np.iinfo(np.int64).min - b2[mask1] > arr[mask1]).any()
    ...: 
100 loops, best of 3: 4.2 ms per loop
```

@jorisvandenbossche : Are you proposing I use this more convoluted method then?  Thoughts?

@jorisvandenbossche : Some feedback on my question <a href="https://github.com/pydata/pandas/pull/14324#issuecomment-251452745">above</a> would be greatly appreciated.

@gfyoung yes pls use one of the methods proposed above

@jorisvandenbossche : Your solution is unfortunately not backwards compatible with older versions of `numpy` (e.g. 1.7.1) that don't have `np.broadcast_to`.  Let me see if `np.broadcast_arrays` could work.  If not, I'll have to go with @jreback suggestion.

so put a conditional on the numpy version (or use the eval soln)

@jreback : I thought we don't do those kind of checks (or try to avoid them).  In any case, I'm trying with another method as I mentioned above.  IMO this isn't something THAT important that we need to check `numpy` versions.

i don't see a reason not to do a check in the numpy version

or use the eval soln (which is fine but will fall back to numpy if numexpr is not installed)

@jreback : Fair enough.  Also, I have no objections to your eval solution.  I'm trying it right now, as `np.broadcast_arrays` (the alternative to `np.broadcast_to`) doesn't meet the bill.

The `eval` solution will be very slow if you don't have numexpr installed, so I would prefer not to use it.

@jorisvandenbossche : Unfortunately, your solution is not backwards compatible.  And if you don't like @jreback suggestion, then what do you suggest?  Compared to my original change, the `eval` solution would at least be an improvement.

just check the numpy version

i am not sure why you think this is an issue

@jreback : And then what, use the slower solution that I used before if the version is not compatible?  Would it be preferable to fallback to my original solution or use the `eval` one you used?

yep

@jreback : How about my second question?

I am sure that there is a way to achieve the same as `broadcast_to` does for older numpy versions. Eg it uses `np.nditer` under the hood. Or we can simply check for scalar vs array: scalar -> fill array of correct shape with this, array -> should have the same shape as the other array

@jorisvandenbossche : Your fill idea could work actually.  Let me see what I can do there.

Well at least the `pd.eval` method works, but I'll do the `numpy` version check now.

broadcast_to is only a few lines of pure Python code. It would be quite straightforward to put it in a compat module -- that's what  I did in xarray: https://github.com/pydata/xarray/blob/master/xarray/core/npcompat.py

@shoyer : I suppose, but why boilerplate that if a simpler solution can be used?

New timing information:

``` python
In [1]: import numpy as np

In [2]: import pandas as pd

In [3]: arr = np.arange(1000000)

In [4]: td = pd.to_timedelta(arr)

In [5]: ts = pd.Timestamp('2000')

# Master
In [6]: %timeit td + ts
100 loops, best of 3: 3.51 ms per loop

# PR
In [6]: %timeit td + ts
100 loops, best of 3: 4.06 ms per loop
```

@jreback , @jorisvandenbossche : Travis and Appveyor are passing, and the performance is significantly better than it was initially.  Ready to merge if there are no other concerns.

Can you add benchmarks that have all possible cases with possible performance hits? (positive overflow, negative overflow, combination -> the three branches of the if/elif/else in the check)

@jorisvandenbossche : Which benchmark suite should I place it under?

@gfyoung I would add specific benchmarks for the `_checked_add_with_arr` with the three overflow cases to algorithms.py or binary_ops.py, and then add a normal case (no overflow) to timedelta.py (eg the example used in the discussion here)