Tracking issue: edge recording performance

[molpopgen]

This issue tracks what needs to be done to eliminate the need to sort the edges associated with new births.
The method has been used in fwdpy11 for about 3 years.
(It is what I presented to one of the first online tskit meetings in 2020.)

By more carefully recording edges as they are born, we can eliminate the need to sort them.
This works for overlapping and non-overlapping generations.

A Python prototype is here.
Some of the necessary changes to the C API are here, implemented via hacks to the C API in tskit-rust.

We can shave many hours off of simulation time (see prototype link above for images). The method approaches the efficiency of simplifying via threads that I presented recently. The parallel method is enabled by #2665. The results in the notebook shown above get about 80% of the performance gains that I saw with threads, but with one core and less memory needed, thus pushing back the parameter space where methods like #2665 will be helpful.

TODO list:

• Implement the modular simplifier. Importantly, the implementation used an opaque pointer approach to keep all the simplification guts private. Testing this is simple: we record edges to a second edge table that we then sort, then apply them to the new API. By "scrambling" these arrays correctly, we can trigger errors (non-contiguous processing of parents, etc.).
• Implement a simple edge buffer in C. This will be based off of what has worked well in fwdpp. Again, opaque pointers will keep the guts private so that we can perhaps improve things later on.
• Write a new variant of the example program that uses the efficient method.

Notes:

• Because the edge sorting currently applies criteria NOT needed by simplification, the output tables will be slightly different. We can't use naive methods to compare outputs from the integration tests. The rust implementation linked above had hints.

[bhaller]

This is one that I think should be kept open for reference, or maybe moved to a Discussion if you think that's more appropriate. This is information that SLiM and other tskit clients might well want to see, down the road; it's knowledge that we don't want to lose track of.

[jeromekelleher]

converted to discussion