Finale: Replacing Dictionary to Cut Time in Half Again

struct Slot {
    var keyPointer: UnsafePointer<UInt8>?
    var keyLength: Int
    var hash: UInt64
    var entry: Entry
}

struct StationTable: ~Copyable {
    static let capacity = 1 << 14  // 16384, a power of two
    static let mask = capacity - 1

    private(set) var count = 0
    private var slots: UnsafeMutablePointer<Slot>

    init() {
        slots = UnsafeMutablePointer<Slot>.allocate(capacity: Self.capacity)
        slots.initialize(
            repeating: Slot(keyPointer: nil, keyLength: 0, hash: 0, entry: Entry()),
            count: Self.capacity
        )
    }

    deinit {
        slots.deallocate()
    }
}

mutating func add(
    temperature: Int,
    cityPointer: UnsafePointer<UInt8>,
    length: Int,
    hash: UInt64
) {
    var index = Int(truncatingIfNeeded: hash) & Self.mask

    while true {
        let slot = slots + index

        if slot.pointee.keyPointer == nil {
            slot.pointee.keyPointer = cityPointer
            slot.pointee.keyLength = length
            slot.pointee.hash = hash
            slot.pointee.entry = Entry(first: temperature)
            count += 1
            precondition(count < Self.capacity, "station table is full")
            return
        }

        if slot.pointee.hash == hash,
           slot.pointee.keyLength == length,
           memcmp(slot.pointee.keyPointer!, cityPointer, length) == 0 {
            slot.pointee.entry.update(temperature: temperature)
            return
        }

        index = (index + 1) & Self.mask
    }
}

struct Entry {
    var min: Int
    var max: Int
    var sum: Int64
    var count: Int

    init(first temperature: Int) {
        min = temperature
        max = temperature
        sum = Int64(temperature)
        count = 1
    }

    mutating func update(temperature: Int) {
        min = Swift.min(min, temperature)
        max = Swift.max(max, temperature)
        sum += Int64(temperature)
        count += 1
    }
}

Okay, we have arrived at the last episode of the Billion Row Challenge. Last time we had a huge improvement where we got the time to just under five seconds. So we are in the order of magnitude of the best solutions that are out there. Another thing that I noticed on the 1 billion row challenge, if we look at the original blog post, it had a leaderboard for the top results. And this is what we're looking at last time. time and I and I actually went back and I read more of this post and it turned out that there were some people who were because he had given you the answers the key that it is then going to be judged on some of the solutions end up optimizing specifically for those keys and realized that there weren't potentially 10,000 city names there was much low much less much fewer and so he We ended up doing a bonus round with the 10,000 keys set, and those are much closer to our numbers. Oh, okay. That is interesting. Then there's also...this one is 32 cores, 64 threads, so this is a beefier machine that I am running on. You can get this to damn near instant for some of these solutions. But I think that it's worth noting that this is not the machine I'm running on. It's going to be wildly dependent on the hardware. So instead of focusing on the leaderboard, I think it's best just to focus on, are you in the general ballpark? And judge against yourself with the improvements that we've made so far. Yeah, that makes sense. I think it's particularly interesting because we haven't, I mean, I don't know how to compare how much time you and I have spent with these other optimized solutions, but I just have a feeling we have spent much less time Probably All right, so this is where we stand right now So let's go into instruments and we're going to record a trace to see like where is the time being spent now Because there there are things that we can do we can find you know the low-hanging fruit It's going to be harder and harder to find those things and then probably harder and harder to optimize them So my suspicion is we have like one more optimization that's kind of easy enough to make, and that should give us some results that we can call it done. Let me make sure that we're using the large file here, and we are. And I will hit start.

And so this is now showing us this work being spread across all of the different cores, which is nice. Yeah, that is always interesting to see. It also is significantly slower, but just because we're instrumenting, I'm guessing that's affecting it. What do you mean significantly? Oh, the total runtime is longer. Yeah, so this was like 10 seconds. And we are in release mode. So I'm not quite sure what that accounts for that. Me neither.

