Subject: [quicwg/base-drafts] PADDING Frame performance (#434)

From: Lucas Pardue <[email-masked]>
Date: Tue, 11 Apr 2017 13:31:37 -0700

#158 introduced a change to the PADDING fram making it a single octect long. @rjb1000 made the this comment on that change, which I think is still a valid concern:

> With this new approach, it will no longer be safe to do that: the parser must keep parsing 1-byte PADDING frames until it finds a different type of frame, or reaches the end of the packet.
> 
> If the PADDING frame included a length, it would be possible to advance a pointer to the start of the next frame in a single parser action. Without a length field, the parser must work through the PADDING frames one by one.

Is the concern unjust?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434

---

From: ianswett <[email-masked]>
Date: Tue, 11 Apr 2017 13:56:53 -0700

The cost of skipping continuous padding is larger than doing nothing, but it's extremely small, particularly since the data is accessed sequentially, which is great or CPU caches and the packet was just decrypted, so it should already be in some layer of CPU cache.

I'd estimate that this adds <5% in the worst case(an entire packet of padding) on top of decryption and receiving the packet from the NIC, and it's probably less.  

A PADDING frame with a length makes it necessary to have two padding frames, one that's one byte and one(or two) that has a length, since if you have a length, it'd be impossible to have a one byte padding frame.

So yes, I think it's premature optimization to worry about it, since even with a single byte padding frame, I believe padding frames are the cheapest frame type to process per byte.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293397462

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 11 Apr 2017 14:50:05 -0700

> I'd estimate that this adds <5% in the worst case(an entire packet of padding) on top of decryption and receiving the packet from the NIC, and it's probably less.

Hmm yeah I hadn't thought about it this way. Since a simple implementation might just loop thorugh the buffer and no-op when the frame type is PADDING there's not much to do (compared with some conditional related to reading some length etc). With branch prediction this should turn out quite well, even more so for your worst case? (Perhaps the worst case in that respect is a more varied packet contents). 

There's a simple way for me to test this out and stop speculating...

> A PADDING frame with a length makes it necessary to have two padding frames, one that's one byte and one(or two) that has a length, since if you have a length, it'd be impossible to have a one byte…

Great point. Simplicity makes a strong argument for me.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293410875

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 13 Apr 2017 07:39:09 -0700

Well, I knocked up some code to test the different approaches for parsing packets containing a mix of padding and one other frame. The code is at https://gist.github.com/LPardue/64b555ecc70b7abe85fc96bb37f2f4f8

* Approach A: 1 Byte PADDING frame
* Approach B: N Byte PADDING frame where the first 3 bytes describe frame type and padding length.

The results were not what I was expecting. For a packet of 65000 bytes, (across 1000 iterations) the tests showed:

* A: Mean read time: 284135.9 ns, Median read time: 121362 ns.
* B: Mean read time: 33.29 ns, Media read time: 29 ns

The difference is several orders of magnitude. I'm suspected the code is buggy. If its not, some fuzz testing implies that A scales linearly with padding length, while B is fairly independent of padding length.

These number are small in the broad scheme of things, so I'm not suggesting this is a strong reason to reconsider.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293914562

---

From: MikkelFJ <[email-masked]>
Date: Thu, 13 Apr 2017 08:18:07 -0700

If you can read 65K in 29ns, the optimizer is playing you a trick. See conclusions far down in this blog for insights. https://medium.com/@icex33/10-thousand-times-faster-swift-737b1accd973

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293926020

---

From: MikkelFJ <[email-masked]>
Date: Thu, 13 Apr 2017 08:21:42 -0700

Unless you only have one frame with 65K padding  that can be immediately skipped of course. Then it is no surprise.

On padding performance - Ian is right that in the typical case for the intended use, single byte padding will be very fast, faster than skipping based on a length field, likely. However, for abusive purposes where MTU is large, and also for the forced large initial handshake packet, the overhead may be noticable.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293927060

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 13 Apr 2017 08:35:13 -0700

> If you can read 65K in 29ns, the optimizer is playing you a trick. See conclusions far down in this blog for insights. https://medium.com/@icex33/10-thousand-times-faster-swift-737b1accd973

Whoops slipped my mind. Fiddling with GCC optimiser flags definitely improves things for the A case but like you say that might not be reflective of real-world processing. With optimisation, small amounts of 1 byte padding performs more competitively the length-based variant.

I'm all for simplicity. However, perhaps there is a case for both "pad 1 byte" AND "pad to end of frame"? The later could be represented as a new frame type, or perhaps a single padding frame type that does bit masking akin to ACK/STREAM frames. (Of course, that means that 0x00 is no longer usable for such a purpose).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293931097

---

From: Lars Eggert <[email-masked]>
Date: Thu, 13 Apr 2017 08:42:10 -0700

We can always add the new frame type later, if skipping zeros is reported to be problematic.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293933093

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 13 Apr 2017 08:58:01 -0700

SGTM. 

I feel @rjb1000 initial question has been answered, and there is no required action so I'm closing the ticket

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293937624

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 13 Apr 2017 08:58:01 -0700

Closed #434.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#event-1042153331

---

From: MikkelFJ <[email-masked]>
Date: Thu, 13 Apr 2017 09:04:19 -0700

Speaking of padding - one annoying feature about the STREAM frame is that if payload fits up to N - 1 MTU, you need to introduce the datalen length field, but then it won't fit into MTU and you have to add a single byte padding. The padding is not the issue, but it adds complicated special cases that can lead to bugs. In my proposal on TRIM frames, I consider the case where datalen is always required to repurpose the header bit, but it would also simplify this special case, because either the data fits, or it wont.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/434#issuecomment-293940147