Dictionaries Behind The Scenes - Gisela Rossi

Speaker 1: Okay. Okay, so let's talk a bit about dictionaries. So any running Python program at any time has many active dictionaries, even if the program that the user is executing doesn't act explicitly use a dictionary. And some of the examples are the ones that we saw in the pool. So model namespacing or key arguments. And this quote I took it from Fluent Python book, which is very nice and I recommend you search it. So it has three parts. So one is hashing and dictionaries, which is basically

Speaker 1: hashing is uh the backbone, the engine behind dictionaries. A bit of on dictionary security, how secure are our dictionaries , and a bit of on some performance optimizations. Uh dictionaries because they are everywhere, they are highly optimized. And I think one of the uh the things I would like you to get out of these talks is that Python core developers have a level of detail on the craftsmanship that they do that is amazing. So let 's let's get into the first bit. Talking a bit more about hashing

Speaker 1: and dictionaries. So let's start at the beginning. And sorry if I this is something you already know. I just don't want to lose anyone. So what is hashing? So a hashing function is something that can be used to map data of an arbitrary size to an integer. And the things that a hashed function must satisfy by definition is that if two objects are equal, then their hashes must be equal. But if you're gonna be using this everywhere, you're not only gonna ask the minimum of the definition, you also want a bit of extra. And we'll talk about in a sec. So one of the things that make hash tables

Speaker 1: , hash functions so nice is that we use them to build hash tables. And hash tables are one of the most beloved data structures in computer science. You probably run into them all the time. You probably have been asked about them at interviews and at your daily job you use them. And one of the nice things is that on average, most of the operations you want to do, like insertion, search, deletions, are all constant time. And this is kind of from a picture I took from Wikipedia, how a hash function can be drawn. You have some keys and you use your hash function to map it to certain brackets.

Speaker 1: And we retalk something uh that I mentioned now because you will come back later Is that we talk of a collision when you have two of these things, like for example, John and Lisa, and your hash functions map them to the same bucket. And in that case, you will have a collision. So we talked about asking for more than the minimum of a hash function. And one of the things that we want to ask is that it will minimize the collisions. So we want to minimize the situation where we have two different keys and we map them to the same bucket because that needs to be resolved and no matter how we resolved it will degrade performance of your hashtable So that is something you want to minimize. And you also want it

Speaker 1: the hash function to be something that is cheap to compute because you're going to be computing it quite often. Now, why I'm talking about this? Why am I talking about hash tables and hash functions? I'm talking about this because Python dictionaries are implemented using hash tables. uh they also python sets. Uh so that is why you have these kinds of errors when you're trying to use, for example, a dictionary as a key to another dictionary, which was one of the questions of the pool. You will have you will get something like this type error unhashable type in this case is list but you will you will get unhashable type dict if you try to use a dict

Speaker 1: And this has to do with the fact that it's not a valid input for your hash variable, for your hash function. Let's talk a bit more about this. So this is the formal definition of what it means to be actual in the Python world. An object is hashable, let's read together. An object is hashable, it has a hash value which never changes during its lifetime and that can be compared to other objects. Hashable objects which compare equal must have the same hash value. Hashability makes an object usable as a dictionary key or set member. So basically what 's what was missing was the hashability.

Speaker 1: And if we digest this definition a bit more, it hash a hash value means that It needs to have a dunder hash method defined, and that which never changes during the lifetime, it is talking about mutability. It doesn't depend on mutable attributes And can be compared to other objects is talking about having a dander eck method Okay, so we have like different pieces of our puzzle and we have a definition that kind of puts it all together. So we are talking about uncashability, we are talking about mutable attributes We are talking about comparing things. So let's digest this at least

Speaker 1: a little bit more. So user -defined objects Hashable. So if I define an object and it 's is is that gonna be hashable? And by default, yes The Dandereck method that is used is the identity, so two things compare equal only if they are the same object. But you can override all these behaviors. So we said for something to be hashable, you have to have an under egg method and an underhash method. Well, I mean you can override these things and tune and customize the behavior you you get. Um so these two

