Compilation time problems when building matrices


(Elia Cereda) #1

Hi,

I currently writing a demo app to teach myself the fundamentals of Metal and a big part of that is obviously working with matrices. What I’m seeing is that the code build them has some serious compilation time problems.

The worst case is this function, which according to -debug-time-function-bodies takes over 9500ms of time to compile.

static func frustum(l: Float, r: Float, t: Float, b: Float, n: Float, f: Float) -> float4x4 {
    return float4x4(rows: [
        [ 2 * n / (r - l), 0, (r + l) / (r - l), 0 ],
        [ 0, 2 * n / (t - b), (t + b) / (t - b), 0 ],
        [ 0, 0, -(f + n) / (f - n), -2 * f * n / (f - n) ],
        [ 0, 0, -1, 1 ],
    ])
}

I’ve tried making some naive changes to the code and gotten it down to a much more reasonable 4ms, but the result is not something I would write if given a choice.

static func frustum(l: Float, r: Float, t: Float, b: Float, n: Float, f: Float) -> float4x4 {
    let twoN = 2 * n
    
    let rPlusL = r + l
    let rMinusL = r - l
    
    let tPlusB = t + b
    let tMinusB = t - b
    
    let fPlusN = f + n
    let fMinusN = f - n
    
    return float4x4(rows: [
        [ twoN / rMinusL, 0, rPlusL / rMinusL, 0 ],
        [ 0, twoN / tMinusB, tPlusB / tMinusB, 0 ],
        [ 0, 0, -fPlusN / fMinusN, -twoN * f / fMinusN ],
        [ 0, 0, -1, 1 ],
    ])
}

I’m taking this to swift-users since I’m aware this is a known pain point with the compiler. Is this specific instance something that would be worth filing a bug for?

Since I do not understand enough of the compiler to understand specifically what is causing problems with the first piece of code, I would also be extremely grateful if something from the core team (or anyone for that matter) could share some wisdom regarding what to do here.

Specifically, is there something that could be done to the first code to reduce the amount of overloads that the compiler needs to consider? In my naive view of the world, a sum or a multiplication between two Floats can only ever produce another Float, is there some way to pass this knowledge to the compiler?

Regards,
Elia Cereda


(^) #2

i have a similar function in my code which uses four intermediates but
compiles in reasonable time

    {
        // frustum
        let f_width:Float = self.half_h * self.twice_size,
            f_height:Float = self.half_k * self.twice_size,
            dx:Float = -self.shift_x / self.half_h,
            dy:Float = -self.shift_y / self.half_k

        let clip_ratio:Float = 1000

        self.projection_matrix =
        [self.z/f_width , 0 ,
0 , 0,
         0 , self.z/f_height,
0 , 0,
         dx , dy , (1 + clip_ratio) / (1 -
clip_ratio),-1,
         0 , 0 , self.z*2*clip_ratio / (1 -
clip_ratio), 0]
    }

The intermediates are also things you’re going to want to store if anything
for code clarity since the array literal starts looking messy when you
shove long expressions into it. It also cuts down a little on the number of
redundant operations you have to do (from 21 in your example to 16),
especially divisions which you have six of in the original.

···

On Wed, Jun 28, 2017 at 1:51 PM, Elia Cereda via swift-users < swift-users@swift.org> wrote:

Hi,

I currently writing a demo app to teach myself the fundamentals of Metal
and a big part of that is obviously working with matrices. What I’m seeing
is that the code build them has some serious compilation time problems.

The worst case is this function, which according
to -debug-time-function-bodies takes over 9500ms of time to compile.

static func frustum(l: Float, r: Float, t: Float, b: Float, n: Float, f:
Float) -> float4x4 {
    return float4x4(rows: [
        [ 2 * n / (r - l), 0, (r + l) / (r - l),
            0 ],
        [ 0, 2 * n / (t - b), (t + b) / (t - b),
            0 ],
        [ 0, 0, -(f + n) / (f - n), -2 * f
* n / (f - n) ],
        [ 0, 0, -1,
            1 ],
    ])
}

I’ve tried making some naive changes to the code and gotten it down to a
much more reasonable 4ms, but the result is not something I would write if
given a choice.

static func frustum(l: Float, r: Float, t: Float, b: Float, n: Float, f:
Float) -> float4x4 {
    let twoN = 2 * n

    let rPlusL = r + l
    let rMinusL = r - l

    let tPlusB = t + b
    let tMinusB = t - b

    let fPlusN = f + n
    let fMinusN = f - n

    return float4x4(rows: [
        [ twoN / rMinusL, 0, rPlusL / rMinusL,
    0 ],
        [ 0, twoN / tMinusB, tPlusB / tMinusB,
    0 ],
        [ 0, 0, -fPlusN / fMinusN, -twoN * f /
fMinusN ],
        [ 0, 0, -1,
    1 ],
    ])
}

I’m taking this to swift-users since I’m aware this is a known pain point
with the compiler. Is this specific instance something that would be worth
filing a bug for?

