Optimize encoding of composites

[turbolent]

Issue To Be Solved

The encoding of composites to CBOR values can be optimized.

Suggestion

• Switch from CBOR map to CBOR array

Definition of Done

• Optimize composite encoding
• Change decoding to only support this current format (i.e. remove old backwards-compatibility decoding code)
• Remove unnecessary field sorting when decoding
• Tests
  • Encode new format
  • Decode new format
  • Decode old format, incl. round-trip, i.e. encoding should match new encoding

[fxamacker]

I'm getting following performance gains on linux_amd64 with Go 1.15.10.

Comparisons Using Production Data

Encoding

name                                           old time/op    new time/op    delta
EncodeComposite/1comp_0dict_139bytes-4           16.0µs ± 1%    13.6µs ± 1%  -15.27%  (p=0.000 n=10+10)
EncodeComposite/2comp_0dict_160bytes-4           20.9µs ± 1%    15.7µs ± 1%  -25.16%  (p=0.000 n=10+10)
EncodeComposite/104comp_0dict_14850bytes-4        910µs ± 1%     657µs ± 1%  -27.78%  (p=0.000 n=9+10)
EncodeComposite/870comp_837dict_776155bytes-4    35.2ms ± 1%    19.6ms ± 1%  -44.35%  (p=0.000 n=10+10)

name                                           old alloc/op   new alloc/op   delta
EncodeComposite/1comp_0dict_139bytes-4           3.79kB ± 1%    2.98kB ± 2%  -21.32%  (p=0.000 n=10+10)
EncodeComposite/2comp_0dict_160bytes-4           4.85kB ± 2%    3.36kB ± 0%  -30.74%  (p=0.000 n=9+10)
EncodeComposite/104comp_0dict_14850bytes-4        247kB ± 1%     188kB ± 0%  -24.16%  (p=0.000 n=8+10)
EncodeComposite/870comp_837dict_776155bytes-4    7.50MB ± 5%    4.35MB ± 0%  -41.99%  (p=0.000 n=10+10)

name                                           old allocs/op  new allocs/op  delta
EncodeComposite/1comp_0dict_139bytes-4             76.0 ± 0%      62.0 ± 0%  -18.42%  (p=0.000 n=10+9)
EncodeComposite/2comp_0dict_160bytes-4              103 ± 0%        73 ± 0%  -29.13%  (p=0.000 n=7+10)
EncodeComposite/104comp_0dict_14850bytes-4        5.03k ± 0%     3.45k ± 0%  -31.28%  (p=0.000 n=8+10)
EncodeComposite/870comp_837dict_776155bytes-4      141k ± 0%       76k ± 0%  -46.02%  (p=0.000 n=10+10)

Decoding

name                                           old time/op    new time/op    delta
DecodeComposite/1comp_0dict_139bytes-4           11.6µs ± 1%     9.7µs ± 1%  -16.38%  (p=0.000 n=9+10)
DecodeComposite/2comp_0dict_160bytes-4           16.9µs ± 1%    12.7µs ± 1%  -24.47%  (p=0.000 n=10+9)
DecodeComposite/104comp_0dict_14850bytes-4        757µs ± 1%     569µs ± 1%  -24.90%  (p=0.000 n=9+10)
DecodeComposite/870comp_837dict_776155bytes-4    40.3ms ± 1%    26.3ms ± 1%  -34.65%  (p=0.000 n=10+10)

name                                           old alloc/op   new alloc/op   delta
DecodeComposite/1comp_0dict_139bytes-4           3.90kB ± 0%    3.35kB ± 0%  -13.96%  (p=0.000 n=10+10)
DecodeComposite/2comp_0dict_160bytes-4           5.54kB ± 0%    4.38kB ± 0%  -20.92%  (p=0.000 n=10+10)
DecodeComposite/104comp_0dict_14850bytes-4        296kB ± 0%     238kB ± 0%  -19.61%  (p=0.000 n=10+10)
DecodeComposite/870comp_837dict_776155bytes-4    15.0MB ± 0%    10.5MB ± 0%  -29.67%  (p=0.000 n=10+10)

name                                           old allocs/op  new allocs/op  delta
DecodeComposite/1comp_0dict_139bytes-4             56.0 ± 0%      53.0 ± 0%   -5.36%  (p=0.000 n=10+10)
DecodeComposite/2comp_0dict_160bytes-4             97.0 ± 0%      89.0 ± 0%   -8.25%  (p=0.000 n=10+10)
DecodeComposite/104comp_0dict_14850bytes-4        5.05k ± 0%     4.65k ± 0%   -7.98%  (p=0.000 n=10+10)
DecodeComposite/870comp_837dict_776155bytes-4      265k ± 0%      216k ± 0%  -18.56%  (p=0.000 n=10+10)