Non-determinstic poor performance with nested If conditions

[trav-c]

CloudFormation Lint Version

cfn-lint 1.15.1

What operating system are you using?

Linux (Fedora 40 x86_64)

Describe the bug

When nested Fn:If conditions are used (or possibly just large numbers of Fn:If conditions) cfn-lint performance can degrade severely.

Processing the attached template can range from seconds, to over a minute for the attached example, the original full template, which has multiple nested Fn:If cases has been observed to take up to 8 minutes to process in some cases.

I have figured out that I am able to achieve repeatable processing times by forcing specific python hash seeds, in the following examples the hash seeds are random test values that I found that trigger both fast and slow processing, but the overall time can vary widely depending on the hash seed, ie there's not just one "slow" and one "fast" case.

Based on a few stack traces taken from "slow" examples I suspect that the issue may be related to sympy2's DPLL implementation, but that's just a guess based on a handful of stack traces, and the issue could also be higher up in the call chain.

Removing the nesting of the If condition from the template does appear to significantly improve both the absolute performance, and the variability, but I'm not sure whether that's specifically related to the nesting of the If conditions, or just the total number of possible condition combination branches.

This issue may be somewhat related to the previously addressed #2597

Expected behavior

Template processing should ideally be single, or low double digits seconds at most, but regardless of absolute performance the time required to process a given template shouldn't change by orders of magnitude between runs based on random factors like the python hash seed.

Reproduction template

# To reproduce "fast" cfn-lint evaluation use PYTHONHASHSEED=2821703311
# $ time env PYTHONHASHSEED=2821703311 cfn-lint --ignore-checks W1001 E3003 -- nested-if-conditions.yml
#
# To reproduce "slow" cfn-lint evaluation use PYTHONHASHSEED=1356847902
# $ time env PYTHONHASHSEED=1356847902 cfn-lint --ignore-checks W1001 E3003 -- nested-if-conditions.yml
#
Parameters:
    WebACLId:
        Type: String
    DeploymentRegion1:
        Type: String
        Default: ''
    DeploymentName1:
        Type: String
        Default: ''
    ServiceDomain1:
        Type: String
        Default: ''
    S3WebAssetsBucket1:
        Type: String
        Default: ''
    S3WebTemplatesBucket1:
        Type: String
        Default: ''
    S3ExtAssetsBucket1:
        Type: String
        Default: ''
    S3ExtraTemplatesBucket1:
        Type: String
        Default: ''
    DeploymentRegion2:
        Type: String
        Default: ''
    DeploymentName2:
        Type: String
        Default: ''
    ServiceDomain2:
        Type: String
        Default: ''
    S3WebAssetsBucket2:
        Type: String
        Default: ''
    S3WebTemplatesBucket2:
        Type: String
        Default: ''
    S3ExtAssetsBucket2:
        Type: String
        Default: ''
    S3ExtraTemplatesBucket2:
        Type: String
        Default: ''
    DeploymentRegion3:
        Type: String
        Default: ''
    DeploymentName3:
        Type: String
        Default: ''
    ServiceDomain3:
        Type: String
        Default: ''
    S3WebAssetsBucket3:
        Type: String
        Default: ''
    S3WebTemplatesBucket3:
        Type: String
        Default: ''
    S3ExtAssetsBucket3:
        Type: String
        Default: ''
    S3ExtraTemplatesBucket3:
        Type: String
        Default: ''
    DeploymentRegion4:
        Type: String
        Default: ''
    DeploymentName4:
        Type: String
        Default: ''
    ServiceDomain4:
        Type: String
        Default: ''
    S3WebAssetsBucket4:
        Type: String
        Default: ''
    S3WebTemplatesBucket4:
        Type: String
        Default: ''
    S3ExtAssetsBucket4:
        Type: String
        Default: ''
    S3ExtraTemplatesBucket4:
        Type: String
        Default: ''
    DeploymentRegion5:
        Type: String
        Default: ''
    DeploymentName5:
        Type: String
        Default: ''
    ServiceDomain5:
        Type: String
        Default: ''
    S3WebAssetsBucket5:
        Type: String
        Default: ''
    S3WebTemplatesBucket5:
        Type: String
        Default: ''
    S3ExtAssetsBucket5:
        Type: String
        Default: ''
    S3ExtraTemplatesBucket5:
        Type: String
        Default: ''

