PERF: Parse certain dates in Cython instead of falling back to dateutil.parse
State: closed

This tremendously speeds up parsing of certain date patterns: `MM/YYYY`, `MM/DD/YYYY` and `DD/MM/YYYY` (where separator is one of ` `, `/`, `-`, and `\`), as previously they were parsed using `dateutil.parse` which is implemented in Python.

- [x] closes N/A
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry


Labels:
name: Datetime
description: Datetime data dtype
name: Performance
description: Memory or execution speed performance

Comments:
Hello @vnlitvin! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:





There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2019-04-19 06:17:53 UTC
Performance benefits, shown by `asv continuous -f 1.01 upstream/master parse-slashed-date -e -b io.csv.ReadCSVParseSpecialDate -a sample_time=1 -a warmup_time=1`:

before|after|ratio|test name
-|-|-|-
[1d4c89f4]|[72a6ed8c]||
**master**|**parse-slashed-date**||
721±10ms|44.3±2ms|0.06|io.csv.ReadCSVParseSpecialDate.time_read_special_date('mY')
493±4ms|17.9±0.3ms|0.04|io.csv.ReadCSVParseSpecialDate.time_read_special_date('mdY')
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=h1) Report
> Merging [#25922](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/1d4c89f4d747854def6c32733383b4afa250165d?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `n/a`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/25922/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #25922      +/-   ##
==========================================
- Coverage    91.8%   91.79%   -0.01%     
==========================================
  Files         174      174              
  Lines       52536    52536              
==========================================
- Hits        48231    48227       -4     
- Misses       4305     4309       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.35% <ø> (ø)` | :arrow_up: |
| #single | `41.87% <ø> (-0.08%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/25922/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `75% <0%> (-12.5%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/25922/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.79% <0%> (-0.12%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=footer). Last update [1d4c89f...72a6ed8](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=h1) Report
> Merging [#25922](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/f53bb061939fb54d6c826c4db408c458d3d2a1db?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `n/a`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/25922/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #25922      +/-   ##
==========================================
- Coverage   91.99%   91.98%   -0.01%     
==========================================
  Files         175      175              
  Lines       52383    52383              
==========================================
- Hits        48188    48185       -3     
- Misses       4195     4198       +3
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.54% <ø> (ø)` | :arrow_up: |
| #single | `40.74% <ø> (-0.15%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/25922/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `75% <0%> (-12.5%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/25922/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.9% <0%> (-0.12%)` | :arrow_down: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/25922/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `90.71% <0%> (+0.1%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=footer). Last update [f53bb06...2cd971a](https://codecov.io/gh/pandas-dev/pandas/pull/25922?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

xref https://github.com/pandas-dev/pandas/issues/12667

I like the spirit of of this PR, but i am a little weary of the creep in scope. pandas does have some date parsing utility especially for iso dates, but I feel that more niche formats should be dispatched to dateutil i.e. maybe dateutil should inherit this performance improvement

Thoughts @jbrockmendel?
I agree with @mroeschke about creep scope.  Do we have strong reason to believe that performance on this particular set of formats is a major pain point for users?

> I agree with @mroeschke about creep scope. Do we have strong reason to believe that performance on this particular set of formats is a major pain point for users?

As far as I can tell, `dateutil` is pure-Python by design, so it would be really hard to integrate this there.
I don't see why this date format should be treated differently than ISO8601 one (our parsing is definitely way easier to maintain than that).

As for being a pain point - this format is quite widely used in certain real-world data sets, like Mortgage or NYC Taxi Rides, so yes, it _is_ a pain point in some cases (Mortgage dataset that takes dozens of minutes to be loaded _because_ of this format being parsed slowly is the reality I measured).
> As far as I can tell, dateutil is pure-Python by design, so it would be really hard to integrate this there.

dateutil is pure-python, but it also has lots of room for performance improvement.  Also IIRC @pganssle has been considering adding C/cython/rust backend(s).

> I don't see why this date format should be treated differently than ISO8601 one (our parsing is definitely way easier to maintain than that)

That logic can apply to many formats, most of which we don't want to be responsible for internally.

> Mortgage dataset that takes dozens of minutes to be loaded because of this format being parsed slowly

I think if you pass the `format` kwarg to `to_datetime` it should use `array_strptime`, which I expect would be performant.
> I think if you pass the `format` kwarg to `to_datetime` it should use `array_strptime`, which I expect would be performant.

There's no direct way of passing `format` argument to `to_datetime()` from `read_csv`. I have prototyped passing the argument to run a benchmark, though, and measured the performance.
It is performing roughly the same (in the margin of error), but it requires the caller of `read_csv` to know date format beforehand (including knowing the separator, so if different separators are for some reason used in different rows this would fail to parse correctly).

date format|`format` + `array_strptime`|proposed PR
-|-|-
mY |     43.9±0.4ms   |43.5±0.3ms
mdY|     16.4±0.08ms |  16.5±0.2ms

So I'm stating that using `format` keyword here could save from implementing our speed ups, yes, but at expense of end user knowing the format of input data, while our PR makes parsing almost equally fast without requiring knowledge from the user (and keeping public API unchanged! 😄  ).
Does this not need additional tests?

I can't comment on the scoping stuff, but one of the hardest parts of changing any auto-magical interface is that it's *very* hard to tell if the things you are doing are going to break something someone is counting on. Even something like this with a fast-path, you should probably be doing a decent amount of testing of the desired behavior *and* similar, related behavior - hard to even say what that would do.

Since you are trying to replace `dateutil.parser.parse`, this may be an ideal situation to use [hypothesis](https://github.com/HypothesisWorks/hypothesis), because you can test the property "this function returns the same thing as `dateutil`" for all kinds of formats, since you're looking for something that is basically a faster version of `dateutil`.
> Does this not need additional tests?

Great question, it most likely does need tests, we'll add some.
I have added tests and fixed bug. Thanks @pganssle
Glad that it helped to add tests.

Maybe it's a job for a different PR, but I do still think it may be worth adding hypothesis-based tests testing that `dateutil` and `pandas` return the same thing for a wide swathe of dates and formats. It's super easy to change something about datetime parsing logic and change some use case you didn't think about.
> testing that `dateutil` and `pandas` return the same thing for a wide swathe of dates and formats

Note that this change changes the behaviour for dates like `MM/YYYY` slightly, as `dateutil` parses `MM/YYYY` with day set equal to current day while our patch parses it set to `1`. I think our approach is more consistent with how other abbreviated dates are parsed, see 

https://github.com/pandas-dev/pandas/blob/4814a2875d078d6e9e9300bd1f77af15ef4f0f0a/pandas/_libs/tslibs/parsing.pyx#L195-L298

It never replaces `day` in `_DEFAULT_DATETIME` so day stays `1` there.

@vnlitvin While I think defaulting to "today" was not a good choice in `dateutil`, the reason I have not changed that is that it would be a backwards-incompatible change.

If you are going to make a backwards-incompatible change to the behavior of the library, that should be **very** prominently documented. This change is only documented as a performance improvement.
> This change is only documented as a performance improvement.

That is because I didn't suspect that `dateutil` would use today's day for some unrelated date :)
We will update `whatsnew` with this change.
@vnlitvin You wrote:

> There's no direct way of passing format argument to to_datetime() from read_csv.

Yes, there is.  You can use something like the following for a MM/YYYY format:
```
df = pd.read_csv(filename, date_parser = lambda d:pd.to_datetime(d, format="%m/%Y")
```

I believe this will use a C implementation of the parser and be very fast.  Can you test that and compare it to what you have put together to see if there is still a significant difference?

> I believe this will use a C implementation of the parser and be very fast. Can you test that and compare it to what you have put together to see if there is still a significant difference?

Sure, thanks for pointing the way.
Here's the results of measuring stuff:

format|master|to_datetime|proposed PR
-|-|-|-
%m/%Y (3 times)|689±5ms|103±0.8ms|43.3±0.5ms
%m/%d/%Y|457±3ms|37.1±0.3ms|16.6±0.2ms

So this `pd.to_datetime` approach is about 2.2x slower than proposed patch, _plus_ user has to know date format beforehand, _plus_ one cannot have mixed dates (like `15/02/2000` and `03/18/2010`). Both current master and our proposed patch allow for _not_ knowing the format and being able to mix MM/DD and DD/MM (I see no use case for that, but still), but ours is about 20x faster.
> @vnlitvin While I think defaulting to "today" was not a good choice in `dateutil`, the reason I have not changed that is that it would be a backwards-incompatible change.
> 
> If you are going to make a backwards-incompatible change to the behavior of the library, that should be **very** prominently documented. This change is only documented as a performance improvement.

After more carefully looking into the code and performing some tests via `pandas.read_csv` (thx @anmyachev for running these!) instead of `dateutil.parser.parse` we found that we are not changing the behaviour, as Pandas have already been parsing `MM/YYYY` with day=`1` - they effectively supply "default date" to `dateutil` equal to `01/01/0001`.

So we're actually _not_ changing the behaviour! :) _whew_
@vnlitvin Glad to hear that.

@jbrockmendel Do you know anything about the current state of the pandas datetime parsing test suite? Do you think it's got adequate format coverage to feel confident enough that there will be no behavior change from this PR? If so I'll stop pushing for the property-based test suite in this PR. If not, it may require a more careful assessment of the possible edge cases.
> Do you know anything about the current state of the pandas datetime parsing test suite?

Reasonably thorough, not as centralized as they could/should be (ideally this would be easy for a newcomer/auditor to check for themselves).

tests.tslibs.test_array_to_datetime
tests.tslibs.test_parse_iso8601
tests.tslibs.test_parsing
tests.indexes.datetimes.test_tools
tests.scalar.timestamp.test_timestamp

>  If so I'll stop pushing for the property-based test suite in this PR [...] possible edge cases 

I think this is worthwhile.  A very simple test would take _any_ string and assert (match or both raise).

I'm still not sold on this PR being something that should be done in pandas.  I'd rather go in the direction of seeing less parsing code in pandas and relying on dateutil more (possibly pending the compiled dateutil backend discussed elsewhere)
Summarize:
- We sped up parsing some of the common date formats. And I must say that these formats are important to users.
- How soon can users get a performance boost? Consider a few cases.
    - These changes will be accepted by you and will be included in pandas 0.25.0. So, users will receive a profit *this* month. Work on the acceleration of the dateutil module will be conducted and ultimately will be able to go there and you can do pandas's code without parsing this dates formats or will remove parsing code at all. Users in this case get performance regardless of the development progress of dateutil, and on the other hand it should not be a pain to maintain. This was a first case.
    - Consider a different situation: these changes will not be accepted and you'll wait for acceleration from dateutil. I think that dateutil is unlikely to accelerate this format. Therefore, in the total time of development of the new version dateutil, it is necessary to lay the time to speed up some other (and there are many) formats. It will also take some time to add the necessary dependencies to the project. The scale of the changes and the addition of new dependencies will generate many bugs, and some of them will not be very trivial (oh, this will also take many time). The problem is that it will take much more time than a month and even more is that no one can say the exact timing of the appearance of the accelerated version of the date parsing module. And during this development period (with an indefinite duration) users will spend their valuable time, which could save in first situation.

*What we will do?*
@anmyachev My main concern is that you have not adequately tested this patch, which means that people using *other* formats may see serious *regressions* in 25.0.

The risk of these sorts of regressions and the general additional complexity of maintaining parsing code is one reason that I believe @jbrockmendel is questioning whether `pandas` should be in the business of doing this sort of thing *at all*. There are already speed improvements for many common formats. That together with `infer_datetime_format` gets you decent performance in *most* cases, in my experience, so I don't know if the real-world impact of this will be as dramatic as you seem to imply.

I'm not saying that I oppose this change, mind you. I'm more or less neutral as to how much parsing `pandas` wants to do. Given that `pandas` is series-oriented and `dateutil` is single-value-oriented, I think it makes sense for `pandas` or someone else to do a certain amount of "reinventing the wheel" to tune performance to the specific task of parsing a large collection of datetime strings, though I'm not sure if this is one of those cases.
@anmyachev the issue is testing. dateutil was exclusively handling these formats before, now we are doing them in pandas. We need tests for them. It shouldn't be hard to add this.
@pganssle @jreback As for the tests ... I agree. Began to develop hypothesis tests.
> My main concern is that you have not adequately tested this patch, which means that people using _other_ formats may see serious _regressions_ in 25.0.

That _should_ not be the case (but as always with software, one never knows beforehand... and yes, "famous last words" 😄).
My point is, we've made the code to handle strictly specified formats and report back "don't know how to parse this" in all other cases, so it would happily hum along the previous way of parsing dates if they're not in a format which is handled by this patch.

That said, adding more tests only hurts testing time, but in return gives some assurance that the code is behaving as it should.
> Is there a reason you are not returning an indicator whether the date parsed as dayfirst or not?
> 
> the issue is that if we have _multiple_ dates some of which are dayfirst parsed and some are not does this do the right thing?

I think that this indicator was not added, because there is no need for it, that is, in the function that calls ours, this information is not used and, moreover, the processing behavior will change.
@jreback @jbrockmendel I've rebased on `master`.
Anything else we need to fix or improve before this could be merged?
@jreback Done & green
thanks @vnlitvin and @anmyachev nice patch! these involved can take some time to review (and write of course).