Redefine strongly typed containers as a more flexible, repeatable, embeddable construct.

What we have...

Draft 11 added support for Strongly Typed Containers (Array and Object) - http://ubjson.org/type-reference/container-types/#optimized-format

The underlying premise of the design was to define a header (TYPE and/or COUNT) at the beginning of a container which contains X number of Value Type elements.

Short-comings...

The biggest problem with this approach is what has been getting discussed in #43 - strongly typed containers cannot themselves contain other containers (strongly typed or not) -- so this construct, while highly optimized for certain use-cases, introduces a limitation that doesn't exist in JSON (any container can contain any type -- even if they are not of the same type).

Ok, so what about Issue 43?

Issue #43 fixes that limitation, but as been pointed out to me privately by @kxepal - we still find ourselves with some limitations of STCs the way they are defined -- they are still too rigid and not for a great technical reason.

What limitations still exist?

Namely:

1. Mixed-type containers cannot be optimized - you either need to use the largest type to store all the values (e.g. in the case of numbers) or you have to rely on a standard un-type-optimized container.
2. The COUNT provided in an STC right now dictates the hard end of that container, e.g. if an array has a count of 4 that means after the 4th element the scope of that array closes. This can potentially rule out the use of highly optimized STCs in streaming environments (like a DB or large client-server requests) where the response cannot be totaled ahead of time -- the workaround for this currently is to change the structure of your data to consume 0 or more containers and append them together into a single datum - this is frustrating for implementors (needing to change data to meet limitations of spec) or a non-starter for using STCs in these cases.
3. JSON natively supports mix-typed containers (e.g. arrays containing strings and objects and other arrays and numbers) - with Draft 11 versions of STC, UBJSON imposed a new limitation specific to UBJSON that typed containers could only contain a single type - requiring implementors that had to deal with mix-typed containers to either remodel their data or add app logic to work around the limitations in the spec (same problem as the previous point)

How do we address these?

This proposal is taking the finalized header defined in #43 (here - #43 (comment)) that looks like this:

