My next speaker is Brian, Brian has been speaking the good of room before, even online if
I remember correctly, is some amazing complex subjects of how GoWorks internally and has been
doing an amazing job.
So I invited him back this year, well, actually, he asked, to talk about Swiss maps, which
I previously showed to wrongs his map, he's going to talk about the actual Swiss map,
so round of applause for Swiss maps.
This is a Swiss map, all right, no, well, okay.
So Swiss map is a new map implementation in Go124, and so we understand why we're here.
Hello, my name is Brian Borum, I work at Grafana Labs, where pretty much all of our backend
codes are written in Go, I've been working in Go for 10 years or so, and at work I work on
these things, open source projects for storing metrics, logs, traces.
Why am I talking about this?
Well, I watched this talk, map Cooler Cundus, is Matt in the room?
No, okay.
Is anyone who worked on this in the room?
That's good, I can just tell you anything, okay.
So yeah, I watched this talk, which is about the C++ implementation of Swiss maps, and
I find it very engaging and funny, and so this talk is, this Matt's talk is an hour
long, and in fact, this is part two, so he took two hours, and I have like 25 minutes,
so we're going to go.
So there's a map, right?
There's a map in Go, a map is a key value store in memory, and the one thing that we need
to get out of a map is that everything is pretty much constant time, so putting things in,
looking things up, and deleting things constant time.
So how do we do that?
So this is kind of an abstract, how a map works, a hash table, how does the hash table work?
Well, we take the key, I can't see the red dot, oh well, we take the key, which is over
on the left, we put it through a hash function, hash function generates a 64 bit number,
and that number changes for every different key, hopefully, 64 bits might be smaller than
your key, so they might sometimes map onto the same hash, but hopefully you get a wide diversity
of hash, and then you take that number and modulate it with some buckets, and if two things
map onto the same bucket, then you make a chain with pointers.
So this is called open hashing, this is kind of classical technique that you might have learned
in university, something like that.
There is another way of doing it, this one's called closed hashing, where instead of making
a chain you just put it in the next slot, that's not entirely true, I'm going to lie
from time to time in order to go faster and simplify what really happens.
So this one is called closed hashing, so I put those words in big text, focus on the
first two letters, so this is why it's a Swiss map, because CH is the country code for
it, it didn't hurt that the people mainly working on it worked in Google Zoo, but apparently
this is the story, it's called a Swiss map, because it uses closed hashing, alright, let's
get into, so the previous version, the app to go to 1.23, just a contrast, how does that work?
I'm going to have a spirited attempt to get a dot, no, how about if I move this somewhere
over here?
Yeah, right, so this is the data structure, right, in memory, it starts with a little bit
of sort of header information, and there is one slice of buckets, just like we saw before
we take the hash value, it's always a power of two, so modulus is cheaper, because we're
very, very focused on performance in this whole thing, and then was a bucket, look like
a bucket, in this case in the go map has eight up to eight things in it, and they are laid
out all the keys, then all the values, a little bit of metadata for the bucket, and then
if you manage to fill the bucket, another one will be created with an overflow pointer,
so there's this chaining thing going on, but eight at a time, and if you get a lot of
overflows, then the whole table is resized, doubled in size, so that's how the previous
go map worked, this is the new one, it's pretty similar, there are a couple of kind
of main important changes, that the overflow pointer has disappeared, so true to the name
we're using closed hashing, we do not make chains of buckets, but the other big change,
I mean the keys go key value, key value, that's a little bit of a change, but the big
big change is instead of just one table of buckets, there are multiple, and we look a
little bit more about how that works, but basically what that allows is it allows the table
to grow more gently, or it can sort of grow each table can grow independently, so we
don't have to double the size of the whole thing all at once, right, we look at a little
bit more detail, so first of all let's just talk about what is that metadata, okay, so this
in example I've got four entries, four tables, I've got three tables, but two of the entries
point to the same table, that's how it allows it to grow gently, you can have one table
two, four, eight, whatever, you can have five tables, and the directory doubles in size as
these things grow, and we take a certain number of bits off the top of the hash in order
to look up the directory, so in this case we've got four entries in the directory, we take
two bits, it's going to get more complicated, strapping, we take two bits off the top
of the hash to look up the directory, we take the next bits down to bit 57 to look into
the bucket, to pick a bucket by modulus the size of the table, and then what do we do with
the other seven bits? Oh, we'll come back to that, I thought you'd be wanting to see
some benchmarks, so I put a benchmark in next, it's faster, so the x-axis is a number
of elements, so this is a benchmark from the go runtime, so we make a map and add a certain
number, like a million or whatever, elements to it, and then we look up all of the elements,
so every time we look it up in this benchmark it's a hit, and then we run this as a go benchmark,
so we get nanoseconds pair up, and so just to point out the numbers, it's basically
the same for small maps, and the big picture, why does it slow down, because the map
no longer fits in cache, right, your CPU has an L1 cache, which is tiny, a few tens
of k, something like that, as a level 2 cache, which is maybe a megabyte, it has a level
3 cache, which might be 32 megabytes, once you get out of the fast L1 cache, it starts
to slow down, and so basically with everything in cache they're going at about the same speed,
and as the map gets bigger, this kind of a bit in the middle, where it's like two or
three times faster, and then it gets in kind of asymptotically reaches a few percent faster,
on this benchmark, benchmarks are basically lies, right, so I run it with a real program,
which is Prometheus that I work on, and unfortunately it's like, it's about the same,
it's, very little difference observed between go 1.23 and go 1.24 RC2, and the reasons for that
are probably complicated, and I have had some discussions with Michael Pratt, who did a lot
of the work on the goal version of this, so hopefully we can get this up, but yeah, that's
a little disappointing, so I thought I'd stick that in the middle, so we get the sadness over
with, okay, so where's Michael Clicker, right, back to the metadata, so what we're going to do
with those seven bits, we're going to store them in the metadata, so once again we take the key,
we hash it, just the ones on the way in, or we need to rehash it if we did this thing of doubling
the table, we need to rehash all the elements, but generally speaking just once, we call the hash
function, we get 64 bits, and we take the bottom seven bits and stick that in one bite of the
metadata word, why seven, well we have one more bit which tells us if there's anything there are
tall, so the one bit says that it's empty or deleted, and the other if it's not emptier deleted,
the other seven bits are from the hash, one bite per element, so I've got three elements in this
bucket, so we get three hash values, and then the other five bytes here are going to say that it's empty,
that's the bit pattern with a one at the top means empty, let's look an example of how this
works in the code, so I've made up some numbers here, once again the eight zero means empty,
we're going to look for something that has the seven bits three, can anyone see it,
yes it's easier if you're human, but if you're a computer, so the the obvious way to do this,
and in fact the go one dot twenty three implementation loops, so a little four loop it says is it
the first one is it's second one is it's third one, loops are kind of slow, so cash misses and
branches are the two things that are slow right at the lowest level in your CPU, so we do something
extremely funky, I say we I didn't write this, we replicate that byte eight times,
we exclusive or, seriously, so the one that we're looking for is the one where we got zero,
so we do a funky thing to basically turn the zero into FF and then we mask that down to just one bit,
so in just a few instructions with no branches we have found the element we're looking for
and I thought you might think I was lying, so I used to go bolt, so this is the actual
machine code for this function, the go code is on the left it kind of looks like noise,
the machine code is easier to understand,
and that is, it's on the right here, and yeah, so we take the thing, we multiply it by that,
I mean that's the decimal version of that one zero one zero thing, we do multiply, we do x or
add not and done, no branches, so that's pretty cool, but there's more, if you read the description
of this talk, I promised you Cindy, what is Cindy, well this is not Cindy, so the sort of typical
traditional way that computer works, you have a stream of instructions, you have a stream of
and we compute some sort of results, the green bit is the is the logical processing unit in
the middle of your your computer, so this is Cindy, we still have one stream of instructions,
but we have multiple sets of data coming in at once and producing multiple sets of results,
so this was this kind of idea was invented really for graphics, or it can also be used in
sound processing, but once it's in the CPU, people use it for all kinds of things, and
we're going to use it to look up on map, how do you do that, how do you write Cindy in go,
well you can't, I mean the only the way this works is inside the compiler, so this is in the go
compiler source code, internal ssa.gen and trinzics.go, it matches on the name of that function,
which we had earlier, if you set this is an environment variable go AMD64, so that takes a value v1 v2 v3 v4,
and that tells the go compiler how capable your processor is, the default is v1 which is like
a, I don't know, Pentium from 1980 or something, it's nobody use, every processor pretty much has
got these nice Cindy instructions, but you do need to set the variable to v2 to convince the compiler
that it should be using them, and yeah, I couldn't use Godbolt because you can't set the environment,
but you can't persuade Godbolt to compile that exact function, so I can't show you it that way,
but I'll show you, I'll show you in this visualization how the Cindy instructions work,
I mean the basic point of this is that things like that multiply that we saw earlier,
multiplies pretty slow instruction in the CPU, it might take 14 nanoseconds,
whereas mostly instructions we're going to look at here take one nanosecond, plus or minus,
I lie a lot, okay, so we saw this before, right, there's some, these are the seven bit hashes,
three of them, and 80 remains empty, we, this instruction is called a broadcast, so we go from the
one byte to eight bytes all the same in a single instruction in a single clock cycle.
We don't have to do XOR and an end and a knot, because there's a single instruction
that matches each byte individually, so we find the one that we're looking for,
and then we squish that down to a single byte where one bit tells us which one we found it at,
and it's a little confusing because the bytes and the bits are the opposite ways round, so
blame until. So, yeah, this is, this is, the bias complicated as my talk gets,
so what are we looking at here, we've used Cindy instructions where each instruction
executes more or less in one clock cycle. We have from a bucket of eight up to eight elements,
we've found the one, in my example, that matches, because only seven bits, there's, there's a one
in 128 chance that you get a false positive, so it's a little bit better than 99% of the time,
you find the exact right one instantly, but if you've got a, what we need to, we need to check
the whole key anyway, once you find a match, we need to check the whole key just to,
because the hashes are small anyway. So, false positives are a little bit of a drag,
but less than one percent at a time, and so this, this, it blows my mind, this is really why I
wanted to do this talk, because this code is so clever and so tight, and I believe this is
down to Jeff Deenan's surgery, again, who are the sort of superbeings of Google.
All right, what else we got? More benchmarks. This is memory size.
The 124 map is generally a bit smaller, and sometimes it's a lot smaller, so let me just explain
how I drew this chart, how I measured this. I actually, when you run go benchmarks, it gives you a
memory number, but that includes memory that was allocated and free. This is just the allocated
memory. The stuff that's left live, what your program actually needs to run.
And what I do is I call make, and I don't give it the right size. I don't give it any size at all.
So the map has to grow, and what we see with those humps is all of those overflow buckets,
and then the doubling. Those two things give you this massive jump. So the go 124 map can be a
lot smaller, just depending on how unlucky you get. It tends to always be a bit smaller,
because it is packed tighter, what we call the load factor. How many elements will it allow
in a map before doubling the size? That went up slightly.
Yeah, I just wanted to, that's the overflow buckets. That's why those big humps are the overflow
buckets. Okay, shut up. This is the worst case for memory. So this is a map of an empty struct,
right, a structment nothing in it, and people use this as a set type, just we just know if it's
in the map or not. The 124 map ends up allocating eight bytes for each empty struct,
which is a bit of a mistake. Sorry. So yeah, this is the, this is the showing the go 124
the Swiss map in the worst possible light from all the benchmarks and all the
investigation that I did, this is the worst thing it does. Probably this will get fixed.
Oh, by the way, release. Oh, yeah, let me talk about that in a second. So this is, this is the issue
to track 71368. If you want to know when they fix the empty struct bug or inefficiency.
The release of 124 is delayed, because I found this bug. It's not a bug in go. This is a bug
in the library called modern go reflect two, which I had not heard of, but it is used in JSON
iterator, which I use all the time. JSON iterator was using unsafe techniques to look at the
internals of map. The internals have changed a lot. It's broken. So there's going to be an RC3
go 124 RC3 in like on Tuesday roughly. So that pushes back the release by like another week.
What they did in, so this is the tracking bug in where the problem exists, but this library
seems to be abandoned. So you know, just stop using it. So in go there's a layer, they basically added
an extra layer of indirection, because that's the way you fix every problem in computing.
So basically when you use this or any library that is going behind the back of map to look at
the internals, it actually gets a compatibility layer, which then now works. But adding the
compatibility layer slows you down. So it only slows down the people using the the back door
access, the unsafe access. But that's kind of worth knowing about. All right, we're basically
done. I wanted to put up all the people that really worked on it, just to be clear, I did not work on
this. So very, very clever people. And yeah, I could take questions. I have some links here
if, uh, and some credits.
Are there any pressing questions? I see a very raised hand right over there. Please speak as
close as you can to the microphone. Thank you for the talk. If we go so button to the
instructions, it means it's already architectural dependency for the processor and yeah, yeah.
So the code I showed was was Intel AMD code. And so they, they have not written, yeah, they've
not written this code for ARM or any other architecture yet. But it can be written. And then the
other version with the multiply, that does work on ARM. So it's already faster on ARM, but we don't
have the SIMD implementation on ARM yet. Thank you. If you have more questions, please be
going to be in the hallway. We have to switch fingers now, last forever plus.