But instead of focusing on the specific number of seconds, I'm just going to look at like what is the percent weight. Now I will say, well, I just want, I mean, just to throw it in there is that I'm actually not familiar with how instruments works in general lately. But in the past there have been, because like performance work is so important, there's been a lot of hardware level support for very low overhead sampling and instrumentation of code. Yeah, it does seem weird that it got twice as slow. It can't. I just, it's unthinkable that it would be purely the instrumentation, but it could be like there's more over, there obviously is more overhead somewhere else. Okay. So because all these threads are doing the exact same thing, I'm going to go over here to call tree and we're going to say to not separate by thread. Oh, yeah, that's interesting. So then just lump all the results together. So now we get the total time. And this time is now gonna be in the minutes because we're now taking all that time and adding it together, right? So, you know, 10 cores or whatever it was, 16 cores. Okay, so all the time's being spent here. And if we just sort of expand out, we get down to this process results function, code, which is a good thing to see. And then here the numbers start to split apart pretty drastically, but look at the top two. Dictionaries. Dictionaries, getter, and setter. That is interesting. Like over 50% of the time is spent manipulating the dictionary, the results dictionaries that we are building up. That's the only place where we use a dictionary right now? Yes, that is happening. Uh, down here we have, uh, in process results. We, Oh yeah. Results is a dictionary type. Yeah. Yeah. I remember now. So we get this, um, this guy, we get our city key, we parse our temperature and then we, uh, do this here. Now, interestingly, where is the case where we don't have...

Oh, here. That's what I was looking at. So this entry here, or sorry, this entry variable here is reading out of the dictionary, then mutating its copy and then putting it back. So we could probably, I believe there is some way of mutating in place for dictionaries.

But ultimately what I want to experiment with today is instead of using dictionary, which is a general purpose tool that is tuned for the vast majority of use cases,

none of which we really care about in this case. We just want it to be as fast as possible. In fact, we're already abusing it by sort of bypassing its hash and hashing ourselves. Yeah, that's true. Okay, this is all very interesting. Okay, so what I would like to replace it with is a flat hash table that uses open addressing and linear probing. So I have some Wikipedia things up here. I've never heard this from open addressing before. Okay. So open addressing means that you have a key, and then that key takes you directly to the entry in your table. And the data is right there. Oops. I don't know what I just did. But the data is just right there. It lives along with the key. So you don't have to go to, so like maybe from computer science, if I go back to my whiteboard. So say we have a key which gets put into this list here. So we've got a key and that key is like maybe a pointer to like some memory. And this could be an array, right? So to handle put the element in that first one. But if we have another key and that key puts us in this bucket, but there's already an item there and it doesn't equal the item, then we're going to go over to the next one. So these arrows are following pointers to memory that's on the heap. So it's scattered all over the place. There's also the notion of linked lists for collisions, which is all fun stuff to explore for data structures and computer science. I can nerd out on that stuff. But this is not fast.

Ideally, the memory exists just in one big array. Yeah. And inside of here is the memory that contains the key and the value. and given the key, we can jump straight to this spot. Yeah, yeah. This has way better locality. Yes. Cache locality is a term that I have become familiar with, right? Because when we're reading from an array like this, the CPU will put as much of it can fit linear. You're probably going to grab the next bit, so I'm just going to take this entire window of memory and put it in the L2 cache or L1 cache. So, and it is like, you know, the difference of, you know, reaching out and grabbing something off your desk versus having to drive to the grocery store to go get it. That's kind of the analogy I like to use or, you know, the difference between L2 cache and RAM, for instance. And then the hard disk, I might as well be driving to where you live. You know what I mean? Yes, exactly. Okay, so this is great if I can choose this function that says, given a key, I get an index. And that is guaranteed to be unique, right? Which we can't guarantee. Well, we could cheat. I mean, I bet you those optimized solutions probably are scanning the keys first and then producing something called a perfect... One solution could be a perfect hash. Yeah, and that is actually against the rules. There's no pre -computation allowed. It has to be done at runtime as part of the measurement. So what happens if we have a hash function that is pretty good, that takes a key, gives us an index, and if that index is occupied, then we can use linear probing, which is the other term I mentioned, open addressing and linear probing. Linear probing just means, okay, let's just grab the next spot. And if that's empty, we're going to take it. So you do get some sort of pathological cases if this function is bad, right? If you have many, many entries that all slot into the same piece in memory, then you have to do linear scanning to find out. Yeah, it degrades to a pure, regular array. I guess also unsorted, I'm sure. Yeah, unsorted, because there's no sorting with the keys. I do have a question though, hang on. I don't understand the open addressing part. to open addressing? Let me see if Wikipedia has a better way of describing this. It's a method of collision resolution with hash tables. With this method, a hash collision is resolved by probing or searching through alternative locations in the array. And so there's linear probing, quadratic probing, double hashing. I just don't understand why the term open addressing was chosen here. Yeah. Not that it matters much. I just wanted to understand. I sort of interpreted that as like addressing the data structure directly rather than the indirection of like, first you get where the key is and that key points to your data. But maybe that's a different term that I'm not familiar with. It's not super important anyways, but I'm following you. Okay. So we have this problem of like, let's say we have 10,000 keys and we have 10,000, or N here is 10,000, then we have to be perfect. Otherwise, we end up with these cases of like, you get collisions, you probe, probe, probe, probe, probe, you got to walk around the end of the array and go back to the beginning until you find you're in your empty slot, right? But if we make something that's just like way bigger, right, then we have a lot more holes in the array and holes are good, because we can just go jump straight to a spot in memory and it's likely to be free. Yep, I'm following you. So we're going to have some sort of max count here. Okay.

