6 ms·
A few years ago I spend lots of time and effort at Goldman Sachs solving a performance problem in a major part of their internal cloud infrastructure. The prog
by eru 6y ago
A few years ago I spend lots of time and effort at Goldman Sachs solving a performance problem in a major part of their internal cloud infrastructure.
The programme in question was running into performance problems, and a few smart people had already banged their head against a wall solving them.
After lots of experiments and different approaches, my solution was to remove most of the advanced data structures that were in the code.
In theory, they should have given us logarithmic runtime on some common operations, but the constant factors were too large. I proved (in the mathematical and the practical sense) that a brute force scheme combined with a careful randomization would dramatically improve real world performance with a fraction of the previous line count.
Despite me removing those interesting data structures, I still count it as a great application of my algorithms-and-data-structures knowledge: a big part of expertise is to be able to spot opportunities for simplification.
- WalterBright 6y agoAt Caltech, we'd call that "brute force and ignorance" which is often the best solution. For example, Enzo Ferrari once said that the secret to better performance is more horsepower.
- eru 6y agoWell, I was using less horsepower. The problem in the previous solution was that it took a while to keep the fancy datastructures updated. (It's a globally replicated distributed system..)
- karolist 6y agoThe actual quote was something like "aerodynamics are for people who can't build engines" which proves your point a bit better.
- WalterBright 6y agoIt's actually a bit ironic, because I consider Ferrari to build elegant cars while my old V8 Dodge is a triumph of brute force and ignorance. They're both great cars at opposite ends of the spectrum :-) A variation on the sentiment I heard in a movie: "turbochargers are for wussies, real cars have cubic inches!"
- dolmen 6y agoElegant doesn't always go with optimized aerodynamics.
- foota 6y agoIt doesn't matter how well you can optimize if you don't measure in production and benchmark!
- vishbar 6y agoDue to the physical architecture of CPUs/etc., data structures that have "worse" asymptotic performance are often quite a bit faster than those with "better" performance. For example, iterating through a small array to find an item and test for existence is often quite a bit faster than using a hash set for the same operation.
- eru 6y agoIn the same vein, pre-processing your data via sorting on some carefully chosen keys can sometimes alleviate the need for purpose built data structures. And because of caches, sorting can sometimes beat hashtables.
- dhsysusbsjsi 6y agoWhich is why I just use the standard library.
- eru 6y agoMost languages have more than one data structure in their standard library.
- nostrebored 6y agoThis was the focus of my advanced algorithms course at Georgia Tech in my senior year. We had basically a full semester on random algorithms, and I remember walking out each day feeling like the fancy algorithms I'd memorized the previous year were a bit less glamorous. The number of algorithms that removed multiple complicated stateful steps with 'and we randomly select an element from the array' was mindblowing. As I work on more and more distributed systems I keep seeing opportunities for simplifications with randomness (with obvious drawbacks on occasion).
- eru 6y agoYes! Randomised algorithms are my favourite. You can sometimes put all the randomness in one part of the algorithm, even. Like shuffling before a naive quicksort. In practice that's often even easier to understand (and debug!) than algorithms that keep making random choices as they run. Shuffling and sorting are two humble but powerful building blocks of many algorithms. Both distributed and sequential. In the example of what I did at Goldman, the core of the problem was essentially a souped up multi-dimensional bin packing problem. The big insight was that the typical distribution of our input data, random assignments had a high enough chance of being good, so we didn't need to keep track of everything in k-d-trees. (k-d-trees are also awesome. And I even implemented randomized k-d-treaps at first, before I hit on an even simpler solution.)
- ourlordcaffeine 6y agoDo you know any good books or resources to read up more on random algorithms?
- eru 6y agoSee eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-nutsbolts.pdf https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n... And https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor... describes one of my favourite algorithms. https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf is also interesting. You can find a lot of good material just via Google, actually. If you read the likes of The Art of Computer Programming for breakfast, you might like 'The Discrepancy Method - Randomness and Complexity' available at https://www.cs.princeton.edu/~chazelle/pubs/book.pdf https://www.cs.princeton.edu/~chazelle/pubs/book.pdf But it's not for the faint of heart.
- Pmop 6y agoI've learned approaches like this when I took a Operations Research class. I found it all exciting. We've also learned techniques to better choose between meta-heuristics like CGRASP, or flat algos, or integer programming, and so on. Now I'm seeing if I can think of some cool pet project where I can apply this stuff.
- eru 6y agoOh, I also applied lots of linear and integer programming. The main benefit of something like integer programming is that you get a clear separation of the specification of your solution and the algorithm that computes it. When even smart people naively attack any kind of optimization (or selection) problem, the resulting approach often mixes the business logic for specifying the optimum solution and the code for finding that optimum. That makes any change in business requirements very hard to implement.
- mumblemumble 6y agoEric Lippert did a nice blog post on this sort of thing a few months ago: https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.
- jihadjihad 6y agoI think one of the main takeaways of his post is that anything is survivable when n is small, and that the overhead required to spool up more robust data structures just isn't worth it for small n.
- spaetzleesser 6y agoI often find that the actual number that could be called “Small” in this sense is often quite large. Computers are very fast these days.
- eru 6y ago> The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance. I'd say _some_ algorithms and data structures with great theoretical characteristics tend that way. Just as many other work great in practice as well. You have to measure and benchmark.
- nathanyz 6y agoExactly this. While the underlying theory is excellent on many of these theoretical algorithms, they typically don't perform as expected when taking into account the infinite complexities of the real-world. But being able to understand the core value of the algorithm enables you to adapt or modify slightly in order to get it to work as needed in the real world. In general just knowing that there are specialized algorithms for certain classes of problems is 80% of the expertise you gain over years of experience. Knowing that things like Bloom filters exist when you hit a problem that could be solved by this class of algorithm gets you much further than expertly memorizing any specific implementation of the algorithm. There are a variety of them depending on the actual use case you are looking to solve for.
- kamaal 6y agoAlgorithms are all about eliminating waste effort. Not using programs invented by others to manipulate data structures. Those just happen to be solutions to some problem patterns. A person good at algorithms is some one who can make things happen with least effort possible. Not some one who can invert trees, even more so when there is not need to invert a tree. You can see how good some one is at algorithm stuff to see how much drudgery exists in the way they do work themselves.
- 908B64B197 6y agoA lot of algorithms and data structures are not cache aware and assume that all memory operations have the same cost. It's sometime best to use the 'worst' approach that allows most data to be as close to the CPU as possible for the longest.
- Aperocky 6y agoNested loops go brrrrr
- eru 6y agoNo loops in this program. It's all written in Erlang, so it's (tail) recursion all the way.