Proposal: "generic" chunk key encoding

[clbarnes]

Motivated by the incoming image codecs and existing data sets which are stacks of 2D images.

The generic chunk key encoding would be flexible enough to allow prefixes, suffixes, re-ordering the chunk index, and more besides. Its configuration values would be a format string (using e.g. python/rust-like {value} interpolation, or js-like ${value}, or mustache-like {{value}}, or whatever), whose inner values refer to the index within the chunk index (e.g. for chunk index (10, 11, 12), "c/{0}/{2}/{1}" would resolve to "c/10/12/11"). There could further be an empty interpolator {}meaning "all unused items", and aseparator` field with how to separate them.

For example, the default CKE could be written

{
  // ...
  "chunk_key_encoding": {
    "name": "generic",
    "configuration": {
      "format": "c/{}",
      "separator": "/"
    }
  }
}

and the v2 CKE could be written

{
  // ...
  "chunk_key_encoding": {
    "name": "generic",
    "configuration": {
      "format": "{}",
      "separator": "."
    }
  }
}

A 3D greyscale JPEG stack with Z slice directories and file names like {column}_{row}.jpeg could be

{
  // ...
  "chunk_key_encoding": {
    "name": "generic",
    "configuration": {
      "format": "images/{0}/{2}_{1}.jpeg",
      "separator": "/"  // unused, could be omitted
    }
  }
}

Some discussion points

• should both indexed and empty interpolations be allowed together?
• if so, might we also want to allow negative indices so that e.g. the last 2 dimensions are switched regardless of how many have come before?
• should there be a default separator for when it's not given, like there is for default and v2?

[d-v-b]

I like this idea. It does introduce a new coupling between the shape field and the chunk_key_encoding field -- we can associate a generic chunk key encoding with a "dimensionality", unlike the existing chunk key encodings. That would be bad if anyone expected to re-use the same literal chunk key encoding metadata in different arrays, but I don't think that's ordinary usage.

should both indexed and empty interpolations be allowed together?
if so, might we also want to allow negative indices so that e.g. the last 2 dimensions are switched regardless of how many have come before?

what about {"format": {0}/{2}/{*}, "separator": "."} defining functions like this:

• f((0,1,2)) -> "0/2/1"
• f((0,1,2,3,4)) -> "0/2/1.3.4"

here, the {*} template means "all the indices that haven't been explicitly declared"

[d-v-b]

should both indexed and empty interpolations be allowed together?

Are there any real use cases this would enable?

[clbarnes]

It does introduce a new coupling between the shape field and the chunk_key_encoding field

Indeed; this might require new validation mechanisms.

here, the {*} template means "all the indices that haven't been explicitly declared"

Yes, that's what I was thinking with the empty interpolation variable. I don't have strong opinions on empty/ asterisk/ ellipsis; nor on the syntax of the braces.

Are there any real use cases this would enable?

Same as the one I gave for negatives, I suppose - if you want the final element to be a specific index (e.g. first or last) but then the rest of them in natural order, and then you also want the same config to work across dimensionalities.

[clbarnes]

Some rough benchmarking addressing performance concerns from #28 (comment)

A first-pass python implementation takes about 1 microsecond to do the formatting for a 7D chunk where the format string includes positive and negative indices and an asterisk. The template is parsed once using the regex \${\s*(\*|-?\d+)\s*} (now we have 2 problems) when the metadata is first read and stored as a list of chunks which are raw strings, an index into the chunk index, or the set of indices into the chunk not to include in the asterisk.

[mkitti]

Some rough benchmarking addressing performance concerns from #28 (comment)

My question on the benchmarking is what happens at 10³ to 10⁶ chunk key encoding operations.

The tricky part to get correct here is not the raw execution time but rather the management of string allocation and deallocation. You would want to avoid the creation of many dynamically allocated intermediate strings by using a string buffer to perform the interpolation rather than concatenating raw strings pairwise.

The challenge for optimization is whether the length of that string buffer can be determined statically at JIT or compile time or if this now is dependent on dynamic allocation at run time. When can we determine an upper bound on the size of the resulting string?

Now that the challenge has been stated, the larger question is if predefined schemes that provide a subset of the functionality provide some implementation advantage by the virtue of being simple. Thus, it is not obvious to me that we should cull simpler chunk key encoding schemes in favor of a generic one.

[normanrz]

The challenge for optimization is whether the length of that string buffer can be determined statically at JIT or compile time or if this now is dependent on dynamic allocation at run time. When can we determine an upper bound on the size of the resulting string?

In the current propsal of generic, it would be possible to determine an upper bound for the string buffer when opening the array and examining the metadata, because you can count the place holders and get the max length of chunk IDs from the shapes. The other characters in the interpolation format are static. So, just as the current chunk key encodings as well as the proposed suffix encoding, dynamic allocation is required for generic, but possible with a fixed-size buffer as determined when opening the array.

Now that the challenge has been stated, the larger question is if predefined schemes that provide a subset of the functionality provide some implementation advantage by the virtue of being simpl. Thus, it is not obvious to me that we should cull simpler chunk key encoding schemes in favor of a generic one.

If you want to express a chunk key encoding that is equivalent to the proposed suffix, I am not convinced that it isn't possible to implement the generic encoding as performant as it would be to implement the suffix encoding (except for some minimal overhead upon array-open). Having dedicated suffix and prefix encodings would be redundant and result in more implementation effort.

[clbarnes]

Rust impl at 100ns per interpolation with the same strategy (49 million iterations in 5s).

In the rust impl, I pre-allocated the string buffer simply using the length of the input format string. That means you avoid reallocating for a chunk index up to 10_000 in each dimension (because the format string uses ${0} syntax, i.e. 4 bytes per index). You'd probably want some more headroom if the catch-all is used, and maybe a bit more if your separator was on the long side. Rust doubles the size of the string if you grow it beyond its initial bounds. I think a size like 10 * (len(fmt_str) + (4 + len(sep))) would be pretty safe, and if not, 2 allocations is probably fine as well.

I am practically certain that another string allocation here or there per chunk IO op will mean nothing compared to the cost of actually doing the IO. If we think that's the level of our bottlenecks, we should fire all the python devs.

FWIW, I benchmarked with a runtime calculation of the buffer length and it took an extra 2 nanoseconds, i.e. one five-thousandth of the IO roundtrip time to a direct-attached NVMe drive.

It's not in my proposal here, but I could see a use case for zero-padding the chunk index values, which would necessitate a more complicated string interpolator. As proposed here it's like 80 lines of python, 150 lines of rust, without golfing it.

[LDeakin]

+1 for also supporting zero padding, it would be necessary for my virtualisation usecase

[mkitti]

Rust was not the particular focus of my benchmarking question, although looking at that implementation would answer a few questions. Rust std uses string formatting macros where the format string needs to be known at compile time as a string literal, so part of my question was about the cost (in terms of performance and complexity) of not having such facilities available for a string format known only at runtime. I'm aware that there are runtime fmt crates.

I'm more interested in what this looks like in the least performant language of interest.

If you want to express a chunk key encoding that is equivalent to the proposed suffix, I am not convinced that it isn't possible to implement the generic encoding as performant as it would be to implement the suffix encoding (except for some minimal overhead upon array-open). Having dedicated suffix and prefix encodings would be redundant and result in more implementation effort.

I think it is certainly possible to implement generic encoding in most cases, but I also think it is more complex to do well relative to suffix. If you do have a generic cke available, you would certainly prefer to use that and perhaps even map a suffix encoding to use it. If you do need to implement one from scratch, this seems like a non-neglible jump in complexity to me.

[clbarnes]

+1 for also supporting zero padding, it would be necessary for my virtualisation usecase

Implemented! I just went with rust-ish syntax (which should also work-ish for python): regex \{((\*|-?\d+)(:0(\d+))?)\} i.e. pre{0:02}a{-1}b{*:03}suf.

Rust std uses string formatting macros where the format string needs to be known at compile time

In my implementation, I don't rely on rust's formatting for the format string directly, I parse it into a list of tokens. I use the write! macro to build the string directly into a buffer, one token at a time; python can do more or less the same thing, although it doesn't really give you the tools to avoid allocations. But I wouldn't be surprised if it weren't so different from what a suffix, prefix, or indeed the default chunk key encoder do under the hood.

Either way, I'd be happy to write python and potentially wasm bindings for the rust impl.