So let's start off with a struct called station table. Yeah, so like this station table is going to be basically And we're going to use an unsafe pointer to some type that is going to be our array of slots. That actually will need to be mutable. So I'm going to make a slot type. And the slot is going to grab our key pointer. Because remember, we don't want to copy the string key into a new place in memory, because we have this memory map file that will live for the entire lifetime of this application, we can point to that memory instead of copying it. So this ends up becoming an unsafe pointer to some byte in memory, but critically can be nil because slots are going to be empty at first. Yep, okay. Okay, so then I'm going to say... But that's the key. But doesn't the slot have to also contain the values? It does. Yeah, okay. It does. So in addition to this key pointer, we also need the key length, which will be an int. And we also need our pre-computed hash, which I think was an unsigned int 64. You went to 64. And then finally, we need our entry, which is this struct with a min, max, sum and count. So like these two things give us the city name. This gives us the ability to figure out where it exists in our station table. and the entry is the data. Yeah. Okay, so now- Can I have one more question for you? Yeah. Because I don't use the unsafe types that often in Swift, but there's so the unsafe pointer, I get it. And I understand why you have the length. Is there not an unsafe type? I know there's the buffer pointer, but that's like a whole string of human dates, for example. Are you talking about this one? Yeah. Is there not an unsafe structure that contains both the pointer and also like a length? It just seems like a really common thing to need. That's buffer. Oh, that is buffer. So I think maybe I could do unsafe buffer pointer here to you int eight. Let's explore both of these. Doesn't matter. Yeah, I'm just, right, that does make sense because that's what it is. Okay, yeah. Okay, so now this station table, because it's a collection, I'm gonna need say a private set var count, which will equal zero. And I mentioned that we're going to need to know how big this array is. Like how big is this data structure? And I'm going to pick one that's sufficiently large enough, like larger than our data set, potential data set, so that there are holes in it. And so I'm going to make this a static let capacity. And for capacity, I'm going to make sure that this is a power of two. And so if I do two to the tenth power, that gives me a thousand. Eleven gets me two thousand. And if I just keep going, I end up with, this is like the next power of two over our data set size, which would be 10k. In fact, it'll be considerably larger than when we split this across cores, right? Because each one's going to have some

Right. Okay, so if I do bit shifting, then that's 2 to the 14, which equals 16, what was it? 2 to the 14 is 16, 384.

okay now I'm going to need my init which is just going to start at zero and the first thing we need to do to this sort of pointer in memory is allocate the memory so this is like we're full on outside of Swift helping us here yeah so slots here is going to be unsafe mutable pointer dot allocate and then you allocate with the capacity that you want and because it knows the layout of this type then it can figure out how many bytes of memory to reserve because we just did that we definitely

to deallocate that pointer.

That is interesting because this is a struct. It is a struct. Yeah, let's make it a class.

Actually. You can actually do that. That's a new thing with a non-copyable type. You can actually do it. Sorry. You can do it. And that is the point that we, We, that, this is the point that I think is really valuable because we don't often run into these situations where like, where does non-copyable help us? And the reason why this is a problem is I could have some code here, which is like, hey, I've got a station table, right? We just allocated memory here.

And then if I say var y equals x, I'm making a copy of a pointer to that existing memory. But later, when they go out of scope, x deallocates, and so does y. Yeah. And y becomes effectively a dangling pointer. Well, this becomes a double free, so that's a crash. Oh, yeah, they both deallocate. Yeah, with the d in it, exactly. You either get the double free or the dangling pointer. Yeah. Yeah. So if I say that this is a non-copyable type, it prevents me from doing this.

