Idea for reworking the type structure (adding abstract types)

[MillironX]

Hi all,

It's been a while since I've had a chance to really sit down with this project, and I think that has helped clear my head of some preconceived notions and let me see where the cracks are in the current API setup.

All of the issues on the issue tracker right now are in the same vein of "since a Haplotype can come from an alignment, then find a way to translate an alignment back to a Haplotype." That should be trivial, but it hasn't been. #42 is still in draft mode because there are edge cases that I can't find a way to detect and deal using the current API.

One of the primary problems I have with the current API is that there is no way to deal with Variations that represent different types of Edit. For example, counting up in a cigar string should add 1 for Variations that contain a Substitution, but add the length of the Insertion or Deletion otherwise. There are way too many times that I have to do the ugly hack of reflection and if statements.

e = mutation(var)
if e isa Deletion
    # do one thing
elseif e isa Insertion
    # do another thing
elseif e isa Substitution
    # do yet another thing
else
    error("Unsupported type $e")
end #if

Julia's thing is multiple dispatch, but the way the API is constructed doesn't allow for multiple dispatch to be used effectively. Maybe I'm conflating me not finding a reverse-alignment solution with the clunkiness of the API, but considering how much time I've spent hacking together private methods just to make my alignment methods work, I think it's time I invest in a new API before moving on to alignment.

My proposal is to make both Variation and Edit into abstract types, then make Substitution, etc. into the concrete implementations. This diagram should present the type structure I'm thinking of.

(I did not include parametric types here in the diagram for brevity, but those would stay).

Now, instead of doing reflection and delegating based on if trees, the above code chunk would behave something like

f(x::Deletion) = deletion_implementation(x)
f(x::Insertion) = insertion_implementation(x)
f(x::Substitution) = substitution_implementation(x)
f(var)

That feels more Julian, and it should bring performance benefits from losing branches.

I want to get some feedback on what impacts this API change might have, since it basically will require a bottom-up rewrite of the entire package. Two basic questions:

1. For anyone who uses SequenceVariation besides me, will this change your workflow for the better or worse? If you don't use SequenceVariation, might this induce you to?
2. What are the performance implications of switching to abstract types like this? I mentioned how we have shifted runtime decision branches into compile-time dispatch, but I'm not naive enough to assume that there are only positives from this switch. The main reason I picked up this project is because my own variation-searching algorithms were hundreds of times slower than what @jakobnissen came up with here. I don't want to repeat those mistakes.

Thoughts, comments and feedback of all kinds are welcome before I start tearing this library's guts out. Thanks.

[jakobnissen]

What you are suggesting is a better API, but it will result in slower code. That is why I originally wrote it as it currently is (a struct wrapping a union).
Consider your proposed Haplotype, which contains a Vector{Edit}, with Edit being abstract. Now you create some function that loads an edit, and passes it to a function - say the f example function in the post above.
The optimally efficient way of implementing this is using if-statements (or computed goto, but it's not possible to express those in Julia). Currently, the Julia compiler uses an optimisation called "world splitting", which does the following transformation:

Before world-splitting:

edit = haplotype.edits[i]
f(edit)

After world-splitting

edit = haplotype.edits[i]
if edit isa Deletion
    deletion_implementation(x)
elseif edit isa Insertion
    insertion_implementation(x)
elseif edit isa Substitution
    substitution_implementation(x)
else
    f(edit) # fallback branch to throw the right MethodError
end

I.e. world-splitting automatically produces the same code that you are currently doing manually. The problem with that is:

1. World-splitting only happens up to a couple of methods of f, I believe it's currently 3.
2. Worse, Julia doesn't promise that world-splitting will continue to occur in the future. And there are good reasons to believe that optimisation might be removed in the future. The reason is that the compiled methods produced by world splitting are vulnerable to invalidations, and these invalidations are currently a large source of latency. Indeed, I've myself written a long rant arguing that this optimisation does more harm than it does good. If this optimisation is removed in the future, then the proposed design with abstract types will become much slower.

In contrast, if-else statements are, and will always be, fast. Their main drawback is that they are annoying to write and error-prone. The ideal situation would be if Julia had native support for match statements like Rust. They're essentially just a more ergonomic way of writing these if-else blocks.

I propose either:

1. Continue with the current implementation with structs containing a Union, and all functions that use that struct using if-else statements.
2. Take a dependency on SumTypes, and have Edit be a sum type. Use the @cases macro in functions. This is more ergonomic than if/else statements, but it requires the dependency on SumTypes, which I wouldn't do myself. SumTypes reaches somewhat into Julia internals and is maintained by only one single person, which makes it fragile and prone to break in a few years if Mason Protter disappears.

On the other hand you can just use SumTypes for now and then change it to if/else statements later if need be.

[MillironX]

Thanks! That's the kind of info I needed to hear. I'll have to create some MWEs on my end and benchmark them to see how well they work. I wonder if there's a way I can create a set of macros that will mimic my "ideal" API, while still providing the underlying performance under the hood without just reimplementing SumTypes.

As to SumTypes, I'm not against using it as a dependency for now (it receives more regular updates than I've given SequenceVariation), but it's definitely not an ideal situation. Once again, I'll run some benchmarks on my end on some MWEs and see if I like the API enough to sacrifice the "purity" of this library.