CppCon 2017: Nicholas Ormrod “Fantastic Algorithms and Where To Find Them”

Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2017
-
Come dive into some exciting algorithms - tools rare enough to be novel, but useful enough to be found in practice. Want to learn about "heavy hitters" to prevent DOS attacks? Come to this talk. Want to avoid smashing your stack during tree destruction? Come to this talk. Want to hear war stories about how a new algorithm saved the day? Come to this talk! We'll dive into the finest of algorithms and see them in use - Fantastic Algorithms, and Where To Find Them.
-
Nicholas Ormrod: Facebook, Software Engineer
Nicholas is a infrastructure engineer at Facebook. If he talks too much, disable him with a well-placed nerd snipe.
-
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/registration/
*-----*

[@aaakashkumar]

1:22 Heavy Hitters 11:42 Morris Traversal 20:40 Reservoir Sampling 27:32 HyperLogLog

[@DareToSavorVanillaWithBacon]

Feels like a TED talk

[@mohammedj2941]

A compliment or criticism?

[@blazkowicz666]

@@mohammedj2941 yes

[@tophyr]

JFC some of you guys are a tough audience. This is a great presentation, with not a single "um" - what you're picking up on as conceitedness or actor-ness or whatever the hell else is "wrong" with the way he talks is simply a well-rehearsed talk and emotive vocal tones so that the audience doesn't fall asleep in the middle of some dense technical material.

[@philipfry9436]

21:50 And that is why Facebook's 'biggrep' is so fast. It bail out when it get too slow.

[@abhalla]

Excellent talk, both in terms of content and delivery. Thank you.

[@Dominik-K]

This is a really amazing talk and it's true, that algorithms are the tools of our trade

[@bstlang]

For binary tree destruction Morris Traversal is overkill, given that you don't need to reconstruct the original structure of the tree. A Θ(N) speed algorithm with O(1) space requirement follows, with the added benefit of being very small, thus not putting much pressure on the instruction cache: while (root) { while (root->left) { root = root->rotate_right(); } auto next = root->right; delete root; root = next; } O(N) rotations will be performed as well as Θ(N) deletions. This is essentially: singly_linked_list_destroy(binary_tree_to_slist(root));

[@peppybocan]

but pointers are BAAAAD :D ... but recursion is uuuglyyy... :D ... sometimes I feel like language PROs are in the C++ STD Committee and everyone else is just a noob from kindergarten.

[@CrimsonTide001]

That's what I was originally thinking he was going to do.

[@multigladiator384]

this is a good solution sir

[@absurdengineering]

I urge you to write out rotate_right. It’s not free, it’s not O(1).

[@gregkrimer1000]

Brilliant presentation

[@rakesh4a1]

This is very very gud presentation on algorithms, i saw his other talks too. I do not have that level of understanding of algorithms, has to try understanding these.

[@GeorgeTsiros]

"uhm"s per minute: 0 !

[@nathanssteurs1650]

Great talk, but who says "unique putter"

[@brothir]

Unfortunately it's not uncommon I find. I hardly ever abbreviate anything, but if I were to abbreviate pointer it'd be "pntr". People would still probably say something like "punter", but what can you do.

[@noxabellus]

Group-think gurus and their followers

[@bartekkko]

Because in the STL it's called unique_ptr

[@kim15742]

Herb Sutter for example, Scott Meyers

[@fdwr]

Nod, it sounds ridiculous. Is it any harder to say the correct word "pointer"?..

[@prydt]

loved the talk!

[@Peregringlk]

In 31:42, it says the probability of having K leading zeros is 1/2^k. So, the probability of having no leading zeros (the first bit is 1), is 1. Which means that you are granted that any random string have no zeros at the beginning, which is not true. I think 1/2^k is the probability of having k leading equal bits: k zeros, or k ones. If you want to restrict to be specifically k zeros, I think the probability will be 1/2^(k+1). Right? So there's a 50% probability of having a bit string with 0 leading zeros, which matches his next sentences of saying that 64 numbers (out of 128) will have no leading zeros.