That's right. Which, and this is the first time since the introduction of that, that I felt like, oh, that's a useful thing that I need. Like, I know it's useful in certain situations, but I just typically don't encounter them. Yeah. I mean, it's a specialty thing that is actually, I think, quite rare to need to use. Okay. Okay, so we've allocated memory, but we've just been given a chunk of memory by the operating system that has whatever in it, right? So we're used to zero initialized memory in Swift, like your variables. Like if I just say this is an int, or if I say a bool will default to false, like there's all this just sort of implicit behavior that we have that we don't get here. So I do need to initialize this and I'm going to say repeating. And at this point, I'm going to repeat a slot that has, I don't know what happened with, well, keyportner is nil. I guess it's figuring that out for me. The key length is zero, the hash is zero and the entry is empty zero. And then this is self.capacity. So we're doing some work up front to just zero out the memory so that later when we're comparing, we know if the key pointer is nil, then this slot is empty.

Okay. I think it's also worth considering whether to do this. I was just thinking the same thing. Yeah. And I experimented with that, but then I got a little concerned about the usage unwrapping it and inserting it rather than just saying the struct data is already there and we just mutate it. Maybe that's the same. I'm actually, you know, I'm not entirely sure which one will be better here. Yeah. Okay. So now we have the, we have a function, a mutating func called add. And add is going to take our data. So we're going to have the temperature that we are... let's do temperature. And that is an int because we're multiplying by... or we're dividing by 10 at the very end. And then we have the city's pointer, which is to uint8. Yep. We have a length of the city name, which is an int, and we have our hash, which was pre-computed, which is a uint64.

OK, so here's an interesting thing. How do I turn that hash into an index? Yeah. So this is 64 bits.

And our capacity is considerably smaller than that. So there are numbers that the hash will generate that are far bigger. And so you might reach for, well, let's just divide by the length of our array, divide by capacity. And that would give us, or sorry, mod. And that would give us a place in memory. But division is very expensive. Okay. is repeated division. Yeah. So there is a trick, and I can't say that I came up with this trick. I'm curious what this trick is. A trick in computer science, which maybe you remember from school. So far, nothing's coming to mind so far. Okay. So if I take the capacity and I subtract 1 from it, then I get back another integer that is 1 less than this. All right. And it's worth taking a look at these numbers. So let's look at 16384.

And convert this to decimal to binary. It's one with a bunch of zeros, right? And if I split this up by our, well, there's 14 of them. So let's do, there's the first byte. and then it would be like this, right? But we can just kind of ignore this one for the moment. I mean, like there's zeros off into infinity in that direction. So if I subtract one from that, that ends up with zero, one, one, one, one, one, one, one. Wait, wait a second. Hang on a second. You get Fs. Sorry, this is binary, not hex. Oh, binary. Okay. Yeah, yeah, yeah. Yeah. Okay. So 16384 and 16383, if I convert this to binary, I get that. If I convert this to binary, I get this, right? Yes. Yes. Okay. So what that's useful for is then I can just take any number that's like this long. long. Well, let me make sure that it is in binary. But I've got a huge long number. And then I do bitwise and on it. All of these are zeros. So it's basically just taking the below 14 bits of the number. So it's the same idea as mod modulo for fitting a big number into a small space by wrapping, but this one is doing the same thing by just chopping off the most significant digits. Yeah, it's just truncating the hash. Yeah. So this is the trick we can use, and it only works if this is a power of two. That's right. That's right. Okay, so that's our first thing. But we could always convert. That is your right that it only works if it's a power of two, but that's saving us a relatively small, because we could just, all we need to do is know what are the total number of bytes we need to represent our capacity. And we can basically produce a mask that'll work. I think, am I wrong? Maybe I'm wrong. We, I mean, that's work though. doing no work, which I think is, you know, but it's upfront. So that's, that's that, that the work we do, we do that exactly once the mask gets computed one time and then used the total number of times. Yeah. Yeah. Yeah. But regardless, not important. I don't know if that's true, honestly, because in order for this to work, what I want to do is say hash and bitwise and it with the mask. Right. Right. What I'm saying is computing the mask is a one time cost. but we need the masks bits to be all ones. Oh, I see what you're saying. I think that that would end up using less bits than, we would always end up lining up one less than a power of two if all the numbers are one. It could be optimal. Yeah, it could end up being more optimal to do this on a power of two. I totally believe that. In fact, that seems like it could be the case because then we'd be wasting bits in our mask. But regardless, yes, I'm following you 100%. I like to think through those things. We need to turn that uint64 into an int because, and I think there's a truncating. That's a number. Truncating if needed, binary integer hash. Interesting. Okay. So it will need to truncate to this. Actually, no, it won't because you went, I'm on a 64-bit Mac. This is a 64-bit int. It is a uint64, so you'll lose one bit, I guess. Well, it'll turn into a different number. Yeah, I suppose that's true.