Conditions:

    HaveWebTarget1: !And
      - !Not [ !Equals [ !Ref S3WebTemplatesBucket1, '' ] ]
      - !Not [ !Equals [ !Ref S3WebAssetsBucket1, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName1, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion1, '' ] ]
    HaveWebTarget2: !And
      - !Not [ !Equals [ !Ref S3WebTemplatesBucket2, '' ] ]
      - !Not [ !Equals [ !Ref S3WebAssetsBucket2, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName2, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion2, '' ] ]
    HaveWebTarget3: !And
      - !Not [ !Equals [ !Ref S3WebTemplatesBucket3, '' ] ]
      - !Not [ !Equals [ !Ref S3WebAssetsBucket3, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName3, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion3, '' ] ]
    HaveWebTarget4: !And
      - !Not [ !Equals [ !Ref S3WebTemplatesBucket4, '' ] ]
      - !Not [ !Equals [ !Ref S3WebAssetsBucket4, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName4, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion4, '' ] ]
    HaveWebTarget5: !And
      - !Not [ !Equals [ !Ref S3WebTemplatesBucket5, '' ] ]
      - !Not [ !Equals [ !Ref S3WebAssetsBucket5, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName5, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion5, '' ] ]
    HaveExtTarget1: !And
      - !Not [ !Equals [ !Ref S3ExtraTemplatesBucket1, '' ] ]
      - !Not [ !Equals [ !Ref S3ExtAssetsBucket1, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName1, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion1, '' ] ]
    HaveExtTarget2: !And
      - !Not [ !Equals [ !Ref S3ExtraTemplatesBucket2, '' ] ]
      - !Not [ !Equals [ !Ref S3ExtAssetsBucket2, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName2, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion2, '' ] ]
    HaveExtTarget3: !And
      - !Not [ !Equals [ !Ref S3ExtraTemplatesBucket3, '' ] ]
      - !Not [ !Equals [ !Ref S3ExtAssetsBucket3, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName3, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion3, '' ] ]
    HaveExtTarget4: !And
      - !Not [ !Equals [ !Ref S3ExtraTemplatesBucket4, '' ] ]
      - !Not [ !Equals [ !Ref S3ExtAssetsBucket4, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName4, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion4, '' ] ]
    HaveExtTarget5: !And
      - !Not [ !Equals [ !Ref S3ExtraTemplatesBucket5, '' ] ]
      - !Not [ !Equals [ !Ref S3ExtAssetsBucket5, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentName5, '' ] ]
      - !Not [ !Equals [ !Ref DeploymentRegion5, '' ] ]

    HasAnyTarget: !And
      - !Or
        - !Condition HaveWebTarget1
        - !Condition HaveWebTarget2
        - !Condition HaveWebTarget3
        - !Condition HaveWebTarget4
        - !Condition HaveWebTarget5
      - !Or
        - !Condition HaveExtTarget1
        - !Condition HaveExtTarget2
        - !Condition HaveExtTarget3
        - !Condition HaveExtTarget4
        - !Condition HaveExtTarget5


