complement and subtract are very slow with large number of features

[agalitsyna]

The inner working of complement/subtract includes multiple bioframe/pandas operations. Potentially, it can be replaced by something more low-level and faster.

My user experience: subtracting 700_000 regions from 300_000 genomic segments takes 1 hour and 40 minutes to subtract.

[smitkadvani]

Summary

• Subtract operation when performed for larger numbers of intervals takes longer time. Execution time while subtracting 700_000 regions from 300_000 genomic segments total is found to be less than a minute.
• pandas.DataFrame.sort_values is responsible for the most of the execution time which is being internally called via overlap function
• Optimising pandas.DataFrame.sort_values seems to be out of scope at this point.
• https://gist.github.com/smitkadvani/8f2428a943b87a085361cce2eafbc87d
  Experiement
  Reproduced subtract operations for large interval.Behaviour of the code is verified using profiling tool.
  make_random_intervals function source code is derived from performance-guide documentation for bioframe

lp = LineProfiler()
df1 = make_random_intervals(int(1e7), 300, 100)
df2 = make_random_intervals(int(3e6), 100, 200)

lp = LineProfiler()
lp_wrapper = lp(bf.subtract)
lp_wrapper(df1, df2)
bf.subtract(df1, df2)
lp.print_stats()

Following is the block of profiling stat.

Total time: 16.4223 s

Line #      Hits         Time  Per Hit   % Time  Line Contents
  1377         3        1e+10    4e+09     81.8      df_subtracted = overlap(
  1378         1          0.0      0.0      0.0          df1,
  1379         2 2222976000.0    1e+09     13.5          complement(
  1380       301     417000.0   1385.4      0.0              df2, view_df={i: np.iinfo(np.int64).max for i in all_chroms}, cols=cols2
  1381         1    1251000.0    1e+06      0.0          ).astype({sk2: pd.Int64Dtype(), ek2: pd.Int64Dtype()}),
  1382         1       1000.0   1000.0      0.0          how="left",
  1383         1          0.0      0.0      0.0          suffixes=suffixes,
  1384         1          0.0      0.0      0.0          return_index=return_index,
  1385         1          0.0      0.0      0.0          return_overlap=True,
  1386         1          0.0      0.0      0.0          keep_order=True,
  1387         1          0.0      0.0      0.0          cols1=cols1,
  1388         1       1000.0   1000.0      0.0          cols2=cols2,
  1389         1       6000.0   6000.0      0.0      )[list(name_updates)]
==============================================================

• It's clear that overlap function takes the most of the time for subtract operation.
• Later, profiling for overlap operation is carried out using following code segment.

all_chroms = np.unique(list(pd.unique(df1['chrom'].dropna())) + list(pd.unique(df2['chrom'].dropna())))
view_df_temp = {i: np.iinfo(np.int64).max for i in all_chroms}
compliment_df2_with_viewframe = bf.complement(df2, view_df_temp)

lp1 = LineProfiler()
lp_wrapper = lp1(bf.overlap)
lp_wrapper(df1, compliment_df2_with_viewframe)
bf.overlap(df1, compliment_df2_with_viewframe)
lp1.print_stats()

Profiling summary

Total time: 11.971 s

Line #      Hits         Time  Per Hit   % Time  Line Contents

   580         2  556171000.0    3e+08      4.6      out_df = pd.concat(
   581         1          0.0      0.0      0.0          [df_index_1, df_input_1, df_index_2, df_input_2, df_overlap], axis="columns"
   582                                               )
   583         1          0.0      0.0      0.0      if keep_order:
   584         1 5526529000.0    6e+09     46.2          out_df = out_df.sort_values([index_col_1, index_col_2])
   585                                           

• pandas.DataFrame.sort_values takes the most amount of time