And okay, so that gives me my index. Now, it may be empty or may not be. So we're going to do a while loop here. And here I need to get the slot that we're looking at. And we learned this last time that we can just take this pointer and we can just add to it, which gives us a pointer to that slot. Yeah, it's interesting that that works. Okay, so now we need to look in the memory at that slot to see if the key pointer is nil. And because slot is a pointer, we can say, give me the pointee and look at its key pointer. And if that's nil, then we found an empty slot. Yep. If it's not, then we need to... So, let's see, we need to check to see if this is the same city. Because remember, we're going to be getting temperatures for the same city over and over and over again. We need to mutate the one in place. So is this the same city or not? So in order to do that, we need to check to see if the slot.pointee... Now, notably, the key pointer will not be two different cities. Because this is pointing into our data. It's pointing into our data, and you could have two different locations in memory that have the same text. Yes, we will. They repeat all over the place in this file. And so what I need to check is to see if... Let's first check the hash to see if that equals the hash that is coming into this function. Okay, yeah. Okay. So the hash matches. Then we also need to look to see if the length matches equals length.

And we actually have to, because it's possible for two strings to have the same length and unluckily have the same hash. That's true. So at that point, we need to do memCompare to compare the bits of the two pointers. which, so here we'll do slot .pointee.key pointer. And at this point, we've proven that it's non-nil, so we can force them out here. And then this one becomes the city, what did I call it? Pointer. And then now, and we also have the length. We have the length there. And mem compare will return equal, sorry, zero if they are equal. So let me just put this on new lines to make this a little bit more clear. Do we need to do, is that length argument, that last argument to mem compare, I think it has to be the minimum of slot pointy key length and length. Am I wrong about that? They're equal. Oh, yeah, yeah, yeah. So you are correct because it would make us walk across the end of one array. But because this is short circuiting Boolean logic, we, you know, the mem compare is the slow case. So we want that last. Yeah, that makes sense. This all makes sense. Okay. So at this point now we found an existing entry.

I'm just going to like fill in this logic of like finding the slot and then we'll do the other stuff first. Okay, if it's not the same city, and I'm wondering, maybe I should just return, just sort of flatten the structure out a little bit. I think it'll be easier to read. So like, first case returned, second case returned, and then if we get here, that means that this is a collision, and we need to linear probe next slot, which is just index plus equals one. And this can overflow our array. So we end up needing to do the same idea of index equals index plus one and then bitwise and with the mask which is going to keep it in the same space yeah it'll keep it in the same space that's very interesting okay okay

so at this point now we have an empty slot so now we just need to insert the empty slot so we can now say that the slot is equal to a new slot.

And then the key pointer is going to be our city pointer. Key length is length, hash is hash, and entry is entry. And here I need to add min is going to be the temperature, max is going to be the temperature. And I feel like it's actually like, could I just do something like first and pass in the temperature? I think so. And then just simplify this a little bit. So self.min equals temperature, max, sum, and count as one. This needs to be an int64.

And so back here I can see entry with the first one, temperature. Okay. So we've got that one. If it's the same city, now we need to combine with the existing one. And so we can say self, not self, slot dot pointee dot entry. And similar to this, I want to say update with this temperature. And so I can go over here to my type here and say mutating func update with temperature int. Maybe I'll keep this named. So now self.min is min, which I'm going to have to say swift.min to disambiguate that. Of my self.min with temperature, then max here, Sum plus equals temperature, which I will need to upgrade to int 64, and then count plus one.

