Re: [hybi] voting on frame length ideas

[John Tamplin <[e-mail]>]

On Mon, Aug 23, 2010 at 6:48 AM, Shelby Moore <[e-mail]> wrote:

> It is my understanding that this is caused by a lack of complete
> understanding of the issues, not by a valid difference of opinion. In
> fact, most disagreement in life derives from incomplete communication.
> When we think someone else is 'wrong', 99% of the time it is merely the
> opposing sides do not yet understand the logic of each other.


In this case, I think it is more likely that we have different use-cases in
mind.  Clearly someone who wants to process millions of WS frames per second
is going to have a different perspective from someone who wants to easily
implement a WS server in python to service a handful of requests per hour.
 It is unlikely those two will agree on how it should be done on their own
accord.


> Thus I explained that due to its internal economics, an implementation
> might be optimized with its maximum size larger than 126 if there were no
> costs of doing so, but perhaps not if the cost of processing conditionals
> combined with the fact that 98% of frames are less than 126, justified
> setting a _STRICT_ maximum size of 126, if that eliminated the
> conditionals. Remember above I pointed out that the _STRICT_ maximum size
> was a benefit when coupled with frame size that uses conditionals, because
> it allows the implementation to control its costs and maximize its
> economics. But the problem is that if we choose an option which can only
> do 0 - 126 size with conditionals eliminated by the _STRICT_ maximum size,
> then the (implementation self-optimization) optimization is a disaster,
> because it means a large frame has to be fragmented by the sender to 126
> byte frames! However, the receiving implementation probably did not have
> any benefit of limiting the maximum frame size to 126, except for the
> minimization of the conditionals cost.
>

I think it is ludicrous to suggest that an implementation would advertise a
maximum frame length of 126 just so its code for option #2 would look like:

int len=readByte();

rather than:

long long len = readByte();
switch (len) {
  case 126:
     len = readUnsignedShort();
     break;
  case 127:
     len = readLongLong();
     break;
}

while the former is certainly faster, that neglects the overhead of having
to process thousands of frames instead of one, which is what this would
require the sender to do when it needed to send a frame larger than 125
bytes.  Even if the receiver didn't care about costs to the sender or the
intervening networks, the receiver on net spends far more CPU time per
payload byte than if it just did the checks.

In addition, I think the receiver would still have to check that the length
byte was not 126 or 127, because their is no guarantee that the sender is
playing by the rules.


> So ladies and gentlemen, that is why I proposed "Option 15/63-bit" (I
> formerly called it "Option 1/15-bit"). Do you understand now?
>
> The 15-bit (32767 bytes) size when conditionals are eliminated by
> optimization of the _STRICT_ maximum size, is more than sufficient to
> prevent the above disaster scenario.  Also it has negligible (2%? [1])
> costs relative to the prior best option, "Option #2 - 7/16/63-bit":
>

I still think you can't get away from validating the input length, which
means you still have conditionals.

Regardless, I think the cost of a compare and an untaken branch is
absolutely negligible when comparing the other costs of processing a frame.


> 3) After I proposed "Option 15/63-bit", a new option was proposed "Option
> 8/16/32/64-bit". I can't yet decide between these two options, so I voted
> for both of them in the informal poll (and voted against all other
> options, except "Option #2 - 7/16/63-bit"). The "Option 8/16/32/64-bit"
> gives more reversed bits, but it adds a CPU cost of loading the LenLen,
> loading a value of 1 and left shifting by LenLen.


Rather than calculating a number of bytes to read for the length, it seems
more likely it will be:

short header = readUnsignedShort();
long long len;
// possibly shifting to make it 0-3 for table jump implementations
switch(header & LEN_LEN_MASK) {
  case LEN_LEN_8:
     len = readByte();
     break;
  case LEN_LEN_16:
     len = readUnsignedShort();
     break;
  case LEN_LEN_32:
     len = readUnsignedLong();
     break;
  case LEN_LEN_64:
     len = readLongLong();
     break;
}


> The "Option
> 8/16/32/64-bit" does not have any explicit conditionals that can be
> eliminated with a _STRICT_ maximum size, but a _STRICT_ maximum size is
> still required, else there will be an UNNECESSARY conditional to test if
> frame size is greater than maximum size (for those implementations that
> gain from such). Thus I am reasonably confident that "Option
> 8/16/32/64-bit" is superior to "Option 15/63-bit", but I am waiting to
> hear any other feedback on the list about this comparison.
>

The advantage of 8/16/32/64 vs 15/63 is the availability of more reserved
bits, and savings when the size is >= 32767 (with a significant savings up
to 4G).  Otherwise, 15/63 is the same number of bytes up to frame lengths of
255, shorter for 256-32766, and longer for 3277+.  It is hard to assign a
value to the reserved bits, and the rest comes to the expected distribution
of message sizes above 256 bytes.  My traces don't help much there, because
the largest frame I observed in the Wave and GWT Quake traces is 1393 bytes,
and the number of samples above 256 are very small.


> Let us contemplate how the _STRICT_ maximum size impacts the 63-bit
> sendFile() optimization?  An implementation will choose to minimize its
> costs, so we have to consider the selfish economics of what ever we
> choose. Perhaps with "Option 8/16/32/64-bit" we can tolerate the one
> conditional and make maximum sizes a hint, not _STRICT_?
>

If the receiver only has a fixed 64k buffer and you send it a 128k frame,
what is it supposed to do?  I don't see any recourse besides dropping the
connection.  Doubly so if it told the sender during the handshake that was
the largest frame size it could accept.


> [1] I write that only 'slightly', because John Tamplin had provided a
> distribution of frame sizes from some real world applications, which
> claims that only 2% of frame sizes will be greater than 126. I write
> 'claims', because statistics of the present, do not always predict the
> future (aka Murphy's Law). One thing I just realized now, is I forgot to
> check/ask John the mean and std deviation of frame size? To better
> quantify the impact of adding 1 byte to the header as the other options
> do.
>

Mean/stddev from the sample traces:

   - Wave C->S uncompressed: 287/80, compressed: 39.8/29.7;  S->C
   uncompressed: 213/234, compressed: 34/33.4
   - GWT Quake C->S uncompressed: 51.6/22.6, compressed: 24.7/6.2;   S->C
   uncompressed: 225/139, compressed: 39/34.8

-- 
John A. Tamplin
Software Engineer (GWT), Google