Re: [hybi] voting on frame length ideas

[John Tamplin <[e-mail]>]

On Mon, Aug 23, 2010 at 12:34 PM, Shelby Moore <[e-mail]> wrote:

> > 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 think that depends on what you call througput.  If you mean frames/second,
then clearly it should always indicate a size of 1 so it can get the most
possible frames.  If you mean payload bytes/second, then I disagree --
having one 100k frame and doing an extra compare instruction is going to get
far more payload bytes through in the same time than processing 100k 1-byte
frames, even if it doesn't include a comparison.


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


There was no such assumption, see above.


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


Not checking it means a sender that ignored the maximum frame size could get
the receiver out of sync with framing boundaries.  Experience has shown many
attacks to follow from such problems.

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


Which you are taking out of context and extending it far beyond the
circumstances it was intended.  You also attributed that person to support
your proposal, which in fact they did not.  Regardless, it would be best to
speak your own opinions rather than restating someone elses.


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


Between these options, there is an extra byte for small frames regardless.


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

You are going to have branches anyway.  Your suggestion would be (inlining
the loop for clarity):

short header = readUnsignedShort();
long long len;
int lenlen = (header & LEN_LEN_MASK) >> LEN_LEN_SHIFT;
int lengthBytes = 1 << lenlen;
while (lengthBytes-- > 0) {
  lenlen = (lenlen << 8) | readByte();
}

Even if you unroll the loop and branch to different points in the reading
code, there is still a branch there:

It is really pretty basic -- if you have a variable number of bytes for the
length, there will be branches regardless.  If the number of branches are
small, you can optimize for the branch-not-taken case, which will have
minimal impact on the pipeline on most architectures in the 98% case.

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