Design

[brentp]

We seek input from the rust genomics community about the design. Specifically issue#2

We are interested in brain-storming the benefits of the Box<dyn> approach vs the enum approach which allows static dispatch and extracting the exact Struct. While Box is more flexible in some ways, it has many downsides.

[NatPRoach]

I've admittedly not tried this myself, so this might not work, but you may be able to have your cake and eat it too to some extent by adding to the enum an element that contains a Box<dyn Positioned>.
Something like

pub enum PositionedEnum {
    BedRecord(bed::record::Record<3>),
    GenericExtendablePositioned(Box<dyn Positioned>),
}

Then if people want to extend the API the easy way and take the performance hit from the dynamic dispatch they can.
Definitely doesn't fully solve the problem, and there's still tradeoffs to consider, but might be worth considering.

[brentp]

wow. I like this idea! I think it's a great balance--we get static dispatch for the common, supported types but also allow user-added.

thanks very much!

[brentp]

I started stubbing this out here

[pmarks]

My initial reaction is: are you sure you want/need heterogeneous collections of Positioned objects at the lowest level (ie inside IntersectionIterator)? My instinct is that you'll be much happier with pub struct IntersectionIterator<'a, Pbase: PositionedIterator, Pother: PositionedIterator> with no boxing or enum, which yields appropriate generic Intersections type.

You can always instantiate a more generic IntersectionIterator with an enum or a boxed type if you need the heterogeneity, but you don't require it from the start. Then at the top level of your CLI, you'll have some match block that fills in the concrete types that are actually needed at runtime (so (open_reader)[https://github.com/brentp/bedder-rs/blob/d051b6520401caddc81a05364838c9065dcb8ee5/src/sniff.rs#L47] would return an enum and you'd match over that).

I think there 3 advantages of the generics approach:

• best performance - everything is monomorphized
• simplest inner code - don't need to deal with boxing / enums in the innermost code.
• more strongly typed: you always know what types you've got, so you can write higher level operations that require a more specialized type of records and enforce that with a type constraint (e.g. your example here)

Drawbacks:

• at least 2 generic parameters on all your intermediate methods that build on top of the core generic primitives.
• some potential for getting into "generics hell" where it's hard to write out all the generic and constraints. (I think you'll have to try this out to see how complex is gets).
• lots of monomorphization --> potential for long compile times. if you have 5 different Positioned impls that could apply to each side of the intersection then you'd have 25 concrete version, so that might force you to have an enum type to use sooner rather than later.

Anyway, not sure that's the right way to go, but might be worth exploring a bit to see how it feels.

[brentp]

@pmarks I'm still not a seasoned rust developer, so bear with me.
I think what you're describing will work if you always only have 2 files (-a, and -b in bedtools speak). But we want this to be generic so you have a query file and any number of (heterogenous by type) -b/database/Pother iterators.
Does your idea still work if you have many Pother iterators?

[pmarks]

Ok I see how bedtools -a FILE1 -b FILE1 FILE2... is set up. In that case you would need the heterogeneity, so Pother::Item would need to be either Box<dyn Positioned> or an enum type. So if that's the common case then making IntersectionIterator generic, and then always use in a runtime-dynamic type might not be helpful.

[brentp]

thanks for verifying. perhaps there's a way to specialize the common case of only -a and a single -b without adding too much burden for maintenance or too much cognitive load for using the API.

[brentp]

The enum approach is mostly implemented here. There's a sizable performance hit:

   Running benches/random_intervals.rs (target/release/deps/random_intervals-801ebcd7f6173da3)
Gnuplot not found, using plotters backend
Benchmarking simple intersection: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 22.5s, or reduce sample count to 20.
simple intersection     time:   [221.62 ms 222.33 ms 223.11 ms]
                        change: [+35.681% +36.470% +37.386%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe

I think it is still worth it as matching on the enum will be quite nice and perhaps we can remove the value() method from the trait.

[brentp]

This is implemented and incorporated into main branch.
I changed a few other small things to get performance back up.
Now we have the same performance as bedtools -sorted. bedtools is not known to be fast, but the -sorted part is quite performant.

(base) brentp@x1:~/src/bedder-rs$ time bedtools intersect -sorted -a LCR-hs38.bed.gz -b LCR-hs38.bed.gz -g $fai -c | md5sum
04f79bd3e2754ee3886402a325c2597f  -

real    0m1.053s
user    0m1.080s
sys     0m0.061s
(base) brentp@x1:~/src/bedder-rs$ time ./target/release/examples/intersect_bed_count LCR-hs38.bed.gz LCR-hs38.bed.gz  $fai | md5sum
04f79bd3e2754ee3886402a325c2597f  -

real    0m1.014s
user    0m0.971s
sys     0m0.116s