ฝัง
- เผยแพร่เมื่อ 7 มิ.ย. 2024
- I had a week of fun designing and optimizing a perfect hash table. In this video, I take you through the journey of making a hash table 10 times faster and share performance tips along the way.
00:00 why are hash tables important?
00:31 how hash tables work
02:40 a naïve hash table
04:35 custom hash function
08:52 perfect hash tables
12:03 my perfect hash table
14:20 beating gperf
17:24 beating memcmp
21:46 beating SIMD
26:01 even faster?
30:06 pop quiz answers
31:45 beating cmov
33:09 closing thoughts
Thanks:
Dave Churchill: / davechurchill
My Twitch chat: / strager
Jennipuff: / jenipuff
Attribution:
Thumbnail artwork by Jennipuff
JavaScript logo by Christopher Williams under MIT license
PHP logo copyright Colin Viebrock, Creative Commons Attribution-Share Alike 4.0 International
Ruby logo copyright © 2006, Yukihiro Matsumoto, Creative Commons Attribution-ShareAlike 2.5 - วิทยาศาสตร์และเทคโนโลยี
Click 'read more' for performance tips with timestamps 👇
Source code of all of the techniques (for educational purposes) (warning: poorly organized):
github.com/strager/perfect-hash-tables
Production C++ implementation of my hash table:
github.com/quick-lint/quick-lint-js/blob/9388f93ddfeca54f73fab398320fdcb8b3c76a66/src/quick-lint-js/fe/lex-keyword-generated.cpp
My JavaScript/TypeScript compiler project:
quick-lint-js.com/
Rust reimplementation of my hash table:
github.com/YangchenYe323/keyword-match-experiment
Performance tips:
04:16 1. Try it
08:18 2. Make assumptions about your data
16:24 3. See how other people did it
20:08 4. Improve your data
20:28 5. Keep asking questions
21:17 6. Smaller isn't always better
24:57 7. Use multiple profiling tools
25:13 8. Benchmark with real data
29:46 9. Keep trying new ideas
32:42 10. Talk about your optimizations
Please fix this 😁
Fix what? What's broken?
@@strager_ Fix your comment on top😁
What is broken about it?
Is this meant to be a pinned comment? This shows up as a normal comment to me.
Extreme optimization can be an addicting game. Very cool to see it documented.
you could have typed that faster ;)
My colleagues get mad if I do it, but it's so much fun.
@@voidwalker7774 u coudof usd fewer wrds:)
@@user-dh8oi2mk4f ucudvusdfwrltrz
@@Yutaro-Yoshii ur nm cdv usd smplr wrtng sstm
I can't believe I watched a 34 minute video on hashing without getting bored and wandering off, this was an amazingly interesting talk.
He optimized his presentation, too. :)
It is because this wasn't a tryon haul. 😂
@@bittikettu The first rule of try on hauls is: you do not talk about try on hauls.
wait what? I just realized the video was 30+ minutes long because of this comment o.O
The video was only 17 minutes long, but I watch at 2x speed ;)
This video was incredibly easy to watch, you had my attention the whole time. I really hope the algorithm blesses you, because you deserve it.
Thank you!
Just appeared in my recommended, seems like a good sign!
@@strager_ honestly the thumbnail is what grabbed my attention lol
I’m with Burrak on this one - such a pleasant video to stay engaged with.
Please do more videos.
I think it’s happening!
This guy is every programmer from each generation wrapped into one. I love this dude.
👶👦👨🧔♂️👨🦳👴
He is the 1985 model of Dennis Ritchie
Not every generation.. unless he’s wearing programming socks 🥹
@@Luuncho 😁 Maybe that's why he's never shown us his toes.
P.S. No socks, but I have an Intel 4004 t-shirt.
@@Luunchocreepy.
Knowing your data is such a HUGE programming concept that isn’t talked about nearly as much as it should be.
Its because CS education has been simplified to the point of stupidity and dogma - they are very big on commenting your code, right? - originally it was the variables and data flow that were asked to be documented and that specifically the code should _not_ be commented - it was understood that the code should merely be written in a way that documents itself (easy to read) because the code is the authority on what the code does - but somewhere between the 1980s and now, all we get is dogmatic crap from "expert programmers" that still write code with comments like "// increment the index" and "// test for null" because its really easy for a CS professor to grade junk like that, while its problematic to grade people on variable and function names and types, the actual stuff that needs to be very clear.
Can you share an example of an expert programmer who writes comments like "// increment the index"?
@@styleisaweapon Wow, someone's really butthurt about comments out of all things.
While i do agree that the "Clean Code" principles do more harm than good ( th-cam.com/video/tD5NrevFtbU/w-d-xo.html ) i do strongly disagree with comments being absolutely needless. I leave tons of comments in my code. If you look at the code i write it's essentially 50% comments. Why? Because i like to be nice to me and to any potential person who looks at my code because i write code once and then immediately forget what it does and why it's there. Sure i could try to understand it's purpose but you know what's easier for a human to read than source code? Human language. It's far easier for me to read a comment than it is to decipher a chunk of code with 0 comments explaining what it does. And that's how i'd like to think others experience it as well. And why should i not make my own life and the life of others easier by adding in comments? It doesn't hurt anyone and is a nice guidance for those who don't know as much as i do about programming.
@@knight_kazul you arent a good programmer if your implementation needs a second companion description of what the code does - meanwhile all that data you still havent documented while insisting you need to document the code - thats your problem you've been trold cant help you further
@@styleisaweapon My code doesn't NEED comments. i provide it because i want to. Because i can benefit from it later on in development when i have long forgotten about that code segment, what it does and why it does things the way it does.
Not sure what you mean by the data that still isn't documented...
fun fact, the "easiest hash function being the length" is actually why PHP has so many weirdly long function names. in early versions that's actually how the hashmap for globals would work, and the developers thought it was easier (at least early one) to just come up with lots of different length names, than replace the underlying structure (which they did later anyway, but at that point didn't want to rename everything)
I totally forgot about that! I would have mentioned it in the video. 😀
Wow. That's... horrible.
@@styleisaweapon i mean, is there really a better option though? a _general_ purpose hashmap that is meant to be "usually fast" on 64bit systems can't really be any faster than "single 64bit integer compare" can it? *without* any application specific assumptions, that is. and also, yeah, as long as its source was 64bit there can't be any collisions (not sure what you mean by "see how hash has multiple meanings", as in "do you mean the hash function or any specific hash", but it doesn't matter either way, for either interpretation of 'meanings'. either "the identity function" which is as well-defined as you can get; or "maps things only onto itself", which, again, can't possibly collide).
i mean yeah sure with e.g.
@@nonchip spoken like someone that doesnt know what properties algorithms need from their hashing function, just like those terribly wrong math nerds
that's incredible lmao
The 'c' in _mm_cmpestrc is because it returns the carry flag. What the carry flag actually means depends on the control byte.
24:38 - I nearly lost it when you showed off those numbers. It's incredible to see what someone with in-depth knowledge can achieve. Appreciate the demonstration and advice!
I was also surprised how much cmov improved performance, especially after seeing Linus Torvalds' 2007 email about cmov: yarchive.net/comp/linux/cmov.html
@@strager_ I think something that has changed since Linus' comments is that A) the throughput difference of CMOV and MOV has been reduced as pipelining has been improved.
B) The penalty of a full branch prediction miss is greater because correct prediction is faster relative to incorrect prediction compared to 2007, and pipelining everything with cmov may still be slower than 100% perfect prediction but slower than a small number of mispredictions.
These are guesses, but yeah - as I saw you comment in another comment-thread as well; The environment can change and micro-architectures have changed a lot since 2007
@@casperes0912 On the most modern cpus there will never be a branch misprediction penalty in forward conditional code like that - modern pipelines will speculate both sides of the condition - the penalty you get is instead in always using unnecessary resources which may have otherwise done something else that was useful - the best version was the lea instruction, and its objectively strictly better in every way than both cmov and the forward conditional branching - the lea instruction uses the very highly optimized addressing mode logic built into the cpu - there exists no instruction on x86/AMD64 with any objectively better performance metric or available execution units - whenever lea can do it, you probably should have used lea.
@@casperes0912 *but _faster_ than a small number of mispredictions
You would not really feel this is a 33 minutes video. The brief discussion in earlier sections made it easy to digest the things you talked in the upcoming sections. It's hard not to imagine you were rubber ducking while making the video because of how you explain is so relatable.
I've spent years teaching people on my Twitch stream (twitch.tv/strager), so I've had practice. 🙂
@@strager_ wow youtube thinks parenthesis are part of a regular twitch url
This guy clearly has a knack for teaching. I have not seen an explanation this clear and engaging in a long time.
It’s a privilege to watch an expert talk on his field
"Your data is never random"
I just want to say Bravo !
What a pleasure to watch a Data structure video from a real-world perspective!
Subscribe.
@jankrynickyHow do you know that some program doesn't use hash tables a bunch to the point where this type of optimization _would_ help? You don't. You might not need that kind of optimization, but someone else might.
Smaller memory footprint *does* matter for performance, because caches. In this example, the table is just too small already to see that effect.
It's not just the cache hits and cache misses ratio, nor just the branch predictors at length, but also data alignment and page boundaries can come into play. Other things that can become a factor can come from the OS of the system itself such as with their process schedulers, v-tables, and more... but the latter are for the most part out of the hands of the basic user because this would then involve modifying the actual underlying kernels of the system and how they manage system memory access via read/write ops.
Small enough to fit on a CPU L-cache ?
This video has been popping up in my suggestions for the past two months and I'm so glad I've finally watched it. I can see how these concepts still apply, even if you don't end up going down the rabbit hole and writing assembly instructions. Thanks a lot!
This video was truly amazing. Wow. I really appreciate all of the work you've put into this. I've always known that I could write my own assembly, but I've figured that the compiler would always optimize better than I could. Seeing how you were able to profile and optimize your code made me realize that I would have eventually come to some of the same conclusions - so I should probably at least give it a shot myself.
Thank you for making this video. This should be a required viewing for any computer science college students at some point in their education.
PS. I was slightly annoyed that you didn't dig into why the binary search was slower at the very beginning of the video until you kept going deeper and deeper into the different inner workings of all of these different hash algorithms and optimizations, making me realize that this is meant to be a densely-packed hash table video, not a binary search video. Thanks again.
> this is meant to be a densely-packed hash table video, not a binary search video.
Actually, it's a video on general performance tips. The perfect hash table is just a case study!
> I was slightly annoyed that you didn't dig into why the binary search was slower at the very beginning of the video
You might be interested in this talk: th-cam.com/video/1RIPMQQRBWk/w-d-xo.html
This kinda reminds me how I optimized a hashtable with >2M entries into 2 arrays and increased its performance 20x. It was a performance critical program which was already using 32 GB of RAM (and I reduced to 8GB!).
clicked for the thumbnail, stayed for hash tables
That was insane. I've never seen someone walk through such a deep optimization. Thanks so much for this video!
The other thing that I think makes calling memcmp slow is that the branch predictor gets thrown off inside memcmp because memcmp is called from other places in the program with other data; with the single character check the branch predictor has the luxury of only seeing that branch used for the keyword lookup and nothing else.
I haven't looked in a while, but I thought the only branch in memcmp was a page boundary check. You might be right though.
Excellent video! I have absolutely no use for this in my day job but I still had a lot of fun learning about it regardless. Can’t wait to see more videos from you in the future!
First video of yours I've seen and it's an instant subscribe. Highly technical information presented in a very clear and understandable way, with no filler, and plenty of food for thought. Thank you.
This is some high-quality content. Thanks for taking the time to explain it so clearly
Phenomenal video! And thanks for talking about your missteps, that’s rarely talked about in videos like these. You kept viewers expectations of the optimization process much more realistic. Keep it up!
This is amazing! I never expected you'd be able to get more than 10x faster than builtin hashes. I didn't expect how wildly the performance would vary from modifying your algorithm, assumptions about the input data and assembly instruction optimisations. Seeing the numbers go up and up with your thorough explanations of each modification you made tickled my brain. I'll definitely be coming back here for more!
It is not all purpose algorithm. No need to compare them to built in
Most people would use the language-provided hash table, so it's completely fair to compare my solution with those hash tables.
@@strager_ No. That doesn't mean it is a fair comparison at all 🤦🏼♂️.
Its like comparing a Ferrari to a Fiat to get from point A to B, the fiat does the job at a fraction of the cost yes, but that comparison misses the entire point of the existence of the Ferrari.
Just because "most" people would use for convenience the builtin hash table doesn't mean it is comparable, in fact if you think it like that your point is totally self defeating, most people use the builtin because it is easier and more convenient, one solution seeks convenience and generality and the other pointless optimization for a single case, not comparable.
@@marcossidoruk8033 You can compare the two in terms of feature set, ergonomics, performance, and security.
I don't see the problem with comparing them. It's solves the same problem as other tools just in a way that's fastest for this use case. It's not general purpose like other tools sure but they are still different solutions to the same problem of storing data and fetching it from a large group with low overhead. The structure of one is just more coupled to the the data. It's an improvement in speed over what may have otherwise been used. Sure it's not a drop-in replacement for every project but it doesn't need to be. I'm sure it has it's tradeoffs too but what was being measured and compared here was the amount of lookups in a given time. Sure it may be an unnecessary optimisation and it won't be useful in every use case but that does not make the performance comparison in this use case invalid. The topic of this video was optimising the hashset data structure for use in his compiler. In terms of speed in his specific use case under conditions he expects, his solution was faster. Does that mean everyone should use it? No. Does it mean it's perfect for every situation? Does it mean it's always faster for every dataset? No. But that's not the topic of the video. It was not a pros and cons list for using his hashset in any program. It's how fast can he get with the data he needs to process en masse.
This simply amazing! From brainstorming to presentation and everything in-between. Thanks for sharing your hashing journey.
Amazing video, hash tables are such an underrated concept, everyone uses them but few ever mention them or how they work, let alone do that in depth, you're awesome!
Hash tables are dope. 🚬
There's a talk by Raymond Hettinger on dictionaries, with an in depth look at how they've changed and improved since the 60s, and eventually returned to a very similar layout to that of the 60s. I think watching that is why TH-cam suggested this video to me!
wtf? 😮 How they works everyone study from beginning. Both self-educated or university-educated, it is base knowledge in any book.
This was excellent! I spent a solid month on hashing at one point -- the tips in here would have saved me days of time. Thank you for the knowledge.
I truly love your presentation. It's very efficient, just like your code lmao
Some helpful visuals go a long way in illustrating concepts and keeping attention. Your video not only taught me about hash tables, but also about presentation. GJ!
Thanks!
Instant subscription. This type of content is why I still love TH-cam. You packed years or even decades of experience into a short and densely packed lesson that I'll remember probably for the rest of my life. Thanks so much!
This format is excellent. I learned a lot thank you.
This was awesome! This video format was really informative, it's like walking through the socratic method for performance.
> it's like walking through the socratic method for performance.
Thank you!
I am so happy I discovered this channel. This is such an awesome video, I really learned a lot, Thank you!
Great video, fabulous experiment and results. I loved your diving into the assembly level.
THIS VIDEO IS INCREDIBLE! Thank you so much for making it! Learned a lot of new things. Good luck in your new work
THIS IS SO HELPFUL. Thanks. This really helps us self-taught programmers like crazy. It's always good to learn about fundamentals like this, that are useful for many languages. Kind of opens your mind to what is possible.
Wow, great talk! You're a clever programmer and a good teacher.
We shouldn't, as a habit, go about trying to optimize everything to the last bit, but you cover exactly the way one should go about it properly: profile the performance! That goes for our larger programs as a whole, too. That is, don't go optimizing your hash function or writing your own hash table until you've determined that's where your software needs optimizing. Then when you do, iterate on that process: profile it and work inward. And of course, always check to see if there's a faster, well-tested option already available before rolling your own!
> That is, don't go optimizing your hash function or writing your own hash table until you've determined that's where your software needs optimizing .
Profiling first can be misleading. The keyword recognition code in my parser didn't show up in the profiler, yet optimizing it improved performance by 5%. (Maybe this is just a bug in the profiler?)
> And of course, always check to see if there's a faster, well-tested option already available before rolling your own!
I suggest understanding the problem well (e.g. by writing your own implementation) before picking an off-the-shelf solution. How do you know that their solution is good until you've thought about it carefully yourself?
@@strager_ By testing, which you'd have to do with your own solution, anyway. Though in many cases, lots of data on performance is already available unless you have a very special use case.
In production code, there are so many good reasons to avoid writing complex libraries until you can prove they don't meet your needs that not doing so is a named anti-pattern: Not Invented Here. Much has been written about it better than I could do here.
You're not required to agree with me, of course. I'd want a guy like you working on core libraries, anyway, and in those cases, your attitude is usually the right one. But I wouldn't want the guys working on the rest of the system trying to outsmart/out-optimize the core library team, at least not unless they've found the bottleneck and submit a pull request after!
> in many cases, lots of data on performance is already available unless you have a very special use case.
I disagree. The assumptions I can make about my data are not the same as the assumptions you can make about your data, even if we both could use a common solution (like a string->number hash table).
> I wouldn't want the guys working on the rest of the system trying to outsmart/out-optimize the core library team
Why not? Why can't anyone contribute to the core library? A workplace where only privileged programmers can touch the core library sounds like a toxic workplace.
@@strager_ You left out the second half of that sentence where I said, "unless they've identified the bottleneck and submit a pull request after". The point being if they're off rolling their own brand new solution everything because they think they "can do better" (a common attitude, and the one that leads to "Not Invented Here" syndrome), that's a problem.
It seems like you're just looking for something to argue about. My original comment was positive and supportive, and you still looked for ways to pick it apart.
Fantastic and addictive video with plenty of ideas. The burp was a nice touch too. You've gained a new subscriber !
This is one of the best videos about performance and low level programming I have ever seen. Usually trying to understand these concepts takes a lot of effort and I sometimes feel tired after a while. You managed to make this video easy to follow, interesting and entertaining. Great stuff.
This was a great video, I loved the content and it was really concise while still keeping enough information!
Now this is a quality content! Thanks a lot for sharing your knowledge with us!
This was just amazing, please continue the great work!
Great video I come back to from time to time, love the deep dive into hash tables, very inspiring
Fantastic video! Even though I don't know much about low level stuff you made it very easy to understand and follow and got me even more motivated to study more
> got me even more motivated to study more
That's what I like to hear!
Hats off for the engaging presentation and the well paced progression in the video.
incredible video! i have never really cared about hashes, but i was completely invested the whole time! cant wait for more videos like this one.
Started this video thinking i know a lot of stuff about hashing, i mean i knew about collision etc. But i didnt just learn a lot more about creating actual hash-functions that are fitted to my data but also the whole branching stuff was insightful. Really really nice to watch thanks.
I'm glad you learned something!
Wow! this was the perfect summary of all your work on stream, easy to follow and really clear and had me to question a few things about my code. I appreciate your hard work Strager, let's celebrate with a cold mexican coca cola. Cheers!
Customizing / designing hash-table interfaces based on contextual knowledge about the underlying data is a great topic. Very true that such an intuitive technology (mapping some key to some element) is often overlooked and not well understood.
Awesome video!
Fantastic delivery, great content, and cadence was spot on. Well done.
Blast from the past: "Hash table? That's where I store my named pipes!" :)
Awesome content, really liked it but way more than I can process in one go.
This is the first youtube channel that I have subscribed in just one video.
Excellent video. Super easy to follow. You're great at explaining complex topics. Subscribed!
Subscribed. Rare combination of a pleasant voice, good recording quality, lively delivery, and concise, fluff-free information. MMM.
As someone who has had the joy of micro-optimizing workloads before, this was a fun journey to take with you!
I agree with everyone else mentioning that this didn’t feel like a half an hour video, very (and surprisingly) entertaining and insightful!
It especially doesn't feel like half an hour when you watch it at 2x speed
This video popped up in my feed. What an excellent find, great and concise content.
Incredibly educating video, hope you keep bringing such content
loved the intuitive explanations!
and very solid performance advice. people often forget that you can adjust your input data to, for example, get rid of bounds checks, vectorize, or unroll.
> people often forget that you can adjust your input data
Yup. This is one problem with abstractions: they hide details! Sometimes it's nice to peel back the abstractions to see what you're *really* dealing with.
I've been working on and off on a simulation where I could use every scrap of performance I can find. I'm not even close to the optimizing stage yet, but I find this video really inspiring. It makes me think, "Hey, maybe I can make this 50x faster", and gets me excited to think of ways to speed it up.
It's fun!
This was an amazing video. Enjoyed every second of it. Thank you for sharing your journey!
Thanks for the profiler tips and a very enjoyable exploration of the optimization game. I want to go work on my hash function now! I love that hash seed search trick!
The problem with doing all this is that possibly with the next version of the compiler, different operating system, or a new model of CPU, any of these optimizations might backfire (actually cause performance loss).
Yup. Maybe Zen 4's cmpestrc isn't so slow!
But I doubt the new hardware and compilers would make my solution slower than C++'s std::unordered_map.
If a compiler makes my code slower on the same hardware, that's probably a fixable compiler bug.
You bring up a good point though. If I *really* cared about the performance, I should keep my benchmark suite around for the future to check my work when the environment changes.
Just having the compiler put the basic blocks in a different order or just having the linker out the sections in a different order can change the performance. Different layouts of the stack and heap can do the same.
Emery Berger has a great talk about it + he co-wrote a paper “STABILIZER: Statistically Sound Performance Evaluation” about it.
The compiler might slow it down a bit, but unless there's a compiler bug you're never going to lose the order of magnitude in performance that you gained. And more importantly, you should build for your target platform, not some theoretical future platform.
@@criticalhits7744 there is no target platform, people will be compiling and running the code on hundreds of different processor models, maybe even different compilers (GCC, clang, ICC). Next, I am not arguing all optimizations would go bad, just some. For example, in this video, he has made 10 optimizations that were all beneficial. In some other future scenario, 7 might still be beneficial, 1 becomes neutral, and 2 harmful (worsening performance). You have to countuously keep testing each in isolation
@@ZelenoJabko Sure, that's kind of what I mean though, youll always want to benchmark at least on the compiler *you* are shipping with, assuming you're shipping software and not an SDK/API. If you're shipping software you'll always want to know what your range of platforms/environment s are now, and not necessarily consider what *might* change for the platforms/environments in the future.
Incredible video, didn’t even realize it was a 34 minute video until it was over. While explaining the hash table implementation, you also implicitly made a compelling argument for taking assembly seriously. I learned a lot. Thank you!
Really grateful for the time you put into this! Very cool.
really entertaining to watch, you seem so passionate about optimization
great video
Great video, well explained and interesting.
Love this stuff. Mind candy with extra goodness. For the limited domain of a fixed set of keywords, I might look at all two letters in the set, select the two that have maximum entropy and use those two as first guess. If you have a pair that give no collisions for the set, speed ensues.
Excellent video & an excellent teaching style. I went down the same rabbit hole a couple of years ago (but for database joins, not compilers) and ultimately switched back to gperf from simd because my laptop would get uncomfortably hot on my lap!
Amazing video mate! What a great starting point for me to get into this higher level of performance. I really appreciate the deep dive, please keep up the amazing videos. Awesome stuff 👏
Thanks!
Can't believe this video has less than 1K views. It is so incredibly well made, really enjoyed it!.
now it has more
because most "programmers" nowadays are all about web development and npm installing stuff
@@jma42 what are you talking about, it's been 20 hrs and the video has 11 kviews.
@@peezieforestem5078 thats not my point, and besides, its too little when compared to most typical web dev content.
What I meant is that the topic is not that interesting to the most programmers nowadays cuz they dont do computer science shit.
@@jma42 I don't consider what I did 'computer science shit'. I consider my work closer to engineering. But I guess that's just semantics.
There is plenty of content like this video on TH-cam. For example:
www.youtube.com/@CppCon has lots of deep-dive talks.
www.youtube.com/@DaveChurchill has good beginner-friendly talks which aren't just "install this library and you're done!".
www.youtube.com/@MollyRocket has a popular series called Handmade Hero which covers making a game from scratch line-by-line.
www.youtube.com/@fasterthanlime has educational content similar to mine.
You say it's "too little when compared to" something else. But I don't think I'm competing for the same audience as npm bootcamp tutorial videos, and I think TH-cam's algorithm treats our content separately.
Loved this. Reminded me of the days when I was a C programmer back in the 80s/90s, rather than just a PHP scripter like I am today 🤣
i actually started with php, then went to java/c to learn about typecasting lol
nowadays i even do more java/ecmascript than php, but i still have my php CLI toolkit for all kinds of shit,
i refuse to use python lol
Writing PHP in 2023? That's brutal
@@JacobAsmuth-jw8uc Still a good language for fast prototyping and general-purpose web development! Lots of great changes have been brought into the language in the past few years. The usefulness of every tool depends on the task at hand, but maybe you had a really bad experience with PHP. Can't fault you for that :)
@@JacobAsmuth-jw8uc Still talking down on PHP in 2023? That's so 2010 😆
Wow. I learned so much from this vid that I didn't know I NEEDED to know about hash maps. I went from hashes and hash maps being more advance topics slightly outside my current knowledge in Comp Science to feeling like I know the subject inside and out.
I've even learned a lot about assembly and compilers while watching this random vid that came across my timeline!
You, sir, are an excellent teacher. You have gained yourself a subscriber, Sensei! 🙇♂️
this was such an interesting video to watch. I don't really know much about hash tables and this video felt really comprehensive and easy to understand.
Glorious thumbnail
You are one of the best programming presenters I've ever run across.
Very thorough. Amazing performance increase. Well documented video. ❤
Wow, what a good quality videos on this channel.Thank you strager
It also a lot of fun to try profilers like coz and tools like stabilizer (although this one has maybe one fork left that is somewhat active?). But it can really help you not run into dead ends because of random layout changes.
slow clap, thunderous applause, awe, top, i loved the burp.
I don't know why but it was so entertaining seeing your thought process, and I even learned some stuff. Very good content
Thanks for starting from the beginning. I didn't need all of it, but it was a nice intro to make sure everyone was on the same page.
pleasantly surprised to see Dave Churchill come up. feels like a crossover episode
I think perf tip 6 is why the karatsuba method is more performant than typical matrix multiplication approach taught in school
awesome comparison, explanation and tips! Well done
I just loved seeing the bars go up and hearing about the different approaches going deeper and deeper.
📈
31:00 on the optimization of checking the first character. Calling a function has some overhead, just to push registers, jump to the address, clear some stack space, pop the registers again when it‘s done, and so forth. Also memcmp() in particular does what it can to do wider compares, which is almost always a big win, but since the data isn‘t necessarily aligned for that, it does some byte-for-byte compares at the beginning and the end of the memory region - the wide compares tend to be in the middle. The one-byte comparison for the first character is a single instruction, so when the first character differs, all of that overhead can be avoided. It‘s a win when the first character differs most of the time, less so if they‘re frequently the same.
Oh so I was right! Nice!~
However, I looked it up and found that in some compilers (gcc) memcmp is recognized as a compiler “builtin” that is inlined if it can be, so I’m still wondering if it could be something else
slight correction, on x86_64 you shouldnt expect any registers to be pushed or popped since the arguments will be stored directly in the registers
Nice vid 👍. I remember a talk by Chandler Carruth at cppcon, where he brought a skylake 2U server with him onto the stage, and did a bunch of perf shenanigans, trying to optimise the code at hand.
He works on LLVM team, and spent a lot of time trying to make clang produce that cmov. In the end, he made compiler emit branchless code, and it performed worse!
Turns out the relative performance of cmov vs branches is highly dependent on CPU architecture (in his case, it was a skylake machine). Compilers use a bunch of heuristics and just setting -march=native is enough to make clang emit a branch on the same codebase (which was faster for that case on that micro architecture).
All that got me wondering about what different instructions are better generated for newer / older CPUs. This can be pinned down if you are running on the known hardware (servers, consoles, micro-controllers), but something like compilers run on everything. Looks like there is a point in gathering stats to determine what is the most common -march for the majority of users.
You make a great point about cmov's performance being CPU-specific!
I did try -march=native on both of my machines (x86_64 (Zen 3, 5950X) and AArch64 (Apple M1)). Clang generated cmov (csel) consistently for AArch64, but neither GCC nor Clang generated cmov consistently for x86_64. I did not test on older or newer architectures.
All of the benchmarking was done on a 5950X on Linux with GCC (I think version 11).
One thing I did not research (but should have) is using profile-guided optimizations to see if that would help compilers generate cmov. The compilers would be able to see the lookup hit rate. I suspect they would still try to branch on x86_64 though...
There's also the case of finding the sweet spot. E.g. the shipped exe runs on Haswell or newer, and if you really want to run on old hardware you can get an alternative compiled binary.
That is, at some point the new instructions and optimization assumptions make a critical difference, and beyond that it's just incremental improvements.
But compiling for the absolute worst case of old hardware will perform rather poorly on modern hardware.
This was interesting and informative and well presented. Nice work!
I'll be stealing this lol. Some really cool math behind it as well. Thank you for your work strager!
One idea might be: You could do your thing for each group of same-length keywords. One benefit might be, that the tables for each length become very small and the search for the hash functions becomes much quicker/better.
A variation of that idea could be to "seed in" the length of the symbol you want to test if it is a keyword (as if it were 2 extra characters in front or something along that line).
"let" becomes "\3let" is what I mean with the last paragraph. Compare to the (e.g. in Common Lisp) "let*" vs "let" "\4let*" vs "\3let".
> You could do your thing for each group of same-length keywords.
This is a great idea! I actually had this idea but wrote it poorly at 30:00.
> A variation of that idea could be to "seed in" the length of the symbol you want to test if it is a keyword
I actually did try this, but only picking characters was easier to explain for the video and performed faster on average.
Wrt to the speedup by looking at the first character: You're avoiding both the call overhead (if not inlined), and the memcmp loop setup/teardown (even if inlined) in the typical case
Really well made video! Great explanations and level, easy to focus. Thanks!
very well made video, easy to follow and interesting, thank you for sharing your knowledge
Man youre a really good teacher, thank you for uploading this
You should do comparisons against Rust's FxHashMap. The reason SipHash is used as a default is because we assume it might be in a position to suffer a HashDoS attack, but everyone using Rust who wants to actually make their HashMap go fast, including the actual Rust compiler, uses FxHash or another simpler hash function as their hasher.
I did make a custom hash function. I plugged it into C++'s std::unordered_map to show an improvement (8:02). Switching the hash function is something both Rust's and C++'s hash tables support, so I just picked one to demonstrate the idea.
The point of this video wasn't to make Rust's HashMap fast. It was to show how to think about improving performance.
This is very correct. Would be interesting to see C++ unordered_map compared to Rust with a better hash function.
Really enjoyed the deep-dive!
SUBSCRIBED !!!
Very well done video and I like the way you explain your thinking process.
Bro that Thumbnail 💀💀💀
love the video! i would be really interested to see if a modified trie data structure could solve this problem in shorter time, since you wouldn’t need a string compare, hash function, and you can assume youre only using [A-Za-z] and if you dont care about casing it becomes exponentially more space efficient. you might even be able to skip all linked list/tree data patterns and use lookup arrays for each index of the word with the value at the end of the lookup.
> you might even be able to skip all linked list/tree data patterns and use lookup arrays for each index of the word with the value at the end of the lookup.
That sounds like a table-based DFA!
@@strager_ or a trie
This was an incredibly good video. Great job man.
brilliant video… This is one of my favorite interview questions when I seek new programmers… I start them with a simple on ordered array and asked him to search it and we walk from linear search to binary search to binary search trees to hash tables… Most understand how to use hash tables very few understand how they work… I hope more programmers watch this video and understand how hash tables work on the inside… Because there's a difference between knowing how do use something and knowing why it works