14 ms·
Chandler Carruth told a similar story in one of his talks. He met Ken Thompson and saw beautiful C code for the first time because he had encountered a perform
by MathMonkeyMan 1y ago
Chandler Carruth told a similar story in one of his talks.
He met Ken Thompson and saw beautiful C code for the first time because he had encountered a performance problem in a service. The service had to choose a policy to enforce (or something) based on the incoming request. It was taking too long to match the criteria of each potential policy against the request.
Ken wrote a finite automata based pattern matcher that would simultaneously advance through all of the policies' predicates. It was perfect, and it was much faster than the existing code.
Then somebody noticed that 99.9% of requests matched a particular policy, so they changed the existing code to just check that predicate first, and the code sped up a zillion times, much more than with Ken's solution.
- tasn 1y agoThis is such a great anecdote, thanks for sharing! Somehow relatedly, I still remember the first time I heard about profile-guided optimization which is essentially the same but for all of your code at once (well, same idea, not sure it's aggressive enough to reach the same result as the anecdote you shared).
- scottlamb 1y ago> Somehow relatedly, I still remember the first time I heard about profile-guided optimization which is essentially the same but for all of your code at once (well, same idea, not sure it's aggressive enough to reach the same result as the anecdote you shared). Exactly: profile-guided optimization is pretty awesome if you have the right infrastructure. You can get maybe 15% speedup on your program without going deep into all the code. But it has limits. IIUC, it gathers information about which code is hot, including which branches are taken, and enables certain compiler optimizations based on that. [1] But it's not going to make huge algorithm changes, it's not going to change data structure definitions [2], and it's not going to prepare good microbenchmark input for you to compare your new algorithm against the current one. Also, this article is about Java, and profile-guided optimization is something Java just has baked into its JIT already. [1] I don't know exactly which, and they likely vary by compiler version. But I think a variety of stuff to better use cache: breaking code apart into likely-"hot" vs likely-"cold" pages, deciding which loops are worth aligning, and where inlining is worthwhile. Also where branches should be optimized for likely vs unlikely vs unpredictable (conditional instructions). When it's worth autovectorizing. But it's not as good at SIMD as good as a human who puts two weeks into it, and SIMD usage is constrained by the inability to change data structures. [2] in theory, in Rust's default #[repr(Rust)] it could reorder a struct's members, but it's not going to say change from array-of-struct to struct-of-array format or hashmap to btree.
- ralegh 1y agoThis is fine assuming the popular request types don’t change, but arguably if both new versions of matching are sufficiently fast then I would prefer Ken’s long term as the other could become slow again if the distribution of request types changes.
- sfilmeyer 1y agoAs a counterpoint, what fraction of the future engineers who will touch the project are likely to be able to competently edit the finite automata based version without introducing bugs and what fraction will be able to competently edit the if statement that checks the particular policy?
- mikepurvis 1y agoA further question mark is whether any of this has sufficient instrumentation to be able to notice and act on a change of and when it occurs.
- andrepd 1y agoNonsense. The pre-check can literally be one line (if common_case {fast_path()} else {slow_path()}), and thus enabling or disabling it is dead simple and obvious if the problem changes in the future. Lines of thinking like that are part of the reason most modern software is so sloooow :)
- ants_everywhere 1y agoYou can even track the request statistics live and disable the fast path if the distribution of requests changes significantly.
- Rendello 1y agoThis situation where two paths produce the same output but one is optimized is the easiest case in property-based testing, as the property is just: normal(x) == optimized(x)
- snvzz 1y agoMy take is that code is disposable, and often needs to be written to figure out what is really needed, then disposed off. Learning this is worth writing the otherwise useless code.
- deleted 1y ago[deleted]
- Cthulhu_ 1y agoOr one should spend a little more time at first to fully understand the problem, in both the mentioned case and the OP, use realistic data.
- yetihehe 1y agoSometimes you can't have realistic data without writing some code first, that will allow you to gather that data.
- TillE 1y agoWriting code is very very often a big part of understanding any new problem. It's just that you should be quite comfortable discarding that code. Refactor mercilessly and all that.
- scott_w 1y agoWriting code that solves the problem is a huge way of proving you understand the problem.
- ddalex 1y agoI came to the same conclusion months ago with the advent of coding LLMs.... I used to treat code as precious, carefully saving, cataloguing and referencing git commits and SQL scripts and command line histories, because they were painful to write, and thus they are valuable. I mean, they were, because when I had the same need again, I could find previous instances and reuse stuff. Now ? I just dump the problem into an LLM and it spits up a script that solves it, and then I throw away the script because it horribly bugged for any other case then my particular problem, but hey, I just solved my problem
- sylware 1y agoI am writing assembly and often you have many code paths/data structures which "fit". Each combinaison of code paths/data structures will favor some specific usage/data in spite of the others. And this is not real "optimization" since usually those code paths have roughly "the same" cost. The bottom of this: it is what you think of semantics and real-life usage of this code which will drive those "choices". That said, you can still have generic optimizations which will benefit nearly all (for instance quick sort).
- n3t 1y agoAnyone has a link to the talk?
- MathMonkeyMan 1y agoNeither I nor ChatGPT could find it again.
- n3t 1y agoFound it! https://youtu.be/nXaxk27zwlk?t=393 https://youtu.be/nXaxk27zwlk?t=393 (there is more context before the timestamp)
- underdeserver 1y agoThis is a good place to mention profile-guided optimization. In PGO you profile your application running in the real world (via automatic instrumentation) and the compiler uses the output to make optimization decisions. I'm not sure what exactly they use it for, but I imagine it could be used for loop unrolling, switch case ordering, branch prediction optimization, memory ordering and more.
- menaerus 1y agoWhat if your "application" is a server-side code hosting multitude of different types of workloads, e.g. databases? I was never really convinced by the PGO benefits for such open-ended and complex workloads.
- ltbarcly3 1y agoPGO operates at the cpu branch level. The main benefit, if i understand correctly, is to reduce branch mispredictions which lead to pipeline stalls. Theres absolutely no reason to think that the specific workload of a system generally makes random/arbitrary/heuristic be the best way to pick a most likely branch for a given branching instruction. For example, when scanning data you might check if the current value is equal to a test value, and branch on that to either code that handles the match, or else code that moves to the next entry to test that. This may be extremely likely to match (95%) as in a hash table, or very likely to not match (string search). A compiler can't tell which is true, and your workload literally has no impact on this unless it is pathological.
- menaerus 1y agoI don't follow. If I have an ingestion-heavy workload then my hash-map will certainly be stressed in a completely different way than if I have a read-only workload. The data that PGO collects during the former will be different than the data that it collects during the later, so, how is it not that the workload doesn't impact the PGO optimizations? Perhaps I misunderstood you.
- RedNifre 1y agoOkay, but how about checking the 99.9% policy first and if it doesn't match, run Ken's solution?
- fifilura 1y agoYou'd be better off with some stupid code that junior devs (or Grug brained senior devs) could easily understand for the 0.1% cases.
- smcin 1y ago(In that specific case, with that specific very skewed data distribution, yes. But not necessarily in the general case. So "they" would be better off with that solution, but not a generalized "you").
- username135 1y agoThen how do they learn
- chii 1y agoThey can learn finite automata from computer science text books.
- username135 1y agoTrue, i suppose, but theres simply no substitute for contextual, on the job learning. imo
- mannykannot 1y agoMy guess is that they would be more likely to “fix” and “improve” Ken’s algorithm than understand it (Jon Bentley mentioned, in passing, a similar case where this was the outcome.)
- fifilura 1y agoOh! "Educating the newbies/grunts" is the reason for #$#@&#? I'd say that an org has a limited number of pennies to spend on non-trivial code. Let's spend them wisely.