Fast native data structures: C/C++ from Python

Speaker 1 [00:05]

Hey, everyone! So I'm happy to have so many people here in this room. I'm happy to be at this conference. I haven't had an in-person conference for two and a half years now. The last one was also PyCon DE in Berlin. So I'm happy to be back on stage. This is my talk run fast native data structures. It might be a bit of an intimidating title. So I hope I'm happy to have you all here. And it's not going to be intimidating at all. I'm actually going to show you how simple it is to use native data structures from Python to extend your tool set. I'm going to do all this in Scython, so I'm going to show Scython a bit. As I said, Victor, I'm a Scython core developer, I'm a maintainer of Scython, actually, so this is kind of, yeah, my tool of choice, and the tool I've been working on for a lot of years now, and, yeah, Cython actually turned 20 years old just about a bit more than a week ago on April 4th, so this is something to celebrate. I wasn't actually there when the project was founded originally. I was more, so the original source code was Pyrex, Pyrex was the predecessor of Cython, but I was involved in starting the Cython project back in 2007, when we forked Pyrex and now built Cython from it, and ever since then, people have been using Cython for all all sorts of different things, and really cool things. In any of these endeavours there that you see there, people have been using software that was written in Scython. Taking pictures of black holes, sending robots to Mars, right? Really cool. Instagram is a big Python user and uses Scython code. Climate modelling, machine learning, all that. Whenever you're doing some kind of data analysis, you'll probably be using some piece of code that's written in Cython. So what is Cython at all? I've been talking about Cython. I'm going to use a Jupyter notebook for my presentation here, and Jupyter has support for lots of different languages, which is really nice, really cool. Not only Python, but even stuff like C and JavaScript and whatever. And it has support for Scython, so you can just load Scython and then have your code be compiled in Scython and run as native code. So that's That's the tool chain that I'm using here, I'm using GCC on Ubuntu as a C compiler, I'm using Python 3.10, and I'm using the latest unreleased Cython, because I'm a core developer, I use unreleased versions of my own tools. And once you have loadxcython in your notebook, you can then mark cells with %%cython to have cython compile your code and have it run as native code. So how does this work? What cython does is it takes your Python code, so you write extra Python code, and then it translates that into C code, then you use a C compiler to generate an extension module, So binary module for Python, and then you can import that module normally and use it as whatever normal module you would use in Python, and just export functions, classes, whatever you've implemented in that module. So compared to Python, there's just an additional translation and compilation step involved, but afterwards you end up with something that totally behaves and looks like a Python module. Let's take a look at Python. As I said, you can start your cell with CYTHIN. Has anyone never used a Jupyter notebook before? Is that new to anyone? Lovely. When I asked that, like, I don't know, seven years ago, maybe at a conference, a lot of hands would go up, but now it's like the normal case to do interactive programming in Python. So, wonderful. No hands up at all. As I said, it compiles the cell in Cython, and as you can see, that's totally normal Python code that I have in there, even the import Cython, that's just for type annotations that I'm then using, but otherwise it's just normal Python functions, just trivial examples here. So type annotations, you probably know type annotations from Python code, using the same feature, except that it's not just saying int, list, or dict or whatever, like normal Python data types. Here I'm using a Cython int which is a C integer, and this is how I'm using C data types in my Python code here. So the cool thing that Cython gives you, it allows you direct access to C data types from your Python code, so you can basically write Python code, but mix in C data types at any time, and Cython will take care of optimising your code for the data types that you use. OK, so functions, there are a couple of different function types in Cython, which is because it interacts with C code, so you need a way to tell, you know, have code callable from C code, for example. And, you know, this is a normal Python function. This is a Python function here that uses type annotations, So internally in this function, x is a C integer, and this x plus 1 operation here will actually run in C, so it will be a plain C x plus 1 operation, rather than the Python object operation, taking the object in x, taking the object 1, doing an add operation on both and then creating the object. This is plain C code. You don't see it, which is cool. just that annotating the variable here gives me direct C operations. Then, as I said, for calling your code from C code, you need something that's a C function, and for that we have a decorator, it's called C func, so when I decorate this Python function here, I get a C function from it. This is a plain C function with a C signature, C calling convention, and I can even pass this around as a C function pointer. And then there's a third thing, a C call decorator, which gives me a mix of both, so I get a Python function with an underlying C function, and this allows me to do fast C calls to this function without passing through the Python call interface. All these cases are covered. As you can see here, you can call these functions normally from a Jupyter notebook, so even though these are compiled, it just turns out as a normal Python function that I can call from a Jupyter notebook. Except for the C function, which is a C function, so you can't call it from Python. Okay. Calling see functions? Using actual C code from my Cython cell. All this is done in Cython 3, so we added a couple of nice features in Cython 3.0, which, as I said, is unreleased, so we are still in alpha, but all these features are there, and you can use them, and it's alpha because it's not feature complete, it's not alpha because it wouldn't work or break, It works perfectly, it's just, you know, we're not there yet. So this is how I would use the sine function, for example, from the libc math module. So this is actually using C functions there, even though you don't see it, right? The only place where you really see this is when I say from siphon C imports. So this is a special package, kind of, a magical package, that allows you to import C declarations, make them available to your module, and then I can use C functions directly here, and this little dash A up here gives me an annotated version of this module, so I can see what Cython makes of it, and when I click on this line, I can see that sine of pi by 2.0 actually turns up as it should exactly in the C code as a C operation. So this is calling the C sign function there. Okay. Fast access to Python data structures. So in this talk, we'll see how to talk to how to use C data types, C containers, but also how to have a faster way to use Python data types, right, and we'll start with Python lists. So let's say we want to sum up the squares of a list of integers. So let's just have a little data set here, range of 80,000, shuffle that to get rid of any, you know, any optimised behaviour, so So it's just a random distributed list, and then, as you would probably try as a first approach, you would say sum of i squared for i in ints, OK? So when I run this on 80,000 integers, it takes 11 milliseconds on my laptop, which is pretty OK, and we can also do the same in a loop. So when I spell out this generator expression as a normal Python loop, and do the summing as a Python plus operation here, rather than using the sum function, then I can run the same thing, and surprisingly, maybe surprisingly for some of you, this is faster. So we had 11 milliseconds before, now we have seven or something like eight milliseconds here. Why is that? Because there's a bit of overhead involved in using generators, generator expressions in Python, and especially for something as short-running as I squared and then get the next value, this overhead shows. So this is simply why the spelled-out loop in Python is faster than the generated expression here. So we take that as a baseline, and we'll see how to make this faster by using Cython. So how fast is it when we compile this in Cython? I'm using the same function as before. all I change is I'm adding to my cell, and now I run the same through Cython compiled, and you can see it's a bit faster. So we had something close to 8 milliseconds before, and this is 6.3. Okay. Cool. The speedup number you see here is compared to the sum generator It is a speed-up of not quite a factor of two overall. Previously, we had a factor of 0.69, 0.7, and now we are at 0.55. It is a little bit faster. It is not that fast, but we can make it run way faster, because now we are in C, and we can use C tricks. Let's Let's look at what Cython made of this. So Cython dash A again, give me the annotated version of this code, annotated representation of this code, and now I can click on this line, I can see that the whole multiplication, the whole summing and multiplication is actually using C API functions, so you can see in pi number multiply, pi number in place add, so this is using object operations, right, but We know we're dealing with integers here, so let's use C integers. So it can run much faster if we use C long as a data type, which on my machine is a 64-bit integer. It may not be on yours, so if you're running Windows, however unlikely that is in this group, but if you're running Windows, then C long is actually only 32 bits, even on a something to get used to, but then you can use C long long, which is definitely 64 bits or more. So, let's use C longs, all I'm doing here is I'm adding two lines such as that, two lines for declaring the data types of I and S, and now we can see that the whole thing runs in 790 microseconds. So that's less than one millisecond. That's a speed up of, well, we're at 7% of the original speed now. So we saved 93% of the time. Why? It's running in C. Doing math operations in C is what your CPU is built for, right? Cool. Yeah. That's way faster. Let's look at different data types. Python arrays. This was a very simple case. We had a list of integers. When you're dealing with larger amounts of data, you probably wouldn't keep them in a Python list, so numeric data at least. You would use different data types, commonly NumPy, but let's look at what Python provides first. Python provides an array data type. How many of you knew this, that there's an array data type in the standard library? Not so many, right? You would probably use NumPy instead, right? You can use Python standard library. So that's the array module which has an array data type, and that's a resizable array of native C data types. You can use character or int, double, anything you can find in C data types, and this is how I copy my list of integers into a Python array of type C long. So the little L there says this of type C long, and then the big L is just my data that I'm copying in there. Okay. Let's try the same thing on the code we had before, and we'll see that it actually runs slower than we had before. Why is that? Weird, huh? Well, the thing is, now we're actually storing the integers in a native array, meaning there are C integers, right? And in order to iterate over them, what we're doing now is we take these C integers, wrap them in a Python int object, so we create a Python int object from it, then do the calculation on it, which is done in C, so we unpack the Python int object right away into a C long again, do the calculation, it up. But the object creation in the middle is very costly. In the Python list case, we had all the data readily available as Python objects, and we didn't have to create the objects, we just had to unpack it. Now we have to create the object first and then unpack it. So this is costly in comparison. And you can see it almost costs us a factor of two. from 0.07 to 0.12. So, what do we do? Python 3 designed, actually, Python 3.0 came with a new buffer interface for assessing C memory buffers. That was designed by the NumPy people at the time, and it's a lovely and great interface that works for all sorts of data structures. Most people use it for NumPy, but it also works for Python. So what I change here in my siphon code is a type declaration, so from the bear, take some object as argument. I'm switching to, you know, you get an object, but actually that's something that supports it's the buffer interface, it's one-dimensional buffer, so there's only one colon here, two-dimensional would be colon, comma, colon, as you would probably know from NumPy, and the item types in that array is a siphon long, so C long. I'm statically declaring what kind of data input I'm expecting, and I'm receiving some object that internally has some C array memory buffer of C longs. That's all we need to tell Cython how to deal with the C array. Now we pass our Python array of C integers in there, and Cython is able to unpack that and look at the straight C array in memory, run over it, and now we can see that this gives us another speed-up factor of 10, so we're at 0.006 now. OK? Yeah. Lovely. And above there, you can see the comparisons to the other implementations that I had. So unpacking it directly from the array was 0.046. And even unpacking it directly from the list And doing the calculations, see that was 0.08. So that's the speedup we get compared to these versions. So as I said, another factor of 10 in performance. Cool. And the same works with NumPy arrays. So I used Python lists. Now I do the same with NumPy. I use exactly the same implementation. this annotation with the memory view, right, and it's able to unpack the numpy array in the same way as it did for the Python array, and you get exactly the same performance as before because the main part of the operation is then running on the C array and it doesn't matter whether it comes from NumPy or Python. Here is a little overview of sequence container types. In Python, you probably know how to use a list. A list is pretty limited in what it can provide. Python arrays and NumPy arrays are then able they hold native data types, And so you can work efficiently with them from Cython by unpacking the memory buffer. And the cool thing about the Python array is it's resizable, so you can add data to it which NumPy arrays aren't. Once they have their content, they are pretty much fixed, and so that's a feature they have that NumPy arrays don't. Just to show you how deep you can go into this, into using C stuff, probably the most C-ish thing you can do from Python is allocating C memory, right? And this is how you use malloc and free, again, we have this magic size and C import, and then down there, I'm just saying, here it says malloc, so I'm allocating space for 22 integers, I have to cast that, I have to declare it as an int array, so that's a bit of syntax overhead here, but Python isn't designed for doing C things in the language, so that's what you end up with. Another cool thing here, if the allocation fails, if there's not enough memory, I just say if not CMAM, raise memory error. Right in the middle of something totally C-ish, I can just say raise a Python memory error and tell my user that something went wrong. That's what Cython gives you. It freely mixes some C features and Python features. Okay. Yeah. You can use the CPython heap for that as well, so instead of malloc and free, you can use PyMem malloc, PyMem3, same thing. So how does that look when you use C memory, here is the same implementation that copies the data into the C memory array that are allocated, and then does the computation there, and you see that it's actually, make that a bit smaller so that you can see it, yeah, can't really see it, but it's 0.7 compared to the sum we had. So the thing that strikes here is it's actually costly to copy the data over. So I'm allocating memory, copy the data into it, and then the operation I'm doing on this is very, very short running. And so I would only redo this if I have a very costly operation that I'm doing in C. Then it might be worth it. C++. The cool thing about C++ is it's object-oriented, so previously we only had C functions that we could call. C++ has a standard library with a very nice set of data structures, for example, it has a vector which internally is just a C array of usually simple data. And this is how I can use a C++ vector from Cython. I declare my variable as a vector of C ints, and then I can do the same thing here, same implementation as before, and calculate my sum of squares. And for those of you who know C++, this is what it ends up with. So the iteration here actually uses the C++ iteration protocol. So it uses begin and end, and then plus plus for advancing in the vector. But what you saw before, it's just using a plain Python for loop. So you don't actually see that you're working with C++, it's just one little type declaration that changes the whole implementation here. OK, how fast is that? Well, it gets us to 1.4 milliseconds, which compared to the other cases is fairly slow. But again, we have the case that we're copying over data from some kind of Python input into a C++ vector. And we'll probably only do this if we had some long running operation that we can do efficiently on C++ vectors. For that, it's nice. In this case, it is so short-running that the copying dominates the overall runtime. So the other way around, exposing native data to Python, so far we've only seen how to use native data that some Python container provides. And, for that, Cython provides its memory views. Again, memory views can be used from Python. So, here, I'm using a C++ vector again of C doubles. So, 64-bit floats. And, I'm creating a vector here, and then I'm casting I'm using this typecast to a memory view, I'm providing the size, I'm saying it's consecutive, so each item is after the other, there are no jumps in the data structure, and I'm saying that the data type, the item data types in this vector is double, and then I can use This, for example, to pass it into the NumPySign function to calculate the sign of all the items in the array using NumPy. So I'm just passing this straight into NumPySign and calculate the sum of that so I get the sum of signs. Again, pretty straightforward. It's just take the C++ vector, cast it into something that supports the buffer interface, so that NumPy can deal with it and then pass it into NumPy or SubPy or whatever you can use there to do the operations that you need. Okay. C-rays. C-rays in C, they are statically sized data types. They have something like, you know, 10 integers in an array. In Cython, we added a bit of syntactic sugar for that, so you can use slice assignments on C arrays, you can copy by value, you can do partial assignments, and you can iterate over C arrays. That's fairly nice in comparison to how you would use them in C, which is usually you have an integer loop, and then you do indexing to get at the values, and you have to do all the copying yourself. This is fairly nice in comparison because we're using Python syntax features for dealing with C data types again. Sequence container types, you've seen lists, Python array, NumPy, now we can also use C++ vector as a data type and C arrays, all of these are just available for you as soon as you start using Cytin. Okay. Python dicts. We have seen sequence data types. What about Python dicts? Are they fast, too? They are. Let's look at this use case. We have a lot of integers, and we want to convert them to things. The straightforward thing to do is you have a list comprehension, and you run over the numbers that you have, and you just call the string function on it. Straightforward. What we know is that this list is repetitive. There are lots of identical integers in there, which means that we end up with a lot of strings which are highly redundant, and that costs memory. Okay? This comprehension, okay, we can see for performance comparison, it's 1.2 milliseconds. We can do the same with list map stir to the numbers. The map function simply applies the function I provide to all elements of a sequence, and does the same thing in the end, and it's faster because, you know, it avoids the overhead of this comprehension, So we're at one millisecond for this whole thing. But as I said, we have redundant data in the end. We spend a lot of memory on redundant data, and so what we can try is we can use a dict cache in order to reuse the strings that we've already created, okay? So I have a numbers cache, I have the list of strings that I'm building up one after the other, and so I'm checking if the number is already in my cache, then I take the string from there, otherwise I insert it into the cache, create the string, insert it into the cache and use that, so that avoids all the memory overhead. But in the end, it's slower because I'm now doing a lot more than before, I'm passing things through dictionaries back and forth, that's a lot more overhead than simply applying the string function to our list, and so this is 2.2 times slower than the plain fastest map function implementation. Can we do better? Let's compile it in Cython and see what that gives. Okay. That gives us a factor of 2, apparently, simply by adding percent percent Python. It is twice as fast. We are getting close to the fastest implementation. If you remember, that was 1 millisecond. Now we are at 1.1 millisecond. This is already faster than this comprehension in Python. Using the cache variant. We are saving memory and time now. Cool. Can we do better than this? We will see. What about F strings? We call the the string function, what about f strings? They can do the same thing, right? And f strings are actually fast in Cython because we have our own implementation for them, and so you can see that now we're at 1.05 milliseconds, which is pretty much what we had for the map function, right? So we're at the same, almost exactly the same speed now, and we are at at 0.45 compared to this comprehension, so, yeah, so, same speed as the Python implementation, and so that's a little improvement again. What if we ask Cython to use C integers here? We've seen that C integers can be so much faster than Python integers, right? Cool, wonderful, let's try those. So we type our loop variable here that, you know, runs over the integers to type that as C long. It is actually slower. We are at 1.2 milliseconds. Why is it slower? Well, the thing is, what we are doing here now is we are iterating over a list of integers, we unpack them into C integers, and then we test if the C integer is in a dictionary, in order to do that, we need to have a Python object, so we are creating a Python object from the C integer again in order to see if it is in the dictionary. Maybe it is. In that case, we are looking it up in the dictionary, so again, we start from the C integer, we need a Python object again, so we create another Python object for it. In the other case, again, here we create a Python object. So there's a lot of back and forth between C integers and Python objects going on, which makes it slower again. But we can avoid that. We can use C integers only where they help. So apparently, they don't help for the loop variable, because afterwards, in most cases, what we need is actually an object. We need to test if an object's in the dict. We need to take it from the dict and so on. So we need something that's hashable in Python that's object but we can use the cast inside of the f string so we can cast the value to a c integer and then apply the f string to that right and that's faster that gets us below the speed we currently had so now we're at 900 microseconds so 0.9 milliseconds so that's um pretty much 10 faster than what we had before right again because we have our own f string implementation and we we know how to build an F string from a C integer. Cool. Looking more into C++. Multisets. We've seen C++ vectors which are pretty much the simple container data types that C++ has. What about sets? You know sets from Python, right? Sets in Python are hash-based, which is great, because that makes them fast. But there are algorithms for which hash-based sets are not optimal, and C++ has several set implementations. One is an ordered set. ordering is something we can exploit. The algorithm we are after is calculating the rolling median, so we are running over a long array of data, and we have a sliding window on that of which we always want to see the median value in that window only, right? Not over the whole value range, but only in the window as we are going along. That's nice for smoothing images, for example, for time series, right, when you're running over time series, then you may need something like this. And we're using the medium because it's less sensitive to outliers than the average, right, than the mean. So let's see how that works. This is what we do, right? So we have our sliding window here, and this is our median value on each step. Okay? So rolling median using NumPy. Maximum, minimum, so we're calculating the window that we have, and then let NumPy calculate the median in that window. Okay? Using slicing. Okay? Random data. 10,000 elements, standard normal distribution. And we're at 386 milliseconds, which is pretty slow, right? And we'll see that we can do this much faster. So a window of 100 in an array of 10,000, OK? We can potentially speed this up by avoiding the call to the numpy median function and doing the calculation using C++. There's an nth element function in the C++ algorithm standard library. It does not only come with data containers, it also comes with algorithm implementations, where it is fairly handy. So now we are unpacking the array into memory view again, use the address of that and pass that into the nth element C++ function. Again, it looks totally like Python code, at least from here on, except it's working on C data and using a C++ function in order to do the calculation. Okay. I'll skip that. And one trick that we can see here... I'll also skip that, it doesn't matter. So one thing we are doing here is we are avoiding an allocation, meaning in the NumPy implementation, we did slicing, so we need to create a new NumPy way view, and in order to represent a window, here we are allocating the window data only once, and then reuse it by copying the data into it. Since it's a fairly small window, this makes a big difference because we don't need to allocate data along the way. Okay. How fast is that? Well, we are at 40 milliseconds. What do we have? 300-something, right? That's a good speed-up. So, we are at 0.04, pretty much, saving 96 per cent of the run time again. Cool. What we can do better, using another C++ data structure, and as I said, we can use C++, yeah, we can use C++ audit sets for this, and that is something, as I said, Python doesn't provide this, so implementing this in Python would be very tricky, and it does lead to a way more complex implementation, but the general idea is that we're keeping a set of the values left of the median and right of the median, and then we're moving this along, and since it's an ordered set, we always know where the median is. Okay? That's the idea. As I said, it's way more complex implementation, because it's algorithmically more complex, but since we need the speed, we pay it with more complex implementation using a data type that we normally don't have in Python, but that we have in C++, and Can I show you here? Yeah, so it's using C++ assess to the data Right, so you can see it's looking at the one end of the set using the the fact that it's that it's ordered It's deleting the last value and adding the new one and And that's pretty much how the algorithm works along the way. And then that gets us down to 2 milliseconds. So we're from 230 milliseconds to 14 to 2 milliseconds. So that's another factor of 7 pretty much in the speedup. And it might be worth doing this. Factor of 7 is not something you get every day. So, yeah. Okay. We're pretty much through with the time. So, I'm just quickly going to jump through this. We have really nice features in Cython that allow you to implement efficient data types in, you know, for using them in Python. One is the total ordering operator, which you probably know from Python. We have a C implementation of that, so you can add a total ordering decorator to an extension type, and it does the same that the Python decorator does at runtime, does it at compile time, so generates actual code for this, right, which is much more efficient. So here you can see that the comparisons that we run here, they are faster by a factor of 5, because it's an extension type now. We have data classes. Data classes are a new feature in Python 3.7, maybe, I think, or 3.6 even, when data classes were added. That's the cool little use case where you're only using a class for storing so you have two attributes here, and we have the same thing again in Cython, so that you get efficient extension types from this. So it generates the code at compile time. Cool. OK, I'll skip over that. I've already shown that you can use NumPy efficiently, and you can even use OpenMP to get thread parallel code simply by switching from a range loop, so 4i in range to 4i in p range, and then Cython will generate thread parallel code for you, as simple as that, and then I'm through with my talk, a couple of takeaways. is great, and you can use that to make your code run much faster and to use data structures that you otherwise wouldn't have available. High-level data structures are great, but only if you can unbox them and use them efficiently. And that's how Syphon puts an extra toolbox in your hands, so you get unboxed built-ins, you can get fast access to NumPy to see C++ the structures, and you can do all this in Python syntax. Thank you for listening. OK, thanks for your talk. We're a bit over time now, so I think I'll just ask you the first question, and then we have to move on to the second talk. What are good heuristics for and against adding Cython to an existing project? So basically why would you add it or why would you not add it? So it adds compile time overhead, it makes it a bit more difficult to add, you know, you have to distribute binary wheels where you previously maybe only had to distribute normal Python packages, so it adds overhead to that, but the transition is fairly smooth once you start using Cython and accept that you're having binary modules, there's a lot you can do in your codebase to speed things up, to start using C features, to make the code run faster overall. Once you accept that, it's really a wide range of optimisations that you can start using. All right. Thank you.