Re: [hybi] voting on frame length ideas

["Shelby Moore" <[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.


In my experience will be always be able to converge, because never I have
I found that I have to compromise non-optimally on design.  It is always a
problem of not seeing the optimal design, before eventually finding the
optimal one that works well for everyone. If not, it means conflation has
been pushed into the layer being designed and one needs to take a broader
view and fix the conflation first.

The acrimony comes from clinging to conflation and not able to see that
can do the same thing just as efficiently without conflation.


>> 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;
> }


I do not think is it ludicrous for an implementation to choose the option
that gives it the highest throughput.

I do not expect an implementation to be coded with concern as to the load
on the senders CPU, when it conflicts with its own internal efficiency. 
Economics and game theory.


> 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.


The receiver's economics are orthogonal to the sender's economics in this
case.


>  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.


Please read what I originally wrote again.  I took that into consideration
and still the disaster result occured in my game theory.  Consider all the
variables in the game theory. If I was not clear/coherent/lucid, maybe you
can point that out.


> 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.


I already refuted that:

http://www.ietf.org/mail-archive/web/hybi/current/msg03517.html

If the receiver expects to be attacked, then checking the size field
guarantees nothing.


>> 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.


Incorrect.  See above.


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


Someone else in list said otherwise.  Any way, we lose nothing (negligible
2-4% loss) by getting rid of the conditional branches.  And we gain more
reserved bits and other advantages with the "Option 8/16/32/64-bit".

Are you arguing both sides of the fence in the post below?

http://www.ietf.org/mail-archive/web/hybi/current/msg03532.html

Is the extra byte costly or not?


>> 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;
> }


Yikes! Why?  Why not use the left shift, it is much more efficient than a
branch.  Branches destroy CPU pipelining.


[snip, because agreed]


>> 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.


Agreed, so I see no advantage to making maximum size not _STRICT_.


>> [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

Thank you. So I was roughly correct to use 50 before and estimate a
negligible 2% cost for adding a byte.  Even at 4%, that is still
negligible in overall scheme of things.