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

@Makotom

Жыл бұрын

Please fix this 😁

@strager_

Жыл бұрын

Fix what? What's broken?

@Makotom

Жыл бұрын

@@strager_ Fix your comment on top😁

@strager_

Жыл бұрын

What is broken about it?

@omgtallmonster

Жыл бұрын

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.

@voidwalker7774

Жыл бұрын

you could have typed that faster ;)

@nextlifeonearth

Жыл бұрын

My colleagues get mad if I do it, but it's so much fun.

@user-dh8oi2mk4f

Жыл бұрын

@@voidwalker7774 u coudof usd fewer wrds:)

@YasserS19

Жыл бұрын

@@user-dh8oi2mk4f ucudvusdfwrltrz

@Zex-4729

Жыл бұрын

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

@enisten

Жыл бұрын

He optimized his presentation, too. :)

@bittikettu

Жыл бұрын

It is because this wasn't a tryon haul. 😂

@enisten

Жыл бұрын

@@bittikettu The first rule of try on hauls is: you do not talk about try on hauls.

@NoxWings

Жыл бұрын

wait what? I just realized the video was 30+ minutes long because of this comment o.O

@Tawnos_

Жыл бұрын

The video was only 17 minutes long, but I watch at 2x speed ;)

This guy is every programmer from each generation wrapped into one. I love this dude.

@strager_

Жыл бұрын

👶👦👨🧔‍♂️👨‍🦳👴

@yrtepgold

Жыл бұрын

He is the 1985 model of Dennis Ritchie

@Luuncho

Жыл бұрын

Not every generation.. unless he’s wearing programming socks 🥹

@2ndfloorsongs

11 ай бұрын

​@@Luuncho 😁 Maybe that's why he's never shown us his toes. P.S. No socks, but I have an Intel 4004 t-shirt.

@acex222

9 ай бұрын

​@@Luunchocreepy.

Knowing your data is such a HUGE programming concept that isn’t talked about nearly as much as it should be.

@styleisaweapon

Жыл бұрын

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.

@strager_

Жыл бұрын

Can you share an example of an expert programmer who writes comments like "// increment the index"?

@knight_kazul

Жыл бұрын

@@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 ( kzread.info/dash/bejne/pnhpsNSepqnakrg.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.

@styleisaweapon

Жыл бұрын

@@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

@knight_kazul

Жыл бұрын

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

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.

@strager_

Жыл бұрын

Thank you!

@kasparisdead

Жыл бұрын

Just appeared in my recommended, seems like a good sign!

@opayke980

Жыл бұрын

@@strager_ honestly the thumbnail is what grabbed my attention lol

@decky1990

Жыл бұрын

I’m with Burrak on this one - such a pleasant video to stay engaged with. Please do more videos.

@genehenson8851

Жыл бұрын

I think it’s happening!

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)

@strager_

Жыл бұрын

I totally forgot about that! I would have mentioned it in the video. 😀

@sullivan3503

Жыл бұрын

Wow. That's... horrible.

@nonchip

Жыл бұрын

​@@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.

@styleisaweapon

Жыл бұрын

@@nonchip spoken like someone that doesnt know what properties algorithms need from their hashing function, just like those terribly wrong math nerds

@oxey_

Жыл бұрын

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.

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.

@strager_

Жыл бұрын

I've spent years teaching people on my Twitch stream (twitch.tv/strager), so I've had practice. 🙂

@Walter_

Жыл бұрын

@@strager_ wow youtube thinks parenthesis are part of a regular twitch url

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!

@strager_

Жыл бұрын

I was also surprised how much cmov improved performance, especially after seeing Linus Torvalds' 2007 email about cmov: yarchive.net/comp/linux/cmov.html

@casperes0912

Жыл бұрын

​@@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

@styleisaweapon

Жыл бұрын

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

@magne6049

Жыл бұрын

@@casperes0912 *but _faster_ than a small number of mispredictions

This guy clearly has a knack for teaching. I have not seen an explanation this clear and engaging in a long time.

@rembautimes8808

4 ай бұрын

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.

@jankrynicky

11 ай бұрын

This is not real world. This is "I have way too much spare time and I don't dare to go out" world. This is a level of optimization that's never needed in the real world.

@nikkiofthevalley

9 ай бұрын

​@@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.

@skilz8098

Жыл бұрын

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.

