Subject: Re: [hybi] 8/16/32/64-bit is not optimal?

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 09:01:27 -0400

> On Mon, Aug 23, 2010 at 11:52 PM, Shelby Moore <[email-masked]>
> wrote:
>
>> Since we no longer need the CML bit, then we have 4 reserved bits now in
>> those two choices.
>>
>
> It isn't clear that is agreed,

If this WG is so negligent to conflate the transport and the application
data layer, I will not only strongly protest WebSockets every chance I get
to speak to a large audience (and point them here to read who was
derelict), I will also be well beyond extremely motivated to replace it in
the market with a non-conflated design:

http://www.ietf.org/mail-archive/web/hybi/current/msg03583.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03567.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03551.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03552.html

I assume this WG won't commit such an egregious error.

I hope that is crystal clear.

Btw:

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

> The JS API, in its current form, eliminates many of those options.
> It was also representatives of browser makers who were arguing against
> fragmentation because of receiver buffer management issues, and adding
> CML removed those objections.

Just because you allege that some browser programmers may not want to
(re-)write correct code, is not a valid justification to conflate the
transport and application data layers. If necessary, let them write
transistion code that reallocs and copies to make data contiguious to
interface to that alleged incorrect browser code. In time, the browser
programmers will get tired of the inefficiency and fix their code. Don't
break the WebSockets irrevocably for the universe, just to pander to bad
programming of a few.

> but regardless does not differentiate
> between
> the two.

Incorrect logic.

You had expressed concern that there was only 3 reserved bits in the
7/16/63 option. If 4 reserved bits is the threshold for any WG
participant's decision to chose 8/16/32/64, then indeed it would be the
critical differentiation for that person.

> Note that I prefer the 7/16/63 -- what follows are the pros for
> 8/16/32/64,
> and why I would not object to it.
>
>
>> The 8/16/32/64-bit choice is inferior in almost every way to
>> 7/16/63-bit.
>> If you need the extra reseerved bits, then add a byte to 7/16/63-bit for
>> reserved bits, then the header will be same size.
>
>
> Except if the payload is more than 125 bytes,

Then why have you and Dave Crigland waged a jihad against considering any
use case of 126+?

http://www.ietf.org/mail-archive/web/hybi/current/msg03600.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03598.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03615.html

> in which case 7/16/63 uses
> at
> least one extra byte (2 if you add a reserved byte).

Incorrect.

You mean for the 126 - 255 case only.

BYTES  RANGE        OPTION      RESERVED BITS (including 'More')
----------------------------------------------------------------
2      0-125        7/16/63     4
4      126-65535    7/16/63     4
3      0-255        8/16/32/64  9
4      256-65535    8/16/32/64  9
3      0-32766      15/63       4

And that is why I said that 15/63 is optimal, unless the overriding
concern is more reserved bits!  Which is precisely why the extra reserved
bit from the CMLP is important.  It adds 33% more reserved bits!

>  Also, 8/16/32/64
> supports a 32-bit length option, which eliminates objections that some had
> to the 7/16/63 option.

Could you please point us to the discussion (logic) on need for 32-bit
size field?

>> 7/16/63-bit always has lower CPU overhead.
>
>
> I'm not sure that follows -- with a typical implementation, you replace
> two
> compares/branches (and likely another branch depending on how the compiler
> lays out the code) with a single computed jump (probably via table lookup)

So now you mention the table lookup, when before you were arguing it had
to be a while() loop.  So that is new information.  You subtly inserted
that epipheny you had.

Let me actually spend some time writing the optimized code for each option
and then I will come back to this point.

> so it is probably about the same and will vary depending on the
> architecture.  Regardless, I think you are getting hung up on fractions of
> a
> nanosecond.  For the cases where such timings are important, it is likely
> to
> be implemented in an ASIC or custom silicon anyway.

You continue to ignore that it is not the nominal difference in
nanoseconds that may matter, but rather the ratio between the CPU loads:

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

>> The only advantages I see for 8/16/32/64-bit is it
>> could support 128-bit and 256-bit easily.
>>
>
> Irrelevant, as we have no need for lengths that long, and I don't see any
> difference in the ease of extending either if we did need them.

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

There has been at least one person besides me say that we should "think of
the children" and design as if the protocol could live decades.

---

From: John Tamplin <[email-masked]>
Date: Tue, 24 Aug 2010 11:15:45 -0400

