We had one reporting query that ran for 13 hours or so, in a normal web request. Not very successful, but it tried its best. Running this through explain while thinking of daloks revealed some dependent subqueries. Those are the devil in mysql because they are evaluated per row in the outer query. That takes a lot of time very quickly. Eventually we wrangjangled the dependency into a terrifying group by such that the dependent query could be precomputed and the outer query just joins with the result. Boom, runtime down to 2 minutes.
In another case everyone panicked ... until one of my dudes added an index - which took about a day - and slashed runtimes from 18 hour to 12 minutes. Learning to optimize queries on your RDBMS of choice is very powerful.
If I recall correctly, that raised the "feasible" value of K from about 4 to about 14 on the hardware at the time, which was more than enough for our purposes. I wanted to keep optimizing, but my boss correctly reminded me that shipping the paper was more important.
Works great in dev with a local sqlite instance and ten rows. Not so great in prod.
My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are diffuse - they're literally everywhere, and they don't always show up on a flame graph. On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs).
C is particularly a bigger issue once you consider Amdahl's law. A 20% slowdown in a linear part of the code can show up as a second-for-second slowdown in response times, while a search algorithm that's only a small part of an overall process, or parallelized, you can make it 10 times faster and might only see a 2% improvement in response times. If you avoid allocating more servers, for a new feature, nobody celebrates your achievement. You have to do it wrong the first time for anyone to notice you.
Judging by those, the most important hard parts are around planning and estimating work, and correctly understanding when those make no sense, and in validating code for correctness, especially over time.
If we ignore importance and just go with what's the hardest single task: naming things.
But I think they're of a piece. All of these things are "meatspace" problems. We are constantly fighting the temptation to try to intellectualize the whole process of making software because the center of the problem is trying to interact with a machine. Some don't fight that temptation at all.
You see this problem when people fight automation because they expect everyone to execute a manual process perfectly every time, even when the consequences of failure are very high. They insist that everybody white-knuckle everything and think less of you if you don't agree. They victim-blame. When they're the founding or oldest surviving members of a project, you're gonna have a bad time. People who could fix the problem move on to other jobs.
Naming things is really the same class of problem. A bad name calls to mind assumptions that are not relevant, and you are in constant danger of making category errors every time you think about that part of the code. A bad name becomes a sort of attractive nuisance.
The C problem is a matter of motivating people to do the right thing. Because it's difficult to spot, it's an invisible sin. It rarely comes up in code reviews, so nobody will call you out on it, nobody will make you fix it, finding it after the fact is daunting, and the only people who will care (eg sales) are so often the source of other problems that pleasing them is almost a character flaw. If performance is a feature, then constant time regressions are one of our worst games of whack-a-mole (behind security and internationalization, maybe ahead of sane logging).
[ETA:] I'm just a weirdo who likes to tilt at some kinds of problems I find hard, instead of dumping them on someone else.
I assume you mean that these improvements would not be visible on a flame chart because they were not in perf output? (assuming one was built from the other?)
Flame graph by definition shows where the time is spent and is just a (great, imho) visualization of this data. Some people seem to have a beef with it, but their issues are invariably tied to the way the original data is gathered.
The data can be wrong in a number of dimensions. In general, code that gets called the most sometimes get underreported. Look at invocation counts. Ask questions.
One, they can clear the CPU cache, causing sibling functions to be overreported (one of many sources of how changing a slow function may bring less of an improvement than expected). This shows up strongest when I‘ve gotten a 10% runtime improvement from fixing a function reported as 5% of total time, or a 10x reduction in time from removing half the calls to a remote service.
Two, duplicate or idiomatic code will be scattered across different parts of the code stack, reducing the apparent magnitude of a pattern of logic below the threshold of attention of most people. Code that is in four places may represent 5% of total time and not get looked at, even if it’s an easy fix. The nickels and dimes add up quickly.
Three, functions that operate near the limits of the clock resolution will be counted properly but the cumulative timing rounded down, again putting it below the noise floor for most people. I’ve made a lot of hay re-sorting the results by invocation count and benchmarking changes to functions that never hit the top 20 list.
And last but not least, functions that create but don’t destroy their own memory allocations end up shedding timing that gets picked up by the recipients, homogenizing the timing graph. In particular in GCed languages, a function that is called in a loop that exhausts most but not all of the free heap will invariably end up stalling out in the next phase of a large calculation.
With all four of these, there are several failures of imagination I commonly saw. A flat timing graph is taken as evidence that it is time to stop optimizing, even if the target improvement has not been met. When the “tent poles” are even, getting people to care how tall they are is challenging. Few people will make six changes to the code to achieve a 10% speed up. The Rust compiler may be the first time I’ve witnessed anyone else brag about a 1% performance gain, other than me. They either don’t do it, or they apologize for achieving so little. 10% is 10%, and I don’t care where you found it, if your code quality is high enough. And perhaps most importantly, speed improvements are multiplicative, not cumulative. Use a time budget the way game devs do. If an interaction takes 10x as long as your target, every method that takes 0.5% of current run time represents 5% of your target. This is, in particular, how you spot duplicated slow code. You ignore them at our peril.
Particularly in the era of QA cycles, using a “zone defense” (optimizing one module at a time, instead of going after tall tent poles) netted a higher rate of return per hour of labor and a much larger cumulative improvement, on its own merits and by increasing the budget allotted to perf. It seems concentrating the changes in one area at a time decreases optimization fatigue. On two projects I kept that initiative alive for more than two years, and I was the one that gave up because I had cycled around the entire system and was finding few things to correct (you only learn new tricks so fast, and they go asymptotic eventually). Everyone came to expect every release to be a bit faster than the previous, and I got feedback that this narrative increased sales, and manager buy-in. People will take a chance on you when they like where you’re going, even if you haven’t gotten there yet. Narrative matters, if they trust you, and usually you have to earn it.
You still need to understand how the data was gathered and what it really means. It is also true that flame charts are more useful on projects that are not yet heavily optimized; they clearly show the parts that are very slow compared to others. And when you don't see anything else that can be optimized, it doesn't mean that everything is optimal - the limit is imagination (and knowledge), not the problem space.
Total time = nX + C
No matter how much you optimize X (n here is for instance the number of items), if C is significant then it matters. It is usually harder to optimize the constant C in the OP's experience.
https://www.moderndescartes.com/essays/auc_intuition/ is my writeup on why the sorting approach is the most economical way to approach this sort of problem
For some practical work I was doing, BOB (and SK learn) proved too slow for my liking. I am currently unable to provide much more detail, but I used a similar insight to yours (mine was the amortization of sorting costs to have a better average time complexity) in a library I built for calculating empirical, bootstrapped, confidence intervals for EER's.
https://github.com/feerci/feerci
For massive amounts of decision scores, like millions, this method can give you confidence intervals on EER's where no other library currently in use can. Unfortunately, I have not yet found a theoretical basis for this method, and suspect it might actually break down under some trivial smaller cases. Also, DET curves and their derived measures remain a tough cookie to crack.
Considering AUC's and EER's are somewhat tightly related, I'm thinking this method could also be applied to AUC's.
EDIT: fixed my math, thank you andruby
Yes, N^2 to NlogN feels like it should be a bigger factor, but remember that constants in front of this matter. You are replacing 2-level nested but very straightforward loops that rip through cached memory at blazing speed without any disruption to CPU pipelines with a single loop that involves quite a bit of condition checking and array element swaps (cache is busted, pipelines are busted - conditions are very hard to predict). You gain some, you lose some.
It would be interesting to see them applied separately. The commenters claim that both are important has not been shown by his example yet.
However the results are impressive. Great job with the solution.
The pre-processing is typically worth it if you're searching through a large string, even just once.
Anecdata, but most of my strings were indeed short (searching for manufacturer SKUs inside arrays of other SKUs).
It's scary how many people are unaware of it, though.
Not nearly as dramatic as the example above, but I once cut the time spent on page generation for a commercial CMS by 30% my first day in a new job by realising they did excessive new allocation of strings instead of concatenation (which will amortise the allocations by allocating more space than needed in most C++ implementations).
I find it quite disturbing, because, while I prefer to use Ruby these days, C++ documentation is really explicit about guarantees provided by both the language and the standard library with respect to things like memory behaviour and algorithmic complexity.
There's if anything less going on under the hood with C++ that you're not explicitly told about than in most modern languages.
There's so much more going on under the hood of more high level languages, that writing faster code is straight up black magic [1].
[1] https://stackoverflow.com/questions/28723658/python-why-is-i...
Mastering C++ isn't even required to be productive using it, since there's no need to use all the language features simply because they exist. This also avoids the majority of footguns.
I agree. But the scientific computing community includes a lot of people who have no exposure to computing at all, so that vectors are copied when passed by value (as opposed to a fat pointer a la Go slices) is a performance foot gun for these new users. For that matter, a lot of people coming to C++ from any higher level language will likely be tripped on on this for a while.
> Mastering C++ isn't even required to be productive using it, since there's no need to use all the language features simply because they exist.
Right, I was distinguishing between "mastering" and "knowing enough to be productive". I'm asserting that you can master Go in far less time than is required to be merely productive in C++ (granted, I'm assuming "productive" means "you're not regularly introducing memory leaks, segfaults, etc" i.e., "you understand memory management best practices in C++"). Specifically, I think it takes 1-2 months for a newbie programmer to become a master of Go and ~6 months to become merely "productive" in C++ (bear in mind that even figuring out how to build non-trivial C++ programs is itself a herculean feat).
There’s a lot in c++ that only exists for back compatibility and you don’t need to use it. There’s also a lot of infrastructure so library writers can write very efficient generic code. Most people are not writing libraries and don’t need that stuff.
Also, templates, and the indecipherable errors they throw. And cpp memory handling errors are one of the largest sources of security holes.
I'm convinced that apologising for cpp is basically Stockholm syndrome. These are things we absolutely would not accept in a new language, but we must, because it's what we've got. Rust can't win fast enough, I say...
Rust is powerful enough to do a lot of what C++ is used for, but not the hardest things. There are libraries you write routinely in C++ that you can't code in, or call from, Rust, and never will. The gap will widen with time. Rust is focused on low-level safety at the expense of library power, but you get safety in C++ by coding using more powerful and safe libraries, so C++ comes out ahead in the end.
Rust is a way better language than Go or Java. It would be excellent if Rust could displace them, or even just one of them.
If its adoption rate were to increase by maybe two or three orders of magnitude, it could survive. But the Rust core team seem not interested in doing what would be needed to get that much adoption, and hype alone won't get it there.
Rust's place will be secure when more complaints are written about it than paeans.
Rust has its own problems and pitfalls as well, and I doubt that people who don't understand pass-by value vs pass-by reference and its implications will be happy with fighting the compiler over ownership issues.
Implementing a doubly linked list comes to mind - trivial in C++ - a brain twister in Rust and apologists will hide behind statements like "they're almost always the wrong choice anyway" or they're "just used pedagogically" [1].
A cynic could interpret that as Stockholm Syndrome as well.
[1] https://codereview.stackexchange.com/questions/204183/doubly...
Compare it with lazy evaluation languages like Haskell or declarative languages like SQL where oftentimes you have to run query planner explanation to troubleshoot the performance problems.
Also what’s fun is that the data in the tables can change the explain plan. I got to see this myself when dealing with dev vs prod data.
The very basic experience with RDBMS would point you at a better solution: indexes. Not sure about MySQL or standard SQL, but with Postgres you can keep an ordered index that will be used in an ORDER BY query. It's a common trick employed in programming in general: trade the update/insert cost for query cost (indexes take time to update, but querying is then fast).
1. This change tends to be in your favour, not against you.
2. Data is important, not the code. Of course the plan would change if your data changes. That is the point of the query planner, to find the most efficient way of retrieving the data, based of course on the contents of the database.
I agree that you need a good knowledge of your database in order to be effective. Just like with C++, for example. Unfortunately we're not at the point where we can achieve optimal results without understanding the fundamentals, regardless of the programming paradigm.
And it is a dsl the planner is expected to be very good. Perhaps the next version will always fix it.
There is a lot going on under the hood regardless. That's how computers work. Your Python script has to deal with all the same memory allocation and cache locality issues.
C/C++ just gives you the opportunity to see what is happening under the hood and tune it.
In practice they mainly displace function pointers.
I work on a pretty heavy ML system, which a year ago took about a month to 'fully' train. Today we're down to 25 hours training time using the same hardware, based mostly on improvements to the model. The improvements are coming from a combination of signal processing tricks and tricksy model changes. Inference is similarly much faster, too...
Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each element needed calculation of Kendall Tau on two series of numerical data of length N. Both M and N were on an order of few thousand and naive implementation has the complexity O(N^2 x M^2). The program ran for 6+ hours.
After looking at C++ I realized that a lot of time is spent just copying data needlessly (a result of not knowing the difference between passing a vector and reference to it) and needless memory allocations and deallocations. I did a rewrite from scratch, keeping the tests, but not copying anything and allocating a minimum amount of memory only once, employing the cache locality, spreading the calculation with OpenMP and finally - realizing that Kendall Tau can be done in O(M^2 x Nlog(N)) I found that out on my own, just by squinting and realizing that calculation of Kendall tau for two series is essentially sorting, but later found out that e.g. scipy implementation uses the same approach.
The resulting program ran for 4 minutes on a 2-core and 4 threads.