Mime sniffer: reduce table from 256 bytes to 4

Mime sniffer: reduce table from 256 bytes to 4

The lookup table for sniffing text/plain messages for binary characters
was 256 bytes in size. The information it encoded could be stored in 32
bits.

Use a 32-bit lookup table instead of the 256-byte lookup table. This
reduces binary size.

This change is mostly performance neutral; micro-benchmarks show
no statistically significant change on Android. Micro-benchmarks on
high-performance Intel processors show an additional cost of around
400ns, apparently due to branch mis-prediction.

However, real-world performance is likely to be dominated by the time taken to
load the table into CPU cache, which the new implementation should win
easily.

Also add a micro-benchmark test.

BUG=
TEST=net_unittests

Committed: https://crrev.com/10eb9f5e836087e3c0324043221d217af56d30e2
Cr-Commit-Position: refs/heads/master@{#330577}

[PhistucK, 2015-04-27 14:27:14]

phistuck@gmail.com changed reviewers:
+ phistuck@gmail.com

[Adam Rice, 2015-04-28 02:43:07]

ricea@chromium.org changed reviewers:
+ asanka@chromium.org

[Adam Rice, 2015-04-28 02:43:08]

+asanka The perftests aren't really necessary. I will remove them if you prefer.

See also
https://groups.google.com/a/chromium.org/forum/#!topic/net-dev/ISNDu6Wh_Ug for
discussion of whether this CL is fun or not.

[asanka, 2015-04-29 23:17:44]

Since you've done some microbenchmarking, have you compared this patchset with
just adding the 'byte < 0x20' condition to the existing code?

As Ryan pointed out elsewhere, we aren't too worried about the space taken up by
the 256 bytes used by the map. A mapping from bytevalue => property is pretty
easy to understand. So I'm trying to make sure that this change doesn't make the
sniffing logic opaque to our readers.

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer.cc
File net/base/mime_sniffer.cc (right):

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer.c...
net/base/mime_sniffer.cc:660: static const uint32 kBinaryBits = 0xf7ffc9ff;
Let's try to make this a bit more readable.

kByteLooksBinary and kBinaryBits are both trying to represent a map for
binary-data-bytes (https://mimesniff.spec.whatwg.org/#binary-data-byte). I
suggest tossing in a reference to the spec.

Someone glossing over the code is unlikely to count the bits to know what this
bitmap contains. In effect, this makes the binary sniffing logic quite opaque.

One option is to make it explicit what characters we are excluding, since there
are only 5 values. E.g.:

  static const uint32 kBinaryBits =
      ~(1 << '\t' | 1 << '\n' | 1 << '\r' | 1 << '\f' | 1 << '\x1b');

... which I think should evaluate to the same value as you have here.

Or some other creative way of listing out the contents so that a reader can
easily understand what's going on here.

Also, let's move this next to the definition of ContainsControlCodes() below.
That way it'll be clear how the bitmap is used.

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer.c...
net/base/mime_sniffer.cc:956: bool ContainsControlCodes(const char* content,
size_t size) {
Strictly speaking, this is a much fuzzier predicate than its name suggests.
Perhaps call it something like 'LooksLikeBinary'.

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer_p...
File net/base/mime_sniffer_perftest.cc (right):

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer_p...
net/base/mime_sniffer_perftest.cc:15: TEST(MimeSnifferTest, FastPathPerfTest) {
Not very keen on this type of perftest that measures a very focused bit of code
that's not performance critical.

It might be interesting to have one that measures how efficient our overall MIME
sniffing logic is since it's doing a bunch of pattern matches. If anything there
takes too long I'd like to know, but I don't think the
does-this-look-like-binary logic is a big factor.

[Adam Rice, 2015-05-07 16:52:50]

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer.cc
File net/base/mime_sniffer.cc (right):

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer.c...
net/base/mime_sniffer.cc:660: static const uint32 kBinaryBits = 0xf7ffc9ff;
On 2015/04/29 23:17:44, asanka wrote:
> Let's try to make this a bit more readable.
> 
> kByteLooksBinary and kBinaryBits are both trying to represent a map for
> binary-data-bytes (https://mimesniff.spec.whatwg.org/#binary-data-byte). I
> suggest tossing in a reference to the spec.
> 
> Someone glossing over the code is unlikely to count the bits to know what this
> bitmap contains. In effect, this makes the binary sniffing logic quite opaque.
> 
> One option is to make it explicit what characters we are excluding, since
there
> are only 5 values. E.g.:
> 
>   static const uint32 kBinaryBits =
>       ~(1 << '\t' | 1 << '\n' | 1 << '\r' | 1 << '\f' | 1 << '\x1b');
> 
> ... which I think should evaluate to the same value as you have here.
> 
> Or some other creative way of listing out the contents so that a reader can
> easily understand what's going on here.
> 
> Also, let's move this next to the definition of ContainsControlCodes() below.
> That way it'll be clear how the bitmap is used.

Done.

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer.c...
net/base/mime_sniffer.cc:956: bool ContainsControlCodes(const char* content,
size_t size) {
On 2015/04/29 23:17:44, asanka wrote:
> Strictly speaking, this is a much fuzzier predicate than its name suggests.
> Perhaps call it something like 'LooksLikeBinary'.

Done.

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer_p...
File net/base/mime_sniffer_perftest.cc (right):

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer_p...
net/base/mime_sniffer_perftest.cc:15: TEST(MimeSnifferTest, FastPathPerfTest) {
On 2015/04/29 23:17:44, asanka wrote:
> Not very keen on this type of perftest that measures a very focused bit of
code
> that's not performance critical.
> 
> It might be interesting to have one that measures how efficient our overall
MIME
> sniffing logic is since it's doing a bunch of pattern matches. If anything
there
> takes too long I'd like to know, but I don't think the
> does-this-look-like-binary logic is a big factor.

I don't expect micro-benchmarks to be representative of real-world performance.
I just added them as a sanity check that I wasn't introducing a major
performance regression.

I have replaced the two very synthetic benchmarks with a slightly more realistic
"PlainTextPerfTest". This exposes something that was not apparent from the
previous benchmarks: the Xeon CPU branch predictor really hates the <0x20
branch. Although SlowPathPerfTest was supposed to account for this, it seems it
was not unpredictable enough.

I got the tests to run on Android by hacking net.gypi to add the file to the
net_unittests target (net_perftests lacks the magic needed to build and run on
Android) and ran the tests on my 2013 Nexus 7.

Results:

Xeon Workstation:

New implementation: 1125ns
Old implementation: 670ns
Old implementation with <0x20 check: 1158ns


Nexus 7:

New implementation: 3437ns
Old implementation: 3442ns
Old implementation with <0x20 check: 3479ns


All the Android results are within the margin of error of each other.

What I plan to do next is add benchmarks for the two hottest paths through this
code, which based on histogram data appear to be

1. Mime type is not considered sniffable, and
2. Mime type is "" and is sniffed as JPEG.

[asanka, 2015-05-12 19:20:41]

lgtm. Thanks for doing this!

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer_p...
File net/base/mime_sniffer_perftest.cc (right):

https://codereview.chromium.org/1058003005/diff/40001/net/base/mime_sniffer_p...
net/base/mime_sniffer_perftest.cc:15: TEST(MimeSnifferTest, FastPathPerfTest) {
On 2015/05/07 at 16:52:50, Adam Rice wrote:
> On 2015/04/29 23:17:44, asanka wrote:
> > Not very keen on this type of perftest that measures a very focused bit of
code
> > that's not performance critical.
> > 
> > It might be interesting to have one that measures how efficient our overall
MIME
> > sniffing logic is since it's doing a bunch of pattern matches. If anything
there
> > takes too long I'd like to know, but I don't think the
> > does-this-look-like-binary logic is a big factor.
> 
> I don't expect micro-benchmarks to be representative of real-world
performance. I just added them as a sanity check that I wasn't introducing a
major performance regression.
> 
> I have replaced the two very synthetic benchmarks with a slightly more
realistic "PlainTextPerfTest". This exposes something that was not apparent from
the previous benchmarks: the Xeon CPU branch predictor really hates the <0x20
branch. Although SlowPathPerfTest was supposed to account for this, it seems it
was not unpredictable enough.
> 
> I got the tests to run on Android by hacking net.gypi to add the file to the
net_unittests target (net_perftests lacks the magic needed to build and run on
Android) and ran the tests on my 2013 Nexus 7.
> 
> Results:
> 
> Xeon Workstation:
> 
> New implementation: 1125ns
> Old implementation: 670ns
> Old implementation with <0x20 check: 1158ns
> 
> 
> Nexus 7:
> 
> New implementation: 3437ns
> Old implementation: 3442ns
> Old implementation with <0x20 check: 3479ns
> 
> 
> All the Android results are within the margin of error of each other.
> 
> What I plan to do next is add benchmarks for the two hottest paths through
this code, which based on histogram data appear to be
> 
> 1. Mime type is not considered sniffable, and
> 2. Mime type is "" and is sniffed as JPEG.

Interesting. Thanks for running the tests. I also didn't expect the <0x20 branch
to be this expensive.

https://codereview.chromium.org/1058003005/diff/100001/net/base/mime_sniffer_...
File net/base/mime_sniffer_perftest.cc (right):

https://codereview.chromium.org/1058003005/diff/100001/net/base/mime_sniffer_...
net/base/mime_sniffer_perftest.cc:87: plaintext.reserve(kTargetSize +
plaintext.size() % kTargetSize);
ISTM this should be:

plaintext.reserve(plaintext.size() * (1 << base::bits::Log2Ceiling(kTargetSize /
plaintext.size())));

[Adam Rice, 2015-05-18 01:02:57]

https://codereview.chromium.org/1058003005/diff/100001/net/base/mime_sniffer_...
File net/base/mime_sniffer_perftest.cc (right):

https://codereview.chromium.org/1058003005/diff/100001/net/base/mime_sniffer_...
net/base/mime_sniffer_perftest.cc:87: plaintext.reserve(kTargetSize +
plaintext.size() % kTargetSize);
On 2015/05/12 19:20:41, asanka wrote:
> ISTM this should be:
> 
> plaintext.reserve(plaintext.size() * (1 << base::bits::Log2Ceiling(kTargetSize
/
> plaintext.size())));

Good catch! Thanks.

[Adam Rice, 2015-05-18 01:03:03]

The CQ bit was checked by ricea@chromium.org

[Adam Rice, 2015-05-18 01:03:03]

The patchset sent to the CQ was uploaded after l-g-t-m from asanka@chromium.org
Link to the patchset: https://codereview.chromium.org/1058003005/#ps120001
(title: "Fix calculation of the string reserve size.")

[commit-bot: I haz the power, 2015-05-18 01:03:13]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1058003005/120001

[commit-bot: I haz the power, 2015-05-18 02:05:21]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-05-18 02:05:22]

Try jobs failed on following builders:
  win_chromium_x64_rel_ng on tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_x64_...)

[Adam Rice, 2015-05-18 20:17:32]

The CQ bit was checked by ricea@chromium.org

[Adam Rice, 2015-05-18 20:17:32]

The patchset sent to the CQ was uploaded after l-g-t-m from asanka@chromium.org
Link to the patchset: https://codereview.chromium.org/1058003005/#ps140001
(title: "Compile fix for MSVC 64-bit")

[commit-bot: I haz the power, 2015-05-18 20:24:08]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1058003005/140001

[Adam Rice, 2015-05-18 20:53:52]

The CQ bit was unchecked by ricea@chromium.org

[Adam Rice, 2015-05-19 18:44:20]

The CQ bit was checked by ricea@chromium.org

[commit-bot: I haz the power, 2015-05-19 18:44:44]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1058003005/140001

[commit-bot: I haz the power, 2015-05-19 18:52:04]

Committed patchset #8 (id:140001)

[commit-bot: I haz the power, 2015-05-19 18:53:59]

Patchset 8 (id:??) landed as
https://crrev.com/10eb9f5e836087e3c0324043221d217af56d30e2
Cr-Commit-Position: refs/heads/master@{#330577}