1

I have been interested in arbitrary precision math for some years but have dabbled in languages other than Swift (Livecode, C++ , Xojo ...). I decided a few months back to finally learn swift and I located the BigInteger library:

I had completed my own Swift module and though it was going well but the above library was much better coded and had much better performance. So I moved my high level code to that library. My main interest is number theory and in particular factorization. I found the multiple polynomial quadratic sieve prime factorization python code below.

and migrated it to Swift. It worked great but I had hoped for better performance. I compared the performance of the code running in Python 3.8 versus Swift and found that Python was about twice as fast. Running the code in Python using the PyPy JIT compiler made the Python code about 12x as fast. Code that I had profiled before in Sage ran about 100x as fast as Swift code.

A few observations: I made a modular inverse function that uses shifts and it made the Swift code about 20% faster but made the Python code considerably slower. I believe that this indicates that the BigInt library has a much slower big integer divide function than Python.

I have also discovered that Sage which depends on sympy is moving to symengine which is a C++ wrapper around the boost C++ library.

My final thoughts are that Swift is never going to have fast numerics until it wraps very good numerics code such as boost. Libraries (modules) written in pure Swift will continue to be too slow to be competitive. My two cents.

2

This should never be Swift's goal. If a native Swift implementation isn't fast enough, the language should be improved, it shouldn't just default to wrapping other libraries. I doubt Apple would even allow it in the first place, except for closed source libraries on Apple's platforms (like CryptoKit).

Also, feel free to post your benchmarks.

6 Likes
3

At a glance, it looks like none of the code inside the BigInt module is marked as @inlinable, so unlike C++ or PyPy, there is missed opportunity for the BigInt code to be optimized into your own binary because of the compilation unit boundary. It might be interesting to try LTO to see if it has any impact on the Swift performance. As Swift's build system itself grows to support more cross-module optimization, and as the compiler implementation improves with better ARC optimization, then you'll probably see more comparable performance with C++ or PyPy over time.

3 Likes
4

In addition, it seems inappropriate to judge the theoretical performance of all native Swift libraries based on the performance of a single library that may or may not have seen much performance tuning.

13 Likes
5

For this interested in experimenting and giving early feedback (usual caveats about work-in-progress don't rely on it etc etc), this PR introduced cross-module optimization behind a compiler flag on master recently.

4 Likes
6

In its current form, it doesn't look like that PR will directly benefit this BigInt package, since it's mostly non-generic, and that flag is currently focused on unlocking generic specialization across modules rather than more general interprocedural optimization.

7

There was a pretty compelling talk at the recent LLVM conference about annotated headers (stuff like readonly) giving many of the same benefits as LTO.

Since all of our cross-module interfaces are generated by the compiler, that also seems like some low-hanging fruit for unlocking cross-module optimisations.

8

I flagged that one just because it's the PR that adds the compiler flag ā€“ the goal is for it to drive both kinds of optimization.

9

Swift already gets a lot of this semantics for free, because arguments in Swift are inherently required not to alias or be mutated outside of the callee's control. A lot of our optimizer work this year is geared toward exploiting these properties more thoroughly.

7 Likes
10

This is something Iā€™ve long been hoping for. With each new release of Swift I comb the release notes for any sign of it. I say this because it would be a very valuable thing to have explained in the Swift blog when it is closer to appearing in a stable release. It will be particularly useful to know which things it affects, and in when it will be available. I donā€™t want to miss the memo and continue handā€tailoring @inlinable in packages after the compiler has taken over that responsibility.

3 Likes
11

@rothomp3 has a pull request for another BigInt type:

https://github.com/apple/swift-numerics/pull/84

12

Yes, and I'm actively accepting feedback on that PR, so please everyone have a look haha!

edit: also, some of it is marked as @inlinable, but probably more could be.