Expose sorting API and test C++ implementation.

[jeromekelleher]

Closes #616

Here's an initial proposal @molpopgen and @bhaller. I've tested out basic C++ linkage by stealing @molpopgen's nice code, which should hopefully make the proposal clear.

Basically, in C++ code we'd have

    tsk_table_sorter_t sorter;
    ret = tsk_table_sorter_init(&sorter, &tables, 0);
    check_error(ret);
    /* Set the sort_edges to our local C++ version. We could also set some
     * persistent state in sorter.params if we wanted to. */
    sorter.sort_edges = sort_edges;
    ret = tsk_table_sorter_run(&sorter, NULL);
    check_error(ret);
    tsk_table_sorter_free(&sorter);

One thing I'm a little bit uneasy about is what happens if std::sort throws an exception within the sort_edges function. The C code is expecting sort_edges to return an error if something bad happens, so what'll happen if an exception occurs? Will it all just work out, or will things explode?

I guess we should test it. (If anyone has ideas for less lame ways than assert(something) for defining the C++ tests that doesn't involve an annoying dependency, I'd love to hear it!)

[molpopgen]

Easiest/laziest thing regarding exceptions is the following:

try
{
  std::sort(blah blah blah);
}
catch(...)
{
return -1;
}

This is like a bare except in Python, hiding the exception type, etc..

[molpopgen]

As for tests, I'd just make sure the return value is 0 and then use existing C logic along with your existing test framework. I think you could also make the C++ sorting work via a function with C linkage, so that you can compile tests using that function as if they are C. That'll work as long as any exceptions are caught.

[codecov]

Codecov Report

Merging #627 into master will increase coverage by 0.01%.
The diff coverage is 92.30%.

@@            Coverage Diff             @@
##           master     #627      +/-   ##
==========================================
+ Coverage   87.45%   87.46%   +0.01%     
==========================================
  Files          24       24              
  Lines       18156    18162       +6     
  Branches     3606     3609       +3     
==========================================
+ Hits        15878    15886       +8     
+ Misses       1100     1099       -1     
+ Partials     1178     1177       -1     

Flag	Coverage Δ
#c_tests	89.00% <92.30%> (+0.01%)	⬆️
#python_c_tests	90.61% <ø> (ø)
#python_tests	99.00% <ø> (ø)

Impacted Files	Coverage Δ
c/tskit/tables.c	79.26% <92.30%> (+0.07%)	⬆️

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 47254af...09d41ef. Read the comment docs.

[bhaller]

Looks very reasonable to me. I only skimmed the diffs; I can do a more full review if necessary. The question I have at this point is: why is this scheme being implemented only for the sorting of edges? Wouldn't it make sense to do the same thing for the sorting of the other tables? Perhaps I missed the beginning of the conversation regarding this.

[molpopgen]

why is this scheme being implemented only for the sorting of edges?

The other sorts aren't really registering in profiles the way edge sorting is.

[bhaller]

why is this scheme being implemented only for the sorting of edges?

The other sorts aren't really registering in profiles the way edge sorting is.

Might that depend upon the model being run? Or are you pretty sure it's not a problem for any model? I suppose we can always add the same sort of delegated sorting for other tables later if it turns out to be necessary...

[molpopgen]

You can always make a model to emphasize mutation sorting: set u = 1000 and r = 0. But a lot of the models folks seem to be wanting in involve r >= u and the edge sorting function is the most expensive of the 3--its comparison function requires the most logic. We could add the ability for other callback, but if you're doing 2, you probably want to do all 3, and at that point you've written a stand alone sorter.

[jeromekelleher]

The question I have at this point is: why is this scheme being implemented only for the sorting of edges? Wouldn't it make sense to do the same thing for the sorting of the other tables? Perhaps I missed the beginning of the conversation regarding this.

The only reason for skipping it @bhaller was I wanted to see if you and @molpopgen agreed with the basic architecture before I bothered setting it up for the other tables. No reason why we wouldn't expose the functionality, although things are a bit trickier for mutation and site tables.

[jeromekelleher]

Great, thanks both. I'll finish this up, document it and ping you for a review in a few days. One quick question @molpopgen - is this safe:

