Change type of tsk_tree_t.num_children to tsk_id_t

[jeromekelleher]

Following up on recent additions to the tree data model in #2316, I wonder if we've made the right decision on the type for the num_children array.

While tsk_size_t is the "right" type for something that's a count, having an array of 64 bit numbers is unnecessary here because we can't possibly have more children than there are node IDs, and making this array twice as big as it needs to be is a significant memory overhead.

So, for simplicity, perhaps we should make the type of the array tsk_id_t, even though that is somewhat inconsistent with other usages? The other option would be to make it a uint32_t, but that's tricky because we'd have to typedef it in the BIG_TABLES case. We'd only be doing this to make the type unsigned anyway, which doesn't make all that much difference.

I don't think there's a right answer here, and at least making it a tsk_id_t is simple and consistent with the other tree arrays?

cc @benjeffery @GertjanBisschop

[benjeffery]

I agree that it seems a bit of a waste to use a 64bit type for this count. I know it is a pathological edge-case but the max size of a table is TSK_MAX_ID + (tsk_size_t) 1; we would need to change that to remove the plus 1 if we wanted to be water-tight.

Whats so bad about uint32_t with a typedef?

[jeromekelleher]

Hmm, so let's see how it would happen. Let say we have TSK_MAX_ID nodes, and they form a star tree with 0 being the root. That means that num_children[0] = TSK_MAX_ID - 1, right?

[benjeffery]

Can't the virtual root have as many children as there are nodes? I.e. each node is a root? Never going to happen I guess. Just like to know we understand the edge cases.

[jeromekelleher]

Yes, your right, so worst case scenario is node table full to capacity and an empty edge table. Does overflow the int32?

[jeromekelleher]

One thing we could do is to make a uint32 typedef tsk_count_t for this. We would have to think through where else this should be used, though, and the tedious post 1.0 compatability details.

[benjeffery]

Yes, your right, so worst case scenario is node table full to capacity and an empty edge table. Does overflow the int32?

I can't create a node table that large on my machine! I assume it would though.

I guess if we had tsk_count_t you would use it wherever you had e.g. num_nodes and num_edges which is a lot of places and would lead to a lot of compatibility cruft post-1.0 for very little gain.

Maybe a way forward is to use a tsk_id_t, but make it a tree-sequence integrity failure if you have a full node table and no edges?!

[jeromekelleher]

I guess if we had tsk_count_t you would use it wherever you had e.g. num_nodes and num_edges which is a lot of places and would lead to a lot of compatibility cruft post-1.0 for very little gain.

It may not be too bad because if people had things like

tsk_size_t num_edges = tsk_treeseq_get_num_edges(ts);

and we changed tsk_treeseq_get_num_edges to return tsk_count_t, then we'd be assigning a uint32 into a uint64, which even the most paranoid compiler should be OK with.

I agree it's a lot of work and not much gain though.

Maybe a way forward is to use a tsk_id_t, but make it a tree-sequence integrity failure if you have a full node table and no edges?!

That wouldn't work I'm afraid. Say you had a gap at the start of the tree sequence, then the first tree would be empty and we'd therefore have TSK_ID_MAX + 1 roots.

[jeromekelleher]

A workable option would be to reduce the value of TSK_ID_MAX by one - this will make no difference to anyone, and make an annoying corner case go away...

[jeromekelleher]

I think guaranteeing that a table size can fit into an int32 is a good thing actually, and would save a bit of angst for things like this:

tsk_id_t j;

for (j = 0; j < (tsk_id_t) tables.edges.num_rows; j++) {
    // do something with edge j
}

in principle this is currently undefined, I think.

[benjeffery]

A workable option would be to reduce the value of TSK_ID_MAX by one - this will make no difference to anyone, and make an annoying corner case go away...

I think this is the right way to go. I've opened #2336.