[{]                                 // this is an object
    [#][i][3][$][[]                 // of arrays (3 of them)
        [#][i][3][$][{]             // of objects (3 of them)
            [#][i][3][$][[]         // of arrays (3 of them... again)
                [#][i][3][$][i]     // of int8s (3 of them)

and combining it with an idea proposed by @kxepal -- allowing the header to be repeated 0 or more times within a container, for example:

[[]                                 // array start...
    [#][i][3][$][i]                 // 3x int8s to follow...
    [1]
    [2]
    [3]
    [#][i][3][$][d]                 // 2x float32 to follow...
    [1.11]
    [2.22]
    [#][i][2]                       // 2 fully typed values to follow...
    [S][i][3][bob]
    [L][9223372036854775807]
[]]

Changes required to support this...

Roughly:

• # or #$ (or the combination of the two) would constitute a "header" section inside of a container. Encountering those markers inside a container convey information about the data that is going to follow until the container ends or the next 'header' marker is hit. This is no longer a container header but rather a header for a run of data that follows it.
• The ] or } marker characters would ALWAYS have to be used now to indicate the end of the scope of a container, because the count in the header of a container no longer indicates when parsing of that scope ends.

Implications to use

This would support everything from using STCs the way they are defined now to the more extreme case of optimized/mixed-type containers that we never could support before (but are supported in existing in JSON)

Down sides

Currently the only downside I can think of here is the actual implementation of parsing a strongly typed, mixed-typed container in a language like Java or C# (C++?) where there is no longer a guarantee that parsing a list of int32 values can be safely represented as a List<Integer> but must instead be some UBJSON super type or worse a List<Object> which is a no-go.

I don't think dynamically typed languages will suffer from this, but in strongly typed languages it is sort of nasty.

As the spec goes, I think this is a nice addition to the flexibility and the academically correct way to define strongly typed containers -- in reality though, maybe supporting them in generation/parsing is so painfully inefficient that it doesn't make sense.

Thoughts?

ADDENDUM

Removed the example of the typed-but-not-counted section at the bottom of my proposed example above - @kxepal reminded me (again) why we cannot have types without counts :)

(you can't tell when the container ends, for example if you parsing the int8 value of 93 or the char ']' with the same dec value)

ADDENDUM

Adding to the Down Sides section, consider the following example when thinking of how a relatively straight forward parser API would properly support this -- the only thing I can come up with is a stream parser design (just want to provide concrete details to speak against):

[{]
    [[] // array1 - FQN types.
        [i][32]
        [i][64]
        [i][127]
    []]
    [[] // array2 - single-type STC
        [#][i][3][$][i]
        [32]
        [64]
        [127]
    []]
    [[] // array 3 - mixed-type STC
        [#][i][3][$][i]
        [32]
        [64]
        [127]
        [#][i][3][$][d]
        [3.14]
        [9.99]
        [1.23]
    []]
    [[] // array 4 - mixed-type, mixed-container
        [#][i][3][$][i]
        [32]
        [64]
        [127]
        [#][i][3][$][d]
        [3.14]
        [9.99]
        [1.23]
        [S][i][3][foo]
        [S][i][3][bar]
        [T]
        [F]
        [Z]
    []]
[}]

ADDENDUM

In an effort to continue talking to myself and flushing out this idea, a relatively common implementation of this would be identical to the STAX or JSON streaming parsers where a layer ontop of the stream parser would be necessary to add context to where in the scope of the UBJSON the parsing was taking place (e.g. in an Object, in an Array or inside a strongly typed of counted subset of either of those)

That said the stream parser itself would just emit events when it encountered certain markers, just like XML or JSON stream parsing:

while(parser.hasNextMarker()) {
  switch(parser.nextMarker()) {
    case Markers.OBJECT
    case Markers.ARRAY
    case Markers.CONTAINER_COUNT_HEADER
    case Markers.CONTAINER_TYPE_HEADER
    // etc...
  } 
}

Anyone see any problems with this in other languages?

[meisme]

With this, is there any point in retaining the count header/optimization? We can no-longer use it to reliably pre-allocate the needed memory.

[Steve132]

Making all containers dynamic dramatically inhibits performance in strongly typed languages, because memory for the containers must be reinterpreted now before use.

Before, with a strongly-typed container we could read a binary array of floats as literally that, a binary array of floats. You can parse the ubjson into the appropriate structure, and then the pointer to the first child is literally the address for the entire array. This array can then be used, modified, read, etc exactly like an array would in the language of choice.

//before
ubjr_array_t arr=parse_array(filestream);
float* fp32data=(float*)arr->data;
float avg=std::sum(fp32data,fp32data+arr->size);

//after
ubjr_array_t arr=parse_array(filestream);
float* fp32data=malloc(arr->size*sizeof(float));  //allocate storage for standard array
ubjr_reinterpret_data(arr,UBJ_FLOAT,fp32data);  //copy and reinterpret from mixed type to standard array
float avg=std::sum(fp32data,fp32data+arr->size);

With this, all containers are effectively dynamically-typed, and you can no longer use them effectively as memory objects.

I think this 'feature' is not great. It saves a few bytes of header information in some uncommon cases at a cost of dramatically increased complexity and performance in all the useful common cases (like actually using the data from an STC)

If you really want this 'optimized mixed type' or 'mixed-type strongly-typed container' or whatever it is, it seems better to not have it interfere with the common case use cases that we currently have, by adding a special case to the header parser for an STC...like, maybe when you parse an STC, you can have an 'M' for 'mixed' in the type header after the '$' that tells it to drop to this mode and expect another header followed by a repeating header. That way this doesn't interfere with the rest of the code for the current STC use cases.

@Steve132 Appreciate the very explicit breakdown - this is why I wanted to get other's thoughts.

With this, all containers are effectively dynamically-typed, and you can no longer use them effectively as memory objects.

Yes, exactly.

I think this 'feature' is not great. It saves a few bytes of header information in some uncommon cases at a cost of dramatically increased complexity and performance in all the useful common cases (like actually using the data from an STC)

This is the strongest point you make... this is an optimization for an uncommon case at the cost of making the most common case slower to parse.

Let me ask you this, if we allowed STC's to contain STCs per #43 but otherwise left the constructs unchanged -- in that the header of an STC can only ever come at the HEAD and maps 1:1 to the entire scope of the container -- would you be good with that?

If you agree with that, we can take the suggestion of introducing a mixed-mode flag (M) into a separate proposal, but I don't think that will be super popular for the reasons you point about above (makes parsing so much more laborious... just use an unoptimized array if you have a lot of mixed data)

[kxepal]

@meisme @Steve132
Why are you care about preallocation so much? If you'll receive 2GiB UBJSON data on host with 1GiB RAM, the last thing that you'll made is allocate whole it in memory. Yes, it'll speedup some bits, but ability to preallocate things isn't a feature, but tradeoff which may not being acceptable for certain situations.

[meisme]

@kxepal I think it follows quite naturally from writing an implementation in a non-memory managed language like C++. Naturally there are cases where you wouldn't want to read an entire file into memory, but even still being able to efficiently read the parts you want is beneficial.

@kxepal to your point - you are right, the buffer should not be assumed to be 1:1 with the #-size parsed at the beginning of the container.

I think the big hole that @Steve132 poked in this proposal (that I was trying to speak to in my last few Addendums) is how the nature of mixed-type containers removes our abilities to parse fast-and-quick (making all sorts of assumptions around type and sizes)

A middle ground to this proposal - would be to allow a COUNT to repeat 1 or more times in a container, but the TYPE to only be specified once at the header of the container... a la:

[[][$][i][#][i][4]
  1
  2
  3
  4
  [#][i][2]
  5
  6
  [#][i][4]
  7
  8
  9
  10

This would solve both your problems and addressed the streaming-friendly case for highly optimized data.

If gut-feeling is this could go somewhere, I can spin this into a separate proposal.

SUMMARY (July 19, 2014)

What is being discussion is a modification to the original proposal:

Option 1: Allow STC headers anywhere in a container; fully supporting optimized storage of mixed-type containers.

• PRO - 1:1 compatible with the JSON spec while continuing to allow the use of STCs in mixed-type cases.
• CON - Makes parsing containers in an optimized way much more painful in strongly typed languages like Java or C.

Option 2: Allow ONLY the COUNT header to repeat once a type is defined for a container, but the type of a container cannot change until the scope of the container is closed.

• PRO - parsing in strongly typed languages is much easier since the type doesn't change. supports a streaming-environment where the ENTIRE length of the contents in a container may not be known ahead of time.
• CON - artificially instills a limitation on UBJSON where STC's cannot be utilized in mixed-type containers.

It occurs to me that the mixed-type optimization case is optimizing for Objects and optimized for same-type containers optimizes for Arrays.