Yeah, that's a useful one. And I do feel like this logic here is already complicated enough, I don't want to muddy the concerns. Okay. I think this is good to go, but the one thing we need to do now, because the rest of our code works with those results table, we need to, when we're done with all this, we need a function to make this into a results table. Ah, yes. So that we don't, you know, we don't have to utilize this outside of the, let's just collect all the data and aggregate all the temperatures using this data structure but then when we're done we can call make results i have a question for you yes um so the back i i get what we're doing with the station table but the back in store we chose to use where the slots live is raw memory that we have allocated yes i am curious how the performance difference would be what this would change if we just used a plain Swift array. Because I think it's largely interchangeable. Yeah, exactly. Yeah, as long as you pre-allocate the array. And if you do that, then you don't need, let's see. If you do that, you do not need the non-copyable stuff that we did because we don't de-init directly. It does reference counting. which adds some overhead, but I... Oh, there's no question. There's no... It must be that the array is gonna be more overhead. But I think critically, the thing to... Well, then we can put in slots. We can put in optional slots very easily in that array. Yeah. I think that we can experiment with optional slot because what that would do here is I would say if slot dot pointy if let slot equals slot dot pointy kind of yeah yeah yeah

I feel like I don't think it's worth we already we've already gotten pretty far oh yeah yeah but anyway so it'd be an if let there yeah I I do think it will work can probably be negligible in performance. But I did have the same question. Okay, so here we need to go through the entire dictionary. Yes. Self.capacity. This type of code looks expensive, but it is really not, because it is just... There's nothing to do but just keep marching forward in memory, which the computer is really good at. So let's get the slots plus i, and then that gives us our pointer. And then now we want to make sure that this is,

the key pointer is not nil. If it is not, then we can continue. key. And now here is where we need to turn this back into the key that we use for our results dictionary. Yes, what is the key? The key is city key. Oh, yeah. So city key is basically the same type. Oh, okay, that's not so bad. The only difference is it doesn't have the entry in it, which kind of makes me think like maybe there's a way that we could make these two things kind of the same. Probably. Okay. So we've got our key pointer. We've got our count, which is slot.length, key length, and slot .hash. Yeah, that was easy. And now we can say results key equals slot.entry. And now we've got a results table. That was very easy. Okay. Let's go down to where we might use this.

Notably, this is not sendable. It probably could be made sendable if we added guards around this stuff, but ultimately we're We're just gonna use this inside of our process results function, which is, where is it? Process results in range. So this one, instead of doing results here, we're going to be doing a station table.

We're gonna make one per, effectively per task. Yeah, okay. And then at the end, And I'm just going to change this to else break.

It's a break out of the while loop. And at the very end here, I'm going to say return table.make results. That makes total sense. And then the rest, I think, can be pretty mechanical because now we've got our temperature. We don't need to do any of this anymore. So I will comment that out.

table.add temperature. We've got our city key pointer, city key length count. What did I call it? And city key hash. And oh, not that one. Critically, not that one. So maybe this slot would have been better as like a slot has the city key in the entry. That probably would have been more. Well, you know, we're like boiling this problem down now more and more and more to its essential elements. So, yeah, it does make sense. There's going to be overlap like that. And it's always funny that hindsight, you know, is, you're like, wow, if I were to do this again, who would? Yeah. Okay. Now, we're actually building.

and that's basically all that was necessary. So what did we get rid of? We got rid of the dictionary getter and the dictionary setter, which we noted was about 50% of the time spent. Yeah, that's wild, isn't it? So let's go to our terminal and do a benchmark. So this one is going to warm it up one time, then run it twice to see what the result is.

Well, it got faster. It did. Almost cut in half, which is really pretty satisfying. Just thinking that We've observed that in instruments, the dictionary was taking roughly 50% of that chunk, the biggest chunk, and we got kind of a 50% reduction. It's not quite, but... Very significant. Shaved two seconds off of the previous run, which is incredible. And I feel like there's not much left fat to trim off of this, but I'm sure there are things. If we want to do another instrument, see if there's anything that we can glean from this second run.

and certainly did run faster this time. That is interesting. I wonder if it was more of like the warmup phase. It is, that is a possibility.

So we don't need to do that. I just need to take a look here.

So complete task disclosure. So we get again into process results.

Now there's process results in range here. I'm not quite sure how to read these two things. Like, is it because it was like this one was inlined, but then this one is in the call stack, not inlined. So I'm not quite sure how to read that. But that's 64 % of the time is in here. And now we have a notable percentage, which is platform memchar, know, we already agreed was pretty specialized or optimized and we're unlikely to do better. We can see the mem compare here, which actually did happen. So maybe choosing a larger table would reduce that number, which was 10% of the time. Yeah, that is interesting. I guess you're right. That does imply we're doing that comparison. And so it must have occurred. I mean, it occurred three. It did happen, 10% of our runtime. Yeah, so that would shave off another, you know, two to 300 milliseconds. More memory, throw more memory at it, yeah. Let's take a look inside of here. And now we can see that 26% of the time is in station table add. And I actually do like looking this in the source viewer to see, like, you know, it puts these, you know, to the code. Yeah, it is really cool. Yeah. So we are in that add function, and does it show me anything else? Let me go into there.

