Subject: [hybi] Length encoding performance

From: Eric Rescorla <[email-masked]>
Date: Tue, 24 Aug 2010 09:31:14 -0700

This message is intended to address only one part of the seemingly endless
framing debate, the question of CPU load.

I can no longer keep track of the endless number of permutations which
seem to have been bandied about here, so let's just consider two stylized
approaches:

1. A fixed-width 64-bit field.
2. A variable length 64-bit max field using the high bit as a
   "more" bit.

Here's some reasonable but not tightly coded C code for each of these.
I only spent about an hour on this so there could well be bugs, but I
did do some checking.

Fixed-width:
unsigned long long fixed(unsigned char *buf, int len)
  {
    unsigned long long in = *((unsigned long long *)buf);
    unsigned long long out;

    out = ((unsigned long long)(ntohl((unsigned long)(in & 0xffffffff))) <<
32)
      | ntohl((unsigned long)((in >> 32) & 0xffffffff));

    sum+=out;

    return out;
  }

Variable-width:
unsigned long long variable(unsigned char *buf, int len)
  {
    unsigned long long out=0;

    do {
      out << 7;
      out |= (*buf) & 0x7f;
    } while(len-- && (*(buf++) & 0x80));

    sum+=out;

    return out;
  }

Note that you could argue that the variable decoder isn't totally optimal
b/c
you might not get the entire length in one field, but that can happen for
the
fixed decoder too, so I'm ignoring that for now.

Let's run these in a tight loop. I use 100,000,000 iterations of an unrolled
loop with each iteration running 25 length decodes. On a Mac Pro (2.26 GHz
Xeon),
I get the following timing numbers to two significant figures:

                       Time(s)        Ops/second
  Fixed:                   9.4         270000000
  Variable (1 byte):       9.4         270000000
  Variable (2 bytes):       13         190000000
  Variable (8 bytes):       31          80000000

In other words, for short packets the performance of fixed and variable
encoding
is comparable and for long packets (which we expect to see a lot less of
and
will have more of other types of overhead), we start to see a performance
penalty.
However, even in the worst case, for 8-byte lengths, we can do 80 million+
length
decodes per second. It seems unlikely that this is going to be the
bottleneck
in any real implementation.

In support of this argument, consider that once you've decoded the length
you
need to move the data into JavaScript. In most implementations, this means
allocating a buffer and doing some kind of memcpy. If we use a pool memory
implementation and do the memcpy right off the wire, we have code like this:

    mb = STAILQ_FIRST(&bufs);
    if(!mb) abort();     // would be a malloc in a real implementation
    STAILQ_REMOVE_HEAD(&bufs, entry);
    memcpy(mb->buf, dummy, 64)

Plus a release somewhere else.

Just this additional code slows the system down substantially, but of course
it's still ridiculously fast.

                       Time(s)        Ops/second
  Fixed:                  22           110000000
  Variable (1 byte):      21           110000000
  Variable (8 bytes):     41            60000000

And in a real system you would need to jump out of the C code and into the
JS interpreter, etc. I find it very hard to believe that in such an
environment
the cost of decoding the length will be anywhere near the dominant cost.
Thus, Amdahl's law suggests it's not worth optimizing on this point. I
believe
this conclusion extends to other proposed length encodings.

This isn't to say that there aren't other arguments for or against various
length encoding schemes, but I don't think that performance is a relevant
consideration.

-Ekr

---

From: gustav <[email-masked]>
Date: Tue, 24 Aug 2010 18:55:49 +0200

On 24 August 2010 18:31, Eric Rescorla <[email-masked]> wrote:

> Its really not of interest how jscript or any other language performs
today, the websocket standard is to last for a long time,
and should of course not be designed around how one particular language
happens to perform today.
Especially not jscript that is evolving extremely fast regarding both its
functionality and performance.

---

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

> 2. A variable length 64-bit max field using the high bit as a

If you want to make conclusions below about small frames, then you should
be using a fixed width 8-bit field, which then will make the fixed width
case much faster.

below...

> need to move the data into JavaScript.

In my case, I am thinking about intermediaries, when I think about
performance bottleneck economics wrt to this CPU load issue:

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

Especially since it was Pieter (look at his website) who first caused me
to think about it.

> In most implementations, this means
> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Aug 2010 10:44:46 -0700

Intermediaries are, roughly, my life.
I'm not worried about the decode speed. The number of read()s, buffer
management, amount of memory in use at one time, number of write()s all
matter far far more than decode speed for anything this simple.
The cost of IO dwarfs most of the rest of everything.

-=R

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 24 Aug 2010 10:45:12 -0700

> be using a fixed width 8-bit field, which then will make the fixed width

I don't believe that's correct. Since we need to support >255 byte frames there needs to be a check not just a fixed 8 bit length. Thus performance will be roughly comparable to variable 8.

> Especially since it was Pieter (look at his website) who first caused me

It's not clear to me what you think the function of intermediaries is but if it's anything more than reframing (which seems pointless) then the cost of that is likely to dominate. 

At a higher level if you want to argue that this kind of microoptimization is important I think you need to present a more compelling use case than you have so far.

Ekr