@WeirdDuck781

4 ай бұрын

Small enough to fit on a CPU L-cache ?

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.

@strager_

Жыл бұрын

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.

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.

@strager_

Жыл бұрын

> 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: kzread.info/dash/bejne/Y4Z9sq-KgbWoh84.html

@brunoais

Жыл бұрын

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!).

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!

@strager_

Жыл бұрын

Hash tables are dope. 🚬

@spacelem

Жыл бұрын

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 KZread suggested this video to me!

@juliap.5375

Жыл бұрын

wtf? 😮 How they works everyone study from beginning. Both self-educated or university-educated, it is base knowledge in any book.

Glorious thumbnail

That was insane. I've never seen someone walk through such a deep optimization. Thanks so much for this video!

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!

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!

This is some high-quality content. Thanks for taking the time to explain it so clearly

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

@strager_

Жыл бұрын

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.

@peterfireflylund

Жыл бұрын

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.

@criticalhits7744

Жыл бұрын

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.

@ZelenoJabko

Жыл бұрын

@@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

@criticalhits7744

Жыл бұрын

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

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 simply amazing! From brainstorming to presentation and everything in-between. Thanks for sharing your hashing journey.

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.

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 🤣

@dutchdykefinger

Жыл бұрын

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

@JacobAsmuth-jw8uc

Жыл бұрын

Writing PHP in 2023? That's brutal

@tehbing

Жыл бұрын

@@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 :)

@pepegrillo9722

Жыл бұрын

@@JacobAsmuth-jw8uc Still talking down on PHP in 2023? That's so 2010 😆

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.

Instant subscription. This type of content is why I still love KZread. 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 VIDEO IS INCREDIBLE! Thank you so much for making it! Learned a lot of new things. Good luck in your new work

This format is excellent. I learned a lot thank you.

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.

Great video, fabulous experiment and results. I loved your diving into the assembly level.

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.

Now this is a quality content! Thanks a lot for sharing your knowledge with us!

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!

@CuriousSpy

Жыл бұрын

It is not all purpose algorithm. No need to compare them to built in

@strager_

Жыл бұрын

Most people would use the language-provided hash table, so it's completely fair to compare my solution with those hash tables.

@marcossidoruk8033

Жыл бұрын

​​@@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.

@strager_

Жыл бұрын

​@@marcossidoruk8033 You can compare the two in terms of feature set, ergonomics, performance, and security.

@Rose-ec6he

Жыл бұрын

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.

I am so happy I discovered this channel. This is such an awesome video, I really learned a lot, Thank you!

I think perf tip 6 is why the karatsuba method is more performant than typical matrix multiplication approach taught in school

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!

This was a great video, I loved the content and it was really concise while still keeping enough information!

This was just amazing, please continue the great work!

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!

@strager_

Жыл бұрын

> 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?)

@strager_

Жыл бұрын

> 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?

@bloodgain

Жыл бұрын

@@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!

@strager_

Жыл бұрын

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

@bloodgain

Жыл бұрын

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

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!

@strager_

Жыл бұрын

Thanks!

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!

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!

Amazing, thank you for presenting this!

As someone who has had the joy of micro-optimizing workloads before, this was a fun journey to take with you!

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

@strager_

Жыл бұрын

> got me even more motivated to study more That's what I like to hear!

Fantastic and addictive video with plenty of ideas. The burp was a nice touch too. You've gained a new subscriber !

Hats off for the engaging presentation and the well paced progression in the video.

This was awesome! This video format was really informative, it's like walking through the socratic method for performance.

@strager_

Жыл бұрын

> it's like walking through the socratic method for performance. Thank you!

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.

This was an amazing video. Enjoyed every second of it. Thank you for sharing your journey!

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.

Great video, well explained and interesting.

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.

@strager_

Жыл бұрын

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

Very well done video and I like the way you explain your thinking process.

Excellent video. Super easy to follow. You're great at explaining complex topics. Subscribed!

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.

@strager_

Жыл бұрын

I'm glad you learned something!

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.

@_fudgepop01

Жыл бұрын

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

@gianni50725

Жыл бұрын

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

Enjoyed the vid, looking forward to your future content 👍

This video popped up in my feed. What an excellent find, great and concise content.

WHAT A THUMBNAIL WOW

pleasantly surprised to see Dave Churchill come up. feels like a crossover episode

