be mindful of alignment on the wire

[cscheid]

Part of changing BSON like we suggested was so we could send float arrays that could get directly addressed as a float* into the receiving buffer. (Well, javascript Typed Arrays are slightly more complicated but the idea is the same: you want to have a Float64Array pointed at the middle of some memory buffer)

However, the javascript Typed Arrays spec is fairly strict, and requires that binary data be word-aligned. If we want to have a Float32Array, that object can only point at 4-byte aligned boundaries.

So the naive idea is: if we're sending float data, we should pad the beginning of the payload, so the payload itself starts at a 4-byte boundary from the beginning of the entire message. Double data aligns at 8 bytes.

Unfortunately, doing that directly is a bad idea. Implementing this requirement by straight padding means that the wire grammar is not context-free (it depends precisely on the length of the previous message modulo 4 or modulo 8). This would be, as they say, a serious pain in the ass.

So we need to think carefully about this. Ideas?

[jacobhinkle]

Honestly, I'm mostly concerned with small data that JSON would be capable of handling. I realize you want to pass lots of data quickly, hence the BSON interface. That said, I'll try and be helpful where I can while deferring to you on this stuff:

I don't understand the problem with floats. Why is padding a problem? Presumably we'd prepare a preamble first before starting to stream the data. Is it more of a pita than just strlen(preamble)? Perhaps a small demo of the problem would be helpful.

[cscheid]

It might not be that much of a problem, actually, just something we want to make sure we get right.

Let's say I request a dataset that is a matlab struct, or a json object with a float array and a double array, one after the other, like this:

{ foo = [1.0f, 2.0f, 3.0f],
bar = [4.0, 5.0, 6.0]
}

foo is an array of floats, bar is an array of doubles.

Let's say that the message protocol is: B for {, E for }, and that every key in the object is given by exactly two bytes, and that foo gets mapped to 00 and bar gets mapped to 11. So, unpadded, our message would be:

B00{12 bytes of the float array}11{24 bytes of the double array}E

the problem here is that neither array is aligned to the right boundary, so we can't use Float32Array views into the binary message coming from the websockets API.

That's the basic problem. The naive solution is to do something like this:

B00P{12 bytes of the float array}11PPPPPP{24 bytes of the double array}E

Where P represent padding bytes. This is a well-formed message, but only if the object is the only thing we're sending! The grammar is context-sensitive. For example, if instead we were to send two copies of this same object, like this:

{ foo = { foo = [1.0f, 2.0f, 3.0f],
bar = [4.0, 5.0, 6.0] },
bar = { foo = [1.0f, 2.0f, 3.0f],
bar = [4.0, 5.0, 6.0] },
}

The encoding is now this:

B00B00PP{12 bytes of the float array}11PPPPPP{24 bytes of the double array}E1B00PPP{12 bytes}11PPPPPP{24 bytes}EE

Notice that the encoding of the two copies within the message, and they're both different from the when the object existed by itself. This is because the length of the message is not 0 mod 4 or 8.

If the grammar was context free, then we could cache the byte streams in memory for objects instead of having to traverse the whole tree structure every time. That is a big win if this ever needs to scale up (and we should design for scale).

So I'm looking for a solution that preserves as much "context-freedom" as possible, while guaranteeing alignment.

The solution I see right now which satisfies these requirements is to align every terminal to 8 bytes. But 1) that could be wasteful and 2) if we ever need to align to 16-bytes, we're screwed. So if we can come up with the right solution for this, now is the time.

[cscheid]

I should mention that the reason I thought of this problem is that the R wire protocol I'm parsing (http://www.rforge.net/Rserve/dev.html) does not satisfy this requirement, and so half the time, randomly, I'm currently forced to make data copies.

[jacobhinkle]

I had always assumed that we would not directly support complicated types, meaning stuff that includes both float arrays and double arrays. So basically each chunk would only have one big "data" part that we can send first, before sending the other crap like mtime etc, or maybe that other stuff would be available only by request. In that case, since we are always sending the data first we can handle alignment pretty easily no? We just decide we will always have an 8 or 16 byte preamble and things are automatically aligned.

This raises the other issue of what will be supported data types? In my opinion the relationships between arrays is best expressed in some other format than structs and other compound types, for simplicity and flexibility reasons. In fact since we're planning to use a heirarchical representation why not just represent this data as its own directory? Then when you request the directory/* you get each of foo and bar, in individual blobs.

[cscheid]

Yeah, I guess this means we need to decide which data types we'll actually support :)

I'll open a new issue.