Runtime: System.Security: AsnSerializer performance

[filipnavara]

An issue was raised suggesting that the use of AsnSerializer provides suboptimal performance. Another concern is that it uses heavy reflection APIs that may incur performance penalty even if the information is properly cached for subsequent calls.

I extracted the certificate parsing code from System.Security.Cryptography.X509Certificates and both the new ASN class (AsnReader/AsnWriter/AsnSerializer) and the old ASN reader (DerSequenceReader) into a separate benchmark project. Then I used BenchmarkDotNew with default parameters to see how the different parsing codes behave. The results seem to confirm that there is problem that needs to be addressed:

            Method |      Mean |     Error |    StdDev |
------------------ |----------:|----------:|----------:|
        Serializer | 508.56 us | 3.3825 us | 3.1640 us |
 DerSequenceReader |  16.39 us | 0.3195 us | 0.3680 us |

Serializer is AsnSerializer.Deserialize<CertificateAsn>(certificateBytes, AsnEncodingRules.DER); (as used by current GIT master).

DerSequenceReader is the old code from CertificateData.cs with hand-written reading, which was arguably not strict, so wouldn't pass on the correctness, but it was fast.

For the sake of completeness I also rewrote the old code to switch from DerSequenceReader to the new AsnReader, which should work at the same conceptual level. I didn't add any additional checks (like reader.ThrowIfNotEmpty()) to improve correctness of the code. Here's comparison between the two low-level APIs:

            Method |     Mean |     Error |    StdDev |
------------------ |---------:|----------:|----------:|
 DerSequenceReader | 16.37 us | 0.1470 us | 0.1375 us |
         AsnReader | 14.07 us | 0.0419 us | 0.0350 us |

Notably AsnReader seems to do less memory allocations and is consistently faster than the old API.

There are few points to note. This is one of the heaviest ASN definitions that is used with the serializer, but it is very representative of a real-world usage. While the initial numbers look scary some simple caching (~ 5 lines of code) can improve the AsnSerializer performance considerably (~118.36 us) and it is likely that it could be improved even further.

I am opening this issue to raise awareness of the problem and shift the discussion here without spreading it across various different issues and PRs. I'll publish the benchmark project on GIT hub later and link it from here.

/cc @bartonjs @jkotas @MichalStrehovsky

[filipnavara]

I'm currently investigating several strategies to improve the performance:

• Modifying AsnSerializer to cache the metadata and lookup tables parsed through the reflection and use that for subsequent calls.
• Same as above, but save the precomputed information as source file instead of using reflection at runtime.
• Writing a code generator that will take the serializable class and spits out a class with Serialize/Deserialize methods that use the low-level AsnReader/AsnWriter APIs directly.

Ordered from the easiest to hardest. Each of them has it's pros/cons and many pitfalls.

[filipnavara]

Here's the basic benchmark code: https://github.com/filipnavara/asn-benchmark

[filipnavara]

Few observations:

• Building the deserialization structures (SerializerFieldData) from reflection is expensive. Caching it between calls cuts the time from ~500us to ~130us. That is still almost 10x more than the hand-written code, but it's a significant improvement.
• DeserializeCustomType uses reflection to create new object and then set its fields. This seems to be the other expensive method. I have experimentally rewritten it to use System.Linq.Expressions, precompile it once per type and then reuse it. This resulted in ~70us time in the benchmark alone (without the optimization above).
• Combining the two things above gets me to ~29us and still a lot of uncached information built unnecessarily during each deserialization (eg. choice lookup tables). That's going from 30x performance degradation to 2x.
• Adding cache for choice lookup tables gets it down another notch to ~20us.

I am experimenting with rewriting the whole serializer using expression trees. That will still rely on reflection and it will possibly be even slower on CoreRT than the current version. The side-effect of doing that is that with a little effort it's possible to traverse the expression tree and output C# version of the serializer custom tailored for the specific type.

[MichalStrehovsky]

That will still rely on reflection and it will possibly be even slower on CoreRT than the current version

LINQ expressions are going to be slower in all places that can't JIT. Xamarin on iOS too, for example.

[filipnavara]

I've committed the experiments above to the benchmark code tree. I'll be happy for any feedback on the ideas before I waste more time on it.

[filipnavara]

LINQ expressions are going to be slower in all places that can't JIT. Xamarin on iOS too, for example.

@MichalStrehovsky I am aware of that. I don't know if there's an easy way to benchmark it, but I would expect them to be in the same performance ballpark for this scenario when compared to calling the reflection methods manually.

My idea was to build the whole serializer as expression tree and reconstruct it into C# code that could be built once with the rest of the library code. I am not sure if that is feasible or even a good idea though. It definitely felt like better idea than other code generation approaches though.

[filipnavara]

