Implement efficient seeking from non-null trees using tree_pos

[duncanMR]

trafficstars

Description

Continuing from #2874, we want to finish moving over the tree-positioning code to use tree_pos efficiently. At the moment, tsk.tree_seek will either call tsk_tree_seek_from_null or tsk_tree_seek_linear depending on whether we are starting from the null tree or not. seek_linear repeatedly calls next or prev until it reaches the given position, with the direction being determined by which would cover the shortest distance.

As a first pass, I've implemented tsk_tree_seek_forward and tsk_tree_seek_backward and I've incorporated them into tsk_tree_seek_linear. We will need to revise some of the test_highlevel.py seek tests, because the direction we choose to seek along is different to the old approach in some cases. For example, we now seek forward to go from the first to the last tree in a sequence.

Curiously, my implementation passes all the C tests with no memory issues detected by Valgrind, and it also passes all the test_highlevel.py and test_tree_positioning tests except for the ones dependent on seeking direction. However, it has caused chaos with other Python tests, causing failures and segfaults in test_stats.py and test_divmat.py among others. The failing/crashing tests seem to be primarily be associated with LD calculations and divergence.

I'm currently trying to determine whether the problems are due to an error in my implemention (most likely) or the subtle problems with the time ordering of inserted edges, discussed in #2792.

PR Checklist:

• [ ] Tests that fully cover new/changed functionality.
• [ ] Documentation including tutorial content if appropriate.
• [ ] Changelogs, if there are API changes.

[codecov[bot]]

Codecov Report

:x: Patch coverage is 93.54839% with 6 lines in your changes missing coverage. Please review. :white_check_mark: Project coverage is 89.62%. Comparing base (ce09b35) to head (c79fbd8). :warning: Report is 6 commits behind head on main.

Files with missing lines	Patch %	Lines
c/tskit/trees.c	92.00%	2 Missing and 4 partials :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #2911      +/-   ##
==========================================
+ Coverage   89.61%   89.62%   +0.01%     
==========================================
  Files          28       28              
  Lines       31983    32058      +75     
  Branches     5888     5903      +15     
==========================================
+ Hits        28660    28731      +71     
- Misses       1888     1889       +1     
- Partials     1435     1438       +3     

Flag	Coverage Δ
c-tests	86.61% <92.00%> (+0.01%)	:arrow_up:
lwt-tests	80.38% <ø> (ø)
python-c-tests	88.19% <100.00%> (+0.04%)	:arrow_up:
python-tests	98.80% <100.00%> (+<0.01%)	:arrow_up:
python-tests-numpy1	52.45% <100.00%> (+0.01%)	:arrow_up:

Flags with carried forward coverage won't be shown. Click here to find out more.

Files with missing lines	Coverage Δ
python/_tskitmodule.c	88.19% <100.00%> (+0.04%)	:arrow_up:
python/tskit/trees.py	98.85% <100.00%> (+<0.01%)	:arrow_up:
c/tskit/trees.c	90.61% <92.00%> (+<0.01%)	:arrow_up:

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[jeromekelleher]

That is interesting. I can see the LD calculator causing problems as that does a lot of seeking backward and forward (was the original motivation for bidirectional seeking). I don't see anything obvious wrong, but it must be something to do with sample counts.

One thing that we can at least make progress on is that I think we should keep the option of seeking linearly. So, we make a new option to seek, TSK_SEEK_LINEAR which always uses the linear seek algorithm. We'll want to expose this to Python also, so there'll be a bit of plumbing involved.

We should specify this option in the ld_calculator, as that is definitely somewhere that linear seeking makes sense.

[duncanMR]

That is interesting. I can see the LD calculator causing problems as that does a lot of seeking backward and forward (was the original motivation for bidirectional seeking). I don't see anything obvious wrong, but it must be something to do with sample counts.

One thing that we can at least make progress on is that I think we should keep the option of seeking linearly. So, we make a new option to seek, TSK_SEEK_LINEAR which always uses the linear seek algorithm. We'll want to expose this to Python also, so there'll be a bit of plumbing involved.

We should specify this option in the ld_calculator, as that is definitely somewhere that linear seeking makes sense.

Okay; that makes sense to me. I'll revert seek_linear to its previous form and move the seek algorithm that uses tree_pos to a new function. I'll make the tree_pos method the default for seek, then see exactly which methods need to be changed back to linear in order for the tests to pass. Shall we call the new tree_pos method tsk_tree_seek_nonlinear?

[jeromekelleher]

seek_skip might be a bit more descriptive?

[jeromekelleher]

Something to bear in mind here is that sample_lists might not be compatible with this when seeking around randomly because of the non-linear order that edges can get inserted. A straightforward approach to getting this merged then could be to simply require that TSK_SEEK_LINEAR is always used with sample lists.

[jeromekelleher]

Note this is affected by #3245. Perhaps worth picking up to see if the problem is indeed with sample lists?

[jeromekelleher]

I'm going to take a quick look at this to see what's happening

[jeromekelleher]

I think this is ready for a more general review and merging. I'm reasonably sure that the algorithms are working now and everything is safe, but it's still not clear to me if we should make skip the default (if it's more efficient, why wouldn't we?). I guess a reasonable way forward might be to merge this much and file an issue to track what the performance differences are on a few different things and then decide whether we want to make it the default or not based on that.

[benjeffery]

I guess a reasonable way forward might be to merge this much and file an issue to track what the performance differences are on a few different things and then decide whether we want to make it the default or not based on that.

Sounds good to me.

[jeromekelleher]

I think we need your review and approval then @benjeffery to merge