Allow strongly typed arrays to contain strongly typed arrays

[edgar-bonet]

Hi!

The current (2014-05-23) version of the specification seems to only allow primitive types (called “value” types) inside strongly typed arrays. As an enhancement, I am requesting that strongly typed arrays be acceptable as elements of strongly typed arrays. This would provide optimization for multidimensional arrays, without resorting to any new syntactic construct.

Example

I have (I really do) a few huge JSON files, each holding, among other things, a thousand arrays that look like this:

[
    [1.23, 4.56],  // this is one datapoint
    [7.89, 0.12],  // another datapoint
    // a few thousand more datapoints...
]

I am looking for a more efficient, JSON-compatible, binary representation of the same data. “Unoptimized” UBJSON yields:

[[]
    [[] [d][1.23] [d][4.56] []]
    [[] [d][7.89] [d][0.12] []]
    // a few thousand more datapoints...
[]]

With this representation, each datapoint costs 8 bytes of data (float32 is enough precision for me), plus 4 bytes of overhead. That's 50% overhead, not so good.

The same array as “optimized” UBJSON is:

[[]
    [[][$][d][#][i][2] [1.23] [4.56]
    [[][$][d][#][i][2] [7.89] [0.12]
    // a few thousand more datapoints...
[]]

Now we have 8 bytes of data + 6 bytes of overhead per datapoint. That's 75% overhead, so the optimization is obviously not good for these small inner arrays.

Per the current proposal, the outer array can also be optimized, which yields the following “recursively optimized” UBJSON:

[[]                 // this is an array
    [$][[]          // of arrays
        [$][d]      // of float32
        [#][i][2]   // inner arrays have length 2
    [#][I][3200]    // outer array has length 3200
    [1.23] [4.56]   // first datapoint
    [7.89] [0.12]   // second datapoint
    // a few thousand more datapoints...

Now we have a really optimized layout with zero overhead.

And importantly, we are not introducing any new syntax, but only specifying that the “type marker” of a strongly typed array is:

[type of array] = [[][$][type of elements][#][length of array]

In the above example, the type marker of the outer array ("[$[$d#i<2>#I<3200>" for short) would be recursively parsed as:

level 0: [$ ┐                   ┌→ #I<3200> = array of length 3200
level 1:    └→ [$ ┐    ┌→ #i<2> ┘           = arrays of length 2
level 2:          └→ d ┘                    = float32

Regards, and thanks for the good job.

@edgar-bonet I like the win, in this particular case, but I am having a hard time wrapping my head around the recursive implications here... for example a 3D or 4D array?

I understand the request in a 2D case:

<define header for outer and inner array>
  <data payload>

When I think of allowing 0+ definitions of pairs of type-size ($-#) and each one corresponds to a lower and lower level of array, it puts more and more burden on the parser or generator to be context aware.

I'm not against this, I'm just thinking through it out loud... would like others to weigh in as well.

(Restating examples so we can reference them for further discussion...)

1. JSON (40 bytes)

[
    [1.23, 4.56],
    [7.89, 0.12],
    [3.14, 0.08]
]

2. Plain UBJSON (38 bytes)

[[]
    [[][d][1.23][d][4.56][]]
    [[][d][7.89][d][0.12][]]
    [[][d][3.14][d][0.08][]]
[]]

3. Optimized Container UBJSON (47 bytes)

[[]
    [[][$][d][#][i][2][1.23][4.56][]]
    [[][$][d][#][i][2][7.89][0.12][]]
    [[][$][d][#][i][2][3.14][0.08][]]
[]]

[edgar-bonet]

Well, the definition

[type of array] = [[][$][type of elements][#][length of array]

being recursive, it allows for arrays of any dimension. I am guessing that any UBJSON implementation already relies heavily on recursion. This proposal just requires a little bit more of it.

I've written a not-so-clean Qt-based implementation, but I do not have access to it now (it's in my office). Anyhow, for the parser, the general idea is to have one recursive function for parsing the “type signatures”, and a second recursive function for parsing the actual data. In JavaScript-style pseudo-code:

function parse_type_signature(byte_stream)
{
    if (byte_stream starts with "[$") {  // fixed type array
        advance byte_stream by 2;  // consume "[$"
        var inner_type = parse_type_signature(byte_stream);  // recurse!
        assert(byte_stream starts with "#");
        advance byte_stream by 1;  // consume "#"
        var count_type = parse_type_signature(byte_stream);
        assert(count_type is some integer type);
        var count = parse_data(count_type, byte_stream);
        return {
                type: FIXED_TYPE_ARRAY,
                element_type: inner_type,
                element_count: count
            };
    }
    else {
        // other types...
    }
}

function parse_data(type, byte_stream)
{
    if (type.type == FIXED_TYPE_ARRAY) {
        var data = new Array of length type.element_count;
        for (var i = 0; i < type.element_count; i++)
            data[i] = parse_data(type.element_type, byte_stream);
        return data;
    }
    else {
        // other types...
    }
}

@edgar-bonet I was letting this proposal marinade a little bit in my brain - the space-optimization win is too big to ignore and I've since come around on the upfront definition of the container for an X-dimension set of containers... it is the nature of the strongly typed container anyway, so there is no diversion from what we already have.

I'm asking for feedback from the community on this, but overall I think a great proposal.

[meisme]

Since the strongly typed arrays only can contain one type of data, these cases can always be "unnested" for serialization, moving the complexity from the (de)serializer to the application. The previous example then becomes

[[][$][d][#][i][6]
    [1.23][4.56][7.89][0.12][3.14][0.08]

This is just 30 bytes (of which 24 is the floating point data itself). Personally I don't see the need for introducing the suggested complexity since it will inevitably use more overhead than this. There might be a practical use-case for nested strongly typed objects, though, I haven't thought that all the way through yet.

[kxepal]

While idea looks good, I fear that we'll make UBJSON too complex and ugly with attempt to handle all possible cases with "optimized" constructions. UBJSON should provide plain and simple primitive to easily and effective describe data structures and be error-prone in the same time. I feel we're drifting away from that original idea since Draft 10 (I'll open issue to discuss this a bit later).

Actually, you'd like to see only one case that would be optimised: array of pairs. It's very common case for representing: geo data, money, node relations (A->B), ip-port, list of properties (strings). This could be easily done with new container P (pair) which expects the following byte as element type marker (primitives only) and which is the only allowed to be used in array type description:

Plain array - 44 bytes: 2 + N(4 + 2*S)*

[[]
    [[][d][1.23][d][4.56][]]
    [[][d][7.89][d][0.12][]]
    [[][d][3.14][d][0.08][]]
[]]

Plain array of pairs - 38 bytes: 2 + N(2 + 2*S)*

[[]
    [P][d][1.23][4.56]
    [P][d][7.89][0.12]
    [P][d][3.14][0.08]
[]]

Optimized array of pairs - 34 bytes: 4 + 2NS

[[][$][P][d]
    [1.23][4.56]
    [7.89][0.12]
    [3.14][0.08]
[]]

As for N=1000 the difference becomes more significant: 14002, 12002 and 10004 bytes respectively. As for old good JSON it's around 15001 bytes (as for array of strings since we have to preserve accuracy). As for any other cases I don't feel good about overengineering UBJSON to handle X-dimension arrays. Let's make it more suitable for real world problems and let him doing simple things, but in easiest and effective ways that possible.

UPDATE: Yes, you may argue that there are many other cases where nested arrays may be applicable. And you'll be right: RDF describes data in triples, so pairs wouldn't fit it well. However, that's the only one exception that popular as well as pairs comes to my mind and actually you cannot optimize RDF triplets with UBJSON since these elements are string of variable length.

[kxepal]

But again, all nested arrays optimizations are requires two rounds serializer or predefined data scheme: you cannot apply these optimization while you're not sure if all array's elements has common data type - that's gives you O(2*N) serializing cost and the size benefit should worth that. On real world high load tasks nobody will do that as well as everybody use own line-per-element protocol for JSON data instead of read-and-decode strategy.

[edgar-bonet]

@meisme: Unnesting would not work for me. I have an application that is already in production and works well with JSON, except that the generated files can occasionally get too big to be practical. Users are familiar with the data model, which is “natural” for their use case. I just want to provide a more efficient serializing format in a way that is transparent to the users, thus without changing the data model. And this is a major selling point of UBJSON: it is supposed to work transparently with your current JSON data model.

@kxepal: Most of the time I will indeed have long arrays of pairs. However, occasionally these can be triplets. Typically, when acquiring data through a lock-in detector I have things like

[external_parameter, signal_in_phase, signal_in_quadrature]

The arrays could even be longer if the user sweeps several parameters simultaneously.

About the complexity: I do not think the complexity for the serializer should be an issue. As with any optimization, it is important that the format stays simple for the parser if the parser has to remain universal. The serializer, even a universal serializer, is free to ignore any optimizations... or implement whatever may make sense for the application.

[edgar-bonet]

@kxepal: More on the complexity of the serializer...

I just realized that the O(2N) complexity has nothing to do with this proposal: it's already in the current version of the standard if one wants to leverage the optimization afforded by fixed-type arrays. Here is the algorithm I use for deciding what type to serialize some data into:

/*
 * Find a common supertype of a and b.
 */
function merge_types(a, b)
{
    if (a == b) return either;
    if (either a or b is a subset of the other)
        return the "biggest" type;
    if (a == INT8 and b == UINT8 or vice-versa)
        return INT16;

    // The only part specific to this proposal:
    if (both are FIXED_TYPE_ARRAY with same length) {
        var inner_type = merge_types(a.element_type, b.element_type);
        if (inner_type == INVALID) return INVALID;
        else return FIXED_TYPE_ARRAY of inner_type;
    }

    otherwise return INVALID;
}

/*
 * Get the proper type for serializing this piece of data.
 */
function get_type(data)
{
    if (data.isArray()) {
        var inner_type = NOP;  // compatible with all other
        for each (element of data) {
            var element_type = get_type(element);
            inner_type = merge_types(inner_type, element_type);
            if (inner_type == INVALID) return PLAIN_ARRAY;
        }
        return FIXED_TYPE_ARRAY of inner_type;
    }
    else {
        // other types...
    }
}

As stated in the comments, the only part specific to this proposal is where I try to decide whether two fixed-type arrays have compatible types. I do so by having merge_types() call itself recursively. The recursion is not expected to go deep: only as deep as the dimensionality of the multi-dimensional array.

This is for the universal serializer. It is intended to serialize whatever the user throws at it. I also have a situation where the data is generated by the application itself (a data acquisition process actually) and I know before hand what kind of data to expect. In this case I can output the known type marker of the multidimensional array and then just stream the data in real time with no size overhead, and a very low processing cost (cast to float, convert to big endian, output).

[meisme]

Just to throw it in there, for most strictly statically typed languages (eg C++ which I'm in the process of writing a (de)serialiser for) types (including nested ones) can often be known at compile time, meaning the that the only increase in complexity will be for interpreting the data.

[Steve132]

N-D arrays of raw binary data DO have a pretty significant use in scientific computing and many other data sets....but I'm honestly VERY concerned with the amount of extra logical complexity in the parser and reader this proposal will introduce. It also sorta starts to lose 1-1 parity with javascript.

One 'middle ground' proposal that I would prefer dramatically would fix all the use cases here while simultaneously getting rid of the complexity of the parser and the writer and give us all the performance benefits is as follows:

Call them 'Multi-dimensional Strongly-typed arrays'. What we do is we simply make it so that after the size information in the STC array header there are 0 or more '@' patterns that optionally specify additional array dimensions for this container. (we cant' reuse '#' because it introduces an ambiguity in the parser with a one-d STC array of sized objects)

For example, here's OPs proposal,extended to a 3D array (like 3200x3200x3 bitmap)

[[]                 // this is an array
    [$][[]          // of arrays
    [$][[]      // of arrays
         [$][d]      // of float32
         [#][i][3]   // inner arrays have length 3
    [#][I][3200]    // middle array has length 3200
    [#][I][4223]

    [1.23] [4.56] [4.56]    // first datapoint
    [7.89] [0.12] [4.56]  // second datapoint
    // a few thousand more datapoints...    

Thats fine, but recursively parsing and validating that is a LOT of complexity and a total rewrite of the parser and it doesn't work if ANY
of the recursive elements don't parse properly. It's 18 bytes for the header.

In contrast, heres the MSTA version

[[]                 // this is an array
    [$][d]          // of float32   
    [#][I][4223][@][I][3200][@][i][3]  //first dim is 4233,second dim is 3200, third dim is 3

    [1.23] [4.56] [4.56]    // first datapoint
    [7.89] [0.12] [4.56]  // second datapoint
    // a few thousand more datapoints...    

It's stupid easy to integrate into the parser AND the writer with no recursion or multiple pass parsing, and has EVEN MORE storage savings than the proposal we are discussing ( the header is 14 bytes), and gives us ALL the performance benefits. Parsing is a LOT easier and the data structure for the type does not need to be recursive or recursively parsed