Would have been so much more fun if C# was able to rewrite block expression into expression tree automatically. Sigh. Apparently it comes up in the language design meeting every now and then. There are even prototypes written, with compiler support, but it didn't progress past that.

[MichalStrehovsky]

I would expect them to be in the same performance ballpark for this scenario when compared to calling the reflection methods manually.

It's slow enough that Newtonsoft JSON would like to know this so that it can avoid expression trees and use reflection directly if they wouldn't be jitted.

[filipnavara]

I read that issue when looking into the possibilities, but some benchmark would be nice to have. I already know that the reflection based object initilization on CoreCLR is order of magnitude slower than statically typed compiled code, so the baseline is already quite bad in the first place.

Going to read-up on using CoreRT w/ BenchmarkDotNet to see if I can produce some number on my machine.

[filipnavara]

I haven't found a way to get BenchmarkDotNet generate all the necessary metadata. There's no option to use RD.xml or IlcArgs. I tried to manually instantiate all the types to force the compiler to generate the metadata, but eventually I ended up hitting System.Reflection.MissingMetadataException: 'System.Nullable<System.ReadOnlyMemory<System.Byte>>' is missing metadata. and couldn't get past that.

[bartonjs]

The low debuggability of the serializer sort of always bothered me (that is, when it said something couldn't be assigned it was hard to figure out what/why). Combined with the reflection drama I looked at what it would take for a generator to be sensible. (Sensible is, of course, a subjective term).

Codegen feels less packaged than the serializer, and it makes resource strings hard. But it does allow for much better debuggability, and it moves a lot of the safety rails into the build and a #if DEBUG cctor... and solves the reflection problem, because static analysis says the fields are needed.

https://github.com/bartonjs/corefx/commit/796508dc5efc45cd31927a394b50a4249a53f4b7 has an "if I only build the Pkcs project then all the tests still pass" first draft of things.

[filipnavara]

@bartonjs I looked at the code and I am quite intrigued. The approach with XSLT seems quite lightweight compared to what I was toying with. Then again it doesn't handle all the corner cases yet and all possible types, so it's a bit hard to judge whether it is possible to cover them. I do like the msbuild integration.

The serializer had provisions for wild things like Choice of Choices, which may not be easy to handle in XSLT. It may not even be used anywhere, so it would probably be fine to disallow that.

I may have missed it, but I didn't see if there's any handling of nested classes. Will that just call into another class' Decode/Encode?

Neat trick with the TryReadInt32 and ThrowIfNotEmpty. Maybe it's time for me to submit a PR with Read[U]Int[8/16/32/64] methods? Similarly ReadBitString and ReadOctetString seem sensible additions. When I was converting the hand-written deserializers for the benchmark these methods would have been so handy.

Resource strings are a bit of pain, but maybe it's possible to extract them into some helper methods (just as ThrowIfNotEmpty was added) and keep most/all of them in the shared code?

[bartonjs]

CHOICE { CHOICE { ... } } might need some finagling, since it'd probably sniff for a SEQUENCE tag using the AsnType reference. It's something X.680 calls out as possible, which is why the serializer tried handling it.

My testbed project (earlier than the prototype) made PFX work:

(Ignore the old namespace)

<?xml version="1.0" encoding="utf-8" ?>
<asn:Sequence
  xmlns:asn="http://tempuri.org/asn.xsd"
  name="PfxAsn"
  namespace="System.Security.Cryptography.Asn1">

  <asn:Integer name="Version" backingType="byte" />
  <asn:AsnType name="AuthSafe" typeName="System.Security.Cryptography.Asn1.ContentInfoAsn" />
  <asn:AsnType name="MacData" typeName="System.Security.Cryptography.Asn1.MacDataAsn" optional="true" />
</asn:Sequence>

which produced

```C#
using System;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
using System.Security.Cryptography.Asn1;

namespace System.Security.Cryptography.Asn1
{
[StructLayout(LayoutKind.Sequential)]
internal partial struct PfxAsn
{
internal byte Version;
internal System.Security.Cryptography.Asn1.ContentInfoAsn AuthSafe;
internal System.Security.Cryptography.Asn1.MacDataAsn? MacData;

    internal void Encode(AsnWriter writer)
    {
        Encode(writer, Asn1Tag.Sequence);
    }

    internal void Encode(AsnWriter writer, Asn1Tag tag)
    {
        writer.PushSequence(tag);

        writer.WriteInteger(Version);
        AuthSafe.Encode(writer);

        if (MacData.HasValue)
        {
            MacData.Value.Encode(writer);
        }

        writer.PopSequence(tag);
    }

    internal static void Decode(AsnReader reader, out PfxAsn decoded, out int bytesRead)
    {
        if (reader == null)
            throw new ArgumentNullException(nameof(reader));

        Decode(reader, Asn1Tag.Sequence, out decoded, out bytesRead);
    }

    internal static void Decode(AsnReader reader, Asn1Tag expectedTag, out PfxAsn decoded, out int bytesRead)
    {
        if (reader == null)
            throw new ArgumentNullException(nameof(reader));

        decoded = default;
        int localBytesRead = reader.PeekEncodedValue().Length;
        AsnReader sequenceReader = reader.ReadSequence(expectedTag);


        if (!sequenceReader.TryReadUInt8(out decoded.Version))
        {
            sequenceReader.ThrowIfNotEmpty();
        }

        System.Security.Cryptography.Asn1.ContentInfoAsn.Decode(sequenceReader, out decoded.AuthSafe, out _);

        if (sequenceReader.HasData && sequenceReader.PeekTag().HasSameClassAndValue(Asn1Tag.Sequence))
        {
            System.Security.Cryptography.Asn1.MacDataAsn tmpMacData;
            System.Security.Cryptography.Asn1.MacDataAsn.Decode(sequenceReader, out tmpMacData, out _);
            decoded.MacData = tmpMacData;

        }


        sequenceReader.ThrowIfNotEmpty();
        bytesRead = localBytesRead;
    }
}

}
```

[filipnavara]

Alright, I guess I will try to adapt it for my Certificate deserialization benchmark and see how it performs.

[filipnavara]

Ha, funny bug. This generates invalid code:

<?xml version="1.0" encoding="utf-8" ?>
<asn:Choice
  xmlns:asn="http://schemas.dot.net/asnxml/201808/"
  name="TimeAsn"
  namespace="System.Security.Cryptography.Asn1">
   <!--
    https://tools.ietf.org/html/rfc5280#section-4.1

    Time ::= CHOICE {
        utcTime        UTCTime,
        generalTime    GeneralizedTime
    }
  -->
  <asn:UtcTime name="UtcTime" />
  <asn:GeneralizedTime name="GeneralTime" />
</asn:Choice>

The comment tricks the position() != 1 check in the XSLT to generate else in front of all the if statements.

[bartonjs]

Drat, only invented the comment style in the end. I guess move it out of the Choice element.

[filipnavara]

Yeah, it's easy to workaround once I knew what was going on. It's also quite trivial to fix as part of the XSLT, but I will get to that later. :-)

