# Munchausen benchmark

**URL:** <https://forums.swift.org/t/munchausen-benchmark/69798>\
**Category:** Using Swift\
**Tags:** benchmarks\
**Created:** [February 2, 2024, 4:38pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798 "2024-02-02T16:38:34Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Finagolfin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/finagolfin/32/34388_2.png) [@Finagolfin](https://forums.swift.org/u/Finagolfin)\
**Post date:** [February 2, 2024, 4:38pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/1 "2024-02-02T16:38:34Z")

</div>

I saw [this simple integer benchmark](https://github.com/jabbalaci/SpeedTests) on lobste.rs and [just submitted a Swift version](https://github.com/jabbalaci/SpeedTests/pull/46). If you see any way to speed it up, let me know. Purely aesthetically, I didn't like that I had to do the two numeric conversions and that I couldn't [initialize the cached array at compile-time, as in Zig](https://github.com/jabbalaci/SpeedTests/blob/master/zig/src/main.zig#L6), though maybe that is possible now with a macro? Clean-up and speed-up patches welcome.

---

<div class="post-metadata">

**Author:** ![hassila](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hassila/32/22647_2.png) [@hassila](https://forums.swift.org/u/hassila)\
**Post date:** [February 2, 2024, 5:41pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/2 "2024-02-02T17:41:02Z")

</div>

Which platform did you test on? On M3 Max I get basically the same result as C:

```bash
hassila@min ~/S/swift (master)> time ./main
0
1
3435
438579088

________________________________________________________
Executed in 1.35 secs fish external
   usr time 1.33 secs 0.24 millis 1.33 secs
   sys time 0.01 secs 2.29 millis 0.00 secs

```

```bash
hassila@min ~/S/c (master)> time ./main
0
1
3435
438579088

________________________________________________________
Executed in 1.32 secs fish external
   usr time 1.30 secs 0.24 millis 1.30 secs
   sys time 0.01 secs 1.72 millis 0.01 secs

hassila@min ~/S/c (master)> 

```

---

<div class="post-metadata">

**Author:** ![Finagolfin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/finagolfin/32/34388_2.png) [@Finagolfin](https://forums.swift.org/u/Finagolfin)\
**Post date:** [February 2, 2024, 6:00pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/3 "2024-02-02T18:00:37Z")

</div>

> [@hassila](#):
>
> Which platform did you test on?

Linux x86\_64 and Android AArch64, using the native OSS toolchain for each.

---

<div class="post-metadata">

**Author:** ![wadetregaskis](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/wadetregaskis/32/8494_2.png) [@wadetregaskis](https://forums.swift.org/u/wadetregaskis)\
**Post date:** [February 2, 2024, 6:20pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/4 "2024-02-02T18:20:59Z")

</div>

The most obvious overhead is bounds checking on the `Array` subscripting. Removing those (via `withUnsafeBufferPointer`) improves performance by about 12% on an M2 MacBook Air, i.e. gives you the same performance with `-O` as your version does with `-Ounchecked`.

That makes it pretty much exactly as fast as the C version.

```swift
let MAX: UInt = 440_000_000

var cache: [UInt] = [0, 1, 4, 27, 256, 3_125, 46_656, 823_543, 16_777_216, 387_420_489]

cache.withUnsafeBufferPointer { fastCache in
    func is_munchausen(number: UInt) -> Bool {
        var n = number
        var total: UInt = 0

        while n > 0 {
            total += fastCache[Int(n % 10)]

            if total > number {
                return false
            }

            n /= 10;
        }

        return total == number
    }

    for k in 0..<MAX where is_munchausen(number: k) {
        print(k)
    }
}

```

There's no benefit to using 32-bit arithmetic instead of native word width (exactly the same instruction latency and throughput, on Apple Silicon). So I switched to native word width. It does mean the cache is technically twice the size, but it still trivially fits into lowest-level cache since it's a fixed 10 entries.

The conversion to `Int` is also easier then, although really it doesn't cost anything either way (the compiler seems to permit a straight reinterpretation of the value, without any bounds checking - i.e. the same results as if you used `Int(bitPattern:)` manually).

Precalculating the cache ahead of compile time doesn't make any meaningful difference on performance, but it makes the code simpler.

 ![Time Profile](https://global.discourse-cdn.com/swift/original/3X/e/b/ebe6c0042ae84d75ea62708cf8bc2a2b873826fd.png)

I tried a few other things, but nothing made a meaningful difference. It's not immediately apparent to me how to optimise the remaining hotspots (the inner loop comparisons and cache lookup (that annoying `ldr` - the whole cache could fit into unused registers, but I don't know how to make the compiler realise that nor if it'd actually be usable that way, as AArch64 doesn't (to my knowledge) have a version of `ldr` that indexes the register space rather than memory space).

---

<div class="post-metadata">

**Author:** ![jaleel](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jaleel/32/45076_2.png) [@jaleel](https://forums.swift.org/u/jaleel)\
**Post date:** [February 2, 2024, 7:33pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/5 "2024-02-02T19:33:02Z")

</div>

Also noticed readme in repo mentions size of a file, maybe someone can try Embedded Swift to check? 🙃

---

<div class="post-metadata">

**Author:** ![wadetregaskis](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/wadetregaskis/32/8494_2.png) [@wadetregaskis](https://forums.swift.org/u/wadetregaskis)\
**Post date:** [February 2, 2024, 7:34pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/6 "2024-02-02T19:34:26Z")

</div>

Nothing I did to the `swiftc` arguments could convince it to vectorise this, even though it feels like it should be vectorisable.

So, I took a crude stab at manually vectorising this for NEON, but the result is 25% slower than the scalar version. I suspect because it's not utilising NEON well (the generated assembly looks pretty horrific in general, and I couldn't figure out any way to generate a vector gather instruction).

I posit that this'd work substantially better with SVE2, but unless I really missed something, none of Apple's chips support SVE at all. 😔

```swift
let MAX: UInt32 = 440_000_000

var cache: [UInt32] = [0, 1, 4, 27, 256, 3_125, 46_656, 823_543, 16_777_216, 387_420_489]

cache.withUnsafeBufferPointer { fastCache in
    func is_munchausen(numbers: SIMD4<UInt32>) -> SIMDMask<SIMD4<UInt32>.MaskStorage> {
        var n = numbers
        var totals = SIMD4<UInt32>(repeating: 0)

        while any(n .> 0 .& totals .<= numbers) {
            let remainders = n % 10
            n /= 10;

            totals &+= SIMD4(fastCache[Int(remainders.x)],
                             fastCache[Int(remainders.y)],
                             fastCache[Int(remainders.z)],
                             fastCache[Int(remainders.w)])
        }

        return totals .== numbers
    }

    assert(0 == MAX % 4)

    for k in stride(from: 0, to: MAX, by: 4) {
        let numbers = SIMD4(k, k + 1, k + 2, k + 3)
        let matches = is_munchausen(numbers: numbers)

        for i in matches.indices {
            if matches[i] {
                print(numbers[i])
            }
        }
    }
}

```

I was really surprised by how much I had to baby the compiler, when using the SIMDn types. It feels like the optimiser takes a holiday as soon as it sees one. e.g. I had to manually rearrange the vectorised conditionals (re. the inner loop) to avoid a hefty performance loss. I suspect part of this is the inherent nature of SIMD (being more sensitive than scalar code, because the instructions are intrinsically heavier) but still, it felt like the compiler wasn't entirely pulling its weight.

P.S. I also made an eight-wide version, but it performed nearly twice as bad. Surprisingly, I can't seem to actually find _any_ tech specs for Apple's M2 indicating what it supports re. NEON and vector widths and all that (is NEON fixed 128? It seems like that from glancing at the AArch64 docs from Arm, but that seems really surprising to me).

---

<div class="post-metadata">

**Author:** ![scanon](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/scanon/32/2445_2.png) [@scanon](https://forums.swift.org/u/scanon)\
**Post date:** [February 2, 2024, 8:42pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/7 "2024-02-02T20:42:22Z")

</div>

Yes, NEON is fixed-width 128b vectors. SVE is ARM's scalable vector extension. The ARM ARM goes into quite a bit more detail for the curious.

This is not a great operation for SIMD optimization, because integer division and remainder are not implemented in SIMD on any ISA. This can be worked around by you (or the compiler) replacing them with multiply-high arithmetic sequences, but you then want to do a table lookup which could almost be a PSHUFB/TBL but doesn't quite fit in register and requires splatting out lookup indices and none of that stuff maps into a cross-platform abstraction very nicely, so you really want to write intrinsics (which you can totally do).

This is all totally surmountable, but it's not a nice tidy SIMD demonstration problem.

---

<div class="post-metadata">

**Author:** ![wadetregaskis](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/wadetregaskis/32/8494_2.png) [@wadetregaskis](https://forums.swift.org/u/wadetregaskis)\
**Post date:** [February 2, 2024, 9:55pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/8 "2024-02-02T21:55:36Z")

</div>

> [@scanon](#):
>
> This is not a great operation for SIMD optimization, because integer division and remainder are not implemented in SIMD on any ISA.

Ah, I did wonder about that; I noticed a lack of vectorised forms of those in the output.

It seems very weird, then, that Swift's SIMD types have division & modulus operators even for integer elements. It gives the wrong idea.

---

<div class="post-metadata">

**Author:** ![carlynorama](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlynorama/32/27072_2.png) [@carlynorama](https://forums.swift.org/u/carlynorama)\
**Post date:** [February 2, 2024, 10:19pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/9 "2024-02-02T22:19:48Z")

</div>

Try with `reservedCapactiy`?

```swift
let divisor = 10
var cache : [UInt32] = [0, 1, 4]
cache.reserveCapacity(divisor)

```

and then replace magic number 10 with divisor.

I'd be curious if that helps with the bounds checking issue.

EDIT: @hassila LOL - of course! Fixed. I was comparing against the C which needed them, it's hard when you keep switching. I need to get serious about using SwiftLint.

---

<div class="post-metadata">

**Author:** ![hassila](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hassila/32/22647_2.png) [@hassila](https://forums.swift.org/u/hassila)\
**Post date:** [February 2, 2024, 10:30pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/10 "2024-02-02T22:30:15Z")

</div>

(And (very) tiny nit, I’d drop the semicolons :-) )

---

<div class="post-metadata">

**Author:** ![wadetregaskis](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/wadetregaskis/32/8494_2.png) [@wadetregaskis](https://forums.swift.org/u/wadetregaskis)\
**Post date:** [February 2, 2024, 11:07pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/11 "2024-02-02T23:07:07Z")

</div>

`reserveCapacity` doesn't change the valid bounds of the array. It's merely a hint regarding the underlying memory allocation. The compiler would still need to be convinced that those extra 7 indices were actually initialised (appended to the array).

---

<div class="post-metadata">

**Author:** ![carlynorama](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlynorama/32/27072_2.png) [@carlynorama](https://forums.swift.org/u/carlynorama)\
**Post date:** [February 2, 2024, 11:34pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/12 "2024-02-02T23:34:46Z")

</div>

How about getting the static result from a function and hoping that COW means that the compiler still has the pointer location for count in its hot little hands when it goes to modulo?

```swift
let cache : [UInt32] = setCache()
let divisor = cache.count  

func setCache() -> [UInt32] {
    //removing the o,1,4 because no one else does that.
    var cache:[Int] 
    //cache.reserveCapacity(10) ?
    for i in 0...9 {
        var power = 1
        for _ in 0..<i { power *= i }
        cache.append(UInt32(power))
    }
    return cache
}

```

That's along the lines of what the [C code does](https://github.com/jabbalaci/SpeedTests/blob/master/c/main.c).

And [rust uses an inout](https://github.com/jabbalaci/SpeedTests/blob/master/rust/src/main.rs). Not sure what that'd get us.

```swift
func is_munchausen(number : UInt32, cache:inout [UInt32]) -> Bool

```

Julia, another top performer [has @inbounds](https://github.com/jabbalaci/SpeedTests/blob/master/julia/main.jl), which would be comprable to using the `.withUnsafe` of current Swift, I think.

---

<div class="post-metadata">

**Author:** ![tera](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tera/32/38201_2.png) [@tera](https://forums.swift.org/u/tera)\
**Post date:** [February 2, 2024, 11:46pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/13 "2024-02-02T23:46:19Z")

</div>

Two ideas:

- quotientAndRemainder(dividingBy: 10)

- make an array 256 entries long (padding it by some garbage at the end) and form the index as UInt8 number (further casted to Int to usable as array subscript) – the number that can't possible go outside array boundaries. In this case bound checks should disappear.

---

<div class="post-metadata">

**Author:** ![wadetregaskis](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/wadetregaskis/32/8494_2.png) [@wadetregaskis](https://forums.swift.org/u/wadetregaskis)\
**Post date:** [February 3, 2024, 2:01am UTC](https://forums.swift.org/t/munchausen-benchmark/69798/14 "2024-02-03T02:01:26Z")

</div>

> [@tera](#):
>
> quotientAndRemainder(dividingBy: 10)

I tried that. The compiler is smart enough to produce basically the same result with the code as-is - maybe even identical, I didn't diff the disassembly. Certainly it makes no measurable difference on performance.

For the built-in integer types it's probably always fine, but `quotientAndRemainder(dividingBy:)` can be quite slow, e.g. for BigInt implementations.

---

<div class="post-metadata">

**Author:** ![Finagolfin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/finagolfin/32/34388_2.png) [@Finagolfin](https://forums.swift.org/u/Finagolfin)\
**Post date:** [February 3, 2024, 7:23am UTC](https://forums.swift.org/t/munchausen-benchmark/69798/15 "2024-02-03T07:23:45Z")

</div>

> [@wadetregaskis](#):
>
> There's no benefit to using 32-bit arithmetic instead of native word width (exactly the same instruction latency and throughput, on Apple Silicon). So I switched to native word width. It does mean the cache is technically twice the size, but it still trivially fits into lowest-level cache since it's a fixed 10 entries.

On linux x86\_64, my version is about 10% faster than yours, probably because of the 32-bit usage. If I simply modify my version to remove all use of `UInt32`, thus defaulting to `Int`, it slows down another 10% on top of yours.

On Android AArch64, I see no difference between my two versions, but yours is still slower than both. 🤷

Try them out on x86\_64 and let me know what you find.

---

<div class="post-metadata">

**Author:** ![hassila](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hassila/32/22647_2.png) [@hassila](https://forums.swift.org/u/hassila)\
**Post date:** [February 3, 2024, 10:16am UTC](https://forums.swift.org/t/munchausen-benchmark/69798/16 "2024-02-03T10:16:32Z")

</div>

Added a version using swift concurrency too for fun as there was a subdirectory with such implementations:

> <https://github.com/finagolfin/SpeedTests/pull/1>

Measuring on my laptop, reference implementation in swift:

```swift
hassila@min ~/S/swift (master)> hyperfine ./main --warmup 2 --runs 10
Benchmark 1: ./main
  Time (mean ± σ): 1.404 s ± 0.005 s [User: 1.398 s, System: 0.002 s]
  Range (min … max): 1.399 s … 1.414 s 10 runs

```

Concurrent one:

```swift
hassila@min ~/S/_/swift (master)> hyperfine ./main --warmup 2 --runs 10
Benchmark 1: ./main
  Time (mean ± σ): 116.3 ms ± 2.8 ms [User: 1731.8 ms, System: 4.3 ms]
  Range (min … max): 113.5 ms … 123.4 ms 10 runs

```

---

<div class="post-metadata">

**Author:** ![adam-fowler](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/adam-fowler/32/9266_2.png) [@adam-fowler](https://forums.swift.org/u/adam-fowler)\
**Post date:** [February 3, 2024, 11:00am UTC](https://forums.swift.org/t/munchausen-benchmark/69798/17 "2024-02-03T11:00:49Z")

</div>

`is_munchausen` is doing a modulus and a divide. You can use the result from the divide to avoid doing the modulus.

```swift
func is_munchausen(number: UInt32) -> Bool {
    var n = number
    var total: UInt32 = 0
    while n > 0 {
        let p = n / 10
        total += cache[Int(n - p * 10)]
        if total > number {
            return false
        }
        n = p
    }

    return total == number
}

```

Gave me an improvement from 1.79s to 1.43s. Although I'm not sure that would be allowed as the repo owner states

> In the implementations I tried to use the same (simple) algorithm in order to make the comparisons as fair as possible.

---

<div class="post-metadata">

**Author:** ![wadetregaskis](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/wadetregaskis/32/8494_2.png) [@wadetregaskis](https://forums.swift.org/u/wadetregaskis)\
**Post date:** [February 3, 2024, 4:24pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/18 "2024-02-03T16:24:51Z")

</div>

> [@adam-fowler](#):
>
> You can use the result from the divide to avoid doing the modulus.

That makes the `UInt` version nearly 10% slower (on an M2), but it does improve the `UInt32` version by about 14%.

---

<div class="post-metadata">

**Author:** ![hassila](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hassila/32/22647_2.png) [@hassila](https://forums.swift.org/u/hassila)\
**Post date:** [February 5, 2024, 3:44pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/19 "2024-02-05T15:44:43Z")

</div>

Results that are comparable by running on the repos reference machines was published after @Finagolfin PR was merged just now:

> **[GitHub - jabbalaci/SpeedTests: comparing the execution speeds of various...](https://github.com/jabbalaci/SpeedTests)**
>
> comparing the execution speeds of various programming languages - GitHub - jabbalaci/SpeedTests: comparing the execution speeds of various programming languages

and

> <https://github.com/jabbalaci/SpeedTests/tree/master/_parallel>
>
> //github.com/jabbalaci/SpeedTests/tree/master/\_parallel

C with clang and Rust is faster, while C++ is slightly slower for the single-threaded case  
Rust is slightly faster in the multi-core case, but not too bad.

In terms of binary size Swift beats all three of those...

Not too shabby (albeit a very limited test of course).

---

<div class="post-metadata">

**Author:** ![ksluder](https://avatars.discourse-cdn.com/v4/letter/k/eada6e/32.png) [@ksluder](https://forums.swift.org/u/ksluder)\
**Post date:** [February 5, 2024, 4:55pm UTC](https://forums.swift.org/t/munchausen-benchmark/69798/20 "2024-02-05T16:55:30Z")

</div>

I’m curious why the `cache` initializer went from 10 values to 3?

[Next page](https://forums.swift.org/t/munchausen-benchmark/69798.md?page=2)