And what is this one going to show? Yeah, it's not showing me any additional information there. So I'm not entirely sure how to read the rest of these results. There's clearly time being spent here. This 8.86 seconds station table add, that was what we were looking at. Well, that's interesting. So that's self. So self means that stuff that that function is currently executed, yeah. And that is, there's a while loop in there. It's doing, this is free basically. We're gonna loop over

We're not allocating new memory here. Actually,

how does that end up working? Slot.pointy equals slot. Could we, because pointy is already a slot, could I just say that the key pointer equals pointer? I think so. So, dot key length. Let me comment this out so I can compare.

Another thing I'm interested in while you're doing that is you reference slot dot point e in a number of spots. Like we reference slot dot point e dot key pointer in another number of spots. And I'm not sure if that is, that's a little bit of an indirection, but we don't want those dereferences to happen more than one time. Do you think the compiler would optimize that out? I think that I want the compiler to optimize it out. So you're thinking I would do slot.pointe here and then

p.keylength. Things along this line. Yeah, things along these lines. It's hard to, I don't know which dereferences matter.

Yeah. Because then it happens a whole bunch on line 85, 86, 87 as well. So like even hoisting that up even further. Yep. But you're right. This is something we want the optimizer to get rid of for us. I just don't have a good sense because I never do this kind of stuff. I don't have a good sense of whether it actually happens or not.

Okay.

Let's try that, and then I also, on a separate run, would like to try maybe increasing the capacity by another power of two and see if that... Yeah, yeah, yeah, that's an easy one as well. But one thing, we'll change one thing at a time.

Well, I changed two things. I did the dereferencing fix and the in-place mutation. Holy macaroni. One and a half seconds. Hang on. Okay, wait. Which of these do it? Yeah, put that back. I'm gonna do this and then say P.

Wait, can I do that? P equals? No, I can't.

I need it to come from. You have to write to the pointy. Yeah, I need to do that. Okay. I wonder if we screwed this up, though. It did get faster, but is it still correct? I haven't looked at the results in a long time. I've just been looking at the runtime. That's okay. It looks like this was the biggest. The biggest thing is not creating a new slot. I was trying to understand what's happening in memory at this point. When we say slot like this, this is allocating memory, but just on our stack. Yes, so far, that's a stack allocation. And then we're copying it into this point. We're doing a copy, I believe so, yeah. I'm surprised this didn't show up in our instruments trace, though. But maybe there's something about this function, because remember, all of the time was just lumped under this one function. that those kinds of copies on like the implicit copy that's happening on 73, I think that would be counted as self time in this function, but not as a fun, it won't look up as, it won't look like a nested function call. Yeah. I think. But why wouldn't it be on this line though? Because the call stack. Yes, I think it should be. Is it because the call stack is not getting any deeper here? We're not calling any other functions? That's right. So that line, I have had, I mean, it's been years, but I have had hit or miss results with using instruments to annotate the source and get meaningful information from that. Yeah. Okay. Let me not forget the hash. That part is important. P dot hash equals hash. Okay. So that was a big win. Let's hope we get back to the one and a half seconds. Yeah, that was a big win, but I always get nervous now that we're not doing the right thing.

We can run it and see.

It doesn't print the output anymore? What's happening? Aha!

Sorry, build, release, one BRC. I think it was doing the dev null thing. Oh, yeah, okay, that makes sense. Because it's a big, the output is like 10,000 lines, no?

It's one line per unique city or station.

Let me check. Go big. Time, build, release, one BRC. Input file is this.

Yeah, we build for release.

Oh, you know what? I think that we didn't want to count the printing. I don't remember where we ended up on that. We do have to print the result. That's part of the challenge.

I think that's going to be significantly... Yeah, so here's the lines. Yeah, why aren't we hitting that? Let me just run it in Xcode.

Now because we are in debug mode, it's going to be slower. Slower, but where are we? That feels real slow.

Are we really still waiting right now? Yeah, maybe we are. Hmm.

Maybe we should use the smaller file.

Let's do build run debug.

If I don't include it, what happens? Does it require it? No, It uses the normal one. Okay.

