PERF: Improve performance of hash sets in read_csv
State: closed

- [x] closes N/A
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Improved performance of checking of string presence in hashsets by:
1. implemented lookup table for first symbol of entries - this speeds up negative answers
2. increased size of hash table to reduce the probability of hash collision

Hash bucket increase is needed due to khash search algorithm - it computes a hash of key being searched, uses its last N bits where N corresponds to bucket size, and then does an open ended search over the table if collision happened with calling a comparison function over keys. When keys are strings (or, more precisely, `char*` things) comparison function is `strcmp()` which complexity is O(N), thus we want for collisions to be rare.
Most lookups of those sets happen when values are checked against N/A table which by default has 17 entries. Without the change bucket size is 32, thus hash collision probability is 17/32 (~53%), after the patch bucket size is 256 and collision probability is 6.6%.

I will add `asv` results and whatsnew later.

Labels:
name: Performance
description: Memory or execution speed performance
name: IO CSV
description: read_csv, to_csv

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

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

```diff
@@            Coverage Diff             @@
##           master   #25804      +/-   ##
==========================================
+ Coverage   91.27%   91.27%   +<.01%     
==========================================
  Files         173      173              
  Lines       53002    53002              
==========================================
+ Hits        48375    48376       +1     
+ Misses       4627     4626       -1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `89.83% <ø> (ø)` | :arrow_up: |
| #single | `41.76% <ø> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25804?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/25804/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `89.4% <0%> (+0.1%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25804?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/25804?src=pr&el=footer). Last update [85c3f82...da9d4e6](https://codecov.io/gh/pandas-dev/pandas/pull/25804?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/25804?src=pr&el=h1) Report
> Merging [#25804](https://codecov.io/gh/pandas-dev/pandas/pull/25804?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/85c3f82dff73ede6d5d961611518e007c8ba0098?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `n/a`.

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

```diff
@@            Coverage Diff             @@
##           master   #25804      +/-   ##
==========================================
+ Coverage   91.27%   91.27%   +<.01%     
==========================================
  Files         173      173              
  Lines       53002    53002              
==========================================
+ Hits        48375    48376       +1     
+ Misses       4627     4626       -1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `89.83% <ø> (ø)` | :arrow_up: |
| #single | `41.76% <ø> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25804?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/25804/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `89.4% <0%> (+0.1%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25804?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/25804?src=pr&el=footer). Last update [85c3f82...da9d4e6](https://codecov.io/gh/pandas-dev/pandas/pull/25804?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/25804?src=pr&el=h1) Report
> Merging [#25804](https://codecov.io/gh/pandas-dev/pandas/pull/25804?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/85c3f82dff73ede6d5d961611518e007c8ba0098?src=pr&el=desc) will **not change** coverage.
> The diff coverage is `n/a`.

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

```diff
@@           Coverage Diff           @@
##           master   #25804   +/-   ##
=======================================
  Coverage   91.27%   91.27%           
=======================================
  Files         173      173           
  Lines       53002    53002           
=======================================
  Hits        48375    48375           
  Misses       4627     4627
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `89.83% <ø> (ø)` | :arrow_up: |
| #single | `41.77% <ø> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/25804?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/io/excel/\_base.py](https://codecov.io/gh/pandas-dev/pandas/pull/25804/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2V4Y2VsL19iYXNlLnB5) | `92.48% <0%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/25804?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/25804?src=pr&el=footer). Last update [85c3f82...2ceb850](https://codecov.io/gh/pandas-dev/pandas/pull/25804?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Results of running `asv continuous -f 1.05 upstream/master HEAD -b io.csv -a sample_time=1 -a warmup_time=1`:

before|after|ratio|test name
-|-|-|-
[fbe25233]|[da9d4e64]||
**master**|**khash-na-sets**||
1.34±0.02ms|1.26±0.01ms|0.94|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '.', 'high')
13.7±0.2ms|12.8±0.3ms|0.94|io.csv.ReadCSVSkipRows.time_skipprows(None)
1.41±0.01ms|1.31±0.02ms|0.93|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '.', None)
1.42±0.01ms|1.32±0.01ms|0.93|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '.', None)
32.9±1ms|28.8±0.2ms|0.87|io.csv.ReadCSVCategorical.time_convert_direct
12.7±0.2ms|10.9±0.1ms|0.86|io.csv.ReadCSVThousands.time_thousands(',', ',')
13.2±0.08ms|11.3±0.1ms|0.86|io.csv.ReadCSVThousands.time_thousands('\|', ',')
10.7±0.07ms|9.06±0.09ms|0.84|io.csv.ReadCSVThousands.time_thousands('\|', None)
10.9±0.1ms|9.17±0.2ms|0.84|io.csv.ReadCSVThousands.time_thousands(',', None)
More precise benchmarking:
`asv continuous -f 1.01 upstream/master HEAD -b io.csv -a sample_time=2 -a warmup_time=2`

