Subject: [mmox] Compact Binary Serialization

From: Catherine Pfeffer <[email-masked]>
Date: Tue, 24 Feb 2009 18:01:29 +0100

> There needs to be support for a binary serialization that does not
> contain embedded type or key references, but instead use explicit
> external schema. Thus, to describe a "quaternion" you would simply
> specify four fp16 (or fp32) values in sequence, with no specific type
> information. This can extend to describing general entity property
> values: the type information can be carried by the schema for the
> entity, and does not need to be encoded in the actual data. Allowing
> external schema leads to significant bandwidth savings during
transmission.

Wow, this one is violent!

OK, let's examine it in detail:

1) Example of the quaternion.

As I understand it, a quaternion is currently implemented as:
   <array>
        <float>0.5</float>  <!-- x -->
        <float>-0.5</float>  <!-- y -->
        <float>0.5</float>  <!-- z -->
        <float>0.5</float>  <!-- s -->
   </array>

(in the order x, y, z, s and not math's order s, x, y, z, that's one of
Second Life's strangenesses)

bandwidth could be spared with something like:

   <array>
        <float repeat="4">0.5,-0.5,0.5,0.5</float>  <!-- x, y, z, s -->
   </array>

(If you ask me why this is enclosed within <array> tags while we could
remove these tags without losing any information, I think the answer is:
"because it leads to a cleaner C++ code to access the data in that way".
Correct me if I'm wrong here, Infinity)

Such a functioning could spare bandwith (57 bytes versus 87 bytes for this
quaternion), while still remaining compatible with the other serializations
(but not in a 1:1 straightforward compatible way as they are now).

There could even be more bandwidth spared with constructs like:
   <array>
        <floats>0.5,-0.5,0.5,0.5</float>  <!-- x, y, z, s -->
   </array>

because you don't really need to specify in the data that there are four
floats, it's obvious from the number of commas. That would be 47 bytes
versus 87, including the useless <array> tags. Nearly the half.

2) Moving the type information to the schema.

Yes, that's the "ordinary way" of encoding data in XML.

Ordinary way:
     XML schema or DTD says: we have the avatar's nose orientation
quaternion here. That's four fp32.
     XML data over the wire:
<nose-orientation>0.5,-0.5,0.5,0.5</nose-orientation>

LLSD (simplifying):
     LLIDL says: nose orientation is an array of four fp32s
     LLSD data over the wire: <floats>0.5,-0.5,0.5,0.5</floats>

(Example of nose orientation might be idiotic, I had no time to choose it
better.)
(I have used <floats> and not 4 <float>s because that was boring to type)

**** Jon, you are touching something at the very core of LLSD here. ****

Where ordinary XML markup would say "this is nose orientation", XML
serialization of LLSD says "this is four floats".

While such choices seem weird in an XML file, they make a lot of sense for
binary serialization where the data type of the following data can be
specified in a single byte: "the next sequence of four bytes is going to be
a floating point number". It would be impossible to declare "now there is
going to be the nose's orientation. For the number of bytes involved, look
at the schema" in a binary file using a simple byte.

That does not mean it is impossible to put semantics in the binary file sent
over the wire, but you have to do it with maps, i.e. with the binary
serialization equivalent of:
  <map>
       <key>nose-orientation</key>
       <array>
          <floats>0.5,-0.5,0.5,0.5</floats>
       </array>
   </map>

Have I summed up correctly the whole reasoning behind that, Infinity?

Compare the bandwidth difference with:
      <nose-orientation>0.5,-0.5,0.5,0.5</nose-orientation>
No need to comment on that.

I see this as another example of "Yeah, that's strange XML, but it maps 1:1
to a nice and natural binary serialization" :-(.

Now back to your question: "should we move the type information to the
schema, as all people do in XML?". The answer is probably: "no, because we
want to keep a simple 1:1 mapping with the binary serialization".

Now, could we do partial exceptions for common types like vectors or
quaternions? Perharps. I already suggested:
         <integers>127,255,127</integers>
         <floats>100.0,75.3,28.6</floats>
         <floats>0.5,-0.5,0.5,0.5</floats>

but it could also take other forms with more semantics like
         <colour>127,255,127</colour>
         <vector>100.0,75.3,28.6</vector>
         <quat>0.5,-0.5,0.5,0.5</quat>

although I see the second solution as harder to fit in the existing LLIDL,
which works at a lower level of semantics.

(I intentionally did not store the colour in a vector, because that's
another SL-ism).

I hope that helps.

-- 
Cathy

---

From: Jon Watte <[email-masked]>
Date: Tue, 24 Feb 2009 12:19:06 -0800

Catherine Pfeffer wrote:
> (in the order x, y, z, s and not math's order s, x, y, z, that's one 
> of Second Life's strangenesses)
>

They are in good hands. Direct3D, OLIVE, and a lot of other 3D systems 
use XYZW. It's a bit like the question of row vectors on the left (D3D) 
or column vectors on the right (OpenGL). There are two ways to do it, 
and the world is split about equally.

>      LLSD data over the wire: <floats>0.5,-0.5,0.5,0.5</floats>

Why do you need to send "floats" at all?

>
> I see this as another example of "Yeah, that's strange XML, but it 
> maps 1:1 to a nice and natural binary serialization" :-(.
>

I think the binary serialization in LLSD is too verbose. My suggestion 
was to allow the SD language to express type information to the point 
where you can assume the data types from the context. For example, to 
update properties on an object, you would need to send, in binary, 
something like:

<object-id> <number-of-updates>
(<property-id> <data-for-property>) *

"number-of-updates" is a small integer, so will typically fit in a byte. 
"property-id" is a small integer in the context of "object-id" and thus 
will typically take one byte. "data-for-property" for a quaternion 
stored as four fp16 is 8 bytes. Thus, the actual storage for this one 
property (in the context of where it's used) is 9 bytes; the total 
message size (assuming there is only one property value) is 10 bytes 
plus the size of an object identifier.

Note that "data-for-property" is ONLY the raw data, not with any 
indication of what that data is. The schema for the entity already 
describes what that data is, so you don't need to send that with every 
binary packet you send. Thus, in that form of binary serialization, you 
optimize for transmission size, which is important for interactive, 
real-time transmissions. When you want a more "resilient" format, and 
size doesn't matter, you simply use XML instead.

To clarify: object of id <object-id> has some type. That type has some 
schema, that maps small-integer property-id values to string-name and 
data-type. Typically, when you encounter an object, you will understand 
the type/structure of that object once, but you will see changes to 
properties many times. And, in systems which have fewer types than 
objects (which is most systems except for SL, I think), you have 
additional savings by only needing to encounter a type once, and then 
that work is re-used for each object of the same type.

In this context, the schema for the object type would be described in 
some data description language. That language could perhaps be one area 
where something like LLSD would make sense -- but LLSD, as it stands, is 
not up to the task IMO. Hence, my suggestions (one of which is to 
support external schema for transfer encoding efficiency).

Btw: if you know that you will have the schema when you 
serialize/de-serialize objects, then the "more natural" XML encoding 
would also map easily to the internal binary format, because all the 
data you need about whether things are arrays or ints or whatnot is 
available through the schema, so the more natural 
"<nose-orientation>1,2,3,4</nose-orientation>" XML serialization would 
also be possible (and, IMO, desirable).

> schema, as all people do in XML?". The answer is probably: "no, 
> because we want to keep a simple 1:1 mapping with the binary 
> serialization".
>

But my point is that the binary serialization does not serve the needs 
of what a binary serialization should do, which is save transmission 
space. It contains both key and datatype, where the verbose key name is 
typically inlined instead of sent by reference-to-external-schema. If 
you can describe things with external schema, then you can save a LOT of 
transmission space where it matters, which is in the binary serialization.

Sincerely,

jw

---

From: Dan Olivares <[email-masked]>
Date: Wed, 25 Feb 2009 01:27:17 -0500

Hmm,

Just one thing to point out here;

might seem ok, however, consider what happens when someone in a locale
with a different way of displaying the number tries to figure out what
this means?

In the United States, the following number format applies:  (-)123,456,789.00
In Germany, the following number format applies: 123.456.789,00
In Russia and Finland, the following number format applies: 123 456 789,00

This, in my opinion, is the case for separating them with explicit
separations within the syntax using non-ambiguious terms
Is <colour>127,255,127</colour>, one hundred twenty seven million two
hundred fifty five thousand one hundred twenty seven?
Is <vector>100.0,75.3,28.6</vector> one hundred thousand and seventy
five tenths?

Best Regards

Daniel Olivares

On Tue, Feb 24, 2009 at 3:19 PM, Jon Watte <[email-masked]> wrote:
> They are in good hands. Direct3D, OLIVE, and a lot of other 3D systems use
> XYZW. It's a bit like the question of row vectors on the left (D3D) or
> column vectors on the right (OpenGL). There are two ways to do it, and the
> world is split about equally.
>
>
>> LLSD (simplifying):
>> I see this as another example of "Yeah, that's strange XML, but it maps
>> 1:1 to a nice and natural binary serialization" :-(.
>>
>
> I think the binary serialization in LLSD is too verbose. My suggestion was
> to allow the SD language to express type information to the point where you
> can assume the data types from the context. For example, to update
> properties on an object, you would need to send, in binary, something like:
>
> "property-id" is a small integer in the context of "object-id" and thus will
> typically take one byte. "data-for-property" for a quaternion stored as four
> fp16 is 8 bytes. Thus, the actual storage for this one property (in the
> context of where it's used) is 9 bytes; the total message size (assuming
> there is only one property value) is 10 bytes plus the size of an object
> identifier.
>
> Note that "data-for-property" is ONLY the raw data, not with any indication
> of what that data is. The schema for the entity already describes what that
> data is, so you don't need to send that with every binary packet you send.
> Thus, in that form of binary serialization, you optimize for transmission
> size, which is important for interactive, real-time transmissions. When you
> want a more "resilient" format, and size doesn't matter, you simply use XML
> instead.
>
> data-type. Typically, when you encounter an object, you will understand the
> type/structure of that object once, but you will see changes to properties
> many times. And, in systems which have fewer types than objects (which is
> most systems except for SL, I think), you have additional savings by only
> needing to encounter a type once, and then that work is re-used for each
> object of the same type.
>
> In this context, the schema for the object type would be described in some
> data description language. That language could perhaps be one area where
> something like LLSD would make sense -- but LLSD, as it stands, is not up to
> the task IMO. Hence, my suggestions (one of which is to support external
> schema for transfer encoding efficiency).
>
> serialize/de-serialize objects, then the "more natural" XML encoding would
> also map easily to the internal binary format, because all the data you need
> about whether things are arrays or ints or whatnot is available through the
> schema, so the more natural "<nose-orientation>1,2,3,4</nose-orientation>"
> XML serialization would also be possible (and, IMO, desirable).
>
> But my point is that the binary serialization does not serve the needs of
> what a binary serialization should do, which is save transmission space. It
> contains both key and datatype, where the verbose key name is typically
> inlined instead of sent by reference-to-external-schema. If you can describe
> things with external schema, then you can save a LOT of transmission space
> where it matters, which is in the binary serialization.
>
> Sincerely,
>
> jw
>
> _______________________________________________
> mmox mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mmox
>

---

From: Jon Watte <[email-masked]>
Date: Wed, 25 Feb 2009 11:03:55 -0800

> with a different way of displaying the number tries to figure out what

That could be a non-problem. Define C locale, and you're done. And, btw, 
C locale does not use thousands grouping at all. Note that the schema is 
for machine data interchange (a user doesn't generally enter quats by 
hand :-).

Sincerely,

jw