[@intvnut]

So, is 1 -> 2 -> 6 a Prisoner reference buried in this? Or is that a coincidence?

[@majohime]

Didn't quite understand Morris Traversal in terms of tree destroying. No example of how actually apply this to real tree of unique_ptr-s, I heard speaker mention that in -O1 and higher compilers already do similar thing to optimize destruction but so what? I should just hope my future code will be optimized or I can actually perform this traversal and somehow do this destruction without ever touching raw pointers and doing everything with unique_ptr? Should I call something like right.~Node() while traversing or what?

[@OperationDarkside]

Love this way of presentation. Didn't get everything though. But good to know where to find all of that.

[@DarkTrunksGeorgeSim]

Didn't he mean necessary but not sufficient at ~8:00?

[@alcesmir]

Very much so.

[@mohammedj2941]

I came to the comment section just to search for this.

[@houdiniping]

so where to find these algorithms origin?

[@shivkrishnajaiswal8394]

Wow!!

[@4olovik]

excellent

[@nrwchd]

whoa his parent really named his son orgmode. what a hard core emacs user.

[@arisweedler4703]

VANLOON’s talk: kzbin.info/www/bejne/m5rHdnijfLGEmbc

[@Cromius771]

He should have used std::random instead of his random() % k. He has no idea what type of distribution hes dealing with.

[@tobiasfuchs7016]

Absolutely, but his point is the algorithm. Picking a suitable distribution is left as an exercise.

[@hansiraber]

it seems the algorithm requires uniform distribution. but it should be fine, because that's what the hash function will produce.

[@TomaszWiszkowski]

This all looks great until you realize what happens when things go a tiny bit wrong. Not wrong as a whole. Just a tiny bit. Off-by-one error. If you consider stack overflow as a reason for your code crash - you should very well consider how you would diagnose a single element memory leak in your tree deletion - or use after delete, because whoever wrote that cleverness actually made a typo resulting in a warning reported by tools 3 months later. The algorithm for heavy hitters made me wonder what would happen if the order was A - B - A - B - C - C. There's no heavy hitter here, yet the algorithm says it's C. I'd hate to debug this. I love the unconventional approach to the problem, but with code complexity we're hitting with C++ these days I think I would prefer to have my code readable as a priority. A little bit of pressure on stack is not so much of a trouble. if your trees are poorly balanced you have a much bigger problem than stack use during destruction: it's very likely going to hit your performance. In general. Now picture this (not unheard-of) scenario: your team inherited a project with some technological debt from overseas. The project conceptually is simple, but it's full of quirks like that. You get your stash of bugs along with the source code. What do you do next? Well, you spend next two months learning what the heck is going on - and everything looks like a potential bug. It doesn't have to be, but it just looks like that. A cycle in a binary tree, for example.

[@MonsterCutter]

Or even A - B - A - B - A - B -B - C - C. There B is the heavy hitter but the algo chooses C (which is of the least occurrence). That's probably why he says you need to go through it once again to verify. However I'm wondering how practical it is to go through all the requests since the beginning of Facebook just to verify a heavy hitter (that can still take some considerable amount of time and that on every request, since you want O(1) space thus cannot store anything else than the current hitter? - and for the second pass you need to store the requests somewhere anyway to go through them again, so you're back to O(N) space). And then you went through all the requests since the beginning of time just to find out your algo failed to choose the heavy hitter, and then what?

[@Voy2378]

You did not understand this lecture. Algorithm does the second pass, algorithm is fine.

[@ruroruro]

@@MonsterCutter Hello from 2019. You probably don't remember or care about this, buuuut. In your example, there is no Heavy Hitter. There are 4 Bs out of 9 elements, which is less than majority (50%). Also, he mentions, both the time and second pass concerns. I've actually been researching the problem in question a bit and it seems to me, that his algorithm is actually about the best you can do.

[@kamilkarwacki9590]

I dont agree, its fun writing my own algorithms