[filipnavara]

Here goes the good news:

            Method |     Mean |     Error |    StdDev |
------------------ |---------:|----------:|----------:|
            Decode | 15.17 us | 0.1219 us | 0.1081 us |
 DerSequenceReader | 16.83 us | 0.3332 us | 0.4449 us |
         AsnReader | 14.31 us | 0.2831 us | 0.4408 us |

And on CoreRT:

            Method |     Mean |     Error |    StdDev |
------------------ |---------:|----------:|----------:|
            Decode | 21.09 us | 0.3805 us | 0.3559 us |
 DerSequenceReader | 15.83 us | 0.3163 us | 0.3642 us |
         AsnReader | 19.18 us | 0.3755 us | 0.3688 us |

Description:

• Decode is the deserializer code generated from XML
• DerSequenceReader is legacy code from CertificateData
• AsnReader is legacy code from CertificateData rewritten line-for-line to use AsnReader

I had to fix one more thing in the XSLT, but it worked almost flawlessly. I'm impressed!

[filipnavara]

Had to change

<xsl:if test="asn:SequenceOf">
using System.Collections.Generic;</xsl:if>

to

<xsl:if test="asn:SequenceOf | asn:SetOf">
using System.Collections.Generic;</xsl:if>

Otherwise the following XML would generate code that doesn't compile:

  <asn:SetOf name="Extensions" explicitTag="3" optional="true">
      <asn:AsnType typeName="System.Security.Cryptography.Asn1.X509ExtensionAsn" />
  </asn:SetOf>

Still don't know how to properly describe X500Names which I don't want to get decoded. Previous code used:

```c#
[AnyValue]
[ExpectedTag(TagClass.Universal, (int)UniversalTagNumber.SequenceOf)]
internal ReadOnlyMemory Issuer;

Now I used:

```xml
<asn:AnyValue name="Issuer" />

which looses the "sequence" check part. Nvm, figured out the universalTagNumber attribute.

Some nice things are not there yet, such as support for ReadObjectIdentifierAsString, which may contribute to the small performance differences.

Update: Full source code for reference at https://github.com/filipnavara/asn-benchmark/tree/decode (not meant to be a nice, production ready code; just sharing it in case you'd like to reproduce my results).

[filipnavara]

Adding Decode overloads without the out bytesRead last parameter seemed to bring the performance of the generated code within touching distance of the hand-written one:

            Method |     Mean |     Error |    StdDev |   Median |