Speaker 1: over here um These two over here are kind of common sorry, kind of common pitfalls because Well, this is actually how you have to do it. So if you don't want hashability, you do this. This is the way to go. You set dunder hash to none and now your objects don't hash hashability because maybe that's what you want But this is a common pitfall. So if you override one of these functions, imagine you override under EC, but you don't underwrite under hash, then you lose automatically the hashability of your objects. Because Python behind the scenes will do this. So that is that so that is a bit of

Speaker 1: a precaution. But now let's talk about the the case you probably want which is to override these two things but keep the hashability So usually um I'm gonna take out the point. So usually um If you decide to override the things, you have to go back to definition and remember that you need to build it based on things that never change during the lifetime. Uh and here we have uh a bit of a simple example. So you can use the built-in hash uh function you don't need to become a cryptography lucky for all of us um

Speaker 1: so what you usually do is you get a tuple of your immutable attributes and you pass it to hash and that is how you tune your your um your hash dandar hash function So this is a bit of an example. So let's slow down on this example. This is a class person. And it will have a name which will be an immutable attribute. And I'm defining my dunder hash as the hash, this is the building function hash. And I'm passing a tuple. Oh sorry. It's a bit annoying that you cannot click with the pointer. And I'm

Speaker 1: passing a tuple of one in multiple attributes. And this is how you usually do it. You could have more than one here, like you could have an N tuple, that's fine. But this is how you usually would override your dunder hash. with some tuple passing to the built-in hash. And then you also are overriding your dandurec. And this is a very This is quite a simplification because I'm saying that two persons are the same person if they have the same name. So this is like a very simple, simple example, but this is kind of how you you can do it. So like to redefine your dundra hash, you usually call the build-in hash. With some unmutable attributes.

Speaker 1: And your dandere egg, you can redefine it whatever however you like. But remember to refine both. So that was a bit um That was a bit of a walkthrough on the on the kind of foundations of dictionaries and kind of answering a bit about What values can can can you use as key of a dictionaries as values of dictionaries and so on Now let's talk a bit about dictionary and security. And there was there has been quite an interesting evolution, I would say. So if if dictionaries are going to be everywhere, you wanna you you you kind of are interested in trying to make them robust and

Speaker 1: secure to attacks So imagine for example that you have an HTTP server with a get query string and let me get the pointer again. So this gets parsed into a dictionary where these things that I mark on how do you say on bold letters are the keys of the dictionaries and these will be the valleys So this gets parsed into a dictionary. So what is the danger of this? Basically, if your attacker gets hold of knowing what your hash function is they can fabricate keys that are designed to collide and then they would degrade the performance

Speaker 1: of your service for legitimate users, which is called a DOS attack a denier of service attack. Other examples of things that get parsed into a dictionary and could put you in the same situation is parsing a JSON also produces a dictionary. Uploading a CSB file also gets parsed into a dictionary And in it in general, in any other situation you can think of where you don't have control of what the keys are or how many of them are. You you can get put into this situation. So let's talk a bit of an evolution of Python dictionaries.

Speaker 1: And there were uh there have been three versions of security on Python dictionaries. The first one uh was a non-crypto non-cryptographic um hash algorithm. Uh it was efficient, but it was prone to this kind of attacks that we just described. And this would uh it it was proven uh with an example that Attackers could exploit the worst case of dictionaries. So this was a known issue for a while And people kind of talk about fixing it and so on. It got a bit more delay than maybe the community would have expected.

Speaker 1: But then eventually there were some improvements. The version number two that came is trying to add some randomization to the same algorithm. So the essence of the algorithm was the same, but they added kind of like a A randomized prefix and suffix. And you could customize it with this Python hash seed. You could turn it off completely, or you could customize it to be something else Um did this kind of um mm made it harder so there weren't any uh register attacks or or any Yeah, or it were an