And lines is no values. Aha. Aha. What happened? Did something wrong here. Turns out the program is fast if you don't do anything with the data. Yeah, the fastest kind of program. So was results empty? Results is empty. Results is empty. I think it's because... What's happening here? Process results returns? Did we put stuff in? We changed the process results function. This one returns results, right? Yeah, but it does return results. in that function, are we putting stuff in the results? Let's find out. I don't specifically recall doing that. I'm gonna do table add. Okay, so we are ostensibly doing what we wanna do. I can get the count of the items that are in that table and it was zero. How's that possible? Table add. Something wrong with our table add? Oh wait, did I do something wrong here? That was a return results previously. Yeah, so that should be fine, right? If we don't find this in... That does seem... Yeah, that does seem okay. So I should be able to... Is there something wrong with our table add?

Let me make sure I can get to the table add. So at this point, table count should be zero. And we go into here. We found an empty slot. Oh, I never increment the count. Aha. I do need to do that. Count plus equals one here. Right? Because... Yeah, but does that explain... Are we using the count anymore? Oh, because...

When we make the results, though, we go through the entire thing. Yeah, that's what I'm thinking. Why does the count... Oh, the one thing we need to do here is make sure that this count... is never, let's see, precondition or? Yeah, precondition works in both release and debug builds. Yeah, so this would be count is still less than our capacity. Yeah. Need a bigger boat.

I don't understand, okay, that's a bug, but I don't understand, oh wait, no. So I'm trying to figure out why that count, the mismanagement would have resulted in an empty output and I don't understand why that would have happened.

Let me, where are we right now? We are here. So our table at this point still has zero items in it. Oh, because I need to run it again. Just fix that bug live, yeah.

Okay, well, not there. So table account is zero here, should be one here. Yeah. It is. And then when we get down to- Let's look at the results. Can we run in the debugger table make results and just look at what it looks like?

Copy of a non-copyable type value. Oh yeah, right, interesting, okay. Okay, so I can jump to here. Ooh, this is interesting. That is very interesting.

Count plus equals 1. Our count is what?

16384. How could that have happened?

Oh, hang on. Are we modifying the table at all here?

No, we're not. This is a copy.

Oh, hahaha. Wait, hang on a second. That's a copy. of the pointy. Yes, you're right. So we have a slot, we modify it, but then we don't do anything with it. And so it finds nothing but empty slots. Oh, well, that helps to make it go faster too. Okay, so slot .pointy everywhere.

Let's see.

And I need that. Well, I only need it when I mutate it. It's true. That is true. But I also don't think that that was accounting for much savings. I think so, too. I think we removed critical work, and that's what made it go faster.

I mean, I guess we don't know that for sure, but I think that's what happened. Okay.

Yeah, so this one should be doing the printing, and it does. Okay.

Let me close this. So we're back in running order. Let me do the benchmark. The printing is going to add some time, but I don't think very much.

So we're at 2.6 seconds. So we fixed one problem. Did this change anything?

Because what I did before was the empty slot thing. Let me try that differently. Slot.pointy equals slot with a key pointer, the key length is length, the hash is hash, and the entry is entry first temperature. Yeah.

Okay, no. Yeah. Interesting. Okay. So perhaps this is my mental model of this needs some, some, some, some, some, we're getting, unfortunately, we are starting to get closer to the point where what the assembly looks like matters. And I do not like getting to those kinds of points, but I think that, that in this particular away. And we kind of hit that with the, when we started thinking about doing SIMD as well, which is very typical of SIMD. Okay. I'm going to leave it like this. Yeah, I like that. And I think that I think at this point, there's really no big thing for me to tug at anymore. You know, I did notice that there was the FNV hash has some time But when we look at that, it's also pretty, you know, the point of the FNV hash is to be fast. And then there was this other hash, which I don't think we ended up using. No, we screwed something. That was earlier on. That was the one I suggested. And we screwed something up in the process of doing that. Yeah. But anyway, I don't remember what our first, the naive results was, but it was in the minutes. Right? It took a very long time. uh i in fact we had to stop recording and i told you later how long it took yeah uh so so we went from you know i don't know 15 minutes or whatever it was to two and a half seconds so i think that's something to be proud of and i have learned a whole lot along the journey which yeah it was awesome which is the point and um it was really great to have you join me to go through this and dig into a deep problem. And so I want to thank you as well. Thank you so much for inviting me to do it. I never would have picked this problem and I love that this is what we dug into. Yeah. All right. Thanks everybody for watching and we'll catch you in the next one. Thank you.