Perfect example of an ineffective use of code
During one of the interactions around WWDC related to Swift Performance, an example was put forward as an good example of ineffective use of Swift code.
The article's title was inaptly named:
The article was related to solving the
4th Euler problem, the one about:
- Finding the largest palindrome made from the product of two 3-digit numbers
The conclusion reached in this article was that Swift was a lot slower than Python & Typescript, because his results were as follows:
- Python - 0.33 seconds
- Typescript - 0.85 seconds
- Swift - 22 seconds
Problem is like anything, the deliverable is only as good as the skill of the artisan and/or their understanding.
Here's his Python code for this:
Code:
answer = 0
for i in xrange(999, 100, -1):
for j in xrange(i, 100, -1):
k = i * j
s = str(k)
if s == s[::-1] and k > answer:
answer = k
print answer
This based on his measurements, took 0.33 seconds to complete.
... and here's his Swift code for this:
Code:
var answer = 0
var k = 0
var s = ""
for i in (100...999).reverse() {
for j in (100...i).reverse() {
k = i * j
s = String(k)
if s == String(s.characters.reverse()) && k > answer {
answer = k
}
}
}
print(answer)
The Swift version above, again based on his measurements, took 22 seconds to complete. OMG
So what's the problem with the Swift code?
Well quite a few things weren't even code related.
- Firstly he used Xcode's Swift Playground to run this "Performance Test"
- Secondly he didn't apply any compiler optimisation (see picture below for the settings that should have been applied)
Not changing anything, exception applying the compiler optimisations, dropped the result from 22 seconds to ~3.8 seconds.
Let's now review the code:
Ok, biggest issue is that he chose to use Swift Strings inside a loop to do a simple reverse comparison. We should ask why he chose to use such a complex type for such a simple task. Swift Strings are very powerful, but with that comes a very costly setup and teardown -- re its by design strongly tied to the heap.
He should rather have considered alternatives that stayed on the stack, specifically avoiding the heap if performance was the ultimate goal. Any of the following examples would have minimised or avoided the heap entirely:
- Convert to UTF8
- Use C Strings (far closer to the behaviour of python & its performance)
- Use modulus and Integer Array
- Use arithmetic routines
I chose the 4th approach i.e. believing the entire problem could be solved with some simple arithmetic. Success!:
- To find the largest palindrome made from the product of two 3-digit numbers: 0.5ms
- To find the largest palindrome made from the product of two 4-digit numbers: 63ms
UPDATE:
I decided to include an example that shows an approach with Swift String that is faster than his version, and to hopefully better highlight the problem with his code.
Code:
func isPalindrome(v: Int) -> Bool
{
let utf8 = String(v).utf8.map {$0.hashValue}
let mid = utf8.count / 2
for i in 0..<mid
{
if utf8[i] != utf8[utf8.count - 1 - i]
{
return false
}
}
return true
}
var answer = 0
var k = 0
var s = ""
for i in (100...999).reverse()
{
for j in (100...i).reverse()
{
k = i * j
if isPalindrome(k) && k > answer
{
answer = k
}
}
}
print(answer)
As you should hopefully see the major change is that I've created an isPalindrome function, which works by comparing the UTF8 hash values of characters at the start and end, progressively moving inwards until the midpoint.
Just this simple change has dropped the result from ~3.8 seconds to ~270ms i.e. faster than the Python and we're using String is a far more similar way to the Python code..
If you're still confused as to why his code was so much worse? Here's a few pointers to help:
- He uses String(...) initialisation twice, i.e. memory is malloc'd and released twice to perform a single number check.
- He also does a costly conversion from String to Character (+1 malloc), reverses (+1 malloc) and then back to String.
In conclusion:
I'm not advising you to specifically avoid Swift Strings, but rather to reason about when a particular type is most appropriate for the job at hand. Clearly for something as simple as this Euler problem, you should be looking elsewhere, especially if speed of execution is your goal.
Lastly, his conclusion that Swift was slow, was due to a simple lack of understanding.
If you're interested in understanding of
how to optimise your Swift code, then I suggest you start with some of the WWDC videos covering this:
Ps.
I've specifically chosen not to share my code, in the event you wanted to attempt this problem for yourself.
If however you'd like a copy of my code, just send me a PM.
Sign up with Google![[)roi(]](/forum/data/avatars/m/8/8711.jpg?1563828683){kind=avatar}