Note -- if the level of vitriol in your recent messages continues to
increase, I will simply not respond to you any further.

> the market with a non-conflated design:

Again, this is not application layer information.  The WebSockets layer
deals with transporting messages between endpoints.  The size of a message
is clearly a part of that layer, even if the message is fragmented.  It
isn't applciation layer intermediaries which might fragment the message,
thus losing the total message length of a single-frame message if it isn't
added back.  You may argue that there is insufficient need for this value to
justify the cost and there is room for debate on that, but applying your new
favorite "conflating" word to it is simply incorrect.

Feel free to protest whatever you like to whoever you like -- just don't
keep repeating the same thing over and over here.  We read it the first 5
times.

> break the WebSockets irrevocably for the universe, just to pander to bad

You may disagree with the rationale, but that is the rationale that was
agreed upon in the WHATWG group.  AFAIK, the JS API is still being developed
there and the discussions here are about the wire protocol.  Feel free to
try and convince the WHATWG to support a streaming API for JS users.

Until that point, the vast majority of clients will be receiving messages as
a single block.  Clearly, there are things in the protocol which are not
useful for such clients -- it is hard to imagine even 10 years from now
allocating a 2^63-1 byte string and passing it to JS code.

> Then why have you and Dave Crigland waged a jihad against considering any

As I said, I was pointing out the pros and cons of the two choices.  I do
believe such packets will be a small percentage of real world WebSocket
traffic, but that doesn't mean it doesn't save a byte on those frames.

3      0-32766      15/63       4
> concern is more reserved bits!

Or unless you believe frames under 126 bytes are going to comprise 98%+ of
the frames, in which case it uses on average about 0.96 bytes more.

> Could you please point us to the discussion (logic) on need for 32-bit

