Quadratic runtime of selecting N hyperslabs

HDF5 Library
5

What’s the HDFGroup’s proposed path forward?

I see two approaches:

  1. Try to fix the performance bug in H5S__hyper_merge_spans_helper to ensure that it has the right algorithmic complexity when the trees are very unbalanced. I’d expect that by using bisection it should be possible to merge two selections of size N and M in time max(log(max(N, M)), min(N, M)). Meaning if one tree has size N and we insert a single slab, i.e. the case for (some) H5Sselect_hyperslab it runs in log-time, while merging two balanced trees runs in time proportional to the total number of elements.
  2. Expect users to not use H5Sselect_hyperslab when merging hyperslabs in bulk and instead expect them to use H5Scombine_select, e.g. in a manner similar to the workaround sketched above. This could be achieved by documenting the complexity of H5Sselect_hyperslab and H5Scombine_select clearly and referring to H5Scombine_select from H5Sselect_hyperslab. If so it would be very helpful if H5Scombine_select could be polished to allow combining NONE and ALL selections (see separate topic).