Fantastic delivery, great content, and cadence was spot on. Well done.

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! 🙇‍♂️

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!

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.

awesome comparison, explanation and tips! Well done

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.

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.

@strager_

6 ай бұрын

It's fun!

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.

@strager_

Жыл бұрын

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.

@kallehed6330

Жыл бұрын

This is very correct. Would be interesting to see C++ unordered_map compared to Rust with a better hash function.

Subscribed. Rare combination of a pleasant voice, good recording quality, lively delivery, and concise, fluff-free information. MMM.

Really enjoyed the deep-dive! SUBSCRIBED !!!

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.

I agree with everyone else mentioning that this didn’t feel like a half an hour video, very (and surprisingly) entertaining and insightful!

@hashi856

Жыл бұрын

It especially doesn't feel like half an hour when you watch it at 2x speed

10/10 video. Hearing your thought process was very interesting.

really entertaining to watch, you seem so passionate about optimization great video

I instantly subscribed for the thumbnail butts are the coolest

I can't believe the butt was actually added. TY Strager. It's still Saturday where I am butt my weekend is now complete.

@strager_

Жыл бұрын

You can thank Raticide on Twitch for the butt suggestion!

@NostraDavid2

Жыл бұрын

Thanks Raticide, very cool

Incredibly educating video, hope you keep bringing such content

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.

You are one of the best programming presenters I've ever run across.

clicked for the thumbnail, stayed for hash tables

Really grateful for the time you put into this! Very cool.

Wow, what a good quality videos on this channel.Thank you strager

A man in a faded microsoft T-shirt with his Christmas tree out in March wants to teach me algorithms? You best bet I'm going to listen.

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

That's a great talk! Really nicely explained.

Really well made video! Great explanations and level, easy to focus. Thanks!

Fun project, with some great insights, but I feel like there is a bit of "don't let perfect be the enemy of good enough" going on here. As a matter of pure learning and fun, it's great....but for most projects people should just use gperf until they've truly squeezed every ounce of optimization out of other parts of the code. Especially for newer/younger engineers, it's so easy to get caught down a rabbit hole like this and not realize you've spent precious time optimizing for 5% because you just had to replace gperf, instead of optimizing for 20 or 30% in parts of the code that are actually unique to what you're writing and where there is no "good enough" commodity solution in play. If you've truly squeezed all the juice out of the lemon elsewhere, then sure, go around replacing the "good enough" solutions with "perfect" ones.

@strager_

Жыл бұрын

> for most projects people should just use gperf until they've truly squeezed every ounce of optimization out of other parts of the code I got a 4-5% speedup over gperf with a week or two of work. I'd say that was worth it. (Also I learned some things along the way.) I think keyword recognition is one of the bottlenecks that matter in my program. Some of my techniques could be incorporated into gperf too. > Especially for newer/younger engineers, it's so easy to get caught down a rabbit hole like this Yes, this is a problem. However, engineers need to grow an understanding of algorithms and how their machine works. They need to practice their optimization muscles on easy, self-contained problems, otherwise they can't tackle harder problems. The point of my video was not "drop down to assembly as soon as possible". The performance tips I listed are not specific to assembly, and most apply to far-from-the-machine languages like Ruby and Scala.

Can't believe this video has less than 1K views. It is so incredibly well made, really enjoyed it!.

@peezieforestem5078

Жыл бұрын

now it has more

@jma42

Жыл бұрын

because most "programmers" nowadays are all about web development and npm installing stuff

@peezieforestem5078

Жыл бұрын

@@jma42 what are you talking about, it's been 20 hrs and the video has 11 kviews.

@jma42

Жыл бұрын

​@@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.

@strager_

Жыл бұрын

​@@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 KZread. 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 KZread's algorithm treats our content separately.

This was interesting and informative and well presented. Nice work!

This is a gold mine of system optimization ideas. Much appreciated!

Man youre a really good teacher, thank you for uploading this

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.

@strager_

Жыл бұрын

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

@JohnDlugosz

Жыл бұрын

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.

That was really interesting, thanks for sharing!

This video is fantastic. Well done 🎉

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.

@strager_

Жыл бұрын

> 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!

@Yay295

Жыл бұрын

@@strager_ or a trie

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

@strager_

Жыл бұрын

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

@strager_

Жыл бұрын

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

very interesting and in-depth video. keep the good work