int 
sort_edges(tsk_table_sorter_t *sorter, stuff)
{
   try {
       ret  = cpp_sort_edges(sorter, stuff);
   } catch (...)
       ret = -1; 
   }
   return ret;
}

That seems like a reasonable thing to recommend in the documentation then?

[molpopgen]

Great, thanks both. I'll finish this up, document it and ping you for a review in a few days. One quick question @molpopgen - is this safe:

int 
sort_edges(tsk_table_sorter_t *sorter, stuff)
{
   try {
       ret  = cpp_sort_edges(sorter, stuff);
   } catch (...)
       ret = -1; 
   }
   return ret;
}

That seems like a reasonable thing to recommend in the documentation then?

I believe that it is safe*, but I find the semantics confusing--why does an edge sorting function need to know about the entire sorter layout? What would this mean in terms of the callback proposal described above?

• the way to test the catch will be to have a unit test that always throws on the C++ side. We should test throwing an exception type and a non-exception type, as both are allowed.

[jeromekelleher]

I believe that it is safe*, but I find the semantics confusing--why does an edge sorting function need to know about the entire sorter layout? What would this mean in terms of the callback proposal described above?

This is the same structure I have above. Rather than functions with callbacks, I thought it would be simpler to just overwrite the function pointer on the "class". The table_sorter_t first parameter then is just the object calling convention. If you need to store some state, you can do it on the sorter object which has a void * params field.

[molpopgen]

If I understand right, the sorter still contains a callback? So you have a c++ function taking a pointer to a sorter containing a callback to another c++ function?

[jeromekelleher]

Yes, exactly, that's how it's set up in the test_minimal_cpp.cpp file above. It doesn't seem to matter that the sort_edges that we've defined is a C++ function, presumably because it has a straightforward C signature?

[molpopgen]

It doesn't seem to matter that the sort_edges that we've defined is a C++ function, presumably because it has a straightforward C signature?

That's right. The signature doesn't include the function name, which is "mangled" if it is a C++ function.

[jeromekelleher]

Interesting idea from @molpopgen offline: we should check if sort_edges is NULL before trying to execute it. That way the sorter can get on with sorting sites and mutations while C++ code does the edge sorting asynchronously.

Probably wouldn't generalise to sites and mutations though, since they must be done in a certain order (which will be documented).

[molpopgen]

Probably wouldn't generalise to sites and mutations though, since they must be done in a certain order (which will be documented).

Yeah, the home thread should suffice there anyways: the async edge sorter could run in parallel.

[jeromekelleher]

This should be nearly done now, I think. I hit an annoying problem with doxygen where it's ignoring the typedef'd struct name, so will have to figure out a way around that. Should be done except for documentation though, if you'd like to base your sorting work from this @mufernando. I'll try and get this finished up ASAP and merge though.

[jeromekelleher]

This is ready for review I think - @molpopgen, @bhaller, any chance you could take a look please? Hopefully we can do the actual example as a follow up, I think the C++ tests should be a clear enough indication of how this is intended to be used for now.

[molpopgen]

Will take a look tomorrow.

[bhaller]

Seems very good, just trivial tweaks and comments/questions.

[bhaller]

unclear why this is in the diffs; is this just an unrelated bug fix that's along for the ride?

[jeromekelleher]

Yep, exactly. I must have spotted it while I was in there.

[bhaller]

Is there a utility to not sorting the edges, for some case? I.e., is that why passing NULL produces that behavior, instead of just asserting that self->sort_edges must be non-NULL?

[molpopgen]

You can imagine the following type of logic (psueodcode) being useful for very large tables:

std::packaged_task<int()> efficient_edge_sorter(...);
std::future<int> sorter_future = efficient_edge_sorter.get_future();
tsk_table_collection_sort(...); // sort_edges = nullptr
sorter_future.wait();

The result is that the edge sorting is done asynchronously to the sorting of the other tables, which only depend on times, meaning the contents of the node table.

[molpopgen]

@jeromekelleher -- I think that this is in excellent shape. The only outstanding issue that I see is @bhaller's comment about giving the other tables a similar treatment. I'm fine holding off on that for now, though.

[jeromekelleher]

Thanks a bunch @bhaller and @molpopgen, this was really helpful. I'll open an issue to track adding the C++ example - I think it'd be a good idea for us to come up with most efficient (single threaded) way we can think of to sort the tables. I