Improvements to the Swift implementation

[odmir]

Hello! I am looking at the current Swift implementation of the sieve and have some changes in mind that in my machine lead to ~10x speed improvement. The thing is that I consider these changes to be relatively small, and since they don't change the algorithm in any way, I consider them unworthy of a separate solution.

The changes I'm considering are:

1. Changing the Dockerfile to use a more recent version of the language & Ubuntu 20.04 container instead of the current Ubuntu 18.04
2. Change the Bit count flag in the README to 8 bits since the implementation is using an array of booleans that each occupy 8 bits in memory, even if only one of those bits is used to represent the value (currently it's set to unknown)
3. Changes to PrimeSwift/solution_1/Sources/PrimeSieveSwift/main.swift:
   1. Delete the BitArray protocol definition (lines 3-7) that is unnecessarily being used as an existential and replace its use in line 33 by the concrete struct BoolBitArray that is already implemented
   2. Change PrimeSieveSwift from a class to a struct (at line 31) and make the runSieve method mutating (line 52) to indicate that the method mutates the struct
   3. Add the bits=8 tag to the program output at line 117
   4. Change the benchmark duration from 10 seconds to 5 at line 125, so the benchmark doesn't take any longer than needed

Then there are more "stylistic" changes that make the code more idiomatic:

1. Replace the use of an implicitly unwrapped optional (IUO) at line 123 by initialising the sieve variable to an empty sieve instead (var sieve: PrimeSieveSwift! -> var sieve = PrimeSieveSwift(limit: 0))
2. Replace the use of idx % 2 != 0 by the more descriptive and idiomatic !idx.isMultiple(of: 2)
3. Rename the PrimeSieveSwift type to PrimeSieve
4. Rename the bits property to the more descriptive name, isPrime
5. Change lines 15-28 in the BoolBitArray to be a pair of subscript getter and setter, keeping the indexing implementation the same, and changing every use of the bits property to use the subscript operator like bits[num] and bits[num] = false (at lines 45, 58, 64 and 103), instead of the current getBit and clearBit

My first question is if I should contribute this as a separate new solution or to the existing one.

The contribution guidelines say this under faithfulness:

It uses a class to encapsulate the sieve, or an equivalent feature in your language.

So my next question is if my change from a class to a struct falls under "equivalent feature". A C++ class is closer to a Swift struct than a Swift class, so I guess there is no issue here.

Thank you for your attention.

[tjol]

As I understand it (just as someone watching this)

• A pull request with changes that improve the performance will be welcomed
• Optimisations to existing solutions are preferred to new solutions
• Cosmetic changes that do not improve performance are not appropriate
• If there is a suitable construct called 'class' then this must be used. (This came up in relation to C# recently, which I think is similar to Swift in this regard)

[odmir]

Unfortunately the Swift compiler is probably having a really hard time having visibility into the class. It doesn't look like an issue with the time it takes to create a class, that should be negligible, but an issue with the optimisations the compiler is able to apply and thus leading to significantly suboptimal code generation. In this case, that small, insignificantly-looking change from class to struct (and adding the mutating before the method) results in a speed improvement of >2x. This is very likely missed optimisation opportunities in the compiler and I will be reporting the issue.

[rbergen]

The rule is meant to state that for languages that provide a class construct, that is the (only) way to go to have a faithful implementation, but alternatives are accepted where the class construct is not available. I think it is fair feedback on the phrasing that it currently is not fully clear/unambiguous, so I'll move to change the phrasing concerning this.

[tjol]

@odmir if accessing the properties of the class is the bottleneck (dynamic message passing overhead or something?), is it possible to just keep a local reference or pointer to the BitArray in the runSieve method instead of accessing the object property every time? (And a local copy of the sieve size)

[odmir]

That appears to improve performance very slightly (almost nothing compared to the 2x improvement, though). Something else must be causing such bad code generation. I can't really tell what it is, even after profiling nothing obvious jumps out. Anyway, this is an interesting finding and the compiler should be improved to handle this much better than it currently does.
I will later work on a PR to the solution with some of the other changes, taking into account the feedback here.

[Gouldsc]

I would argue that using a class instead of a struct in this context would be a violation of Swift’s language guidelines. Structs are always preferred unless required to facilitate reference semantics, inheritance, framework compatibility, etc. Structs behave very much like traditional classes in Swift, and 10/10 experienced Swift developers porting the original code would be using a struct regardless of the performance win. It would be an “unfaithful implementation” to use a data type in a manner that violates the language guidelines simply because it exists. This isn't an obscure hack to improve performance; it's how the language was designed to be used.

If the intent of the project is to showcase how the same problem is solved in various languages, it would be appropriate to do so in a manner that follows the usage guidelines for that language, instead of requiring nonidiomatic code.

As a general guideline, prefer structures because they’re easier to reason about, and use classes when they’re appropriate or necessary. In practice, this means most of the custom data types you define will be structures and enumerations.
Swift Language Guidelines

See also:
Swift Language Guideline “Choosing between structures and classes”

[odmir]

Thank you @rbergen for moving this to the right place, I hadn't noticed the discussions section.