This Algorithm is 1,606,240% FASTER

The video explores the optimization journey of an algorithm designed to find 14 distinct characters in a string, starting from a basic hash set approach to advanced techniques. The presenter demonstrates several optimization steps, including using vectors, arrays, and bit manipulation, each significantly speeding up the process. Notably, Benny's algorithm, utilizing XOR operations, achieves a 233x speed improvement, while David A. Perez's method, leveraging reverse iteration and SIMD optimizations, reaches nearly 1000x faster performance. The ultimate multi-threaded solution achieves an astounding 16,000x speed increase, showcasing the power of advanced optimization techniques.

• Objective: Improve the running time of an algorithm from O(N) to a faster O(N) using various optimization techniques.
• Context: The problem is from Advent of Code 2022, which involves finding 14 distinct characters in a long string and reporting the position directly after these characters.

"The problem is simple. It was from Advent of Code 2022, which is to find 14 distinct characters in a long string. Once you find 14 distinct characters, you just report the position directly after those."

• Initial Solution: Use a hash set to collect the first 14 characters, check the length of the hash set, and move forward if necessary.

"The simplest solution possible would just be to use a hash set, grab the first 14 characters, throw them all in the hash set, and then check the length of the hash set at the end. If it's 14, we got ourselves a go; if it's not, we need to move forward and try again."

• Concept: Insert characters one at a time. Stop processing further once a duplicate is detected and move to the next set of 14 characters.
• Improvement: 92% faster run time.

"Insert characters one at a time. The moment you detect a duplicate, you do not process any further and go to the next set of 14. I know it's shocking, right? 92% faster for such a simple if statement."

• Code Impact: Adds a simple if statement for early exit, significantly reducing unnecessary computations.

• Concept: Use a vector instead of a hash set for collecting characters.
• Reasoning: While both hash set and vector operations are O(1), the constant factor for vectors is smaller because vectors avoid the overhead of computing hashes and handling collisions.
• Improvement: 8.9 times faster, nearly an order of magnitude.

"Use a vector instead of a hash set. It might be counter-intuitive, but checking every position can be faster than a hash set lookup. The constant factor for a hash set is significantly larger due to hash computation and collision handling, whereas a vector simply calculates an offset into a memory region."

• Code Complexity: Slightly more complex than using a hash set but provides significant performance gains due to reduced overhead.

• Concept: Utilize bit manipulation to further speed up the algorithm.
• Details: Not specified in the provided transcript, but generally involves using bitwise operations to manage and check character presence more efficiently.

"We're going to get a little bit exotic and go into the bit manipulation world to really speed things up."

• Expected Improvement: Significant, as bitwise operations are extremely fast compared to other operations.

• Concept: Leverage compiler optimizations to enhance performance.
• Details: Not specified in the provided transcript, but typically includes enabling specific compiler flags or using intrinsic functions.

"Then of course, compiler optimizations and everything to go blazingly fast."

• Expected Improvement: Variable, depending on the specific optimizations applied and the compiler used.

• Initial Approach: Simple hash set implementation.
• First Optimization: Early exit on duplicate detection, yielding a 92% speed improvement.
• Second Optimization: Switching from hash set to vector, resulting in an 8.9-fold speed increase.
• Future Directions: Exploring bit manipulation and compiler optimizations for further performance gains.

"Today I'm going to show you the seven steps taken to improve the running time of an algorithm. The slowest one was O(N), and the fastest one is still O(N). Along the way, I'm going to use common optimization techniques that you can use in any application."

• Key Takeaway: Optimizations can dramatically improve performance even within the same Big O complexity, by reducing constant factors and leveraging more efficient data structures and operations.

• Key Idea: Replacing hash sets with arrays can significantly improve performance, especially with a small number of items.
• Performance Impact: In JavaScript, this approach is 6.7 times faster.
• Reasoning: Adding and checking a list is faster than using a hash set on a small scale (e.g., 14 items).

"Adding and checking a list in general is significantly faster than a hash set on a small scale, small scale meaning a few items like 14."

• Explanation: For a small number of items, the overhead of managing a hash set outweighs its benefits, making simple lists more efficient.

