Re: [hybi] frame length encoding

["Shelby Moore" <[e-mail]>]

Exactly processing the header is a stateful and ordered process.

Thus, the time that the CPU spends processing the header, is time that the
network might be idled. The bottleneck is processing the header and then
shunting the frame processing to the other cores. So as the frames get
smaller, the header is larger % of network bandwidth. If the CPU needs
more time processing the header than it takes to move the header over the
network, then at the asymptote of 0 size payload, then network bandwith is
more than 50% wasted.  I nearly certain that as Pieter's point.

Thus eliminating the comparisons is crucial for very small packets.

So it is likely that massively multi-core implementations will choose to
set the maximum size to 125 if you go with Option 2, or 126 with Option 1,
because that is where their economy is maximized.

That is why I proposed you go with Option 1/15-bit, so they can set the
maximum size to 32767 instead.

The comparisons can be eliminated if you set maximum at handshake and
expect the sender to honor it.  You can have a separate version of your
code for that hardcoded maximum.  Even self-writing code if necessary.

Do you finally get my point?


> On Sun, Aug 22, 2010 at 5:32 PM, Shelby Moore <[e-mail]> wrote:
>
>> Network bandwidth is increasing faster than single-core speeds are.
>> Multi-cores are being used to keep up with Moore's Law.
>>
>
> I disagreed with that point as did others, but it is irrelevant to the
> discussion at hand.  He brought that point up in the discussion about
> compressing frames to get the benefit of a small frame.
>
>
>> But the problem is that stateful (Turing complete) algorithms don't
>> scale
>> well to multi-core.  Stateless (lambda pure) algorithms do scale well to
>> multi-core. Maybe you are aware that pure Haskell can scale by compiler
>> to
>> any number of multi-core, whereas stateful languages are brittle mashups
>> of mutex and semaphore heuristics (not mathematically proveable).
>>
>
> Yes, I am aware.  You aren't going to be parallelizing decoding this frame
> anyway.  You can't start processing the payload until you have understood
> the opcode (which indirectly gets you the start of the payload data), the
> CMLP flag, and parsed the length (which gets you the end of the payload
> data).  Even if the length is a fixed 8-byte field, there is still an
> ordering requirement.
>
> The problem with stateful code is that there is always point where adding
>> more cores actually starts to reduce the speed (because of the
>> non-mathematical fit of the algorithm and the communication/coordination
>> overhead between cores growing faster than the speed added by the
>> additional cores).  Basically you end up in mutex/semaphore deadlock
>> hell
>> of inefficiency.
>>
>> If I am not mistaken, the comparisons in the size header field logic,
>> create a state-machine that has to be communicated/coordinated with the
>> multiple cores.  The comparisons change the algorithm from stateless to
>> stateful.  Without the comparisons (and other opcodes and state changes
>> to
>> be added), more cores can be used before the inefficiency overwhelms.
>>
>
> You aren't going to have mutliple cores trying to decode a single frame
> anyway -- the synchronization overhead will be far more than the cost to
> process even the most complex framing we have discussed here.  You might
> try
> and farm off (de)compression to another core, but again that is different
> than trying to decide how many bytes there are in the frame.
>
> Note that Pieter initially voted for Option #1, then introduced Option #0
> which was the same but assigned a reserved bit to the length field.  It
> still had a comparison for the length, so I don't think you are accurately
> representing his opinion.
>
>
>> And also I just think the 15-bits versus 7-bits as the maximum size that
>> can go through without comparisons is safer.  We can not see every
>> possible issue from this WG.  We don't lose much at all, maybe 2 - 5% in
>> network bandwidth, but we gain a lot of comfort zone against the
>> unexpected.
>>
>
> Please explain how it can go through without comparison.  Even if you
> allocate a bit to define which length to use, you still have to test that
> bit.  If you negotiate in the handshake a maximum, you have to test some
> flag you set during negotiation.
>
> --
> John A. Tamplin
> Software Engineer (GWT), Google
>