You can search the archives as well as I can.  From memory, a number of
people were unhappy with an 8-byte maximum frame length because they felt it
would never be practical, and that 16 bits wasn't enough either.  Adding
32-bits gives them an option of not having to send an 8-byte length
(personally I feel the wasted 4 bytes are totally insignificant which is why
the proposals I have created haven't included a 32-bit length step) for
virtually all messages envisioned today.

> to be a while() loop.  So that is new information.  You subtly inserted

I mentioned it first replying to your statement that you would use left
shift and read that number of bytes instead of a switch statement because
you thought it would save branches -
http://www.ietf.org/mail-archive/web/hybi/current/msg03580.html

I apologize - I assumed you knew what I meant by unrolling the loop and how
that would be implemented in C source rather than assembly.  Basically
rather than having a while loop which causes a branch for every byte of the
length, you put all the statements in a row and you jump into the middle of
this sequence of statements depending on the size.  That is usually
expressed in C/C++ as a switch statement, and depending on the architecture
and what the compiler thinks is the most optimal given everything it knows,
it may produce a table jump instruction or roll its own by an indirect jump
through a table.  If you are coding directly in assembly and the code to
handle each byte is identical, then you can usually just compute the address
of the instruction to jump to and then jump to it (and the compiler may be
able to do it as well, though it is less likely).  If the compiler chooses
to do multiple comparisons instead, it is because it is faster.

> the children" and design as if the protocol could live decades.

And millions of decades is how long it would take to send a 2^128 byte
message.  Even if we get yottabit network speeds (10^24, or 10^12 times what
is currently even being developed in research labs), a 2^128 byte message
would take 86 million years to transmit.  So, I don't think we have to worry
about that.

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

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 11:54:08 -0400

> increase, I will simply not respond to you any further.

It was a technical protest.  Those are allowed under the charter.

I wanted to make sure I wasn't accused again of being unclear.

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 12:22:04 -0400

> Again, this is not application layer information.

Wrong:

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

[snip]
> keep repeating the same thing over and over here.  We read it the first 5

You are causing me to repeat, because you keep replying with similar wrong
statements as you did above, and in the past:

You know well the principles of debate.  So don't try to use the "you are
replying too much".

> agreed upon in the WHATWG group.

They were wrong:

[snip]

> traffic, but that doesn't mean it doesn't save a byte on those frames.

So let me point out pros and cons too please.

>> BYTES  RANGE        OPTION      RESERVED BITS (including 'More')

If you can safely assume that, then yes.  I remind you that others on this
list do not want to make that assumption.  So how are you going to build
concensus?

Are you going to accept the fact that your statistics are inadequate
sample, or are you going to force it down our throat?

> virtually all messages envisioned today.

Thank you for re-summarizing their points.

Agreed, of course their logic does not make any sense.  How do we teach
them in order to reach concesus?

> that would be implemented in C source rather than assembly.

Yes you did.  I stand corrected.  I am very aware of unrolling loops, I
simply missed your statement.

[snip]
> would take 86 million years to transmit.  So, I don't think we have to

Again a failure of logic.

The threshold is at 64-bits, not at 128-bits.

So that is only 86 million / 2^64 = 1/214497024112 seconds or roughly less
than a nanosecond.

---

From: John Tamplin <[email-masked]>
Date: Tue, 24 Aug 2010 12:56:55 -0400

> You know well the principles of debate.  So don't try to use the "you are

There seems to be no point in further discussion on this, and repetition of
arguments will not change anything.

> They were wrong:

Then argue it there.

> Again a failure of logic.

See, it is statements like this which encourage people to be combative or to
ignore you.  You mentioned 128 and 256-bit lengths, and my computation was
showing the absurdity of a 256-bit length.  Yes, I could have clarified, but
you constantly make statements impugning the competence of the people you
are talking to.  As an example, it was especially amusing to see you explain
what an older standard was trying to accomplish to a person who was involved
in it, but that doesn't add credibility to your statements.

> So that is only 86 million / 2^64 = 1/214497024112 seconds or roughly less

You suggested a 256-bit length, for which the threshold is 2^128.  I agree,
a 128-bit length becomes feasible when we increase our network speeds by
about 10  orders of magnitude.  Your guess is as good as mine for the
likelihood of that happening during the WebSocket protocol's lifetime, but
my personal feeling is that 63-bit lengths are more than sufficient.  Given
the number of people suggesting that even a 63-bit length is absurd, I
suspect there would be substantial objection to supporting 128-bit lengths.

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 13:47:27 -0400

> Then argue it there.

I already did. I provided the link already in prior reply.  Any one can
reply on the CML thread if they can show I am wrong.

> ignore you.

I wasn't so aggressive in assigning blame for needing to reply, before
people started telling me (in private) I was replying too much.

And you used words like "absurd" several times against me, before I ever
used "illogical" in a reply to you.

If people can dish it out over and over again, I can eventually pick up a
mirror to show them.

Actually you have been fairly non-emotional, and other than a few "absurd"
words, you have been civil.

How about we both try to not use aggressive words?

>  You mentioned 128 and 256-bit lengths, and my computation was

I suggested a 128-bit also.

And I wasn't really arguing to do this.  I am actually arguing that
8/16/32/64 is not optimal (see title of this thread).  I was just trying
to be fair to the proponents of 8/16/32/64 about benefits of their choice
(even though I think 128-bit is borderline silly, and 256 is for sure
ridiculous).

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 13:57:00 -0400

> (even though I think 128-bit is borderline silly, and 256 is for sure

I forgot to make the point that the reserved bits are too rare (3 or 4) in
the other options (15/63 and 7/16/63), to even consider allocating one bit
to this.  So only 8/16/32/64 option with its 8 or 9 available reserved
bits could we even contemplate supporting the 128-bit size.  So it is a
very weak possible benefit for the 8/16/32/64 option.

John you are really good at summarizing things.  I wonder if someone could
summarize the tradeoffs for the 3 main option choices?

---

From: John Tamplin <[email-masked]>
Date: Tue, 24 Aug 2010 14:52:35 -0400

> summarize the tradeoffs for the 3 main option choices?

It isn't clear there are three main choices, and the relative merits of the
different proposals have been discussed many times.  On the Moderator poll
(with only 12 people participating), the only one with more positive votes
than negative votes is 7/16/63.  8/16/32/64, 8/63, and 8/16/16 all have only
one more negative vote than positive, while the rest have at least two more
negative votes than positive.  I think the only thing clear from the poll,
given the low participation, is that we can discard {1-9}*7 and 7/63 from
further consideration.

I think the WG chair or editor (not sure exactly how the process works)
should pick one and make a consensus call to see if we agree and can move on
to the next problem.  At this point, I suspect most people will agree to
anything reasonable to end this interminable discussion.

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 15:07:49 -0400

> anything reasonable to end this interminable discussion.

I thought I remember reading that in cases like this, they would want us
to keep trying until we reach rough concensus.

We are smart adults.  Certainly we can learn to respect knowledge and hash
it out.

The problem is getting past all the personal irrational bias.