Speaker 1: register attacks, but theoretically the vulnerability was still there And so it even though it was an improvement because it made it harder, it didn't completely solve the problem, plus it added uh a a de uh a performance issue um uh comparing to the first version So eventually we came to the last version , which we call zip hash. And zip hash was not an improvement of the first version or the second, but it was a completely new thing. And it's a fine is a family of separate random functions that is optimized for short messages.

Speaker 1: And one of the nice things about this step is what it was proposed and is is quite interesting. And one of the nice things is that it was as fast as version one, but without uh the vulnerability, which is quite uh an ingenious uh solution and and it's quite in intriguing. So if you wanna see this is These slides were done for Python UK on September last year, so actually this all these Python versions are not supported right now. Everything that is Python 2. But this is kind of the snapshot of some Python versions and where do they see it in terms of dictionary security.

Speaker 1: So if you have any version of Python 3 uh which probably you should, uh then you are using the most secure version of dictionaries we know of. So that is good news for you and for me and for everyone. So that is a bit of an overview of the security of fight dictionaries. And now we get to, oops, sorry. And now we get to what I think is probably my favorite part of the talk because it talks about um How Python is built incrementally. It's not one genius idea, it is just a lot of very ingenious ideas built on top of each other. And there is a level of craftsmanship that goes into it that is amazing.

Speaker 1: This selection is completely personal and you probably could have picked another selection of performance optimizations or other kinds of optimization. and they would be as awesome as this probably. But this is some example of fine-tuning that I find fantastic. So if dictionaries are going to be used everywhere, you will also care about performance in time, but you will also care about performance in space and how much space your dictionary is. um take. And this was an optimization presented by Raymond Hettinger that is very it's actually quite simple when you see it, but it it it took a while to come around.

Speaker 1: So imagine you have a dictionary. The version over here was how it was before. So before we would have a very sparse table. of uh of your entries to uh your dictionary so this is your dictionary basically um And this dictionary will always have a percentage of the table that was free. So if you start to add things to your dictionary, eventually it will resize. to keep that percentage of free space. So eventually this was mostly unused space by design. So it wasn't just a snapshot in time. It was by design like this.

Speaker 1: But then Rendmann Hettinger came and actually proposed this. So actually we could replace this sparse table with these two things. So on the one hand we have an array, an sparse array of indices, and then we have a compact table which doesn't have any free space With the actual entries. So for example, imagine I have my dictionary and I go and I add name first. So this is The first thing I'm gonna add and I add it to my table, then I I I'm gonna add age and I add it to my table. You know, and it and it's kind of like It's kind of the same information, you don't lose any information. And on top of that, if you

Speaker 1: if you maybe are paying attention on these indexes You can see that now you remember also the order of insertion. So this is exactly the point in time where that depends on the pole we were seeing happens. But with things with performance optimizations gets added as a side effect, you get the insertion. So what is what are kind of the gains of having done this? Resizing becomes faster, iteration becomes faster, you get a lot of memory savings. There is a special optimization for small dictionaries.

Speaker 1: I don't remember the numbers, but it's quite significant. And then you also get that free side effect that now dictionaries remember the order of insertion. And this was only like behind this the scenes change. So like nothing uh user facing or nothing um you would notice but it was quite significant. The second performance optimization I wanted to talk about it was key sharing in dictionary So as we as we saw in the example, like behind the scenes, Python uses dictionaries for class instances, attributes.

Speaker 1: Uh and and this pep allow sharing of that. Uh I'm gonna give an example So imagine you have this class, which is quite the same as before, like an a person with a name, an age, and salary. So basically Your attribute names can be put together inside the instance or can be stored Separately. And if you have only one instance, it's kind of the same really. But how do this escalate? So when you have two instances now This is all share information because they all have an attribute name,

Speaker 1: an attribute age, an attribute salary. So actually this instead of being duplicated in each of the instances, it's separated And this if you have two instances, you only save one, but if you have thousands of instances, you start saving more. And this led to a memory improvement of up to 20%. So that was uh quite impressive. The optimization I want to talk about was string key optimization. So you know when you kind of everything you do with with dictionaries require you to compare keys, right? If you if you want to