Since I do not understand enough of the compiler to understand
specifically what is causing problems with the first piece of code, I would
also be extremely grateful if something from the core team (or anyone for
that matter) could share some wisdom regarding what to do here.

Specifically, is there something that could be done to the first code to
reduce the amount of overloads that the compiler needs to consider? In my
naive view of the world, a sum or a multiplication between two Floats can
only ever produce another Float, is there some way to pass this knowledge
to the compiler?

Regards,
Elia Cereda

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Elia Cereda) #3

The intermediates are also things you’re going to want to store if anything for code clarity since the array literal starts looking messy when you shove long expressions into it.

Yes, I agree. I guess having everything in the matrix looks kind of nice with simple expressions, but starts to become untenable once you need to do more than a few computations per element. Here I was more interested in learning something about the performance characteristics of the Swift type checker than writing good code. After all, this is a project that I started specifically to experiment.

It also cuts down a little on the number of redundant operations you have to do (from 21 in your example to 16), especially divisions which you have six of in the original.

I’m not so sure about this. I haven’t tried optimising this function for performance, it is called only once in my application for now, but I would expect Common Subexpression Elimination in the Swift compiler / LLVM to be able to automatically identify those redundancies.

Back to the point of compilation times, is there some resource that explains the performance of the type checker? I’ve been reading https://github.com/apple/swift/blob/master/docs/TypeChecker.rst#performance, but that only illustrates possible optimisations to improve the performance from the side of the compiler. I’d also be curious to look at the constraints generated by the type checker, is there any flag that dumps them?
<https://github.com/apple/swift/blob/master/docs/TypeChecker.rst#performance>
Regards,
Elia Cereda

···

Il giorno 28 giu 2017, alle ore 22:21, Taylor Swift <kelvin13ma@gmail.com> ha scritto:

i have a similar function in my code which uses four intermediates but compiles in reasonable time

    {
        // frustum
        let f_width:Float = self.half_h * self.twice_size,
            f_height:Float = self.half_k * self.twice_size,
            dx:Float = -self.shift_x / self.half_h,
            dy:Float = -self.shift_y / self.half_k

        let clip_ratio:Float = 1000

        self.projection_matrix =
        [self.z/f_width , 0 , 0 , 0,
         0 , self.z/f_height, 0 , 0,
         dx , dy , (1 + clip_ratio) / (1 - clip_ratio),-1,
         0 , 0 , self.z*2*clip_ratio / (1 - clip_ratio), 0]
    }

The intermediates are also things you’re going to want to store if anything for code clarity since the array literal starts looking messy when you shove long expressions into it. It also cuts down a little on the number of redundant operations you have to do (from 21 in your example to 16), especially divisions which you have six of in the original.

On Wed, Jun 28, 2017 at 1:51 PM, Elia Cereda via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Hi,

I currently writing a demo app to teach myself the fundamentals of Metal and a big part of that is obviously working with matrices. What I’m seeing is that the code build them has some serious compilation time problems.

The worst case is this function, which according to -debug-time-function-bodies takes over 9500ms of time to compile.

static func frustum(l: Float, r: Float, t: Float, b: Float, n: Float, f: Float) -> float4x4 {
    return float4x4(rows: [
        [ 2 * n / (r - l), 0, (r + l) / (r - l), 0 ],
        [ 0, 2 * n / (t - b), (t + b) / (t - b), 0 ],
        [ 0, 0, -(f + n) / (f - n), -2 * f * n / (f - n) ],
        [ 0, 0, -1, 1 ],
    ])
}

I’ve tried making some naive changes to the code and gotten it down to a much more reasonable 4ms, but the result is not something I would write if given a choice.

static func frustum(l: Float, r: Float, t: Float, b: Float, n: Float, f: Float) -> float4x4 {
    let twoN = 2 * n
    
    let rPlusL = r + l
    let rMinusL = r - l
    
    let tPlusB = t + b
    let tMinusB = t - b
    
    let fPlusN = f + n
    let fMinusN = f - n
    
    return float4x4(rows: [
        [ twoN / rMinusL, 0, rPlusL / rMinusL, 0 ],
        [ 0, twoN / tMinusB, tPlusB / tMinusB, 0 ],
        [ 0, 0, -fPlusN / fMinusN, -twoN * f / fMinusN ],
        [ 0, 0, -1, 1 ],
    ])
}

I’m taking this to swift-users since I’m aware this is a known pain point with the compiler. Is this specific instance something that would be worth filing a bug for?

Since I do not understand enough of the compiler to understand specifically what is causing problems with the first piece of code, I would also be extremely grateful if something from the core team (or anyone for that matter) could share some wisdom regarding what to do here.

Specifically, is there something that could be done to the first code to reduce the amount of overloads that the compiler needs to consider? In my naive view of the world, a sum or a multiplication between two Floats can only ever produce another Float, is there some way to pass this knowledge to the compiler?

Regards,
Elia Cereda

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users