Un-nesting a type from an enum namespace results in a 6x slowdown

[taylorswift]

over the weekend, swift-json’s CI caught a nearly 6x performance regression resulting from a recent API adjustment.

i was able to narrow down the offending change to a seemingly innocuous refactor: moving the definition of a type and its conformances from a nested type to the parent type (which was previously an empty namespace enum).

---

before:

public 
enum Rule<Location>
{
    // @available(*, deprecated, renamed: "JSON.Rule")
    // public 
    // typealias Root = JSON.Rule<Location> 
    public 
    enum Root:ParsingRule
    {
        public 
        typealias Terminal = UInt8

        @inlinable public static 
        func parse<Diagnostics>(_ input:inout ParsingInput<Diagnostics>) throws -> JSON
            where   Diagnostics:ParsingDiagnostics,
                    Diagnostics.Source.Index == Location,
                    Diagnostics.Source.Element == Terminal
        {
            if let items:[(key:String, value:JSON)] = input.parse(as: Object?.self)
            {
                return .object(items)
            }
            else 
            {
                return .array(try input.parse(as: Array.self))
            }
        }
    }
}

workflow run

 [15/16] Linking benchmark
Build complete! (45.71s)
swift-json: decoded 38295 messages
foundation: decoded 38295 messages
swift-json decoding time: 0.482016238 seconds
foundation decoding time: 4.450682692 seconds

---

after:

public 
enum Rule<Location>:ParsingRule
{
    // @available(*, deprecated, renamed: "JSON.Rule")
    // public 
    // typealias Root = JSON.Rule<Location> 
    // public 
    // enum Root:ParsingRule
    // {
        public 
        typealias Terminal = UInt8

        @inlinable public static 
        func parse<Diagnostics>(_ input:inout ParsingInput<Diagnostics>) throws -> JSON
            where   Diagnostics:ParsingDiagnostics,
                    Diagnostics.Source.Index == Location,
                    Diagnostics.Source.Element == Terminal
        {
            if let items:[(key:String, value:JSON)] = input.parse(as: Object?.self)
            {
                return .object(items)
            }
            else 
            {
                return .array(try input.parse(as: Array.self))
            }
        }
    // }
}

workflow run

 Build complete! (37.48s)
swift-json: decoded 38295 messages
foundation: decoded 38295 messages
swift-json decoding time: 2.875409557 seconds
foundation decoding time: 3.795551295 seconds

all of the types involved were public, and all of the implementations involved were @inlinable. what is going on here?

benchmark code

[lukasa (Cory Benfield)]

How is the code invoked? It seems relevant to me that we're not just hoisting the inner code up one level of scope, but we are also making the outer scope object conform to ParsingRule.

[taylorswift]

the benchmarking code looks like this:

@inline(never)
static 
func benchmarkSwiftJSON(_ json:[UInt8]) throws -> Int
{
    try Grammar.parse(json, as: JSON.Rule<Int>.Root.self, 
        in: [JSON].self).count
}

which calls into this swift-grammar function:

extension Grammar 
{
    @inlinable public static 
    func parse<Source, Rule, Vector>(_ source:Source, as _:Rule.Type, in _:Vector.Type) throws -> Vector
        where   Source:Collection, Rule:ParsingRule, 
                Rule.Location == Source.Index, Rule.Terminal == Source.Element, 
                Vector:RangeReplaceableCollection, Vector.Element == Rule.Construction
    {
        var input:ParsingInput<NoDiagnostics<Source>> = .init(source)
        let construction:Vector = input.parse(as: Rule.self, in: Vector.self)
        try input.parse(as: End<Rule.Location, Rule.Terminal>.self)
        return construction
    }
}

which calls into this swift-grammar API:

extension ParsingInput 
{
    @inlinable public mutating 
    func parse<Rule>(as _:Rule?.Type) -> Rule.Construction? 
        where   Rule:ParsingRule, Rule.Location == Diagnostics.Source.Index, Rule.Terminal == Diagnostics.Source.Element
    {
        try? self.parse(as: Rule.self)
    }

    @inlinable public mutating 
    func parse<Rule, Vector>(as _:Rule.Type, in _:Vector.Type) -> Vector
        where   Rule:ParsingRule, Rule.Location == Diagnostics.Source.Index, Rule.Terminal == Diagnostics.Source.Element, 
                Rule.Construction == Vector.Element, 
                Vector:RangeReplaceableCollection
    {
        var vector:Vector = .init()
        while let element:Rule.Construction = self.parse(as: Rule?.self)
        {
            vector.append(element)
        }
        return vector
    }
}

which finally calls this swift-grammar API,

extension ParsingInput 
{
    @inlinable public mutating 
    func group<Rule, Construction>(_:Rule.Type, _ body:(inout Self) throws -> Construction) 
        throws -> Construction
    {
        let breadcrumb:Diagnostics.Breadcrumb = 
            self.diagnostics.push(index: self.index, for: Construction.self, by: Rule.self)
        do 
        {
            let construction:Construction = try body(&self)
            self.diagnostics.pop()
            return construction 
        }
        catch var error 
        {
            self.diagnostics.reset(index: &self.index, to: breadcrumb, because: &error)
            throw error
        }
    }

    @inlinable public mutating 
    func parse<Rule>(as _:Rule.Type) throws -> Rule.Construction 
        where   Rule:ParsingRule, Rule.Location == Diagnostics.Source.Index, Rule.Terminal == Diagnostics.Source.Element
    {
        try self.group(Rule.self){ try Rule.parse(&$0) }
    }
}

which ultimately calls JSON.Rule<Location>.parse(_:)/JSON.Rule<Location>.Root.parse(_:).

here is the definition of NoDiagnostics:

@frozen public 
struct NoDiagnostics<Source>:ParsingDiagnostics where Source:Collection
{
    @inlinable public 
    init() 
    {
    }
    // force inlining because these functions ignore most of their inputs, and 
    // don’t contain many instructions (if any)
    @inline(__always)
    @inlinable public 
    func push<Rule, Construction>(index:Source.Index, for _:Construction.Type, by _:Rule.Type) 
        -> Source.Index
    {
        index
    }
    @inline(__always)
    @inlinable public 
    func pop()
    {
    }
    @inline(__always)
    @inlinable public 
    func reset(index:inout Source.Index, to breadcrumb:Source.Index, because _:inout Error) 
    {
        index = breadcrumb 
    }
}