Speaker 1: insert something you compare to the keys you have if you if you want to um compare if the value stored inside the key is the same as something else You also have to compare. So you have to do a lot of comparisons. Now, comparison of two random Python objects is something quite complex actually because you have to Take the first object, fetch the done direct method, call it with this other object, check if it's designed, define This can raise an exception. If it's not defined, you have to fetch the dandirect of the other object and call it with this one. And again, all this can raise an exception.

Speaker 1: So it's quite complex. But and this is the beauty of Python, none of this can happen with strings. Comparison between strings is always defined. Um, it will never raise an exception, it's quite quick So this is what this optimization is about. Dictionaries with string keys are handed differently from all other dictionaries. And so basically, as we said, comparing two strings versus comparing two random Python objects is a lot faster and cannot raise exceptions. And why is this screen up screen key optimization so shocking or so vital is

Speaker 1: like most internal Python dictionaries benefit from it. So actually even if we as user may want to use keys that are a bit more complex than just strings, like most of the internal Python benefits from this implementation. And if you go look at the implementation for this optimization, it's actually just very simple. It's just an if. If the type of the attribute is of the key is a string, then So it's it's just uh an if so it's probably like a less than five lines of code implementation or something like that, but the but the idea is quite impressive. And that was kind of my talk.

Speaker 1: So yeah, I'm a software engineer. I work at Tessian. If you want to check it out. And also I'm one of the colleagues of PyLadies London, so if you wanna support or talk at PyLadies London, give us a shout. And that is my Twitter where I tweet about Python and pictures of my cat. And these are all the references. uh where where I have taken most of this information. I think the peps are not here. Oh yes, the peps are here as well. So if you want, I can I can copy this list to the chat. And that was me. Thank you so much.

Speaker 2: Okay.

Speaker 1: I'm gonna stop shining. Let me see.

Speaker 3: Um I'm actually gonna answer the first one is from Vaughn. Yes, we are recording this. We are not sure where we will share this. But there is recording going on right now. Then Gisela, we have a couple of questions.

Speaker 2: Can I ask a follow-up on that? Gisela, will we be able to get a copy of your slides?

Speaker 1: Yeah, sure, of course. Yeah.

Speaker 2: We can host them on Django London. com.

Speaker 1: Let me, I can I can actually master that right now.

Speaker 3: Okay, Gisela, we have a couple of questions uh from um from Mary. So I'm gonna read them. Um First is uh first is there is some code in it, so like probably if you open the QA panel you will be able to read them. But first one

Speaker 1: has opened the QA. Um So our Python versions using CPAC still vulnerable to arbitrary key denial of service attacks? As far as we know, no. So the problems we know of were solved. Unless someone can prove that this is vulnerable as well , to the best of our abilities, the answer is no. You mentioned the user-defined classes get Dunder Egg by default. I presume that uh is Excel Dunderek under the hood by default is identity. So it's just uh checking against the identity.

Speaker 1: So is is you get something very limited. So uh the identity default function.

Speaker 2: Yeah, I think that's the same as the code sample Harry posted.

Speaker 1: Ah, okay, I haven't seen the codes.

Speaker 2: Return self is other.

Speaker 1: Okay. Uh why does Python force you to redefine hash to keep hashability when you're having why doesn't it inherit the parents' hash cash?

Speaker 3: Can you can you read them out of love? Yes, sorry, sorry, sorry. So

Speaker 1: if someone is asking uh why Python forces you to redefine dunder hash to keep hashability when you override dander egg why doesn't inherit the why doesn't it inherit the parents uh under hash? And that's a very good question. And I think that is uh design. I mean I think it could have gone either way. My best guess was to avoid people from not being aware that this was the behavior they were getting.

Speaker 2: Cool. I think that's all the questions. I just moved them all into the answered tab if anyone wants to check them.

Speaker 1: Okay, while maybe while someone wants to wait for another question or give some time to someone, I'm gonna uh share the the slide.