lineprotocol: optimize decoding

[rogpeppe]

We implement a few optimizations to make the decoder faster and allocate less:

• avoid allocating the escape buffer up front: this avoids and allocation when there's nothing to unescape
• use strings.IndexByte as a prequel to strings.Count in escaper.escapedLen and keep track of the earliest found replacement index.
• keep a bitwise or of the bytes that we've seen when taking a token, and invoke utf8.Valid only when there's a byte with the top bit set, saving a call to utf8.Valid in the common case at the expense of one pipelinable instruction.
• hardcode space as a field separator.

Benchmark results show some nice improvements:

name                                                           old time/op    new time/op     delta
DecodeEntriesSkipping/long-lines-8                               21.0ms ± 2%     21.9ms ± 1%    +4.64%  (p=0.008 n=5+5)
DecodeEntriesSkipping/long-lines-with-escapes-8                  25.0ms ± 3%     24.3ms ± 1%      ~     (p=0.151 n=5+5)
DecodeEntriesSkipping/single-short-line-8                         269ns ±10%      161ns ± 3%   -40.16%  (p=0.008 n=5+5)
DecodeEntriesSkipping/single-short-line-with-escapes-8            287ns ± 9%      165ns ± 5%   -42.59%  (p=0.008 n=5+5)
DecodeEntriesSkipping/many-short-lines-8                          157ms ± 7%      135ms ± 5%   -14.36%  (p=0.008 n=5+5)
DecodeEntriesSkipping/field-key-escape-not-escapable-8            257ns ± 5%      140ns ± 4%   -45.53%  (p=0.008 n=5+5)
DecodeEntriesSkipping/tag-value-triple-escape-space-8             334ns ± 2%      201ns ± 1%   -39.80%  (p=0.008 n=5+5)
DecodeEntriesSkipping/procstat-8                                 3.05µs ± 3%     2.51µs ± 1%   -17.53%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-8                        23.8ms ± 5%     25.3ms ± 9%      ~     (p=0.056 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-with-escapes-8           95.7ms ± 3%     95.1ms ± 2%      ~     (p=0.690 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-8                  331ns ± 7%      205ns ± 4%   -37.96%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-with-escapes-8     355ns ± 8%      258ns ± 1%   -27.13%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/many-short-lines-8                   222ms ± 1%      169ms ± 2%   -23.81%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/field-key-escape-not-escapable-8     350ns ± 3%      179ns ± 3%   -48.91%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/tag-value-triple-escape-space-8      451ns ± 1%      319ns ± 5%   -29.43%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/procstat-8                          5.57µs ± 2%     4.47µs ± 8%   -19.73%  (p=0.008 n=5+5)

name                                                           old speed      new speed       delta
DecodeEntriesSkipping/long-lines-8                             1.25GB/s ± 2%   1.19GB/s ± 1%    -4.45%  (p=0.008 n=5+5)
DecodeEntriesSkipping/long-lines-with-escapes-8                1.05GB/s ± 3%   1.08GB/s ± 1%      ~     (p=0.151 n=5+5)
DecodeEntriesSkipping/single-short-line-8                       108MB/s ±10%    180MB/s ± 3%   +66.52%  (p=0.008 n=5+5)
DecodeEntriesSkipping/single-short-line-with-escapes-8          112MB/s ± 8%    195MB/s ± 5%   +73.83%  (p=0.008 n=5+5)
DecodeEntriesSkipping/many-short-lines-8                        167MB/s ± 8%    195MB/s ± 5%   +16.64%  (p=0.008 n=5+5)
DecodeEntriesSkipping/field-key-escape-not-escapable-8          129MB/s ± 5%    236MB/s ± 4%   +83.60%  (p=0.008 n=5+5)
DecodeEntriesSkipping/tag-value-triple-escape-space-8           150MB/s ± 2%    249MB/s ± 1%   +66.06%  (p=0.008 n=5+5)
DecodeEntriesSkipping/procstat-8                                435MB/s ± 3%    528MB/s ± 1%   +21.21%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-8                      1.10GB/s ± 5%   1.04GB/s ± 8%      ~     (p=0.056 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-with-escapes-8          274MB/s ± 3%    276MB/s ± 2%      ~     (p=0.690 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-8               87.8MB/s ± 6%  141.5MB/s ± 4%   +61.09%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-with-escapes-8  90.4MB/s ± 7%  123.8MB/s ± 1%   +37.02%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/many-short-lines-8                 118MB/s ± 1%    155MB/s ± 2%   +31.26%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/field-key-escape-not-escapable-8  94.3MB/s ± 3%  184.6MB/s ± 3%   +95.76%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/tag-value-triple-escape-space-8    111MB/s ± 1%    157MB/s ± 5%   +41.77%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/procstat-8                         238MB/s ± 2%    298MB/s ± 8%   +24.82%  (p=0.008 n=5+5)

name                                                           old alloc/op   new alloc/op    delta
DecodeEntriesSkipping/long-lines-8                                 512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/long-lines-with-escapes-8                    512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/single-short-line-8                          512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/single-short-line-with-escapes-8             512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/many-short-lines-8                           512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/field-key-escape-not-escapable-8             512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/tag-value-triple-escape-space-8              512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/procstat-8                                   512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-8                          512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-with-escapes-8           17.4kB ± 0%     17.9kB ± 0%    +2.90%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-8                   512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-with-escapes-8      512B ± 0%         8B ± 0%   -98.44%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/many-short-lines-8                    512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/field-key-escape-not-escapable-8      512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/tag-value-triple-escape-space-8       512B ± 0%        24B ± 0%   -95.31%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/procstat-8                            512B ± 0%         0B       -100.00%  (p=0.008 n=5+5)

name                                                           old allocs/op  new allocs/op   delta
DecodeEntriesSkipping/long-lines-8                                 1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/long-lines-with-escapes-8                    1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/single-short-line-8                          1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/single-short-line-with-escapes-8             1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/many-short-lines-8                           1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/field-key-escape-not-escapable-8             1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/tag-value-triple-escape-space-8              1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesSkipping/procstat-8                                   1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-8                          1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/long-lines-with-escapes-8             7.00 ± 0%      13.00 ± 0%   +85.71%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-8                   1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/single-short-line-with-escapes-8      1.00 ± 0%       1.00 ± 0%      ~     (all equal)
DecodeEntriesWithoutSkipping/many-short-lines-8                    1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/field-key-escape-not-escapable-8      1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/tag-value-triple-escape-space-8       1.00 ± 0%       2.00 ± 0%  +100.00%  (p=0.008 n=5+5)
DecodeEntriesWithoutSkipping/procstat-8                            1.00 ± 0%       0.00       -100.00%  (p=0.008 n=5+5)

Thanks to @stuartcarnie for some of the ideas here.