Skip to content

complement and subtract are very slow with large number of features #120

Closed

Description

@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.

Activity

  1. smitkadvani commented on Mar 26, 2024

    @smitkadvani
    Contributor

    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)]
    ==============================================================
    

    image

    • 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                                           
    

    image

  2. locked and limited conversation to collaborators on Mar 26, 2024
  3. converted this issue into a discussion #193 on Mar 26, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions