Really Slow Array Performance

Hey

I decided to learn how to make Swift go fast :rocket:

I optimised my code with pointers and a lot more, inlining certain functions and so on, to the point where it's barely more readable than C and worse than Rust; the performance is not bad but unfortunately is still many times slower. :turtle:

Profiling the executable tells me that a lot of time is spent appending to arrays. The length of every array in my code is known ahead of time, no time is spent copying the arrays to double their size. I don't know what makes it so slow.
There seems to be an issue with String and Character types, even not doing anything my code can barely output 2mb/s

Even trying to join strings and characters together seems to decrease performance 20 times compared to just using print in a loop

I thought it could be because I'm converting [Character] to String but after rewriting everything with just Strings it's exactly the same :(

Am I doing something wrong or is the String type just really not optimised for speed at all

Hard to tell without seeing your code and/or the algorithm. As a guess there might be some "accidentally quadratic" behaviour in your string handling. If you can easily test your code on strings of different lengths you may even plot the time/length graph to see the actual curve.

The first question is: is your string content unicode or is it, say, ascii only which can modelled via a simpler (and faster) array of bytes? (Note that Character is a multibyte construct of unbound length, in theory you can have the whole war and peace contents in a single character.) Then, assuming it is unicode (user / place names, etc) what do you need to do with those? Finally, can you achieve what you want with the ready made methods like "join" / "components", "filter", etc? If yes - go for it.

1 Like

Here's a simplified version of the code:

@inlinable func returnCharacters() -> ContiguousArray<Character>? {
    let index:Int8 = .random(in: 1...10)
    switch index {
    case 1:
        let sequence:ContiguousArray<Character> = ["a","b","c","d"]
        return sequence
    case 2:
        let sequence:ContiguousArray<Character> = ["e","f","g"]
        return sequence
    case 3:
        let a:Int8 = .random(in: 2...8)
        let arrayPointer = UnsafeMutablePointer<ContiguousArray<Character>>.allocate(capacity:a)
        arrayPointer.initialize(to: [])
        for _ in 1...a {
            arrayPointer.pointee.append("a")
        }
        defer {
            arrayPointer.deallocate()
        }
        return arrayPointer.pointee
    case 4:
        ...

The reason these are arrays not String is because in a few cases the return is from a more complicated function that returns an array; testing with String as the return type:

return "abcd"

did not change the performance.

the main function looks like this:

@main

struct Main {
    static func main() {
        while true {
            let characters = returnCharacters()!
            print(String(characters), terminator: "")
        }
    }
}

the loop would only run while there's less than 100 characters and output the final result, but I changed it to run forever so that I can measure how much it can output in a second

edit:
I do not need unicode support

Array performance is likely not your problem. Character models Unicode extended grapheme clusters; this is a lot of functionality you’re not using but paying for in memory and time. If you’re working with an array of ASCII code points, use [UInt8], reserve your capacity ahead of time, and you can dispense with probably all of your pointer optimizations.

3 Likes

Yeah the pointers are not doing much right now they're just there to skip checking if the index is valid

How do I print ASCII though :eyes:

And, do I have to manually change every character in my code to UInt8, there's over 1500 lines of code

There's no ASCII type :pensive: It seems like a very useful thing that should just be there by default

So if I find and replace every Character("...") with Character("...").asciiValue, will that be converted at compile time?

Just to double check, because this happens a lot: have you verified that you’re compiling with optimization enabled?

Yeah I use swift build -c release

Ok so I replaced every string/character operation in my code with [UInt8]
I'm appending a 0 so it doesn't crash and then I:

print(cString: characters, terminator: "")

this is about 3x as fast, but still 10 times slower than I'd like it to be :smile:
I probably only need to optimise my algorithm now

Thanks for suggesting ASCII; it would be nice to have it as a type:

asciiString("abc") ; asciiChar("a")

Also related, this:

Character("a"); Character("a").asciiValue!

takes up a lot more space than:

'a' ; 'a'.asciiValue

is there a reason Swift doesn't include the character syntax from other C like languages?

Huh. Then stay away from String / Character types as far as possible.

Also instead of this:

I'd just write:

return [UInt8](repeating: ascii_a, count: a)

or if this is the actual code you only have 7 different strings from "a" to "aa...a" - perhaps no need to allocate it.

You can make one:

enum Ascii: UInt8 {
    case A = 0x41
    ...
    case a = 0x61
    ...
}

At the end it would be so extremely fast that the limiting factor would be the call to "random".

1 Like

It's not, the actual code already has values in the array and some cases have inline functions :slight_smile:

That's really useful thanks :smiley:
I'm new to creating types, what's the difference between enum and struct, I only used struct so far?
I would also love to replace Character("a") syntax with 'a' because I use characters a lot in my code

Pointers are not "go fast mode". I mean it; they really are not. Types such as Array are already pointers underneath.

There are ways to use naked pointers to improve the performance of certain code, but pointers themselves do not improve performance, and are much, much, much, much, much worse in terms of ensuring code is correct and free of undefined behaviour.

The reasoning should be something like, "by using a pointer, I can consume this data as multi-byte integers (or use some other bit-twiddling hacks), and I consistently measure a convincing performance improvement which is large enough to justify this burden".

It should not be "I want this code to be fast therefore pointers". What are you actually using these naked pointers for?

This code does not do what you likely expect. Again, since Array is already a pointer underneath, this is heap-allocating a pointer (not the memory it points to). I believe the intention is for defer to deallocate that memory after you return a pointer to it; it isn't actually doing that, which is fortuitous because it would be a use-after-free.

I would urge you to remove any code like this, and pointers altogether.

As others have alluded to, this is not an ideal way to populate an Array. I would advise using the repeating:count: initialiser. It is worth nothing that String also has one of these initialisers.

How large are these arrays?

If profiling shows an issue with your Array code, I would advise starting there. Why do you think it is related to String/Character at all?

String already optimises for ASCII contents. I wouldn't even worry about that unless there was clear profiling data which specifically showed an issue in particular string operations.

4 Likes

@Karl is right, writing C in swift syntax is almost never the way to go, if anything it inhibits certain compiler and LLVM optimizations because the optimizer can no longer make use of knowledge of swift semantics.

i wrote about this some time ago at Low-level Swift optimization tips

3 Likes
Try this
import Foundation

enum Ascii: UInt8 {
    case A = 0x41
    case B = 0x42
    case a = 0x61
    case b = 0x62
    case c = 0x63
    case d = 0x64
    case e = 0x65
    case f = 0x66
    case g = 0x67
    
    var char: Character {
        Character(Unicode.Scalar(rawValue))
    }
}

extension Array where Element == Ascii {
    var string: String {
        map { String($0.char) }.joined()
    }
    func dump() {
        print(string)
    }
}

func returnCharacters() -> [Ascii] {
    let index = Int.random(in: 1...10)
    switch index {
    case 1:
        return [.a, .b, .c, .d]
    case 2:
        return [.e, .f, .g]
    case 3:
        let n = Int.random(in: 2...8)
        return (1...n).map { _ in .a }
    default:
        return [.a]
    }
}

returnCharacters().dump()
print()
1 Like

Have your tried using Array.reserveCapacity? I’d argue that’s the bottleneck since you’re not taking advantage of knowing the size and the array has to double its size.

1 Like

I am already using it everywhere yeah

Have you tired using Array instead of ContiguousArray?

I removed the pointers and the performance is more or less the same

because the arrays are of characters, and the Character type has to support emoji so it's slow. I started using ascii and the performance more than doubled

I thought it would be faster because it doesn't need to do safety checking when writing to the array
it isn't so I removed it

wouldn't a shorter array be faster? I checked and using ascii is an improvement

Yeaaaah it caused a memory leak haha

Do you mean slower than an equivalent C version? It might be helpful to post a sketch of that code too, as this might explain some discrepancy between what you are doing with Swift and what you're doing in C.

This is pretty surprising, so it'd also be good to see a sketch of that code. Creating an array of characters, then parsing that back into a string to print, would indeed probably be pretty costly and a different approach would probably be recommended. It'd be interesting to see how you changed the code in your original post to return strings instead.

1 Like