@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.
@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.
@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
@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!
@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.
@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.
@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 ;)
@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!
@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.
@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
@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.
@radialorbits
Benny's solution with bin manip was great. Slicing and jumping forward, rather than step by step is brilliant
@daltonyon
Amazing, I really love this type of content and inspire me to always thinking about performance
@iamtheV0RTEX
@9:40 You don't actually have to collect up all the elements in the iterator for this! In Rust, if an iterator implements DoubleEndedIterator then it can iterate in reverse. std::slice::iter implements this trait, so calling any of the "r" iterator methods will just start counting from the end instead of from the start.
@aleclowry7654
“Binary ten thousand” is a phrase that makes be very uncomfortable. Lol
@BreakbeatNightmare
More videos like this please! Love the deep dive into blazingly fast computer science topics
@10e999