Resources:

    Distribution1:
        Type: AWS::CloudFront::Distribution
        Properties:
            DistributionConfig:
                Enabled: true
                WebACLId: !Ref WebACLId
                DefaultCacheBehavior:
                    TargetOriginId: TestWebOrigin
                    ViewerProtocolPolicy: redirect-to-https
                    AllowedMethods: [ 'GET', 'HEAD' ]
                CacheBehaviors:
                  - !If
                    - HasAnyTarget
                    - TargetOriginId: TestWebAssetsOrigin
                      PathPattern: '/assets/*'
                      ViewerProtocolPolicy: redirect-to-https
                    - !Ref AWS::NoValue
                  - !If
                    - HasAnyTarget
                    - TargetOriginId: ExtAssetsOrigin
                      PathPattern: '/example/assets/*'
                      ViewerProtocolPolicy: redirect-to-https
                    - !Ref AWS::NoValue
                  - !If
                    - HasAnyTarget
                    - TargetOriginId: TestWebAssetsOrigin
                      PathPattern: '/.well-known/*'
                      ViewerProtocolPolicy: redirect-to-https
                    - !Ref AWS::NoValue

                Origins:
                    - Id: TestWebOrigin
                      DomainName: 'subdomain.example.com'
                      CustomOriginConfig:
                          HTTPSPort: 443
                          OriginProtocolPolicy: https-only
                          OriginSSLProtocols: ["TLSv1.2"]
                          OriginKeepaliveTimeout: 5
                          OriginReadTimeout: 5
                      OriginCustomHeaders:
                          - HeaderName: add-csp-headers
                            HeaderValue: 1
                          - !If
                            - HaveWebTarget1
                            - HeaderName: !Sub
                                - 'web-template-bucket${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain1 ] ]
                              HeaderValue: !Sub '${DeploymentRegion1}/${S3WebTemplatesBucket1}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget2
                            - HeaderName: !Sub
                                - 'web-template-bucket${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain2 ] ]
                              HeaderValue: !Sub '${DeploymentRegion2}/${S3WebTemplatesBucket2}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget3
                            - HeaderName: !Sub
                                - 'web-template-bucket${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain3 ] ]
                              HeaderValue: !Sub '${DeploymentRegion3}/${S3WebTemplatesBucket3}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget4
                            - HeaderName: !Sub
                                - 'web-template-bucket${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain4 ] ]
                              HeaderValue: !Sub '${DeploymentRegion4}/${S3WebTemplatesBucket4}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget5
                            - HeaderName: !Sub
                                - 'web-template-bucket${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain5 ] ]
                              HeaderValue: !Sub '${DeploymentRegion5}/${S3WebTemplatesBucket5}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveExtTarget1
                            - HeaderName: !Sub
                                - 'extra-template-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain1 ] ]
                              HeaderValue: !Sub '${DeploymentRegion1}/${S3ExtraTemplatesBucket1}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveExtTarget2
                            - HeaderName: !Sub
                                - 'extra-template-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain2 ] ]
                              HeaderValue: !Sub '${DeploymentRegion2}/${S3ExtraTemplatesBucket2}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveExtTarget3
                            - HeaderName: !Sub
                                - 'extra-template-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain3 ] ]
                              HeaderValue: !Sub '${DeploymentRegion3}/${S3ExtraTemplatesBucket3}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveExtTarget4
                            - HeaderName: !Sub
                                - 'extra-template-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain4 ] ]
                              HeaderValue: !Sub '${DeploymentRegion4}/${S3ExtraTemplatesBucket4}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveExtTarget5
                            - HeaderName: !Sub
                                - 'extra-template-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain5 ] ]
                              HeaderValue: !Sub '${DeploymentRegion5}/${S3ExtraTemplatesBucket5}'
                            - !Ref AWS::NoValue
                    - !If
                      - HasAnyTarget
                      - Id: TestWebAssetsOrigin
                        DomainName: dummy-origin.example.com
                        CustomOriginConfig:
                            OriginProtocolPolicy: https-only
                        OriginCustomHeaders:
                          - HeaderName: web-domain
                            HeaderValue: 'dev.dev.example.com'
                          - !If
                            - HaveWebTarget1
                            - HeaderName: !Sub
                                - 'web-template-bucket${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain1 ] ]
                              HeaderValue: !Sub '${DeploymentRegion1}/${S3WebTemplatesBucket1}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget1
                            - HeaderName: !Sub
                                - 'web-asset-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain1 ] ]
                              HeaderValue: !Sub '${DeploymentRegion1}/${S3WebAssetsBucket1}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget2
                            - HeaderName: !Sub
                                - 'web-asset-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain2 ] ]
                              HeaderValue: !Sub '${DeploymentRegion2}/${S3WebAssetsBucket2}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget3
                            - HeaderName: !Sub
                                - 'web-asset-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain3 ] ]
                              HeaderValue: !Sub '${DeploymentRegion3}/${S3WebAssetsBucket3}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget4
                            - HeaderName: !Sub
                                - 'web-asset-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain4 ] ]
                              HeaderValue: !Sub '${DeploymentRegion4}/${S3WebAssetsBucket4}'
                            - !Ref AWS::NoValue
                          - !If
                            - HaveWebTarget5
                            - HeaderName: !Sub
                                - 'web-asset-bucket-${ServicePrefix}'
                                - ServicePrefix: !Select [ 0, !Split [ '.', !Ref ServiceDomain5 ] ]
                              HeaderValue: !Sub '${DeploymentRegion5}/${S3WebAssetsBucket5}'
                            - !Ref AWS::NoValue
                      - !Ref AWS::NoValue

[kddejong]

In a way this doesn't surprise me. I need to track down what is causing this as we try to avoid these massive complications as much as possible... we also try set limits on how many permutations we will evaluate.

That being said there are a few areas where we may still being doing needless permutations. I'll be looking into this today.

[kddejong]

I see what you are saying now about the random parts.

[kddejong]

Also looks like installing pycosat helps performance a lot for this scenario.

[trav-c]

Yep, I can confirm that after installing pycosat, at least with the two hash seeds in the examples above I see the "fast" seed go down from ~4 seconds to ~3 seconds, and more importantly the "slow" seed drops from around ~75 seconds to ~3 seconds too.

Without pycosat

$ pip show pycosat
WARNING: Package(s) not found: pycosat

$ time env PYTHONHASHSEED=2821703311 cfn-lint --ignore-checks W1001 E3003 -- ~/nested-if-condition.yml # fast seed

real    0m3.777s
user    0m3.587s
sys     0m0.170s

$ time env PYTHONHASHSEED=1356847902 cfn-lint --ignore-checks W1001 E3003 -- ~/multiply-equals2.yml.txt # slow seed

real    1m18.433s
user    1m17.580s
sys     0m0.528s

With pycosat

$ pip install --user pycosat
Collecting pycosat
  Using cached pycosat-0.6.6-cp312-cp312-linux_x86_64.whl
Installing collected packages: pycosat
Successfully installed pycosat-0.6.6

$ time env PYTHONHASHSEED=2821703311 cfn-lint --ignore-checks W1001 E3003 -- ~/nested-if-condition.yml # fast seed

real    0m2.964s
user    0m2.708s
sys     0m0.240s

$ time env PYTHONHASHSEED=1356847902 cfn-lint --ignore-checks W1001 E3003 -- ~/multiply-equals2.yml.txt # slow seed

real    0m3.060s
user    0m2.826s
sys     0m0.216s

[kddejong]

I've been debating including it as a dependency based on this improvement