remove unused kh_del, pack kh_hash flag bits
State: closed

The kh_hash library includes the ability to delete elements, but this is not used anywhere in pandas.  In the khash library, there are two flags bits for every entry: ''isempty' and 'isdel'.  This change removes the support for kh_del from the khash library, allowing it to use half as many flag bits.

All tests pass.  I ran test_perf ~90 times, and got the results below (baseline = parent commit, times and ratios ± stdev).  There do seem to be a few (at the bottom) whose times increase slightly, which surprises me. 

```
name                                                              head                       baseline                          ratio
series_value_counts_int64                              1.8630 ± 0.0067                2.0982 ± 0.0131                0.8880 ± 0.0063
groupby_frame_singlekey_integer                        1.6717 ± 0.0510                1.8728 ± 0.0508                0.8932 ± 0.0355
index_int64_intersection                              24.6203 ± 0.3258               27.0208 ± 0.2654                0.9112 ± 0.0149
groupby_last                                           2.5098 ± 0.0265                2.7299 ± 0.0252                0.9195 ± 0.0129
stat_ops_level_series_sum                              1.5520 ± 0.0257                1.6864 ± 0.0237                0.9205 ± 0.0200
groupby_first                                          2.5838 ± 0.0281                2.8024 ± 0.0269                0.9221 ± 0.0134
sparse_series_to_frame                               120.5008 ± 0.7108              129.8587 ± 1.1512                0.9280 ± 0.0098
datetimeindex_add_offset                               0.1599 ± 0.0009                0.1715 ± 0.0013                0.9325 ± 0.0088
stat_ops_level_series_sum_multiple                     5.2357 ± 0.1633                5.5971 ± 0.1624                0.9362 ± 0.0390
stat_ops_level_frame_sum_multiple                      6.1508 ± 0.0653                6.5037 ± 0.0922                0.9459 ± 0.0166
read_csv_comment2                                     20.9364 ± 0.7056               22.0784 ± 0.6586                0.9491 ± 0.0421
groupby_multi_size                                    24.8205 ± 0.2378               26.1333 ± 0.2586                0.9499 ± 0.0131
stat_ops_level_frame_sum                               2.3653 ± 0.1711                2.5029 ± 0.1835                0.9500 ± 0.0966
timeseries_add_irregular                              17.1444 ± 0.1979               17.9006 ± 0.2983                0.9580 ± 0.0188
groupby_frame_median                                   5.0956 ± 0.0642                5.3151 ± 0.0801                0.9589 ± 0.0184
match_strings                                          0.3116 ± 0.0042                0.3250 ± 0.0052                0.9590 ± 0.0200
timeseries_infer_freq                                  7.0249 ± 0.1438                7.3208 ± 0.0869                0.9597 ± 0.0232
dataframe_reindex                                      0.2581 ± 0.0017                0.2680 ± 0.0019                0.9633 ± 0.0092
reshape_pivot_time_series                            158.4428 ± 1.6615              164.4806 ± 2.1991                0.9635 ± 0.0164
index_int64_union                                     67.5624 ± 0.5516               69.9954 ± 0.5946                0.9653 ± 0.0113
reindex_multiindex                                     0.8870 ± 0.0103                0.9166 ± 0.0103                0.9678 ± 0.0155
groupby_simple_compress_timing                        30.2154 ± 0.2435               31.1854 ± 0.2564                0.9690 ± 0.0111
groupby_indices                                        6.2456 ± 0.0674                6.4342 ± 0.0803                0.9708 ± 0.0158
panel_from_dict_all_different_indexes                 64.0143 ± 0.3919               65.8792 ± 0.4151                0.9717 ± 0.0085
join_dataframe_integer_key                             1.3216 ± 0.0212                1.3559 ± 0.0206                0.9750 ± 0.0215
panel_from_dict_two_different_indexes                 43.3036 ± 0.3092               44.2583 ± 0.3232                0.9785 ± 0.0100
join_dataframe_integer_2key                            3.8902 ± 0.0218                3.9749 ± 0.0241                0.9787 ± 0.0081
reshape_unstack_simple                                 2.3005 ± 0.0093                2.3416 ± 0.0115                0.9825 ± 0.0062
groupby_multi_series_op                               12.2459 ± 0.0667               12.4435 ± 0.0809                0.9842 ± 0.0083
groupby_multi_cython                                  13.6919 ± 0.0685               13.8917 ± 0.0937                0.9857 ± 0.0082
concat_series_axis1                                   50.1771 ± 0.7017               50.8870 ± 0.8207                0.9863 ± 0.0210
unstack_sparse_keyspace                                0.9630 ± 0.0071                0.9743 ± 0.0086                0.9884 ± 0.0113
frame_fancy_lookup_all                                21.7081 ± 0.2252               21.9861 ± 0.8485                0.9885 ± 0.0303
groupby_frame_apply_overhead                          15.0398 ± 0.2534               15.2089 ± 0.3118                0.9893 ± 0.0260
frame_insert_500_columns                              74.6911 ± 0.5674               75.3304 ± 0.7608                0.9916 ± 0.0124
sort_level_one                                         3.2917 ± 0.0885                3.3215 ± 0.1132                0.9921 ± 0.0415
timeseries_timestamp_tzinfo_cons                       0.0133 ± 0.0002                0.0134 ± 0.0003                0.9922 ± 0.0253
groupby_multi_python                                  51.7335 ± 0.9452               52.1447 ± 1.1834                0.9926 ± 0.0286
stats_rank_average                                    31.3220 ± 1.3618               31.5993 ± 1.2585                0.9928 ± 0.0591
read_csv_standard                                      9.4535 ± 0.1348                9.5228 ± 0.1152                0.9929 ± 0.0185
frame_reindex_both_axes                                0.2233 ± 0.0014                0.2248 ± 0.0018                0.9933 ± 0.0098
timeseries_large_lookup_value                          0.0179 ± 0.0003                0.0180 ± 0.0004                0.9941 ± 0.0239
frame_reindex_both_axes_ix                             0.2794 ± 0.0017                0.2809 ± 0.0020                0.9947 ± 0.0092
frame_iteritems                                        1.8838 ± 0.0227                1.8937 ± 0.0279                0.9950 ± 0.0188
series_align_irregular_string                         60.9044 ± 0.7522               61.2000 ± 0.6323                0.9953 ± 0.0160
groupbym_frame_apply                                  60.5675 ± 0.9349               60.8692 ± 0.9463                0.9953 ± 0.0217
stats_rank2d_axis1_average                            13.5227 ± 0.8773               13.6383 ± 0.8856                0.9957 ± 0.0909
frame_to_csv                                         277.9836 ± 3.7095              279.2427 ± 5.0754                0.9958 ± 0.0222
read_csv_thou_vb                                      26.4393 ± 0.2321               26.5419 ± 0.2718                0.9962 ± 0.0134
indexing_dataframe_boolean_rows                        0.1765 ± 0.0011                0.1772 ± 0.0015                0.9965 ± 0.0102
frame_ctor_list_of_dict                               67.3875 ± 0.8141               67.6344 ± 0.9001                0.9965 ± 0.0177
frame_get_numeric_data                                 0.0459 ± 0.0004                0.0461 ± 0.0007                0.9966 ± 0.0169
frame_iteritems_cached                                 0.0639 ± 0.0020                0.0642 ± 0.0024                0.9967 ± 0.0471
groupby_multi_different_functions                     11.8200 ± 0.0624               11.8596 ± 0.0932                0.9967 ± 0.0093
append_frame_single_mixed                              0.9737 ± 0.0846                0.9841 ± 0.0847                0.9967 ± 0.1209
timeseries_asof_single                                 0.0377 ± 0.0005                0.0378 ± 0.0006                0.9968 ± 0.0197
timeseries_slice_minutely                              0.0414 ± 0.0005                0.0415 ± 0.0005                0.9969 ± 0.0164
groupby_apply_dict_return                             34.7286 ± 0.3478               34.8450 ± 0.5679                0.9969 ± 0.0188
period_setitem                                       746.4594 ± 8.6212             748.9278 ± 11.0465                0.9969 ± 0.0185
concat_small_frames                                   10.6045 ± 0.0675               10.6383 ± 0.1020                0.9969 ± 0.0114
frame_constructor_ndarray                              0.0334 ± 0.0003                0.0335 ± 0.0005                0.9971 ± 0.0182
write_csv_standard                                   267.4531 ± 3.9582              268.3362 ± 5.3285                0.9971 ± 0.0243
groupby_multi_different_numpy_functions               11.8358 ± 0.0759               11.8699 ± 0.0738                0.9972 ± 0.0089
reindex_daterange_pad                                  0.1449 ± 0.0010                0.1453 ± 0.0014                0.9972 ± 0.0120
indexing_panel_subset                                  0.4469 ± 0.0033                0.4481 ± 0.0053                0.9976 ± 0.0137
reindex_daterange_backfill                             0.1494 ± 0.0010                0.1497 ± 0.0016                0.9977 ± 0.0121
frame_ctor_nested_dict_int64                         103.3669 ± 1.0917              103.6315 ± 1.7836                0.9977 ± 0.0198
append_frame_single_homogenous                         0.2324 ± 0.0022                0.2330 ± 0.0023                0.9977 ± 0.0136
timeseries_1min_5min_ohlc                              0.4956 ± 0.0030                0.4966 ± 0.0039                0.9980 ± 0.0097
reindex_frame_level_align                              0.6218 ± 0.0040                0.6230 ± 0.0056                0.9982 ± 0.0110
panel_from_dict_equiv_indexes                         22.4439 ± 0.1723               22.4863 ± 0.2186                0.9982 ± 0.0123
series_align_int64_index                              32.8477 ± 0.1784               32.9009 ± 0.1936                0.9984 ± 0.0080
panel_from_dict_same_index                            22.4174 ± 0.1834               22.4507 ± 0.2267                0.9986 ± 0.0129
read_table_multiple_date                           1852.1563 ± 19.4540            1855.0047 ± 27.9213                0.9987 ± 0.0180
timeseries_1min_5min_mean                              0.4872 ± 0.0026                0.4878 ± 0.0033                0.9989 ± 0.0087
replace_fillna                                         1.4792 ± 0.1068                1.4877 ± 0.1059                0.9990 ± 0.0974
sparse_frame_constructor                               4.6531 ± 0.0459                4.6582 ± 0.0524                0.9990 ± 0.0148
series_ctor_from_dict                                  2.5720 ± 0.0111                2.5746 ± 0.0150                0.9990 ± 0.0072
read_table_multiple_date_baseline                    837.9644 ± 8.9147             838.9167 ± 12.1464                0.9991 ± 0.0177
frame_to_string_floats                                47.9212 ± 0.5630               47.9764 ± 0.7628                0.9991 ± 0.0194
frame_reindex_axis0                                    1.0288 ± 0.0078                1.0298 ± 0.0119                0.9991 ± 0.0133
frame_reindex_columns                                  0.2020 ± 0.0016                0.2022 ± 0.0019                0.9991 ± 0.0121
frame_boolean_row_select                               0.2075 ± 0.0009                0.2077 ± 0.0014                0.9991 ± 0.0077
frame_fillna_many_columns_pad                         11.8545 ± 0.1323               11.8662 ± 0.1362                0.9991 ± 0.0158
series_align_left_monotonic                           14.8503 ± 0.0912               14.8613 ± 0.1038                0.9993 ± 0.0093
melt_dataframe                                         1.0850 ± 0.0078                1.0858 ± 0.0077                0.9993 ± 0.0101
frame_fillna_inplace                                  11.6751 ± 0.2087               11.6855 ± 0.2025                0.9994 ± 0.0247
frame_drop_dup_na_inplace                              2.0111 ± 0.0103                2.0122 ± 0.0096                0.9994 ± 0.0070
groupby_frame_cython_many_columns                      2.4077 ± 0.0116                2.4091 ± 0.0141                0.9995 ± 0.0075
frame_ctor_nested_dict                                67.9949 ± 0.4608               68.0334 ± 0.4236                0.9995 ± 0.0092
timeseries_asof_nan                                    7.1119 ± 0.0627                7.1157 ± 0.0601                0.9995 ± 0.0122
frame_reindex_axis1                                    2.4248 ± 0.0368                2.4263 ± 0.0341                0.9996 ± 0.0203
series_drop_duplicates_int                             0.6140 ± 0.0023                0.6142 ± 0.0023                0.9997 ± 0.0053
timeseries_period_downsample_mean                      9.3964 ± 0.0262                9.3991 ± 0.0291                0.9997 ± 0.0042
dti_reset_index                                        0.4529 ± 0.0091                0.4531 ± 0.0085                0.9998 ± 0.0275
indexing_dataframe_boolean_rows_object                 0.4054 ± 0.0016                0.4055 ± 0.0022                0.9998 ± 0.0067
stats_rank_average_int                                18.1329 ± 0.2115               18.1389 ± 0.2243                0.9998 ± 0.0170
stats_rolling_mean                                     1.3577 ± 0.0044                1.3578 ± 0.0072                1.0000 ± 0.0062
groupby_pivot_table                                   16.3420 ± 0.0934               16.3417 ± 0.1068                1.0001 ± 0.0086
sort_level_zero                                        3.3187 ± 0.1217                3.3238 ± 0.1456                1.0001 ± 0.0524
reindex_fillna_backfill                                0.0707 ± 0.0006                0.0707 ± 0.0007                1.0002 ± 0.0125
reindex_fillna_pad                                     0.0742 ± 0.0019                0.0742 ± 0.0021                1.0003 ± 0.0385
frame_drop_dup_inplace                                 2.2140 ± 0.0116                2.2133 ± 0.0129                1.0004 ± 0.0078
frame_drop_duplicates                                 18.3091 ± 0.1064               18.3022 ± 0.1000                1.0004 ± 0.0080
series_drop_duplicates_string                          0.4529 ± 0.0036                0.4528 ± 0.0036                1.0004 ± 0.0112
series_value_counts_strings                            4.2207 ± 0.0162                4.2188 ± 0.0329                1.0005 ± 0.0085
datetimeindex_normalize                               22.4277 ± 0.2073               22.4172 ± 0.1919                1.0005 ± 0.0126
timeseries_to_datetime_iso8601                         3.8940 ± 0.0482                3.8915 ± 0.0367                1.0007 ± 0.0152
lib_fast_zip_fillna                                   13.4962 ± 0.0750               13.4855 ± 0.0651                1.0008 ± 0.0074
timeseries_timestamp_downsample_mean                   5.8368 ± 0.0176                5.8310 ± 0.0183                1.0010 ± 0.0044
reshape_stack_simple                                   1.7456 ± 0.0143                1.7440 ± 0.0154                1.0010 ± 0.0120
frame_drop_duplicates_na                              17.9970 ± 0.0999               17.9767 ± 0.1071                1.0012 ± 0.0082
stats_rank2d_axis0_average                            21.7999 ± 0.0819               21.7708 ± 0.1766                1.0014 ± 0.0092
timeseries_sort_index                                 17.6179 ± 0.1460               17.5926 ± 0.1269                1.0015 ± 0.0110
lib_fast_zip                                          10.6688 ± 0.0536               10.6489 ± 0.0585                1.0019 ± 0.0075
timeseries_asof                                        7.5577 ± 0.0625                7.5386 ± 0.0509                1.0026 ± 0.0107
stat_ops_series_std                                    0.5937 ± 0.0111                0.5922 ± 0.0109                1.0030 ± 0.0263
index_datetime_intersection                           11.0669 ± 0.0623               11.0133 ± 0.0645                1.0049 ± 0.0081
groupby_series_simple_cython                           4.1735 ± 0.0477                4.1508 ± 0.0511                1.0056 ± 0.0166
index_datetime_union                                  11.1319 ± 0.0546               11.0699 ± 0.0639                1.0056 ± 0.0075
read_csv_vb                                           18.0190 ± 0.2602               17.8894 ± 0.2271                1.0074 ± 0.0194
frame_fancy_lookup                                     2.0631 ± 0.0375                2.0469 ± 0.0496                1.0085 ± 0.0304
reindex_frame_level_reindex                            1.1200 ± 0.0074                1.1125 ± 0.0541                1.0111 ± 0.0907
replace_replacena                                      1.6274 ± 0.1358                1.6190 ± 0.1444                1.0128 ± 0.1209
frame_sort_index_by_columns                           35.3555 ± 0.2725               34.7723 ± 0.1765                1.0168 ± 0.0094
merge_2intkey_sort                                    34.2841 ± 0.3041               33.6600 ± 0.2171                1.0186 ± 0.0112
join_dataframe_index_single_key_small                  5.6301 ± 0.8275                5.5872 ± 0.7877                1.0278 ± 0.2101
join_dataframe_index_multi                            17.5588 ± 0.1660               17.0397 ± 0.1173                1.0305 ± 0.0120
merge_2intkey_nosort                                  15.8161 ± 0.9392               15.0701 ± 0.9006                1.0533 ± 0.0887
join_dataframe_index_single_key_bigger                 9.4991 ± 3.4921                9.4172 ± 3.2368                1.1438 ± 0.5936
```


Labels:

Comments:
This is great. Thanks for digging deep on this one; I would like to replace the usage of khash at some point with an even leaner hash table implementation, but this gives nice performance gains for now. 

I would chalk up the time increases at the bottom to memory allocation /OS issues