Subject: Re: [hybi] Length encoding performance

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

Roberto Peon wrote:
> 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

Roberto and Eric, I refer back to my prior post which summarized my
understanding of the risk relative to CPU load:

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

The points were in essence:

a) any CPU load on reading header is a loss (unless NIC -> DMA buffering
synchronously?)

b) the CPU on the frame header could be the bottle-neck in multi-core in
some scenarios (especially if LAN! network bandwidth increases faster than
single-code speed).

* I will a new point related to #b, that predictive pipeling that gives
modern CPUs much of their speed (effectively multi-core within same core)
is effectively disabled by the communication between cores (because you
can't shunt the incoming frame to another core stocashtically, only
deterministically, because sending a process signal is not a reversible
operation)

>> Eric Rescorla wrote:
>>> 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.
>>
>>
>> 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.

Eric Rescorla wrote:
> 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.

The point I made at least 8 times on this list is that if you set the
maximum size, then you do not need to do that comparison.

And with the 15/63 option, that allows to set the maximum at 32767, and
simply load a fixed short and read the bytes without any bit twiddling.

I appreciate you running benchmarks.  Could you re-run the corrected one?

below...

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

See my point near top about multi-core bottleneck being the CPU on the
frame header.

I am arguing it pays to be safe and minimize the CPU load, especially when
it doesn't cost us anything (except for the edge case where every packet
is less than 126, but actually that increases CPU load per frame header!).

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

Do any of you build multi-core intermediaries?

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Aug 2010 11:27:17 -0700

> See my point near top about multi-core bottleneck being the CPU on the

The CPU cost for doing IO swamps that for doing framing.

> is less than 126, but actually that increases CPU load per frame header!).

I'm just telling you that calling read() again costs more CPU than any of
the framing proposals.
If you're concerned about CPU, then you should go after the place where most
of the scaling problems lie, and that is IO related.

> Do any of you build multi-core intermediaries?

Yes. For years now.
-=R

> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 14:40:16 -0400

>> a) any CPU load on reading header is a loss (unless NIC -> DMA buffering

The CPU load is additive in between read()s.

Also your point does not address ASICs and custom hardware situations
where perhaps the read has much lower cost.

> of the scaling problems lie, and that is IO related.

I assume that is what custom routers and proxies and stuff do already.

And frame header CPU optimization is part of that.

>> Do any of you build multi-core intermediaries?

You design custom ASICs??  You build multi-core from ground up with
engineering of every component used??

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Aug 2010 11:45:51 -0700

> where perhaps the read has much lower cost.

No, it doesn't, but I'd expect that buffer management, IO, etc. would still
dwarf the cost decoding the framing.

> And frame header CPU optimization is part of that.

It is a part of it. It is probably like the 1% part. I'd be more concerned
about the 99% part.

> engineering of every component used??

No. Why would I want to do that when I can do it cheaper using "commodity"
hardware?
You can spend time arguing endlessly and religiously with people about
things, but it is better to spend your energy on the 1% after you've
considered the 99% part! It is far more constructive for the final
end-result.

-=R

---

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

>> some scenarios (especially if LAN! network bandwidth increases faster

The point is it doesn't matter if those other things dwarf in nominal
time, the bottleneck can set an upper limit on the # of cores that can be
used effectively, which limits the throughput regardless of whether those
things dwarf CPU load cost.

It shows me that you don't have experience in designing highly parallel
custom hardware.  So I am sorry, I can not respect your opinion on this
one.

>> > If you're concerned about CPU, then you should go after the place
>> where
>> > most

That illustrates to me at least, that you are not experienced in the
specific use case that I am pointing out in this post.

> No.

I knew that, I just wanted you to admit it.

I have known for a while what sort of systems you are building.

> Why would I want to do that when I can do it cheaper using "commodity"
> hardware?

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Aug 2010 13:17:06 -0700

> custom hardware.  So I am sorry, I can not respect your opinion on this

Well, personal attacks attacks and vitriol aside, all that matters are the
results. Your use case will/can only occur when the transaction rate on
*single connections* increases faster than the CPUs scale. You should
otherwise be able to balance on the IP:port of the sender (i.e connection)
in hardware in a fully parallel fashion.

Your theoretical argument seems unlikely to be the real bottleneck-- I don't
see single connections sending frames so quickly as a likely scenario. This
is an opinion and not fact-- none of us can predict the future and we can't
even observe the present especially well.

> specific use case that I am pointing out in this post.

Out of curiosity, why do you think that will be the dominant use case?

> I have known for a while what sort of systems you are building.

Thats impressive! :)

-=R