------------------ |---------:|----------:|----------:|---------:|
            Decode | 14.33 us | 0.0496 us | 0.0464 us | 14.32 us |
 DerSequenceReader | 17.20 us | 0.0242 us | 0.0214 us | 17.20 us |
         AsnReader | 14.15 us | 0.2788 us | 0.4658 us | 13.92 us |

And CoreRT:

            Method |     Mean |     Error |    StdDev |
------------------ |---------:|----------:|----------:|
            Decode | 19.30 us | 0.0351 us | 0.0293 us |
 DerSequenceReader | 16.21 us | 0.0399 us | 0.0354 us |
         AsnReader | 19.09 us | 0.0411 us | 0.0365 us |

Given the fact that the hand-written one doesn't handle all the error checking I consider this perfect result.

[filipnavara]

Another broken case in the code generation:

<?xml version="1.0" encoding="utf-8" ?>
<asn:Choice
  xmlns:asn="http://schemas.dot.net/asnxml/201808/"
  name="GeneralNameAsn"
  namespace="System.Security.Cryptography.Asn1">

  <!--
    https://tools.ietf.org/html/rfc5280#section-4.2.1.6

    GeneralName ::= CHOICE {
        otherName                 [0]  OtherName,
        rfc822Name                [1]  IA5String,
        dNSName                   [2]  IA5String,
        x400Address               [3]  ORAddress,
        directoryName             [4]  Name,
        ediPartyName              [5]  EDIPartyName,
        uniformResourceIdentifier [6]  IA5String,
        iPAddress                 [7]  OCTET STRING,
        registeredID              [8]  OBJECT IDENTIFIER
    }
  -->
  <asn:AsnType name="OtherName" implicitTag="0" typeName="System.Security.Cryptography.Asn1.OtherNameAsn" />
  <asn:IA5String name="Rfc822Name" implicitTag="1" />
  <asn:IA5String name="DnsName" implicitTag="2" />
  <asn:AnyValue name="X400Address" implicitTag="3" />
  <asn:AnyValue name="DirectoryName" explicitTag="4" />
  <asn:AsnType name="EdiPartyName" implicitTag="5" typeName="System.Security.Cryptography.Asn1.EdiPartyNameAsn" />
  <asn:IA5String name="Uri" implicitTag="6" />
  <asn:OctetString name="IpAddress" implicitTag="7" />
  <asn:ObjectIdentifier name="RegisteredId" implicitTag="8" />
</asn:Choice>

The AnyValue types in Choice result in the following build error message:

/Users/filipnavara/Documents/GitHub/asn-benchmark/AsnXml.targets(17,5): error MSB3703: Unable to execute transformation. Value cannot be null.
/Users/filipnavara/Documents/GitHub/asn-benchmark/AsnXml.targets(17,5): error MSB3703: Parameter name: args

Updated project at https://github.com/filipnavara/asn-benchmark/tree/decode.

[bartonjs]

That's weird. When I build it I get a much more sensible error:

IMPLICIT ANY is not yet supported (X400Address).
D:\git\bartonjs\corefx\src\Common\src\System\Security\Cryptography\Asn1\AsnXml.
targets(17,5): error MSB3703: Unable to execute transformation. IMPLICIT ANY is
 not yet supported (X400Address). [D:\git\bartonjs\corefx\src\System.Security.C
ryptography.Pkcs\src\System.Security.Cryptography.Pkcs.csproj]

Mainly because I couldn't think through what it meant. But what it meant was "don't parse this, just give me bytes" :smile:

[filipnavara]

Interesting. I was running it from fully updated VS4Mac with latest .NET Core 2.1. Well, the error message makes way more sense.

I tried feeding it the worst case I could find. Next up was X.501 Name, but I stumbled on this...

[bartonjs]

Updated my branch. It looked like reasonable code came out.

[filipnavara]

@bartonjs Checked it out. There're still two issues:

• Choice still generates Decode with the out int bytesRead parameter that is now not expected by the caller.
• There's missing decoded. in the EXPLICIT ANY output:
  c# else if (tag.HasSameClassAndValue(new Asn1Tag(TagClass.ContextSpecific, 4))) { explicitReader = reader.ReadSequence(new Asn1Tag(TagClass.ContextSpecific, 4)); DirectoryName = explicitReader.GetEncodedValue(); explicitReader.ThrowIfNotEmpty(); }

The first one is easy to fix, the second one left me puzzled a bit since it seems that the same XSLT code works just fine elsewhere.

UPDATE: The second one is caused by <xsl:with-param name="name" select="@name"/>. If I remove that it generates correct code.

UPDATE 2: Fixing the two issues above made it working for GeneralName ASN. :-)

[filipnavara]

Thanks for the fixes. LGTM