@slurpe_ee
as a beginner developer, seeing you go from an array to bit manipulation was like watching black magic. incredible to see what we can do with these technologies and break them down to their atomic pieces.
@ThePrimeagen
Tell me you were surprised by using a vector to speed up instead of using a hashset but telling me i am beautiful (and liking the video) Slight correction. When I say left shift is multiplied by 10, I meant 10 in binary. Therefore it is two in decimal
@DrOptix
This is really awesome because you don't just show the final kick ass solution, but also present a mental model on how to get from the naive solution to the fast one.
@yungclowns
In the (relatively common) case where there's a 14-character window with more than one duplicate, going backwards within the window allows you to find the duplicate furthest along in the input. This means you can skip ahead further in those cases. It is a good example of a 'greedy' optimization looking for the best case (a late duplicate) first.
@fishfpv9916
Really like videos going over practical algerithm optimization. I feel in school there is a lot of focus on theory and very little on how to make things run fast in the real world. Love to see more of these types of videos!
@brendanwenzel
More of this is needed! I never knew I needed to know this stuff. Best part of YouTube is getting mentored by a senior dev without having to be in the same office!
@white-bunny
6:33 That is NOT the Logical AND Operator (which is &&) but actually the Bitwise AND Operator (&). Great video! I learnt a few things here!
@PanduPoluan
And a note of caution: Although yes the performance increases significantly, the more optimised it becomes, the more specialised and hard to maintain it will also be. For the purposes of the Advent of Code challenge, it's perfectly suitable. However for daily development, the tradeoffs need to be considered really carefully. Finally, before going down the rabbit hole of extreme optimisation, don't forget to profile your code first ! You don't want to spend an inordinate amount of time hyper-optimizing a portion of your code that only affects 1% of total execution time. Find pieces of code that affects 10% or more of execution time and focus your efforts there first.
@arjanbal3972
It's not mentioned, so one way to split the problem for multiple threads, is to divide the string into 64 pieces and ask each thread to solve one piece. You would also need to extend the boundaries of each piece by 14 (maybe 13?) characters on one side so that you can catch 14 size windows that are in multiple pieces. Report the min index from all threads as the final answer.
@GameCyborgCh
good thing it only did it for 11.9 milli seconds because you'd have a pretty hard time keeping your CPU fed at 617GB/s
@alexandersemionov5790
I just had my imposter syndrome gone, and then I watched this video. Damn it! Great video, a lot of small details and bits of information. Being a nerd is a lot of fun. Thanks ;)
@darkfire2703
Nice explanation! I pretty much went for full speed with no regards for readability / maintainability with this AoC (using rust ofc lol). I managed to get my day 6 solution down to about 4 microseconds on one of the discord callenge bots and I had a rather similar approach to you. The performance on the bot was a bit flakey, but some guy had it down to 2us on the bot which was what I got locally on my ryzen 7 2700x
@simonfarre4907
The stack allocated array and the vector array both have cache locality benefits due to them both being contiguous. The difference is the vector is making a syscall (potentially) to get memory off of the heap. You could reuse the vector after an iteration and you could speed up that variant some. The stack allocated array, gets further cache locality, since you don't even need the first fetch of a cache line - its already in the cache. But both have the benefits of spatial and temporal locality.
@aleclowry7654
“Binary ten thousand” is a phrase that makes be very uncomfortable. Lol
@oblivion_2852
I like the comments about the order of hashing. I think in university alot of the time they fail to mention the constants in the complexity conversation and you often end up with people always thinking hashmaps and sets being the fastest completely unaware of the cost of hashing and the common list iterator for collisions.
@daltonyon
Amazing, I really love this type of content and inspire me to always thinking about performance
@radialorbits
Benny's solution with bin manip was great. Slicing and jumping forward, rather than step by step is brilliant
@realryleu
step 1: remove the `sleep(10) # replace with algorithm`
@BreakbeatNightmare
More videos like this please! Love the deep dive into blazingly fast computer science topics
@10e999