Making an Algorithm Faster

Key Takeaways

these are very very quick operations for your CPU to perform in fact this is mainly what the CPU does CPUs don't know how to add numbers together they use I've been seeing this video in my YouTube feed for a while now this algorithm is a million per Faster by this little YouTuber called the primagen and I watched it and it's honestly one of my favorite videos of all time and I think this is one of the few things that I'm actually qualified to talk about so I wanted to give kind of my analysis on making an algorithm faster from the perspective of aite monkey 1.6 million per faster it's hard to even display visually because it shows up as nothing today I'm going to show you the seven steps taken to improve the running time of an algorithm but here's the kicker the slowest one was O of N and the fastest one is still o of N and along so when it comes to interviews the Big O run time is usually the thing that you want to optimize for when it comes to competitive programming though often like the actual runtime matters as well and most importantly when it comes to real development the actual runtime is the only thing that matters on the way I'm going to use common optimization techniques that you can use in any application and then we're going to get a little bit exotic and go into the bit manipulation world to really speed things up then of course compiler optimizations and simy and everything to go blazingly fast but first the problem of course right so the problem is simple it was from Advent of code 2022 which is find 14 distinct characters in a long string once you find 14 distinct characters you just report the position directly after those I'm sure you leak code people automatically know how to solve this problem immediately given an input string like this what we want to do is find the first window which I believe in this case is actually this one of length 14 so I believe that's this such that every character in the window is distinct and then we want to return the index directly after that which I believe in this example is 19 so how do you solve it well it technically doesn't matter given the fact that this window is of fixed length if you only care about the Big O runtime it actually doesn't matter a Brute Force solution would be Big O of let's say 14 * n obviously this is a constant so you check every single window starting at every single character from the leak code perspective the obvious optimization would be the sliding window algorithm where we do this two pointers one pointer is here left second pointer is right you keep Shifting The Pointer until you get a window of size 14 or you reach a duplicate character so in this case we see that our window has two JS now how do you detect the fact that we have duplicate characters the simplest data structure to use would be a hash set since it does provide constant insertions and constant lookups hash sets though actually do have overhead because if you don't know a hash set under the hood is actually implemented with a dynamic array so if we want to get rid of the overhead involved with that we can direct directly just use a dynamic array there's actually two different ways you could use that Dynamic array one would be I think given that the character set is going to be lowercase A through Z you could have one of size 26 where each character will correspond to that index and maybe it can be a Boolean Dynamic array which tells us if a given character is present in our current window that way we can continue having the constant lookups and constant insertions the alternative would actually be to have a dynamic array of size 14 in which case we just take each character push it to the dynamic array constant operation but then how do you perform the lookup because you don't necessarily know which position each character is going to be in well doing a linear scan in a dynamic array is going to be an operation like 04 still a constant and that's relatively fast as well now if you've taken my algorithms course or if you just know how Dynamic arrays work in general they're not magic a dynamic array encapsulates a static array more specifically as the dynamic array grows it's going to continuously allocate new static arrays to keep up with the size and they'll get larger and larger so if we want to remove the overhead from the dynamic array we could just use the static array from the start now static arrays store data whether you're talking about a Boolean array or an integer array so to go even lower you can use something called a bit mask which is actually something we covered in the last few leak code problems coincidentally and so that suppose you use a 32-bit integer again mapping each character to a specific bit this will be even faster from the CPU perspective because we will be doing binary operations for the most part for example bit wise and bitwise or bitwise xor these are very very quick operations for your CPU to perform in fact this is mainly what the CPU does Believe It or Not CPUs don't know how to add numbers together they use bitwise operations to do that and so even though a sliding window algorithm can be implemented with any of these four data structures I hope this makes it clear why the bit mask would be the most optimal way to implement it and the performance gains definitely are real for large inputs as we're about to see if you're not familiar with Advent of code it's kind of like a fun Santa themed holiday Adventure in which you're solving problems to bring Christmas Joy the simplest solution possible would just be to use a hash set right grab the first 14 characters throw them all in the hashset and then check the length of the hashset at the end now one thing I think worth mentioning is the fact that our window here doesn't always have to start at the beginning of the next character like if we detected a duplicate in this case if we see the second J we could then start our window after the first J because we know that the second window is also going to contain two JS because it starts at that J if it's 14 we got ourselves a go if it's not we need to move forward everything and try again we need to try again try again try again try again oh my goodness look at that we have found 14 distinct characters now all we need to do is report that little J right here that J position and we've solved Advent of code so here's the code very very simple we simply go it's simple code but this is rust so that's not personally a language that I'm familiar with but conceptually I think we can see what's going on it looks like this is going to create an iterable of size 14 given the input and this second part W I believe is that window itself and then from that window we're going to collect all of the elements into a hashset data structure and then we compute the length of that hashset if the length is 14 that means it has 14 distinct characters if not then there's a duplicate so it would return false and to be honest I'm not sure the semantics of this but conceptually that's what's going on over 14 characters at a time collect it all into a hashset check the length of 14 boom we're done now there's a very simple optimization that could be made and this is the first optimization which will lead us to a 92% faster runtime and of course that is to insert characters one at a time the moment you detect a duplicate you do not process any further and we go to the next set of 14 I so that's definitely worth mentioning and it does fall into the sliding window approach that I talked about so the optimization he's making is as soon as you detect the duplicate you don't have to compute a window of size 14 but he's still shifting his window by one I believe when you don't necessarily need to which I think he covers later on I know it's shocking right 92% faster for such a simple if statement let's go to the next level of optimization this is going to improve the running time 8.9 fold practically an order of magnitude faster and it's going to surprise you how we do that that of course is to use a vector instead of a hashset it might be a bit counterintuitive you're thinking well why would checking every position somehow be faster than a hash set lookup aren't those constant time yes but so is a single Vector lookup it's also a constant time but I want you to think about something when you see Big O of one constant time it's kind of a lie in the sense that it's actually Big O of a constant multiplied by one now what is that constant when it comes to a hash set that constant is significantly larger than a vector constant and that should make sense right because when you're talking about a hash set you have to compute a hash and an index into a large table inside that table you then have to go to that entry and potentially scan through some couple item list if there are any collisions and check for equality whereas with I think he's absolutely right and I think this is why Big O notation can be so misleading for people especially beginners the constant does matter and that's particularly the case when it comes to small input sizes now in this case since both of them are constant operations it must be the case that a vector will be faster compared to a hashset because of the overhead I mean hash sets are implemented with vectors it's like how a virtual machine runs on top of your host operating system you would not expect the virtual machine to be faster than the host operating system Java code in theory will never be faster than C it'll always be slower with the vector you're still allocating on the Heap like a hashset but you just simply have to follow a reference and calculate an offset into a memory region that's just going to be super fast in comparison and the code's not that much more complex we create a vector instead of a right so here the smart thing to do is definitely declare the vector with the capacity up front rather than it potentially like starting out smaller and having to resize that would be additional overhead that can be avoided the one thing here though that you see is the vector do contains so again this is like o of 14 the alternative would have been to create a vector I believe of 26 characters assuming that the input character set is lowercase A through Z and in that case we wouldn't need to do a vector contains and we also would not need to have a vector of characters we would have a vector of booleans and for each character we would know whether it's present or not based on the true or false value hashset and we simply have to call contains instead of checking the return value of insert it's really not that much different but it is significantly fast fter and the same codee but in JavaScript is 6.7 times faster it is it works in both languages because adding and checking a list in general is significantly faster than a hashset on a small scale small absolutely the case and fun fact even on NE code. there are places where I actually do a linear scan through an array rather than using a hashset because it's several orders of magnitude faster because I have a relatively small data set that I'm searching through so you know Big O notation is not the end all be all all scale meaning a few items like 14 all right the next one should be obvious what we're going to do here and this one will be 26 times faster which of course is to use an array instead of a vector it's stack allocated and we get like some cash locality kind of benefits here very interesting points let's talk about them from the video the other day we kind of talked a bit about memory when a program is running its code is loaded into memory we also have a memory region called the stack it's a fixed size and we have another region called the Heap when we allocate a data structure within our code for example a statically sized data structure like an array let's say like up size 14 and suppose we do that within a function well once that function is finished this will be popped from the top of the stack so stack is convenient when it comes to memory because your operating system will maintain like a pointer and it'll tell you exactly where the next variable that you declare is going to to go and after a function is done executing that pointer will tell you that's the memory that you can free now whereas when you have a dynamically sized data structure like a vector even if you declare the vector up front and you say well I'm going to give it size 14 a vector like I said is generally implemented with static arrays under the hood and those need to be dynamically allocated at runtime and so that's going to use a region of memory called the Heap and your operating system does not have like a pointer that tells you okay well next time I declare a variable just do it on this portion of the Heap so it needs to actually scan potentially like scan through and find a region of memory where we have enough space to store that and then once it's time to free that memory it needs to then go to that region and there's much more overhead in doing something like this for your operating system than it is to use stack now another term that was mentioned cash locality in my humble opinion and I could be wrong about this I don't believe that would be the most significant factor when it comes to the speed up of using an array rather than a vector because cach locality basically means when you read suppose one byte or maybe four bytes one piece of data from memory your CPU will actually make an assumption and say that well if you're reading memory from there I'm going to read extra memory close to there and store it in the cache because it's a quick operation for it to do and if the assumption is correct that you are going to need the data near there well then it's been cached now that would mainly become relevant if you had a vector that was continuously growing and continuously being resized because every time you resize a vector it's potentially going to deallocate some memory from the Heap and then allocate new memory in a different location in the Heap which is probably going to be of larger size and therefore the CPU is once again going to have to take all that data and cach it again whereas a static array stays fixed and that data will probably stay within the cache and there's no resizing going on I believe for a relatively small Vector though the cash locality wouldn't be significant again I could be wrong if you know more than me about this feel free to comat much much faster but obviously this one's a bit more work cuz now I have to keep track of the index as well because I don't want to keep checking all 14 elements every single time but just a subset of them but still not much more complicated than our previous solution now I know at this point this has all been a bit surprising especially if you have not used a real l anguage real language meaning a language that has static arrays hey sorry JavaScript what about array buffer oh based on that definition I think python is actually also not a real language which you know I have no complaints about okay calm down I I mean they kind of do but real talk these next couple of optimizations are going to be a bit wild we're going to go from 26x to 233 times faster we're starting to get into the blazingly fast fter category all right before we can go blazingly faster which is technically a word you first need to hit the Subscribe button and I'm going to explain to you about bits because from here on out all the solution involves some bit manipulation to gain some super speeds because we no longer need to use an array we can use a singular 32-bit number to store the state of our search one thing you have to understand about aski characters is that there is a numeric value Associated for each one of them and they happen to be contiguous from 97 to 12 second a u32 is an unsigned number that has 32 bits you can think of that as an array that has the ability to store a true or a false in 32 positions a true being a one a false being a zero that mean right so what he's getting at here is that a single integer can be used as a replacement for the hash set or vector given that we can create a unique mapping for each character to a specific bit the only complexity involved with this would be coding it up so from our perspective as programmers this solution might be more complicated unless of course you know you're Elite code person like me solving all these bit mask problems lately but from the CPUs perspective this is going to be a much simpler solution it's going to involve less instructions means any character that's moduled by 32 will result in a number between 0 to 31 which is how so this is a very interesting way of doing it I actually do it a different way I typically get the asky value of the character let's say the arbitrary character is X and then I subtract from it the asky value of lowercase a this is generally a built-in function in Python it is in a language like C I'm not 100% sure about rust but in C a character is generally a one bite value or eight bits in C you don't even need I believe a built-in function to do this arithmetic because you can take like the subtraction you can take a character and when you do the subtraction from it for example if you were to do lowercase z subtracted by lowercase a implicitly the integer values of each character will be used so basically the approach that I'm suggesting would map each character from 0 to 25 in a straightforward way now the approach he suggested is actually very interesting you take that integer and actually mod it by 32 the reason for the mod by 32 is because we guarantee that every character will be mapped to a different position given that this set is like 25 if it was greater than 32 that guarantee would not be true but the difference though is that modding by 32 guarantees that the output will be somewhere between 0 to 31 that's fine because we have a 32-bit integer so each character will correspond to a distinct bit in our 32-bit integer but we don't necessarily know that the order of these would hold I believe this modded by 32 is going to be 1 this would be two and then then this would end up being 26 so coincidentally it does work out to be pretty similar and I'm actually not sure if that's a coincidence maybe these aski values were set intentionally so that modding them by 32 would produce this though I could be wrong how many bits are stored in a u32 let's go over a quick example let's say our search state is zero we have not seen any characters yet and we want to insert the character d d or 100 modulo 32 is four a left shift operator is the equivalent of multiplying by 10 that means we're going to shift this one over the terminology he's using I'm not familiar with using like base 10 terminology when referring to binary numbers but maybe that is common in some cases but just to make it clear we are dealing with binary here when shifting to the left by one we are actually multiplying the underlying integer by two and lowercase D if this is the binary representation of it that's actually the integer four by four positions thus equaling the binary representation of 1 0 or binary 10,000 so if our state is equal to zero and we or it with our new binary value that we just created the resulting value will be binary 10,000 so just to make this clear if we have let's say an empty 32-bit integer or zero and we want to set a particular bit if we had that mapping suppose a corresponds to zero suppose B corresponds to one and suppose we want a set B we want in our data structure which is now no longer a hash set it is a bit mask a 32-bit integer we want to then say this bit should turn into a one and with that we can take one bitshift it to the left by this number I'll use actually uh example D in this case D would correspond to three so we would take one shift it to the left by three so it would go from looking like this to looking like this so that tells us this is the bit we want to set and then you can take this number put it over here stack it here and then do the bitwise or between these which will set the bit to one here and every other bit will stay the same from your perspective if you're a beginner to bit manipulation this seems complicated it is for most people this code wouldn't be as readable as the hashset solution but from your cpu's perspective this is actually more readable your CPU understands this more easily because there are less instructions involved so this is a extremely interesting solution to me and it's very subtle so I think it's definitely worth talking about this one cuz it's the first one that actually takes advantage of the fact that we don't always have to restart our window from scratch every single time and it does it in a pretty clever way suppose with the and and or operations we talked about you check a window you set each character and if you see that a character is already set well at that point the window can't be correct so you try the next window and we do it from scratch now if we use actually the exclusive or oper operator which if a bit is already set it will flip it a zero will turn into a one a one will turn into a zero that's interesting because given the first window suppose we can then take a new character and then flip the bit so if it was Zero that bit will end up being one if the bit was already set though it will turn into a zero that indicates to us that we have duplicate characters now if the bit mask originally was meant to store that this particular character exists but now it's zero that seems like a conflict it seems like the bit mask has lost meaning but remember that the purpose of the bit mask is to count are there 14 bits set because if there are that means there are 14 distinct characters so the fact that duplicate characters will turn a bit into zero actually doesn't cause any issues and even more so now we can actually shift our window by one every single time we can take the leftmost character and exclusive or it to toggle that bit and we can take the rightmost character and also exclusive or it to toggle that bit go over the input 14 at a time if you're not familiar with the windows operation it literally goes from 0 to 13 1 to 14 2 to 15 it just does a nice window for you and we keep doing that little window crawl motion over this clever algorithm earned Benny 233 times faster than the hash set or and for the record just the window aspect of that solution is clever but the exor is really the complicated part of that solution you might look at it initially and think you understand it but I don't think it's actually as trivial as that or 23,000 faster it is incredibly clever algorithm hats off to Benny damn it Benny what a smart man and to think my solution was only like 100x faster than the hashset one I feel so stupid looking at Benny's super clever window C in solution let's kind of get into our final form here we're going to look at the algorithm that sped up Benny's by over fourfold it was approximately 1,000x faster so instead of walking through the idea let's just walk through the code on this last one cuz it's just mind to blowing so the first thing we do is just start by going through a fixed size windowing right here you'll notice that we do a input G from index to index plus 14 so that is a constant size window it's very very important to remember that next we create a state variable 32 bits just like Benny solution next we're going to go through that slice and we're going to iterate in Reverse now for me personally when I saw this that means we had to take an iterator get all the elements collect them all up and then walk backwards through them I thought there's no way this is faster than Benny's we do the same operation we take the modulo 32 of the bit we test to see is that bit already set to one if it is set to one then we found a place of a duplicate we then shift on that bit using the or operator then we return whether or not okay I thought that this was something clever going on but no it's actually just set the bit and determine if it was already set and then return the result of that so even if it was already set we would still end up executing this line of code which wouldn't really do anything if it was already set we've seen this bite already so here's one of the two mind-blowing optimizations if we have seen this bite since we're going backwards through the list we can actually jump all the way to this position plus one that is let's think about that for a second what the primagen just described is actually very simple conceptually it's similar to what I talked about earlier remember let's say we're still dealing with like the 14 fix size window we read from left to right we see there's a j and we see there's a second J so where would we want to shift our window next well the next window can immediately start from here because this window is still going to have duplicate JS now the clever thing for this window iterating from right to left is the fact that there could be more than just two duplicates within the window notice that if we went left to right this is what the window would have ended up being now if we go from right to left we see this J and then we see the second J so in this case we will see that okay that second J can be skipped start the next window one plus the position of that so this one will actually start a couple positions further to the right now imagine if this window was like all JS the first window would have ended up just being shifted by one like this the second window if we had like two JS here the second window would have been like this so that's the difference like all this section is what we ended up skipping and if you consider that each one of these positions corresponds to a window of size 14 the optimization is actually pretty significant that's actually something I did not consider I don't know if any of you super Elite code monkeys in the chat thought of this one I didn't because I usually consider Big O run times and this doesn't really affect the Big O runtime but it's a very significant optimization anyways I just thought that was worth explaining because I think those kind of Minor Details can get lost in the sauce and this is not trivial stuff even for me this is not trivial it's a huge optimization we're going to cut out several characters we don't have to look over and over again for if we do not find a repeat character or the false condition we actually return this index which is correct this is the position of the 14 contiguous characters now you're probably asking yourself how how show me show me how this was so fast because I don't understand why going backwards through a list was faster other than that little jump but you still have to iterate over everything right right so check this out this is the compiler Explorer this is godbolt dorg so first I put in Benny's solution right here so we can look at it first now the first thing that you'll notice is that the input right here since it was a fixed size what did the compiler do over here during optimization it actually unrolled the loop it just made it all in line so there's no jumping back and doing this a whole bunch and then jumping out at the end then we get to this our Windows 14 now this is kind of interesting cuz this is pretty much the primary Loop right here we just go over this code over and while this is very helpful like this kind of gives you insights into how the program is executing I think the intuition that I gave is honestly for a human more understandable I think you know these tools are great and I think this is kind of a point I wonder how chat GPT would explain what I just kind of said like I mentioned it's a very subtle point and over and over again so it's it's pretty fast right but now let's look at David's solution so we have the same thing happens to David solution right here it actually gets Unwound so that reverse iterator happens in Reverse right here you can see it right there look that 11 10 9 8 7 5 3 2 1 and then whatever this means I don't even know what it means and I have been told that what's happening up here is all the simd stuff that's happening that means single instruction is multiple data calculations in a single go with the compiler that means you can massively speed up what you're doing so not only is the inner loop being unrolled unlike Benny's it's also getting simd optimization and that my friends is blazingly fast but you're probably asking yourself wait wait wait that so now I think we're getting to a point where this stuff is going to be Beyond me cuz I think we're getting into operating systems and compiler optimizations uh but it's always fun learning one was 16,000 times faster no that was just shy of three orders of magnitude faster 1,000x faster was 983 X faster so how did we make it that much much more faster of course I just used my 64 threads that are just doing nothing of come on of course I'm going to do that and that allowed us to go blazingly fast okay he got us there I actually didn't watch this entire video before I started reacting to this I wasn't expecting that one you got me Prime F in fact 16,000 thousand times faster let's take a closer look at that so the base solution was one so David's solution is about a th000 times faster and so he went from 1,000x to 16,000 x via like Hardware improvements well not just Hardware improvements but making the code parallel and it looks like David's solution the one that went in reverse order for each window and also kind of did the sliding window optimization was about four times faster than Benny solution but it looks like the easiest performance gains just came from the fact that we were using better data structures with less overhead so while these Solutions are less readable and more difficult to come up with I think these are very manageable by the way if you're interested in this kind of stuff and you want to learn more or if you're just preparing for like coding interviews and stuff you might be interested in N coda.io it has a ton of courses adding a lot more lately and if you want to implement like a dynamic array you can actually do that for free 100% free if you just go to neod iio it's this nice little Le code style environment you can learn learn how Dynamic arrays are implemented under the hood and I really enjoy stuff like this if you guys know of any more videos like these please send them my way I love this stuff