CodSpeed Performance Report

Merging #4830 will not alter performance

_{Comparing ct/list-view-zctl (0c3ab0f) with develop (1e6f8a1)}

Summary

✅ 1172 untouched

Codecov Report

❌ Patch coverage is 92.29935% with 71 lines in your changes missing coverage. Please review.
✅ Project coverage is 87.70%. Comparing base (1e6f8a1) to head (0c3ab0f).

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@robert3005 could you clarify what you mean by "make sure results are correct even if the hints are incorrect"? I think I've taken care to make sure that the hints / invariants are always correct even through the different operations.

The downside is that when reading "untrusted" data the validate step will take slightly longer, but the benefit is that we can other operations more efficiently (namely take and filter) later. (Note that ListView version of take and filter + rebuild is roughly equivalent performance-wise to the normal List version of take and filter, not even considering any reset_offsets calls).

Maybe there's an already builtin property that we can leverage for the same behaviour

Unless there's a something very subtle I'm missing, the whole point of ListView (from my understanding) is that we relax the "built-in properties" of List as a tradeoff for a different feature set. That's sort of why I built this semi-auxiliary structure and code to mimic those missing properties. Maybe we don't even need this for most use cases (as I have yet to properly canonicalize ListView so we can run benchmarks, I will make sure that will be done on Monday), but I think this is necessary to always have similar performance to List in all cases.

I didn't notice that the shape is being validated, I think that covers the correctness. I have been wondering if this is that big of an issue if we have more reasonably sized list element chunks? I think right now you end up with 100M elements in the child which is definitely bad. It could be that this is the right approach but I am always hesitant about adding more complexity

@robert3005 to get this moving again, @joseph-isaacs is concerned that if in the future we want to do a chunked version of the elements (as the default version canonical ListView), we would probably want to use a little metadata struct array of these flags for each chunk (not global), and thus we would need to break the file format (see the listview/vtable/serde.rs file).

We also ran the statpopgen benchmark with this optimization (on this branch) and it is still a regression, but much less than before, because the only slowdown here is from the much more expensive validate function. In fact, if we turn off validate for lists, ListView becomes about 15% faster than List.

I am not convinced that chunking the underlying elements array would solve this problem. What chunk size would we use for the elements? The writer has no idea what is a good chunk size because it has no idea what access pattern the reader might have (if the reader reads a single row versus a large amount of data, or if the reader reads in a sort of striped pattern, or completely random, or in a sort of pareto shape, etc).

I also do not think that breaking the ListView format is such a big deal considering nobody is using ListView right now (because it's not done). And we can always revert this before #4853 eventually merges (if we even want to merge that at all, it doesn't seem like we are 100% confident that making ListView the default canonical version of List is the best idea).

I would like to merge this so I can make actual progress on #4853, which has been stale for almost 2 weeks now.

I don't want to change the array serialisation format. I want to change the layout for list arrays. What I think we should do is merge the change to have ListView be the canonical array, we shouldn't add the ListViewShape. Then we should work on a listviewlayout that wouldn't produce insanely large list chunks

Dicussed offline, we can revisit this in the future.