• Key Idea: Using arrays instead of vectors can lead to substantial performance gains.
• Performance Impact: This method can be 26 times faster.
• Reasoning: Arrays are stack-allocated, which provides cache locality benefits.

"Using an array instead of a vector is stack allocated and we get some cache locality kind of benefits here, much much faster."

• Explanation: Stack allocation and cache locality make arrays more efficient for certain operations compared to vectors.

• Key Idea: Tracking indexes manually in arrays can optimize performance further.
• Complexity: This approach requires additional effort to manage indexes.

"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."

• Explanation: By managing indexes, we avoid unnecessary checks, further optimizing performance.

• Key Idea: Using bit manipulation can lead to dramatic performance improvements.
• Performance Impact: Can achieve up to 233 times faster performance.
• Concept Introduction: Using a 32-bit number to store state instead of an array.

"We're gonna go from 26x to 233 times faster, we're starting to get into the blazingly faster category."

• Explanation: Bit manipulation leverages the compactness and speed of binary operations to achieve significant performance gains.

• Key Idea: ASCII characters have contiguous numeric values that can be manipulated using bits.
• Technical Detail: ASCII characters from 97 to 122 can be represented in a 32-bit unsigned number.

"One thing you have to understand about ASCII characters is that there is a numeric value associated for each one of them and they happen to be contiguous from 97 to 122."

• Explanation: Knowing the contiguous nature of ASCII values allows for efficient bit manipulation techniques.

• Key Idea: Using modulo and bitwise operations to manage character states.
• Example Process:
  • Character 'd' (ASCII 100) modulo 32 results in 4.
  • Left shift by 4 positions to get binary representation.
  • Use OR operation to update the state.

"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 4, a left shift operator is the equivalent of multiplying by 10."

• Explanation: This example demonstrates how bitwise operations can efficiently manage and check character states.

• Key Idea: Using logical AND to check if a bit has been set.
• Example Process:
  • Use AND operation to compare current state with new bit value.
  • If result is zero, bit has not been set.

"We just simply use the logical AND operator using our previous example we would run the AND operator on it and we'd get out a value of zero, therefore these two values do not share any common ones."

• Explanation: Logical AND is used to determine if a specific bit has already been set, ensuring efficient state management.

• Performance Optimization: Various techniques can significantly improve performance, from using arrays instead of hash sets or vectors to advanced bit manipulation.
• Technical Depth: Understanding underlying data structures and operations is crucial for implementing these optimizations effectively.
• Practical Application: These optimizations are particularly useful in scenarios with small data sets or specific performance-critical applications.

• Benny's algorithm uses a state mechanism and XOR (exclusive or) operations to efficiently process sequences.
• The algorithm grabs the first 13 characters in the sequence and toggles bits using XOR.
• XOR operation: If a bit is 0, it flips to 1; if it is 1, it flips to 0, allowing toggling of bit states.
• The algorithm processes the input in windows of 14 characters, moving one character at a time.
• The position iterator returns the index of the first true result, indicating where the condition is met.
• The state is updated by toggling the 14th character and checking for 14 ones to identify the desired position.
• The algorithm continues by removing the first character and adding the next character in the window, repeating the process.

"So we do the state thing that we talked about earlier and we grabbed the first 13 characters in the sequence and here's the secret sauce it uses an xor and exor think of it like a toggle if there is a zero in that bit position it will flip it to a one if there's a one in that bit position it will flip it to a zero exclusive or or xor."

• Explanation: XOR operation toggles the bits, which is the core mechanism of Benny's algorithm.

"We do the same operations that I showed earlier except for using xor that means we have toggled on 13 characters at this point from here we just go over the input 14 at a time."

• Explanation: The algorithm processes the input in windows of 14 characters, toggling bits using XOR.

"If we do have 14 ones then we have found the position we're looking for then we remove the first character that we saw that means we go from 14 toggles down to 13 toggles from 1 to 13."

• Explanation: The algorithm checks for 14 ones to identify the position and updates the state by removing the first character.

• Benny's algorithm is significantly faster than a hash set, achieving a speedup of 233 times or 23,000 times faster.
• The efficiency of the algorithm is praised, highlighting Benny's cleverness in its design.