before|after|ratio|test name
-|-|-|-
[fbe25233]|[da9d4e64]||
**master**|**khash-na-sets**||
1.55±0.02ms|1.49±0ms|0.96|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '_', 'round_trip')
1.55±0.01ms|1.48±0.01ms|0.96|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '_', None)
13.2±0.4ms|12.5±0.1ms|0.95|io.csv.ReadCSVSkipRows.time_skipprows(None)
1.56±0.02ms|1.48±0.01ms|0.95|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '_', 'high')
1.84±0.02ms|1.74±0.01ms|0.95|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '.', 'round_trip')
1.81±0.02ms|1.72±0.01ms|0.95|io.csv.ReadCSVDInferDatetimeFormat.time_read_csv(True, 'iso8601')
1.56±0.02ms|1.47±0.01ms|0.94|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '_', None)
1.84±0.01ms|1.73±0.02ms|0.94|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '.', 'round_trip')
1.57±0.03ms|1.47±0.03ms|0.94|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '_', 'round_trip')
1.34±0.01ms|1.24±0.03ms|0.92|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '.', 'high')
1.35±0.02ms|1.24±0.01ms|0.92|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '.', 'high')
1.43±0.02ms|1.30±0.01ms|0.91|io.csv.ReadCSVFloatPrecision.time_read_csv(';', '.', None)
1.43±0.03ms|1.29±0.01ms|0.90|io.csv.ReadCSVFloatPrecision.time_read_csv(',', '.', None)
31.5±0.6ms|28.3±0.3ms|0.90|io.csv.ReadCSVCategorical.time_convert_direct
2.95±0.07ms|2.61±0.06ms|0.89|io.csv.ReadUint64Integers.time_read_uint64
13.1±0.1ms|11.2±0.05ms|0.86|io.csv.ReadCSVThousands.time_thousands('\|', ',')
10.8±0.04ms|9.12±0.08ms|0.84|io.csv.ReadCSVThousands.time_thousands(',', None)
12.8±0.04ms|10.8±0.1ms|0.84|io.csv.ReadCSVThousands.time_thousands(',', ',')
11.1±0.2ms|9.11±0.05ms|0.82|io.csv.ReadCSVThousands.time_thousands('\|', None)
lgtm. @chris-b1 @gfyoung 
thanks @vnlitvin 
@vnlitvin : Nice work!
@vnlitvin getting tons of build warnings like: https://travis-ci.org/pandas-dev/pandas/jobs/511269649

if you can do anything about this.

```
n file included from pandas/_libs/parsers.c:663:0:
pandas/_libs/src/klib/khash_python.h:109:27: note: expected ‘struct kh_str_starts_t *’ but argument is of type ‘const struct kh_str_starts_t *’
 khint_t PANDAS_INLINE kh_get_str_starts_item(kh_str_starts_t* table, char* key) {
                           ^
pandas/_libs/parsers.c:26118:7: warning: passing argument 2 of ‘kh_get_str_starts_item’ discards ‘const’ qualifier from pointer target type [enabled by default]
       __pyx_t_1 = (kh_get_str_starts_item(__pyx_v_na_hashset, __pyx_v_word) != 0);
       ^
In file included from pandas/_libs/parsers.c:663:0:
pandas/_libs/src/klib/khash_python.h:109:27: note: expected ‘char *’ but argument is of type ‘const char *’
 khint_t PANDAS_INLINE kh_get_str_starts_item(kh_str_starts_t* table, char* key) {
                           ^
pandas/_libs/parsers.c: In function ‘__pyx_f_6pandas_5_libs_7parsers__try_bool_flex_nogil’:
```