make sort stricter

[petrelharp]

With subset, we can reorder tables. But we still can't easily take two sets of completely equivalent tables and put them in the same order. From the requirements:

• nodes we can order using subset
• pops and indivs will be ordered by earliest node by subset
• edge order is undefined among parents of the same time
• mutation order is undefined among mutations of the same time
• migration order is undefined among migrations of the same time

The ordering could be total by adding parent to the edge sort key, and node to the mutation and migration sort keys.

This would be nice to do since when doing union #623 we would like to make sure that when subsetting on the shared nodes the tables are equal. It'd probably be useful for other testing.

Table sorting is a bottleneck in forwards sims, so perhaps we want to make the "strict sort" optional; and if strict=True we first sort with the above additions to the keys, then do subset(range(num_nodes)). This would be guaranteed to always get the same order no matter the original order of the tables.

[jeromekelleher]

Sounds good @petrelharp, I'm all for making a canonical form. I agree we can't introduce these extra restrictions as requirements. I doubt it would make any difference performance-wise, but I don't think we can start sorting populations and individuals by default because this will surely break people's code.

I think we should use "canonical" as the term rather than strict, to emphasise we're putting tables into a canonical form.

[mufernando]

Well, it seems the sorting of edges surpass the requirements, because in practice they are being sorted by time, then parent node id, child node id and lastly the left coordinate:

tskit/c/tskit/tables.c

Lines 4325 to 4344 in 1374dbb

	cmp_edge(const void *a, const void *b)
	{
	const edge_sort_t *ca = (const edge_sort_t *) a;
	const edge_sort_t *cb = (const edge_sort_t *) b;
	int ret = (ca->time > cb->time) - (ca->time < cb->time);
	/* If time values are equal, sort by the parent node */
	if (ret == 0) {
	ret = (ca->parent > cb->parent) - (ca->parent < cb->parent);
	/* If the parent nodes are equal, sort by the child ID. */
	if (ret == 0) {
	ret = (ca->child > cb->child) - (ca->child < cb->child);
	/* If the child nodes are equal, sort by the left coordinate. */
	if (ret == 0) {
	ret = (ca->left > cb->left) - (ca->left < cb->left);
	}
	}
	}
	return ret;
	}

So we only need to do add sorting of mutations by nodes if time is tied.

[petrelharp]

Ok, great! We should make this clear in the documentation.

[mufernando]

Ah, also curious about #627, which changes the sorting API.

Should we go off of that?

[jeromekelleher]

Ah, also curious about #627, which changes the sorting API.

Hah, good slot @mufernando. Yes, it would probably be best to base your code off that as I've made some changes there. Better still, why don't I just finish that PR...

[mufernando]

Some notes on a convo @petrelharp and I had earlier today:

1. The proposed stricter sorting would make the tables canonical given the order of the nodes.
2. It's not possible to make the tables canonical without specifying the order of at least the leaves.
3. If we add (time, node) to the mutation sort key, then if time is missing, this might break things if it ends up just sorting on nodes, which aren't necessarily ordered by time.
4. The proposal actually needs one more thing: the mutation parent, to be canonical, because mutations can share time and node.
5. If we add (time, mutation parent, node) to the sort key for mutations, then this would produce a valid set of tables with child mutations always coming after their parents, as long as either (a) mutation times are present, or (b) child mutations come after parents, and parents are specified, in the original tables.
6. This would not guarantee to maintain the relative ordering of mutations if mutation times and parents are not specified, as our current implementation does, which is important for SLiM, but won't be important for SLiM since SLiM will be adding in mutation time. So, it is changing this behavior, but probably only SLiM uses it.

thoughts @jeromekelleher? waiting on your input to get started (mostly depends on whether we will modify the current sort definitively, make it an option, or create a different method altogether).

[jeromekelleher]

This all sounds good @mufernando. Things do get complicated with mutation times being unknown and so on.

I think it's worth sketching this up in Python before diving in to the C code actually. We'll need some test cases which have mixed known/unknown times, have/and are missing mutation parents. Getting these test cases nailed down and having a (simple) Python sorter where we can quickly get to the semantics that we want will help a lot.

[hyanwong]

Just to chip in to say that I depend on having a table sort function that does not change node IDs, so I'd like that to remain the default (which I think was the general idea, anyway, right?). Also that the docs mention "canonical form" for sorting, so we probably want to change the phrasing if by "canonical" we are now meaning a strict sort.