"This clever algorithm earned Benny 233 times faster than the hash set or 23,000 faster it is incredibly clever algorithm hats off to Benny."

• Explanation: The algorithm's performance is significantly better than a hash set, showcasing its efficiency.

"Damn it Benny what a smart man and to think my solution was only like 100x faster than the hash that one I feel so stupid looking at Benny's super clever window crawling solution."

• Explanation: The speaker acknowledges the superior performance of Benny's algorithm compared to their own solution.

• The final form of the algorithm is discussed, which is over four times faster than Benny's, approximately 1,000 times faster.
• The algorithm uses a fixed-size window and iterates in reverse for optimization.
• A state variable of 32 bits is used, similar to Benny's solution.
• The algorithm checks if a bit is already set to one and uses the OR operator for bit manipulation.
• One key optimization is the ability to jump to a specific position if a byte has been seen before, significantly speeding up the process.

"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 git from index to index plus 14. so that is a constant size window it's very important to remember that."

• Explanation: The algorithm processes the input in fixed-size windows, which is crucial for its efficiency.

"Next we create a state variable 32 bits just like Benny's solution next we're going to go through that slice and we're going to iterate in Reverse."

• Explanation: A 32-bit state variable is used, and the algorithm iterates in reverse for optimization.

"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 we've seen this byte already."

• Explanation: The algorithm checks for duplicates using modulo 32 and the OR operator for bit manipulation.

"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 a huge opti."

• Explanation: A significant optimization is the ability to jump to a specific position if a byte has been seen before, enhancing the algorithm's speed.

• Loop unrolling is an optimization technique used by compilers to speed up execution by reducing the overhead of loop control.
• The compiler can transform loops to execute multiple iterations in a single pass, minimizing jumps and checks.
• This technique is particularly effective when the loop's iteration count is fixed at compile time.

"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."

• Explanation: The compiler unrolled the loop because the input size was fixed, reducing the need for repeated jumps and checks, enhancing execution speed.

• SIMD allows multiple data points to be processed with a single instruction, significantly speeding up computations.
• This optimization is particularly useful for operations that can be parallelized.

"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."

• Explanation: SIMD optimization enables the compiler to process multiple data points simultaneously, greatly enhancing computational speed.

• Reverse iteration can sometimes be optimized better by the compiler, especially when combined with loop unrolling and SIMD.
• The example shows that reverse iteration combined with these optimizations can be significantly faster than forward iteration under certain conditions.

"So we have the same thing happens to David's solution right here it actually gets Unwound so that reverse iterator happens in Reverse right here you can see it right there."

• Explanation: David's solution involved reverse iteration, which, when unrolled and SIMD-optimized, resulted in a highly efficient execution.

• Utilizing multiple threads can exponentially increase the speed of data processing.
• Parallelizing tasks across multiple threads can lead to dramatic improvements in performance metrics.

"Of course they just used by 64 threads that are just doing nothing of come on of course I'm gonna do that and that allowed us to go blazingly fast in fact 16 000 times faster than the original solution."

• Explanation: The use of 64 threads for parallel processing significantly boosted the performance, making the solution 16,000 times faster than the original.

• The optimized solution processed data at an unprecedented speed, demonstrating the effectiveness of the combined optimizations.
• The original solution processed 3.84 megabytes of data per second, while the multi-threaded final solution processed 617 gigabytes per second.

"It is so fast that the original solution would process 3.84 megabytes of data per second whereas the multi-threaded final solution did 617 gigabytes per second."

• Explanation: The performance metrics highlight the dramatic improvement, with the final solution processing data at a rate exponentially higher than the original.

• The final solution, attributed to David A Perez, showcased the potential of combining loop unrolling, SIMD, and multi-threading for optimizing algorithms.
• The optimizations were discussed and implemented during a Twitch session, emphasizing the collaborative and educational aspect of the process.

"The 980 three times faster solution is brought to you by David A Perez go give them a follow on GitHub now that's blazingly fast."

• Explanation: The credit for the optimized solution goes to David A Perez, whose contributions led to the dramatic performance improvements discussed.