pydata/pandas — pull request #2572 by thouis (2012-12-20 14:49:38+00:00)
Title: remove unused kh_del, pack kh_hash flag bits

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