I was implementing an
algorithm in Swift Beta and noticed that the performance was very poor. After digging
deeper I realized that one of the bottlenecks was something as simple as sorting arrays.
The relevant part is here:
let n =
1000000
var x = [Int](repeating: 0, count: n)
for i in 0.. {
x[i] = random()
}
// start clock here
let y =
sort(x)
// stop clock
here
In
C++, a similar operation takes 0.06s on my
computer.
In Python, it takes
0.6s (no tricks, just y = sorted(x) for a list of
integers).
In Swift it takes
6s if I compile it with the following
command:
xcrun swift -O3 -sdk
`xcrun --show-sdk-path --sdk
macosx`
And
it takes as much as 88s if I compile it with the following
command:
xcrun swift -O0 -sdk
`xcrun --show-sdk-path --sdk
macosx`
Timings in
Xcode with "Release" vs. "Debug" builds are
similar.
What is wrong here? I could understand
some performance loss in comparison with C++, but not a 10-fold slowdown in comparison
with pure Python.
/>
Edit: weather noticed
that changing -O3
to -Ofast
makes this
code run almost as fast as the C++ version! However, -Ofast
changes the semantics of the language a lot — in my testing, it disabled
the checks for integer overflows and array indexing overflows. For
example, with -Ofast
the following Swift code runs silently
without crashing (and prints out some
garbage):
let n =
10000000
print(n*n*n*n*n)
let x = [Int](repeating: 10, count:
n)
print(x[n])
So
-Ofast
is not what we want; the whole point of Swift is that we
have the safety nets in place. Of course, the safety nets have some impact on the
performance, but they should not make the programs 100 times slower. Remember that Java
already checks for array bounds, and in typical cases, the slowdown is by a factor much
less than 2. And in Clang and GCC we have got -ftrapv
for
checking (signed) integer overflows, and it is not that slow,
either.
Hence the question: how can we get
reasonable performance in Swift without losing the safety
nets?
/>
Edit 2: I did some more
benchmarking, with very simple loops along the lines
of
for i in 0..
x[i] = x[i] ^
12345678
}
(Here
the xor operation is there just so that I can more easily find the relevant loop in the
assembly code. I tried to pick an operation that is easy to spot but also "harmless" in
the sense that it should not require any checks related to integer
overflows.)
Again, there was a huge difference
in the performance between -O3
and
-Ofast
. So I had a look at the assembly
code:
With
-Ofast
I get pretty much what I would expect. The relevant part
is a loop with 5 machine language
instructions.With
-O3
I get something that was beyond my wildest imagination. The
inner loop spans 88 lines of assembly code. I did not try to understand all of it, but
the most suspicious parts are 13 invocations of "callq _swift_retain" and another 13
invocations of "callq _swift_release". That is, 26 subroutine calls in the
inner
loop!
/>
Edit 3: In comments,
Ferruccio asked for benchmarks that are fair in the sense that they do not rely on
built-in functions (e.g. sort). I think the following program is a fairly good
example:
let n =
10000
var x = [Int](repeating: 1, count: n)
for i in 0.. {
for j in 0..
x[i] = x[j]
}
}
There is
no arithmetic, so we do not need to worry about integer overflows. The only thing that
we do is just lots of array references. And the results are here—Swift -O3 loses by a
factor almost 500 in comparison with
-Ofast:
- C++ -O3:
0.05 s - C++ -O0: 0.4
s - Java: 0.2
s - Python with PyPy: 0.5
s - Python: 12
s - Swift -Ofast: 0.05
s - Swift -O3: 23
s - Swift -O0: 443
s
(If you are concerned
that the compiler might optimize out the pointless loops entirely, you can change it to
e.g. x[i] ^= x[j]
, and add a print statement that outputs
x[0]
. This does not change anything; the timings will be very
similar.)
And yes, here the Python
implementation was a stupid pure Python implementation with a list of ints and nested
for loops. It should be much slower than unoptimized Swift.
Something seems to be seriously broken with Swift and array
indexing.
/>
Edit 4: These issues
(as well as some other performance issues) seems to have been fixed in Xcode 6 beta
5.
For sorting, I now have the following
timings:
- clang++ -O3: 0.06
s - swiftc -Ofast: 0.1
s - swiftc -O: 0.1 s
- swiftc:
4 s
For nested
loops:
- clang++ -O3: 0.06
s - swiftc -Ofast: 0.3
s - swiftc -O: 0.4
s - swiftc: 540
s
It seems that there is
no reason anymore to use the unsafe -Ofast
(a.k.a.
-Ounchecked
); plain -O
produces
equally good code.
No comments:
Post a Comment