High Performance Numeric Programming with Swift: Explorations and Reflections
fast.ai
fast.ai
”1. Accessing any value at a particular index in an array is at worst O(log n), but should usually be O(1).
2. Searching for an object at an unknown index is at worst O(n (log n)), but will generally be O(n).
3. Inserting or deleting an object is at worst O(n (log n)) but will often be O(1). These guarantees subtly deviate from the simple “ideal” array that you might expect from a computer science textbook or the C language, where an array is always a sequence of items laid out contiguously in memory”
If you want a more traditional data structure, use ContiguousArray, which is an array. https://developer.apple.com/documentation/swift/contiguousar...:
”The ContiguousArray type is a specialized array that always stores its elements in a contiguous region of memory. This contrasts with Array, which can store its elements in either a contiguous region of memory or an NSArray instance if its Element type is a class or @objc protocol”
If I have an array of ints, is it contiguous?
Especially with modern computers and how importance data locality is the name "array" is kind of sacred. If you want a fancy weird-non array give THAT the longer, annoying name.
I find Julia's core design to be excellent for general purpose programming, better than python in fact since it essentially solves the expression problem with it's type system and multiple dispatch.
It's external program interop is also more pleasant than Python's :https://docs.julialang.org/en/v1/manual/running-external-pro...
Sure, it doesn't have the same general library ecosystem, but even that is being remedied for core areas like web programming: http://genieframework.com/ (a full MVC framework), https://github.com/JuliaGizmos/WebIO.jl (write front end code without javascript) and I'm particularly excited for https://github.com/Keno/julia-wasm, which will allow Julia programs to be compiled for the browser.
For any packages than are python only, it has excellent python interop using the pycall.jl package, which even allows users to write custom python classes in Julia.
With regards to numerical programming, it's obviously already far ahead of swift, and IMO much better placed to beat it in the long run. For example the WIP zyogte package is able to hook into Julia's compiler to zero overhead diff arbitrary code. Using Cassette.jl, package authors can write custom compiler passes outside the main repo and in pure Julia: https://julialang.org/blog/2018/12/ml-language-compiler
In addition, it's macro system, introspection, dynamic typing and value types through abstract typing approach allows for natural development of advanced probabilistic programming languages: https://github.com/TuringLang/Turing.jl, https://github.com/probcomp/Gen, https://github.com/zenna/Omega.jl/pulse
Still missing some verbs, but these will be added.
Although I have done some work to make thing fast see: https://github.com/xiaodaigh/FastGroupBy.jl. I have yet to update it to Julia v1. Hopefully, I will get to that soon. However, the improvement I have made only works for grouping up to 2 group-by variables and I need to learn more about generated functions to make the code more generic. So from my (someone who's actually spent time trying to optimise these data operations) perspective, Julia will take a while to catch up. Hats off to the data.table crew!
C++ of course works fine for this but I imagine Swift would be less terrifying to use.
https://github.com/dyu/ffi-overhead
(For those interested, the order of the first few languages is: lua-jit, julia, c(!), c++, zig, nim, d in order of decreasing speed.)
It's extremely well thought out, concise, powerful, and readable. I think Julia's approach to types and multiple dispatch is a better alternative to traditional OO programming.
One thing the author didn't point out is that C++ (clang), Swift, Rust and Julia all use the LLVM infrastructure, resulting in extremely similar if not identical code generation. If datacenter efficiency truly becomes a priority, highly efficient languages like Julia, Rust and Swift will see increasing use for general purpose programming.
https://juliacomputing.com/blog/2016/02/09/static-julia.html https://github.com/JuliaComputing/static-julia https://github.com/JuliaComputing/llvm-cbe
Julia's secret sauce is LLVM. Considering the guy behind Swift also made LLVM, I'm inclined to think that Swift will come out ahead.
(I know that to you specifically the fact that the ability to choose the starting index is not builtin means it doesn't matter, but I point it out for others who might not know that it's easy to do in Julia.)
That most certainly is not true. See this for example: https://arxiv.org/pdf/1810.09868.pdf
The point is that Julia's design, type system and multiple dispatch facilitates writing dynamic yet highly optimized code for a variety of backends, even those requiring static semantics (unlike LLVM).
There is no way you can look at that paper (or the Flux ecosystem, or the prob programming languages or the SSA IR autodiff) and chalk up Julia's success to just LLVM.
My point is about making JIT a standard feature of CPython.
JavaScript, Dylan, Smalltalk, SELF, Common Lisp aren't less dynamic than Python.
You either need to change the semantic of the language (CPython) or live with a slow JIT for some of the most used features of the language... And changing the semantic of the language is pretty terrible - it fragments your libraries introduces unbreakable borders prohibiting cross package optimizations and extensability, and much worse, CPython is now basically a language that combines the bad stuff of python and C ;) I know, that's a bit too cynical, but coming from a well designed language for JIT (Julia), that's how CPython starts looking to me. You will simply never reach the elegance of a language that was designed from scratch for this.
What I want to point out is, that the whole topic is bigger than "JIT my one slow function and make it fast"! A good read about this topic is: http://www.stochasticlifestyle.com/why-numba-and-cython-are-...
For example in Smalltalk, you can destroy all JIT assumptions about a given object by sending a become: message.
I see (and agree with) your point about worse non-numeric stuff, but if you stand back and squint I get the impression Julia does most of what you applaud here, with the added benefits of a more transparent compiler and a more numeric-focused community (no need for BasicMath there!).
In particular, Flux.jl seems like a fairly direct competitor of S4TF, and this blogpost [0] really blew me away.
[0] https://www.julialang.org/blog/2018/12/ml-language-compiler
Julia is much more mature for machine learning than Swift at this point. So it would be a better choice if you want something that's at least somewhat ready for use now - but I was really wanting to get in on the ground floor on something that's just getting started.
You've gotten into a place with a lot of unidiomatic designs--direct pointer access on COW types, etc.--and it's not clear how much is really necessary:
extension Array where Element:CanDoMath {
// instead of this style:
func sum_outside() -> Element {
var result = 0
let p = self.pointerToStorage // your "get the pointer" method, I think it was just `p`, too?
for i in 0..<count {
result += p[i]
}
return result
}
// how does this compare (in -unchecked mode, at least)?
func sum_inside() -> Element {
return self.withUnsafeBufferPointer() {
var result = 0
for v in $0 {
result += v
}
return result
}
}
}
For (b) if you're planning to call things that need particular alignments then as far as I know you will need to write your own storage at this time.
Thus we hadn't even considered just exposing the pointer and doing it C-style, whence the question as to whether you'd benchmarked the difference between the two.
The abstractions thing is hard, here, the key seems to be defining the bulk operations in terms of pointers (or Swift's "buffer pointers"), essentially what you have in your methods like `SupportsBasicMath.add` and so on. Abstraction is possible here by moving each "type signature"--destination & 1 source? destination & 2 sources? etc.--into "operation protocols", and then having fewer methods but a ton of "operation protocol implementations". Perhaps "more abstraction", definitely not concise. Very dependent on the compiler and inlining, too.
It's a good writeup nonetheless, was just asking a narrow question.
Because I couldn't find anything that provides that using the approach you are discussing, I didn't investigate its performance characteristics. For me, dev UX comes first, and I wouldn't personally be interested in reading or writing in a language that requires the "with" construct wrapping every calculation.
The bigger issue is that to overload a function in a manner similar to C++ you need to have accurate type information, which historically was not available in Objective C since it relies heavily on duck typing and casting objects back through id. If such strong type information was available then the type data could have simply been mangled into the selector by the compiler the same way it is mangled into the symbol name in C++. I suspect that duck typing allowed a lot of productivity and memory wins in the 90s, and that most compilers of the era were not capable of exploiting the strong typing information to optimize as aggressively as they do now, meaning that it was probably the right trade off for the time.
I suppose an alternative implementation of overloading could have been implemented by having objc_msgSend dynamically query the types of all parameters which are overloaded, but that would have resulted in a huge performance hit on every dynamic message dispatch.