u/dharmatechin r/swift • Recommends
Implementing Swift Generics - 2017 LLVM Developers Meeting
0:00 / 0:00
2017 LLVM Developers’ Meeting: “Implementing Swift Generics ”
LLVM
18K subscribers • 15 videos on Hallway
- Recommended by 4 people: 2 on Hacker News, 1 in engineering communities and 1 curated list.
- A classic. People kept recommending it from 2017 to 2022.
- Presented by Douglas Gregor, Slava Pestov, and John McCall
Advanced. Deep dive for people who know the field.
20K views9 years ago4 recommendations
Programming languagesSystems programmingSwiftCompilers and interpretersLanguage design and type systems
Douglas Gregor, Slava Pestov, and John McCall explain how the Swift compiler implements generics using a dictionary-passing approach with reified metadata.
LLVM.org/devmtg/2017-10/ — Implementing Swift Generics - Douglas Gregor, Slava Pestov and John McCall Slides: Coming Soon — Swift is a safe and efficient systems language with support for generic programming via its static type system. Various existing implementations of generic programming use either a uniform runtime representation for values (e.g., Java generics) or compile-time monomorphization (e.g., C++, Rust). Swift takes a “dictionary-passing” approach, similar to type-classes in Haskell, using reified type metadata to allow generic code to abstract over the memory layout of data types and avoid boxing. In this talk, we will describe the compilation of Swift’s generics from the type checker down to LLVM IR lowering and interaction with the Swift runtime, illustrating the how the core representation of generics flows through the system, from answering type-checking queries to the calling convention of generic functions and runtime representation of the “dictionaries”. — Videos Filmed & Edited by Bash Films: BashFilms.comWhy it's here
4 people recommend thisWhat people say. Recommended for its deep dive into how Swift's generics implementation differs from C++, Rust, and Java to support ABI stability.
programming-talkscurated list on GitHubRecommends
Under “Swift”
Implementing Swift Generics 00:44:37 by **Slava Pestov** (2017)
Veedracon Hacker News • Recommends
On “Type Erasure in Swift”
If you're interested, there's a very nice talk on how Swift's generics compile. It's different to Rust in some key ways. link to this video
favoritedon Hacker News • Recommends
On “Compiling Swift Generics [pdf]”
Swift's generics have some unique properties at module boundaries to allow for a stable ABI while enabling library evolution. To get additional background, you might be interested in this0 conference talk (the paper's author is one of the co-presenters). Also, this post1 by a Rust and Swift compiler engineer talks about what Swift does differently than other languages, and the tradeoffs that are involved. 0 link to this video 1 link
u/jdh30in r/ProgrammingLanguages • Mentions
On “Unboxed Types for OCaml”
Great to see people from the OCaml community talking about this!!! I have been raising this issue for a decade. However, frustrating that this presentation covers Lisp (1960) and C++ templates (1990) but none of the more recent and more widespread prior art in this area such as .NET 2.0 generics (2004) and Swift generics (2014) not least because they appear to me to be better than the solution proposed here.
.NET's solution to this problem has handled all hash tables efficiently since 2004. Compared to that, the advantages of this proposal are:
* Potentially faster compilation times.
And disadvantages:
* Less generic, e.g. this `HashTable64` only works with 64-bit keys whereas .NET's `Di…
u/theindigamerin r/ProgrammingLanguages • Mentions
On “Monomorphization vs. Boxing”
To add to this: here's a link to this video from the LLVM Developers Meeting which explains things quite a bit on how Swift generics are compiled.
There's also Compiling Polymorphism Using Intensional Type Analysis, which I believe is the first paper on intensional polymorphism. Following that, there was work on TIL which integrated that into a full blown ML. TIL includes "nearly tag-free GC" which means you can get unboxed stack allocated values without tags (object headers) - the CLR supports this today.
While TIL never quite took off, this retrospective provides insight for the future:
> Though performance was the initial focus, it soon became clear that the lasting idea was that we should be usi…
u/lngnsin r/ProgrammingLanguages • Mentions
On “What languages have protocols like Swift?”
The runtime behaviour is described in the ABI. This SO answer highlights the relevant bits.
TL;DR:
- Witness tables are generated and registered in a data section the Swift RTS dynamically reads from.
- Dynamic protocol types are passed around as very fat pointers with knowledge of those tables, and statically optimised for size.
Additionally, I did find this talk (which I have not watched yet), with those slides.
Now this was in 2017, and I have seen it mentioned that the compiler now performs monomorphisation in addition to Swift's runtime behaviours (and in addition to Objective-C's different runtime behaviours), including eliding indirections and boxing of associated types…
u/bjzabaPikelet, Unnamed Binary DDLin r/ProgrammingLanguages • Mentions
On “Implementing Generics via Passing Type Information at Runtime?”
I believe Swift tries to get the best of both worlds. There's a video on how it is implemented: link to this video - there are costs though, in terms of considerable implementation complexity. I haven't watched it in a while though, so I can't remember the details.
I'm still unsure how I want to handle this in Pikelet, seeing as I'm going to be using a non-uniform representation (like in C++ and Rust) and am representing bounded polymorphism by using dependent records. At the same time I also am supporting higher-rank polymorphism (Pikelet is dependently typed), so this makes things tricky.
favoritedon Hacker News • Mentions
On “Swift Project in 2023”
The Swift story around ABI stability and library evolution is pretty unique. Relatedly, its approach to generics doesn't fall into either of the 2 traditional paths (either box everything like Java and C#, or template instantiation like C++ or Rust). link link to this video
mananaysiempreon Hacker News • Mentions
On “A tail-call interpreter in (nightly) Rust”
> It doesn't make sense to me that an embedded VM/interpreter could ever outperform direct code. You're adding a layer of abstraction and indirection, so how is it possible that a more indirect solution can have better performance? It is funny, but (like I’ve already mentioned1 a few months ago) for serialization(-adjacent) formats in particular the preferential position of bytecode interpreters has been rediscovered again and again. The earliest example I know about is Microsoft’s MIDL, which started off generating C code for NDR un/marshalling but very soon (ca. 1995) switched to bytecode programs (which Microsoft for some reason called “format strings”; these days there’s also typelib m…
u/Dense-Buttonin r/ProgrammingLanguages • Mentions
On “Higher-order Zero-cost Abstractions”
I don't know but there's a great talk about swift generics floating around on YouTube. It doesn't get too detailed into what huerisrics are used to monomorphise but they do talk about some guaranteed optimizations that swift compiler makes to ensure performance of generic methods.
This is one of the most enlightening talk I've ever seen on the subject really.
link to this video
u/1vaderin r/ProgrammingLanguages • Mentions
On “Compiling language with generics to C”
In languages that compile down to C or machine code it's usually done using monomorphization, i.e. just copying the function for each type. However, it is possible to use a more dynamic approach which trades performance for binary size, compile time, and some additional possible features. For example Swift uses both monomorphization and a dynamic approach depending on the circumstances. In Swift it's called witness tables. If you search for this you will find some more info on how this works. For example, one of the Swift devs gave a talk about this at an LLVM conference.
u/Lantuain r/ProgrammingLanguages • Mentions
On “Generic Functions Implementation for my Language”
This 2017 presentation is a pretty good overview on Swift Generics link to this video