Faster than Rust and C++: the PERFECT hash table 

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.

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

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

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!

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 ( ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-tD5NrevFtbU.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...

👶👦👨🧔‍♂️👨‍🦳👴

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.

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

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

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

It’s a privilege to watch an expert talk on his field

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.

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

> 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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-1RIPMQQRBWk.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!).

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 ?

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.

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.

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

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.

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

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 😆

It's fun!

Thanks!

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

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

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.

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

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

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

You can thank Raticide on Twitch for the butt suggestion!

Thanks Raticide, very cool

I'm glad you learned something!

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 RU-vid. 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 RU-vid's algorithm treats our content separately.

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

Thanks!

I didn't have any one-character keys, but if I did, this sounds like a reasonable thing to try.

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.