Datashape scalability

[wesm]

I have a high level design question concerning using text as a serialized representation of array metadata. In my opinion, it is not the best choice as a primary representation. Let me explain why

A problem that the big data community has run into concerns "large metadata" -- storing very wide or very complex tables in file formats like Parquet has resulted in performance problems because manipulating the metadata itself (serialized as a Thrift message) is unwieldy -- parsing and serializing is expensive, and doing small projections / selecting certain fields out of a large data set incurs the cost of the entire metadata.

In Apache Arrow, we have a more restricted type system than datashape, but we decided to use a "zero copy" or "no parse" technology, Flatbuffers (from Google), to represent metadata in a portable way. We chose Flatbuffers over alternatives (like Cap'n Proto -- created by the main author of Google's Protocol Buffers file format) because of community traction and cross-language support (it has first class support for C++, C#, C, Go, Java, JS, PHP, and Python, with Rust and other languages in the works).

Using a technology like Flatbuffers for the serialized representation enables O(1) inspection of schemas, without any copying or parsing overhead, regardless of how big the schema is. Have you thought about using something like this instead?

[skrah]

Thanks for the ideas! I would be curious about the performance aspect before addressing the other points. FlatBuffers has a benchmark that uses a very small struct:

https://google.github.io/flatbuffers/flatbuffers_benchmarks.html

libndtypes2 has a benchmark that uses a huge struct (make bench). The file is:

https://github.com/blaze/libndtypes2/blob/master/tools/bench.c

Parsing and deallocating the huge struct 1million times takes 7.2s on my slowish T400 machine.
Using the small struct from the FlatBuffers benchmark in tools/bench.c, 1 million repetitions take 2.5s.

Unfortunately the FlatBuffers benchmarks don't build here, so I'm using their self-reported time (likely measured on a faster machine that the T400).

Encode (also 1 million times): 3.2s.
Dealloc (also 1 million times): 0.08s.

So on the surface creating and deallocating the types seems quite fast in libndtypes2.

[skrah]

Correction, the benchmark used the old syntax and was broken (should be fixed now in master). The real numbers are:

Huge struct, 1 million times: 112s
Small struct, 1 million times: 5.4s

So it is 5.4 vs 3.2 (self-reported -- machine?, exact benchmark?).

[wesm]

So these numbers are "time to generate a serialized string from an in-memory schema"? The numbers I'm interested in are times to parse (deserialize) and emit (serialize) large schemas, with 1 million or more elements -- the issues I'm describing would show up in use cases like "read the metadata for a given subset of 100 particular fields".

Memory efficiency is also a concern -- one of the benefits of Flatbuffers is that you can select what you want from e.g. a memory-mapped file without any unnecessary copying.

I can collaborate with you on some benchmarks for these use cases sometime in the next week or so if you'd like.

[wesm]

Sorry reading this again

So it is 5.4 vs 3.2

These numbers aren't comparable because the tasks aren't the same. To do a proper comparison we will have to write Flatbuffers IDL that encodes identical data to what's being parsed in libndtypes2. I can help with this

[teoliphant]

Thanks for the reference and connection. I want to make sure we are on the same page as data-shape is only about describing data in memory or disk and not a serialization strategy.

Are you suggesting that we use flat-buffers to store the data-shape meta-data rather than the current data-shape string? An standard for encoding data-shape meta-data to avoid the parsing step at all sounds great.

[wesm]

That's right. When you use zero-copy tools up and down the stack, the on disk representation and the in-memory one are the same. So it's suboptimal for metadata to take longer to "load" for larger schemas when general zero-copy "serialization" tools like this exist.

[teoliphant]

Great suggestion! I just wanted to make sure I understood and Stefan understood.

[skrah]

I'm still trying to figure this out -- Think about this potential datashape use case, e.g. typing a Numba gufunc. This is the existing syntax without datashape:

@guvectorize([(float64[:,:], float64[:,:], float64[:,:])], '(m,n),(n,p)->(m,p)')
def numba_matmul(x, y, res):
    col = np.arange(y.shape[0])
    for j in range(y.shape[1]):
        for k in range(y.shape[0]):
            col[k] = y[k, j]
        for i in range(x.shape[0]):
            s = 0
            for k in range(x.shape[1]):
                s += x[i, k] * col[k]

With datashape it could look like this:

@guvectorize('(M * N * float64, N * P * float64) -> M * P * float64')
def numba_matmul(x, y, res):
    ...

The reasonable thing to do here would be to parse the datashape string once and keep the datashape tree alive in memory. The tree can be walked directly to find elements, guide gufuncs to the proper location and so forth.

Can flatbuffers store ndarrays at all? How would the symbolic dimensions used above be represented?

[skrah]

The easiest way to see how complex the trees get is to print the AST:

make print_ast
echo "(M * N * float64, N * P * float64) -> M * P * float64" | ./print_ast -

[wesm]

The reasonable thing to do here would be to parse the datashape string once and keep the datashape tree alive in memory. The tree can be walked directly to find elements, guide gufuncs to the proper location and so forth.

I think you're arguing based on a misconception. If you want to convert the Flatbuffer to some other data structure (like the C structs you have defined in this project), you can certainly do that. But it is a zero-copy data structure that you can open and examine without any parsing overhead.

Want to work on a prototype together?

[wesm]

Here's an example type that can store ndarray metadata:

table FixedDimension {
  size: long;
}

table SymbolicDimension {
  name: string;
}

union Dimension {
  FixedDimension,
  SymbolicDimension
}

table Tensor {
  value_type: Type;
  shape: [Dimension];
}

(I'm not certain whether you can have an array of union values, you may need to wrap them in a non-union container)

[skrah]

Thanks for the example! So the suggestion is to replace all data structures defined in

https://github.com/blaze/libndtypes2/blob/master/ndtypes.h

with the flatbuffer schema and use flatbuffers for everything, including type tree traversal for gufuncs and pattern matching of types (this needs to be fast, surely there's some overhead in flatbuffers)?

[wesm]

It's definitely a better primary serialized representation instead of a string that you have to parse. It also gives you the ability to read the metadata in all of the languages that Flatbuffers support. You could use another tool like Protocol Buffers or Thrift for the same purpose, but as discussed the parsing overhead will grow burdensome with large schemas

As far as performance, we should write some microbenchmarks to understand the number of nanoseconds it takes to perform certain performance tasks. Do you have any code examples for what you're describing?

In C++ at least, the generated bindings are header only so everything gets inlined

[teoliphant]

Hey Stefan. If I understand correctly, flatbuffers would not replace any code in ndtypes.h for now nor would it replace the datashape strings we are using in numba or gumath. It could, however be used as a representation of datashape that is passed between computer processes.

This looks like a very useful optimization, but I would not place it on the current critical path for you. A PR would be welcome, however.

[datnamer]

Can't the type pattern matching be inlined by numba?