SBTB 2019: Richard Whaling, A brief introduction to systems programming, with Scala Native
Cool. Thanks, y'all. Y'all hear me okay? Cool. So, thanks for coming to my talk. A brief introduction to systems programming with Scala Native. So, about me. I'm on Twitter at Richard Whaling. I'm a lead data engineer at M1 Finance in Chicago
More about M1 Finance in a sec. And I'm I'm the author of this book, Modern Systems Programming with Scala Native from Pragmatic. It's in beta online now, so you can get it for the ebook for about half price and then you get updates until it's done. It's going to be done really soon. I'm finalizing it for Scala Native 0.4 right now, basically. So, really close to the finish line and happy to get this book out in people's hands. If you like what you hear in the talk, definitely a lot more content in the same vein. Brief plug for my employer, M1 Finance
We're based in the Chicago. We're a financial services firm. We do basically brokerage services with free trades, partial shares, custom portfolios, automatic rebalancing. So, I think it's a really awesome innovative product and I'd also be really happy to talk to any of y'all about how awesome it is to to work at M1 Finance. So, definitely come find me if you're interested in hearing more about it. So, brief outline of the talk. Scala Native's moved really far even in the last 5 months since I last gave a talk at at Scala Days this summer. So, really just a quick status update on how far Scala Native's come along and then we're going to do just sort of context and background on systems programming more broadly and then deep dive into some example programs that show how Scala Native exposes the what I think are the really fundamental and intrinsic techniques of systems programming
Um So, quick status update. Scala Native, we're on 0.4.0-M2 right now and most people are using the milestone releases for 0.4 rather than the 0.3 series. M3 is coming really soon and that's going to have 2.12 and hopefully 2.13 support as well. And then once that's ready, 0.4.0 will happen very shortly thereafter. We've also released our official libuv bindings. That's the original Node.js C library for for event looping and IO. Scala Native Loop. And I can talk way more about that at the unconference or or on the side
We're also trying to get cat good cats and ZIO support for 0.4. Really aiming for compatibility with the existing FP ecosystem and leveraging that to sort of bypass the issues around compatibility with with Java IO. That being said, this slide aside, we're going to just go deep into the the lowest possible level and the the the most native side of things. So, to to start, what is systems programming? This thing I I say that the talk is about. Sort of my my pithy like one-liner is it's the domain of programs that demand a mental model of the computer as a machine. Maybe unpacking that's what the rest of the talk is for, but pragmatically this means operating systems, IO, compilers, VMs, containers, embedded systems, real-time systems. Traditionally, it's the things you do in C. And traditionally, it's something you learn a little bit of school and then promptly forget and never use cuz it's not especially pleasant or effective
But it doesn't have to be this way. Systems programming can be elegant, it can be fun, it can can be done in in Scala in a language you enjoy. So, why why have people used C for systems programming still for for so long? I mean, yes, there's inertia, but in particular, operating systems and hardware vendors often don't give you a lot of choice in the matter. They give you libraries and you you have to use them, right? But especially as the we continue to sort of move into the open source era and with the rise of new languages like Rust, you're getting more and more arguments that there are there alternatives to to C for systems programming. I probably don't have time to go deep into them here, but Steve Klabnik, a Rust developer, has a great one. David Chisnell has another. Basically, their their argument is that C isn't necessarily close to the metal per se. It describes the behavior of an abstract machine, but the modern processors with branch prediction, with hyperthreading, with multi-cores, with three layers of cache are very different from the sort of virtual PDP-11 that the C abstract model describes
My hot take though is that um the the C abstract machine is is a feature, not a not a bug. And that what I what I got from learning C was this sort of intuitive understanding of how you solve problems with this abstract von Neumann machine. Um and and what is what is that mean cuz that's more jargon, right? So, John von Neumann, maybe the best mathematician and physicist of the 20th century, inventor of merge sort, and he described the the architecture of modern computers in the first draft of a report on the EDVAC. Um the EDVAC is this. It was a an electronic discrete variable automatic computer. It was sort of proposed and designed in 1944. It wasn't actually running fully until 1949. Von Neumann didn't actually design it
It was designed by John Mauchly and Presper Eckert. And it had 1,000 words of 34-bit wide ultrasonic mercury memory, which feels pretty terrifying to me at least. The the crucial architectural distinction that that caused it to be revolutionary is that it was the first stored program computer which could store both data and code in addressable memory. There are earlier computers that are Turing complete like ENIAC and Colossus, but they were patch programmed with switches and patch cables. And although they tech on theoretical terms could compute just about anything, in practice it took 2 weeks to make them do even even simple things. In contrast, the the von Neumann architecture works like this. You have a central processing unit and it can sort of do two different things. It can either fetch instructions from memory and then it has like a program counter to see where in the instructions it is
And then it also has an arithmetic logic unit that can also fetch data from from memory and do things with the data. And the the sort of interleaving of fetching your code that you're going to run and then fetching the data that the code tells you to do things with. Um Feels like a really fundamental break with the the past of electromechanical machines. And that in particular, it's really the the first realized implementation of a universal Turing machine, which is to say a general purpose computer. This was the the first general purpose computer that it was actually practical to construct and to to write programs for. Um such that within 7 years of this machine being designed and 2 years of it actually running, computer scientists invented random access memory, conditional branches, go-to instructions, subroutine invocation, merge sort of course, two's complement integer notation, Monte Carlo methods, computer music and computer games within a few short years. Just sort of this explosion of of applications and discoveries that were enabled by for the first time having a comprehensible and practical model of a programmable general purpose computer. Um and then 30 years later, dot dot dot, you get you get C, right? Kernighan and Ritchie
Um and I'd argue that C still to some extent presents the enduring sort of syntactical representation of this abstract random access stored program computer. It has a lot of things that are thought of as as quirks of C, right? It has a small handful of primitive data types. It has these zero-terminated byte strings. It has arrays. It has structs. And structs are really just product types like like like tuples or case classes. It has unions, which are sum types, right? It has pointers and it has function pointers, which is to say functions as as values. Um and if you if you take a systems programming course in college, these are all weird arcane features of C you struggle with
My hot take is that underneath C's punishing syntax, there's actually something very very fundamental here. And that these seven techniques are the the fundamental like meat of what it is to program a von Neumann machine in in in general terms. Um so, fast forward another breakneck 45 years and you get Scala Native in 2017. Um and Scala Native, right, is a Scala C compiler plugin that compiles Scala programs to binary executables ahead of time. It uses LLVM, the same compiler framework that that Rust uses. Um Scala Native's noteworthy for its advanced optimizer, its lightweight runtime, its a GC, and its C interop layer. It It should also be pointed out Scala Native isn't a JVM. In contrast, you know, Graal can compile JVM bytecode to machine binary, but conceptually that's actually quite different even if the result is still machine bytecode
Um and the the payoff for that is because Scala Native actually understands Scala, not just JVM bytecodes, Scala Native can provide an elegant DSL for low-level programming with all the capabilities of C. Basically, it's C embedded in Scala. Um, and if you if you take one thing from from this talk, that's that's really the takeaway, and that's what led me to fell to fall in love with Scala Native 3 years ago. Um, so what we're going to do for the the next 20 minutes of this talk is we're just going to illustrate what these fundamental techniques are, these primitive data types, pointers, strings, arrays, structs, unions, um, and and and and functions at the machine level, um, with with short Scala Native programs, um, and we'll see how far we get. Um, but we're making good time. So, caveat, regular Scala very different from what I'm going to show you, works just fine in Scala Native. Um, everything you're going to see here lives in the Scala Native.unsafe API, which is very useful for library authors, but not even where ordinary application developers in Scala Native necessarily need to go. Um, and these slides are going to contain extremely imperative unidiomatic Scala
Um, I feel a little guilty they put me on the functional track because in some ways this is about as far from FP as you're likely to get at a modern programming conference. So, uh, that said, let's let's kick it off. So, first off, you have just a handful of fundamental data types, um, that can't be broken down into anything else. Um, these all have concrete representations in memory, and they have fixed sizes. We can get the size with the the size of operator, which just takes a type parameter and tells you, "Hey, exactly how many bytes does this this take up on on on disk?" Um, so we'll just ask it to to display both the value and the size of an int, a byte, and a double. Let's um, let's actually run it really quick. Cool. So, it's just telling us ints are 4 bytes wide, bytes are 1 byte wide
I really am glad bytes are 1 byte wide, and uh, doubles are 8 bytes wide. Um, also just pointing out that that lovely Scala Native instantaneous startup time, and how big is this binary? Yeah, nice little 1.5 meg, um, binary. So, that that that's sort of the the machine, um, executable payoff, but I I get more excited about the abstract model than the the logistics of of machine code, really. Um, so there's really not a ton of of fundamental data types like this. Um, they're they're all between 1 and 8 bytes. Um, note that strings, right, are not a primitive in C and not a primitive in Scala Native. Um, and then let's let's keep going. So, the the the really famous one, that the signature one in C, is is pointers
Um, and what we have in Scala uh, Scala Native is this type pointer, which takes a type parameter, which is sort of a nice clean parameterized generic pointer type, um, that I find much more ergonomic to work with than the C's, you know, asterisk, ampersand, um, syntax noise. Um, but basically, a pointer denotes the address of a value in memory while being a value itself. Um, generally, what that means is a pointer is just a 64-bit unsigned integer that contains the numerical address somewhere in linear memory of where data of some some type is. Um, pointer values in Scala Native are always created by explicit allocation. So, um, there's certainly other ways to create an int, but if you invoke this built-in stack alloc function, which again takes a type parameter, that's just going to return an uninitialized pointer uh, to an int, um, on the stack somewhere. Um, right? And then once you have one, because again, it's uninitialized like C, um, you'll need to both um, set the value and then also get values out of it. Basically, you can think of this pointer as being a place somewhere in memory where you can store data and get it back out. Um, and the way we do this is with the dereference operator, which is um, uh, the exclamation mark or bang
And the the interesting thing about this is it does different things depending on whether you're on the right-hand side or the left-hand side of the assignment, which you can see at lines four and seven. When you're on the right-hand side of the assignment, um, it's actually a dereference operator. It's saying, "Hey, go read memory at this address and return the int you you find there." Note that I am in fact reading from uninitialized memory here. Um, but then um, what we can do here is that we can actually um, um, a store values into the pointer by using the the same operator on the left-hand side of an assignment, um, and then uh, retrieve the same value back again. I think we're we're good on time. Let's let's do it again. It's really hard to type with um, my the mic in one hand. Um, so so about what you'd expect
We have a pointer that lives at some, you know, scary hex memory address. Um, the interesting thing is that pointers themselves have a size, right? But the size of a pointer is always 8 bytes cuz it's just a a long integer. Um, that might be helpful if I'm doing more live coding, right? Good call. I might I might switch to that. Um, but I'm kind of I'm kind of liking the the the mic like this, too. Um, but because pointers are really just long unsigned integers, um, pointers are always the same size even if they're pointing into things that are smaller than 8 bytes or potentially much larger. A pointer to an array of millions or billions of bytes is still 8 bytes cuz it's just the address, that's all there is. Um, note that there's actually not an address of operator, the the ampersand operator, which um, even is even um, an ergonomic improvement, I would say, over Go, which is generally a lot higher level than Scala Native
Um, instead, we do require these sort of explicit allocations to to get access to a bare pointer, um, but and this gives us really nice safety guarantees. It means if an object is managed by the GC in the runtime, um, it means you can't break the seal and accidentally take the address of something that is very likely to get moved or or garbage collected or compacted away or something like that. Um, so it's actually a really nice um, difference um, to to some of the other languages out there that that do similar things. Um, also, if you're if you're a FP geek, this is actually really closely related um, syntactically and semantically to the the reference and pointer types in Standard ML, which is where I sort of first learned this, and also into Haskell's internals. Um, would love to geek out about that with someone later. But in in some ways, it's a more pure it's a more pure way to represent a mutable cell in memory than Scala's var versus val, right? Um, it can it can so can feel a little unwieldy, but having a type that represents just a bare mutable slot, um, has has some some benefits, also. Um, so yeah, takeaways so far, all your data lives somewhere in memory even if you can't get the get the address of it, and it all has some fixed size. Um, some of those objects will be managed by the runtime, some won't
But then once you do have an address of something, um, manipulations of that address and size are just simple arithmetic, which is very very fast and often known at compile time, which is where you start to to really get some performance payoff. Um, so let's keep going. Let's talk about arrays. And this is a slightly unusual, um, presentation here because I don't think I'm going to show the the the compatibility in C array types just because in C, it's surprisingly rare to use actual array arrays. And in C, it's much more common to just use bare pointers and pointer arithmetic, um, as a sort of generic and portable and variable-sized array. Um, and that's exactly what we're we're doing here. We're we're using um, the standard library malloc function to just grab an array to hold 16 integers. Um, we have to because malloc, this is real malloc, it returns a pointer of byte
Um, in Scala Native, we actually don't have a point avoid pointer type, but because of that, that means we have to explicitly cast it to be a pointer of int. Um, and we just cast it with asInstanceOf, no novel syntax there. So, once we have this int array, um, we can step through it and initialize it, right? Because again, we just got it from malloc, who knows what data is in there. And in Scala Native, the the cool thing about pointers is pointers have this sequence-like syntax, this index accessor, for both assignment and for for read for lookups, um, that's comparatively safe and unintrusive. Um, the the really neat thing is um, it's all doing pointer arithmetic under the hood, right? Uh, just like an array in C, and exactly as fast. Um, the thing that's a little unintuitive is that if you take beca- because the pointer itself has a type, because we know it's a point int, if you take the the address of the the first item and add one to it, that gives you the address at 4 bytes away because when you're doing pointer arithmetic on an array, it generally knows what you want to do is move one item further in the sequence. So, we can um, we can read we can run this one, too. Um, we're just going to initialize uh, 16 items in the array and print them out, and also verify that the result we get from using like index style accessing is equivalent to what we'd get from actually directly computing the address with pointer arithmetic and dereferencing it because they're literally the same thing
Cool. Um, so about what you'd expect. It's just starting at some base address and striding through 4 bytes at a time and instantiating more values. Um nothing nothing really magic here. Um the the other neat thing of this is that it seek seeks into the array are constant time, right? Which is actually a pretty hard thing to get um on any other data structure. Um and if you're willing to allocate a very large array, this can be very very nice for working with sort of medium size uh low gigabyte scale data. Um then let's talk about strings. Um so how do you handle sequential data that's of unknown size or variable size? Um there's sort of two fundamental ways you could go with this
One is some kind of terminating mark uh traditionally a zero byte. Um the other is to somehow store the length of this variable length string um somewhere in a side band or as a function argument or something like that. Um zero terminated strings were probably a mistake, but uh they do have benefits and low overhead, right? Um the way it works in in um in Scala is that uh we have a C char type, but that's actually just an alias for byte. And then we have a C string um type that's just an alias for pointer um of C char, which is really just a pointer of byte. So all all C string says is hey, there's some bytes, and then you get some syntactic sugar for constructing C style string literals here. And that literally is just returning the pointer to the the address where where the data lives. So if we want to like get the length of that, we're just going to use the C standard lib string length function, which just walks through until it finds the the zero byte. Um it should also be apparent what can go wrong with the zero terminated strings, which is if you have an off-by-one error and you don't copy over that zero byte that it's looking for, string length will just walk right off the end into the rest of your program or into into a section of the address space that you don't have access to
Um so this is this gets risky. Um and traditionally string wrangling in C is a huge source of buffer flow errors and security vulnerabilities. The nice thing that Scala Native gives us here um is that the runtime gives us helper methods to convert back and forth between Scala real Scala strings um just a plain string here basically by just handing that data over to the garbage collector and letting it become managed. Um what I found is doing systems programming in Scala Native, if I just push all of my string wrangling off to the runtime, I get a huge increase in in safety assurances, way fewer bugs, and honestly it's not a lot slower than trying to do um sort of wonky C string manipulation. Um so I find this is actually also a huge huge benefit for for doing practical systems programming. Um You know, I don't think I need to go into it byte by byte. So so quick quick recap of the pointer. Um so a pointer of T just indicates the address really of zero or more items of T
So it in some ways it abstracts over the capabilities of other container types like option, like seek, or string. Um and I I I I like to think of it as a sort of mutable container that represents a capability to change remote data. Um it's profoundly unsafe. Um segfaults, undefined behavior are all real risks here. Um but there's also real benefits. I don't go deep into like side-by-side performance comparisons in this talk, but if you look at my um Scala Days talk from last year in 2018, I do a lot of head-to-head um array crunching. Um if you're really interested to see how that can impact real-world performance. Um let's keep going with the the these compound data types
I think I'm a little over time, so I'll go a little faster here. So a struct um really is just a product type like a case class or a tuple. Um in Scala Native, they actually have more like a tuple-like behavior. So we declare a struct of a string and int and an int, and what we get is we get both uh member accessor just like on a tuple. Um and then we also have the the dot at accessor, which can give us the address of a member of a field member of a struct, which means you can get the member of an object without having to do an extra um access. It's again just static pointer arithmetic computation. Um Um you can add syntactic sugar with, you know, usual Scala implicits to add named um accessors, but almost never necessary. Um And then unions, right, are the sort of uh low-level technique for for managing sum types
Um what happens when you have two or more values of different types that could both exist in the same place. Um C has unions, but traditionally they they were at well, they were added pretty late to the language, so it's much more idiomatic to actually just do unsafe casts between unrelated types in C, which feels terrifying. Um but it works because if two structs have a common prefix of fields, those fields only can safely be used interchangeably. And it's really common to have a tagged union where you use the first field of an object of an unknown type to contain an enum indicating, hey, this is foo. Hey, this is bar. And then you can inspect that first field, then cast it to whatever type it actually is, even if they're of totally different values. Um so like an example would be something like this. I said I don't think I can go line by line, but the idea is you can basically implement your own polymorphism um sort of from scratch
Um it sort of harkens back to Green Spun's rule that all sufficiently complex C programs contain an implementation of half of common Lisp. Um but uh being able to implement half of common Lisp in in Scala is pretty cool if you ask me. Um so finally we get function pointers. Um functions are just values in C, but they're not the same as Scala functions, right? Because functions are literally just the address of some compiled code in the program binary. That's all all there is, right? It has a fixed address. It and it in particular it doesn't have lexical scope, which means it's not directly interoperable either with a Scala function or even like a a static member on a on a Java object. Um and then once you have that address, function call is just argument marshalling and go to. Um it can be much much faster than method dispatch and vtable lookups and all that
Um and there's actually a lot of ways to fake um lexical scope just by sort of taking a bag of data and storing it in a in a void pointer or something like that. Um that being said, Scala Native gives us um this really nice C func pointer type um that lets us construct in this case it's a comparator for quicksort. Um and a compare in this case so a C function pointer is just a single abstract method type um that has a single apply function. Um and by constructing it this way, we actually get back a bare C style function pointer that we can then pass as an argument to in this case a C function, the C standard lib quicksort function. And this is where you really open up enormous um levels of of performance is being able to hook into, you know, the C quicksort for, you know, sorting an array that's 5 GB in in RAM or something like that, which basically becomes impossible to even do. Um and again, like what we're doing here is sort of again, it's another half of of polymorphism. It's sort of trait style um message uh method dispatch um but sort of implemented from from scratch, which is both terrifying and exciting. So what are I guess my takeaway here is that like the the more I reflect on all this is that there's this affinity between systems programming and functional programming, right? That we have functions as values, we have sum and product types, you know, way back in the lowest possible layers um even though we sort of can lose them in the intermediary object-oriented um layers that a lot of modern software is built on
Um this has really deep roots in Scala's heritage. Like um I learned a lot of this from Standard ML originally. Um and even Haskell has a lot of of capabilities like this under the hood. Um but I what I will say is having written a lot of this is that Scala Native's unsafe API for me is actually easier, safer, and more productive than than even than writing C to do the same thing. Um it also feels more elegant than working with the OOP Java layer that Scala depends on. Um and I think it's really a a huge breakthrough in the ergonomics of systems programming to have this sort of consistent, compact, um mostly type-safe um wrapper around these these fundamental capabilities. And it's even something you could think of porting to to other non-Scala Native platforms. The sun.misc.Unsafe API could do this
Um Graal could do something like this if they were inclined to. Um and it it just really opens up a lot of these exciting problem domains um to a lot more people. And um yeah, that's basically my talk. Thank y'all. Cool. I don't think I have time for questions, but happy to talk about this uh around, and I'll probably do a an unconference uh or something on Scala Native. Thanks again, y'all. Yeah, thanks so much, Richard
I for one am