14,000x Speedup (2015)
james.hiebert.name
james.hiebert.name
Otherwise we end up with basically this: Person 1: "I am very smart." Person 2:" Rubbish. It is I who am very smart." That is not interesting, regardless of who is smarter. Worse, it all-too-easily turns a community like HN into an unfriendly place.
When in doubt, simply remember that the intended spirit is curious conversation, and then your comments will naturally contain interesting details and insights without the other stuff.
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.
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.
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.
In practice they mainly displace function pointers.
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 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.
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.
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.
Anecdata, but most of my strings were indeed short (searching for manufacturer SKUs inside arrays of other SKUs).
The pre-processing is typically worth it if you're searching through a large string, even just once.
Works great in dev with a local sqlite instance and ten rows. Not so great in prod.
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.
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.
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.
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.
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...
Climate scientist here. Colour me a little confused. We have a GCM which is (typically) on a structured grid, i.e. with latitudes & longitudes on a pixel-like grid. Finding the GCM (coarse) grid cell for a given latitude/longitude of the downscaled (fine) grid is an integer operation, i.e. invert lat = lat0 + i x delta_lat and lon = lon0 + j x delta_lon. Must be missing something here. Even if there is a strange projection, you can map it such that the deltas are uniform.
This binary search "optimized" abomination is... more difficult to read and reason about than either than the integer math or "brute-force" solutions, and slower to boot. All it has going for it is that it's not the absolute slowest choice.
It may not be integer math, because we've not been told if the grid is regular... but it certainly is still easier than this.
The solution here is faster than the absolute naive solution of finding all distances, but it is both slower and less readable than integer math grid conversion..
I could see why you would make the choice of the naive, slow solution. I could see why you would choose the fast, integer math grid conversion one. But I don't see why you would choose something slower than the optimum solution that is also much, much less readable.
That is, the naive solution and the integer math solution are Pareto-optimal choices... and this abomination ain't.
The differences between this comment and the GP comment are significant. The GP included specific information, where this comment is just a putdown, and the GP allowed for the possibility that there is missing information, i.e. that the "author is an idiot" interpretation is not the only possible one.
It's moot anyhow, because the main reason not to have threads go that way is that it does bad things to the community. Each time it happens, we deepen the pathways towards making HN nastier and more toxic, and since those are the default paths already, we need to consciously cultivate the opposite.
Note this guideline also: "Please don't sneer, including at the rest of the community."
It's worth remembering that HN is a statistical cloud of posts, not a person, and so can't think anything.
Even if we ignore the fact that it's grid to grid conversion, (which should just let you math the answer, without any searching) the fact that all the data is sorted means you can do the equivalent of a merge sort and only have to look at a two point for each step.
And how on earth can you take .117 seconds to line up a half a megapixel worth of grid points, even with their "fast" algorithm. They are using the R language which should be fast, right? Are they doing something expensive with it? Or perhaps there is an insane amount of data elsewhere making these lookups super expensive?
The author optimized their code in a way that was fast enough, and fast enough to massively change the entire business process around their code. It's very commendable. Further optimizations may have not been worth it.
Seeing the code in article, it can be that a part in that speedup is because R is used and not only of a better algorithm.
[1]: https://predictivehacks.com/a-comparison-between-iteration-r...
I can o lump resume the problem is badly described to miss some subtly.
I hope.
My other comment was going to be that using binary search is not that much computer science. I mean, it's elementary programming knowledge, you don't need a degree to know that.
A few ways to solve this pop to mind. As Aeolun mentions in a parallel comment, you can just divide coordinates if your grid is regular. But it often isn’t.
In that case, you can attack it in a few ways. One time Feynman was giving a lecture and said “This triangle looks a little cockeyed. Obtuse! That’s the word! I know about the triangles but not their names.” And I’m not Feynman, but I did forget the name of this: you build a tree of squares. First one is your whole grid; split it into four smaller squares, those are the children; repeat till your resolution is sufficient. Then you can attach whatever you want to the child nodes (in this case, grid squares). Since it bisects space into halves, you can do a search in O(log n).
But what if you want to go faster? What if it’s absolutely crucial for speed, like a physics engine, to be able to ask “which objects occupy this region of space?”
My favorite algorithm is absolutely delightful: a radix sort on floats. http://www.codercorner.com/RadixSortRevisited.htm
You end up getting O(k*N) time, just like radix sort normally gives you. But the real magic is that it works with bounding boxes. There’s an article from the same author which I can no longer find, detailing it. But the idea is, you sort all your objects in one spatial dimension first, say along the X axis, and then you don’t need to do anything to search quickly. No trees. Suppose you want to ask “does this region of the X-axis have any objects?” You just... do something, ha. I forgot the next step, so I don’t want to say a mistaken answer and tarnish poor Pierre’s idea, which is quite nice. But he’s been working on this problem for basically decades, so here’s one of his N papers on the topic (of spatial partitioning, not applying radix sort to solve it): http://www.codercorner.com/ZeroByteBVH.pdf
I could work it out if I sat down with it for a bit, but, I leave it to one of you younger devs can take up the torch. It’s a fun puzzle.
And some people have taken that to extremes, building 3d rendering engines and tech demos in what is a very constrained environment.
You compute the bounds along each axis in linear time. The sorting of these bounds can be done in linear time, then you take a pass over each axis looking at the marked intervals, which is also linear.
Once a month, they reloaded the patron database; it took about 24 hours. If there were a network interruption or power glitch, it would have to be rolled back and run again the next day. Pretty bad.
It wasn't my task, but I was curious why this program took so long to run, so I started picking it apart. It was written by a PL/I programmer -- his first Perl project. No comments. He was no longer there. No one understood the script.
I started changing things, among other things I moved the Oracle-specific DBD calls out into a separate module, because someone on the internet said Perl ran more efficiently that way. And poof! just like that, the program then ran in 8 minutes, down from 24 hours.
I looked like a hero, but I very openly said I wasn't quite sure what I did. Just got curious and moved things around, and apparently discovered some bug in the DBD layer by pure accident.
Sometimes curiosity and willingness to experiment is all it takes.
I am a HPC cluster admin. Many years ago, we had a (for us back then) rather large project. Several million hours of CPU time. During a support case, I happened to stumble across the source code for the project. And I was pretty surprised. It was a few hundred lines of Pascal, compiled with fpc. I knew about the language being used and was told other compilers dont make a lot of difference "because the code only uses 32-bit values". Hmm, suspicious, but you can't dictate how people solve their problems. At least not easily. But the small LOC count, and a upcoming weekend without a lot to do got me thinking. So I sat down and more or less mechanically translated the code to C++. Making use of templates to move a value from runtime to compile time. And bang, I got a speedup of 5x. So a few hours of time spent by someone NOT involved in the project at all helped to save around 5 mio. hours CPU time (around 1.5x my yearly salary).
Of course, this is a pretty extreme example and not really representative for the scientific computing community. Still, with my experience watching people run big jobs I am estimating that we waste around 50% of our computing time (world wide) on insufficiently thought-out implementations and lack of knowledge about the actual architecture the code is running on. Sometimes, I am happy if a user knows the difference between OpenMP and OpenMPI :-)
I disagree.
Source: dude, trust me.
There is the odd project that is so computationally intense that it needs to be written near optimally, but most scientific computing is a quick-and-dirty calculation run inefficiently on a giant cluster so you can get that figure for your paper and move on.
You could make this abuse of <script> a bit more tolerable with something like the CSS `script[type^="math/tex"]:not([id]) { display: inline }`, but that will still be hidden to text-mode browsers or browsers where the CSS fails to load. It’s much better to just not use <script> in this way.
KeenWrite[0], my desktop text editor, has an Export HTML using TeX/SVG feature that encodes math glyphs as vector paths, embedding the SVG into the resulting HTML file.
On the subject of optimizations, KeenWrite can render 1,000 simple TeX formulas to SVG format in about 500 milliseconds (on my desktop machine), sufficient for real-time previews. Two libraries needed changes to accomplish this feat.
First, JFreeSVG and Apache Batik both suffer from the same performance problem: they use Java's NumberFormat to convert floating point numbers to strings. It's slow because of internationalization rules, which aren't necessary for a machine-readable format. The fix entailed replacing NumberFormat with the Ryū algorithm[1].
Second, JMathTeX[2] was parsing TeX by throwing exceptions for flow control. In Java, throwing an exception forces the virtual machine to fill out a stack trace. Normally this wouldn't result in abysmal performance, but the flow control was being executed for each character in every macro name encountered. Pre-parsing macro names without any flow control resolved the issue.
Further optimizations were made, but those two were the lion's share. Combined, the total time went from 1 TeX formula to SVG format in ~5 seconds to 1,000 in ~.5 seconds.
[0]: https://github.com/DaveJarvis/keenwrite
I used a similar optimization when I was younger to enable interactively plotting very large (at the time) 2D point datasets. We stripped out points that were so close together that the difference would not be visible. The X,Y coordinates were each binned to an integer pixel location and both were packed into a single long integer. Then we stored a hashset of longs so we knew what pixels had points occupied. When adding a point to render, we did O(1) hashtable lookups to see if the location already had a point in it. The result was an extreme speedup because we could avoid rendering all points which were not visible, and it scaled linearly with the number of points.
X = Math.floor(bigX / bigXMax * smallXMax)
Is there some magic here I’m not seeing?
And even for non-regular grids, as long as they're somewhat regular (like timezones), you can narrow it down to just a handful candidates that a linear scan will then solve instantly.
We've not got the whole picture though, but you don't need CS training to know that a loop within a loop within a loop within a loop is a bad idea.
The speedup I measured could have been even greater if longer strings were being matched, but in practice the longest string I tested it with took over 14 hours to match before the change, and ~2 milliseconds after the change. This alone is a ~25 million times speedup.
It was such a fun problem to solve, and by far the largest speedup I had ever seen. It was also the first time I encountered this issue outside of compilation class in college, but the way this regex was constructed made the issue pretty obvious.
So they had something like this for this structured part:
[a-zA-Z]+[a-zA-Z0-9-.]*[a-zA-Z0-9]?(\.[a-zA-Z]{2,3})?
Let's call the regex above STRUCTURED. Now how do you match either one of these structured strings followed by either `.foo` or `.bar`? They had it as:
STRUCTURED\.foo|STRUCTURED\.bar
The change I made was simply to match it with:
STRUCTURED(\.foo|\.bar)
I hope the general idea still comes through despite the simplification and required obfuscation.
CS is a wonderfully useful, deep and broad field. There's nothing so special about some simple Big O complexity that he couldn't have taught every developer in the department this rather than bragging and upstaging the person who wrote a correct but slow implementation. Patting all of CS on the proverbial back for this smells of gatekeeping.
I've started Qvault to try to address the problem... We'll see where it goes.
There are just jobs I never would have gotten or kept if I wasn't able to solve complex problems, on my own, the few times they come up.
This is something that is so hard to get across to boot camp grads. They complain about how hard it is to get a job, how hard it is to progress at the jobs they do get, how hard it is to write basic programs on their own, how hard it is to even figure out what is important to study. But then, if I suggest that constantly focusing on shallow, broad study of JavaScript-framework-du-jure might not be sustainable and that Computer Science might actually be relevant to software development, suddenly I'm the asshole for calling into question the teaching methods of the boot camp system.
For me, it's also a quality of life issue. I just can't imagine being satisfied with a career where I'm just a glue coder. I want to make new things. If I were working in the automotive industry, I wouldn't want to be on the assembly line, I'd want to be in the engineering department. And most of the people I talk to want to make new things, too. They just don't seem to want to hear that "building something from the ground up" requires "understanding fundamentals".
What's not to love about bureaucracy?
I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US created a parts-of-speech tagger and released the source in the early 2000's. I wanted to leverage this tagger to create a topic oriented search engine, but it was WAY too slow. It took about 10 seconds to tag a document (back in 2003 on decent hardware), and since I needed to tag hundreds of millions of documents, and despite having about 15 servers at my disposal, this was not going to work. So I dug into that algorithm and realized it was trying to test all of it's conditions all of the time to figure out which rule would apply. I redesigned it to index the rules and only apply them if it was possible for that rule to have some effect. Or something like that, the details are now fuzzy. The speedup was roughly 1000x, and made the tagger usable at scale.
Plot twist: I took a computer science class (as a Mech E major) taught by that same professor years earlier and failed it. That class was Data Structures.
But your story shows the gulf that exists between Computer Science and software development. You needed to actually use a piece of software constrained by business requirements (not spinning up 250 servers), and when it didn't do what you needed it to, you changed it. The fact that you failed a data structures class didn't prevent you from refactoring and improving the code. The fact that that professor wrote code that performs poorly on good hardware doesn't negate the fact that there was probably some novel CS implementation in there somewhere.
I know in the past I've gotten caught up on CS profs having terrible websites or programmers not understanding the intricacies of bubble sorting but I think it helps to keep in mind that they are two different disciplines that inform each other, and the gap is seeming to get wider over time.
I find the opposite to be true, but it depends entirely on what problems you work with on a daily basis.
Data structures and algorithms are a toolbox and the more you know, the more options you have at your disposal to tackle a specific problem.
If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; interviews done by people who don't have the faintest clue about what they're hiring you for (which is a big problem itself).
I suppose that's true, my perspective is as a client engineer where for the most part, someone's built the data structures for you. Yes you need to know their performance characteristics and when to use them, but otherwise if you're building them yourself you're doing something wrong. I'm sure that's not true in all roles.
> If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; interviews done by people who don't have the faintest clue about what they're hiring you for (which is a big problem itself).
I'm actually really passionate about recruiting and improving the recruiting process anywhere I work, I'd love you to elaborate on this.
Unfortunately this is a really complex topic and I'm afraid I'm not nearly knowledgeable or experienced enough to give any meaningful advice in a concise way.
Say a candidate is to be hired for developing and maintaining a line of business app. In this case it's important for them to know the programming environment, frameworks and tools, as well as working with large programs or legacy code if applicable.
Start by asking a few "no brainers" sprinkled into a general conversation about their previous work experience and increase the "difficulty level" from there.
There will come a point at which the only honest answer will be "I don't know" or "I'd have to look that up", which is the perfect opportunity to just hand them a tablet (or laptop) and let them do so. This is an excellent way to learn how they look-up technical information (which sites do they use, how long does it take them, do they use meaningful keywords).
Another effective way of judging someone's skill is asking them to point out problems with a small piece of code or have them discuss required modifications to meet some constraint (e.g. sort a dataset by one of a user-selectable set of criteria, but you can only read each item once and the dataset doesn't fit into memory - a common problem with archival data stored on tape).
These are just some pointers, but they all have two things in common: they require the interviewer to know what the candidate is going to work on and they need more preparation work than just a checklist that reads "knows how to implement an AVL-tree in Python" or "can tell the arguments of all 6 overloads of std::transform_reduce() in C++17".
But a structured program will take you through these things, ensure that you understand them, be available to answer questions in a manner other than "bang your head on the problem for weeks" or "just give up", and provide a structure progression through to more advanced topics.
I think it's important to keep both sides of this in mind; the universities do not have a monopoly on the knowledge and arguably it's easier than ever to pick up yourself, but that doesn't mean the structured experience is useless either. I've worked with some very good self-taught people, but they all have also tended to have gaping holes in their education relative to a good computer science education. (I agree with those people that they are much better than some people who end up with bad computer science educations. Unfortunately, if one optimizes one's computer science education for "the easiest 4.0s", one can end up with very similar gaping holes in one's formal education!)
It also often seems missed that somebody who went through a formal degree in lieu of gaining real-world experience can also gain real-world experience at least as easily as somebody who got the equivalent of a formal degree through real-world experience.
Fun fact: Just getting the job done works out well most of the time, technical debt is introduced but as in your example it served its purpose.
[a] Key words are 100 items very rarely: if you’re sorting many times a second (for whatever reason) or (relatively) large datasets, using a quicker sorting algorithm than bubble or insertion would make sense.
It's the equivalent philosophy to always buying the cheapest tool you can the first time around. When you break that tool, then you go out and buy the expensive one.
1. Solve the problem.
2. Ensure correctness of that solution
3. The code is easy to reason about
4. The app is robust
5. "good enough" performance
6. Performance tuning
Which is of course the "correct answer", and of course in practice these all blend together I will emphasize any number of those at a given time (who doesn't love spending an occasional afternoon just chasing pointless benchmarks?). But I never come at it from a "big O mindset" even when that's what I'm doing in practice, I just call it "common sense" and heuristics: don't put slow things in tight loops, memoize when you can, and leverage concurrency.
In my line of work (CV), moving a slow blocking operation from serial to async will get you easy, bigger wins 90% of the time, vs seeking out something in polytime and refactoring to nlogn.
Know your data.
It's a good reminder to always try to understand your likely workloads as well as possible (know your "n"), and to get good measurements (what are K1 and K2 values) before prematurely optimizing these kinds of things.
"f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0"
Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0?
https://en.wikipedia.org/wiki/Big_O_notation
Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-)
Edit2: Added "memory of" - I'm pretty sure what I was taught was correct, just my memory of it that is all too fallible.
After all, the most efficient (in terms of big-O) known algorithm for multiplying two numbers uses a 1729-dimensional Fourier transform and only becomes more efficient once the numbers involved are significantly larger than the number of atoms in the universe[1].
I say this as a professor myself, because we do that all the time in my team: we create some software system (also in NLP, by the way), we do experiments to show that it improves whatever metric we are interested in or that it teaches us something interesting, we publish a paper with it, make the code available and then move on to the next paper. That's what we are typically incentivized to do. The time spent into optimizing a system that we are not going to take to production anyway is time not spent doing more research. Which doesn't mean that we don't know how to optimize.
- It serves as a form of documentation for what the optimized stuff is supposed to do. I find this most beneficial when the primitives being used in the optimized code don't map well to the overarching flow of ideas (like how _mm256_maddubs_epi16 is just a vectorized 8-bit unsigned multiply if some preconditions on the inputs hold). The unoptimized code will follow the broader brush strokes of the fast implementation.
- More importantly, you can drop it into your test suite as an oracle to check that the optimized code actually behaves like it's supposed to on a wide variety of test cases. The ability to test any (small enough) input opens a door in terms of robustness.
But, fyi, this tagger was not just a professor's demonstration, it was kind of ground-breaking and served as a foundation for other taggers. The professor went on to have a pretty awesome career at a few different big tech companies, far surpassing my own success. And yes, I agree, I am sure he could have made it faster himself had he dedicated the time to it.
I don't understand the reduction of all of math and CS to complaining about people who overindulge their notations. I've been reading this recently, and it just affirms how important and ubiquitous mathematical thinking is everywhere in life: https://www.gatesnotes.com/Books/How-Not-to-be-Wrong.
Now, you can imagine smart algorithms, trees, hashes...
Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all its updates. No indexes. Some algorithms were plainly O(n^3).
Yeah, I got into many heated discussions with "computer scientists" in the team. Yet for all their might they were not able to improve upon the program because they forget that algorithmic complexity is only one factor of performance.
Because I used extremely simple algorithms (like linear search) the operations were very simple and progressed quite fast on a CPU that was good at prefetching from the storage.
The total amount of memory available was just 0,5MB meaning that the "super inefficient" scans still completed within perception threshold of the user.
While O(n^3) was used for some operations, the application state machine which limited number of actual number of steps. Most transactions follow same basic pattern of execution and so I don't care what happens when somebody does 500 updates to the transaction when I can figure out there will ever be 5 state changes at most.
There were other consideration for the program. For example, it had to use very little instructions (we were very short on space) and it had to work in constant memory (to be able to statically calculate stack space necessary, for example).
Obviously you chose this solution because it made the most sense given your constraints (time/money/knowledge/microcontroller limitations). But that doesn't mean it was an optimal solution nor that with slightly more time/money/knowledge a significantly better solution couldn't have been found.
Frequency of run is also important - a batch job that takes 5 hours that only runs once a month? Is it worth optimising that?
Had a week long argument once about an (relatively) inefficient MySQL query because "it's not going to work for 1000 things" when a) we had barely 10 things currently running and b) the customer was >this far< from cancelling because stuff wasn't working (which this query would help with.) It was a frustrating time. I think there's a lot of developers who "know the price of everything and the value of nothing".
I set a breakpoint at the beginning of the main() method and it crashed before it even got to main().
That had me scratching my head for a minute, then I realized that the program was static initializing a 2^32 byte array. The prof had a 64-bit computer (probably DEC Alpha) which you could do that on, but it didn't work on my 32-bit x86 machine.
It turned out that the program never used the array that it allocated so deleting one line from the code got it to run.
Most CS profs never have to really finish the systems they work on so they lack many of the skills and attitudes of the professional programmer. Some of them are artisans with code, but mostly they making a living writing papers and teaching classes and the code is tertiary.
Isn’t this just a simple quantization? (Lat/20,Lon/20) should do it?
I also live in scientific computing world where the author lives and many other scientists don't appreciate the complexity of these optimizations the author hand waves away. It's easy to after the fact say, "well obviously look at this.." and show after the fact runtime performance improvements, it's another story to explain how you arrived at this, the time thinking about the problem sitting at dinner and before bed, while exercising or having coffee etc.
My biggest gripe with developers in this regard is how clever people like to act. They have a challenging problem and often spend significant amounts of time, then pretend like it happened over lunch. This does happen but from my experience, it doesn't happen regularly, not as many like to portray. You often iterate through several other optimization approaches aor ideas that fail or are discarded.
It's similar to when you see obnoxious compressed mathematical notation in a presentation where the author jumps through something they spent years on like it's trivial. If it was trivial, it wouldn't have taken you years and although a solution presented and checked to a problem is much clearer now than before, it's by no means obvious. This gives other professionals irrational expectations of resource allotment (in terms of your paid time) to solve these problems and makes your life more difficult than it needs to be.
Imagine if after Einstein spent time developing special relativity he skipped it all, hand waved, and said, "well clearly e=mc^2..." no--absolutely not clearly, but that's amazing insight.
Step 2: Brag about your speed up
I feel like base level algorithm/ds knowledge is getting higher so these will disappear, even if you don't know the exact solution your intuition will make you think "there's no way this needs to be so slow" and then you do some research/thinking.
Since the membership of any of the local cells in the global cells is static, we only have to compute this once. Then we add a globalCell parameter to each local cell to specify which global cell it's contained in.
If this uses up too much memory, we could go to a slower but still much, much faster than the blog post's method of something like:
- Create 2d array where the 1st dimension is a sorted list of local row values, one per global row value, that represent the maximum X value within any global cell. Then the the 2nd dimension are local column values, one per global column value that similarly correspond to the maximum Y value of any local cell per global cell. (mapping the coordinates to an array)
- Find the entry that the current local row value fits into (for example the entry with a value higher than the local row value, which is higher than the next list entry).
- This selects a second dimension array for that global row that has similar properties: it's only necessary to then find which value the local row fits into to determine the global cell (which would be the array's value at that index).
Languages and libraries should support broad deemphasis on counting and iterating and so on. If a user wants to find a thing, they should be taught to use a method on the collection, haystack.find(needle). If they want to iterate, they should be taught to use iterators, haystack.map(measure). And so on. We, as instructors, teach people for needle in haystack and that solves the problem and they move on so they can accomplish their real goals. All of the code in this article could have been written in one iterator chain in a language that didn't promote for l in locals as a first option, and with instruction that saved such implementation details for later.
Sometimes it is one of those "we did a quick hack and then forgot about it as data sizes grew", sometimes one just forgot about the complexity, and occasionally there are people who don't understand the problem at all.
In the example in the talk, it was less about knowing cs algorithms and more about knowing the details of how modern computer architecture works, but the lesson is the same: sometimes the background knowledge of a cs degree is useful.
He also has the same point about optimizing our code rather than just adding more and more machines.
https://arxiv.org/pdf/1509.00549.pdf (Results on page 28)
I suspect we would have seen similar speedups with larger vectors.
If you look at the tweaks to the algorithm, they're relatively minor, but with very significant gains. Sorry about the code syntax; the audience for the paper were statisticians.
I.e., 14000x means there's probably another factor of 10 or 100 in there. But 0.1s might be fast enough.
I get 2x on std::sort pretty easily. I am hoping to get a general speedup like that for half the algorithms in the C++ Standard Library into C++23. Maybe the other half a little later.
Caches mean nobody knows how fast anything should be, so lots of things seem fast until you see one faster, then the old one suddenly looks slow.
It depends on who you hang with :) I am 99% sure that 99.9% of people don't think like that. From my experience, people see computer programmers as nerdy mystical wizards and tend to say that they haven't got the slightest idea on how someone would even begin to make software.
Certainly not all of course.
Obviously the author of this script didnt know about sql joint. Reduced the work into one "for" loop and an custom sql join query as input, script running in less than 5 minutes compared to average 5hours before.
Note: I know numpy is C and faster than python but that was not the point. The point was using vectors vs bruteforce.
The most recent one was where a dev used an array scan to find a piece of data in a record array. We changed that to a hash table look up and saw a 100-1000x increase in performance on our larger datasets.
Not quite as dramatic, but still pretty good.
If you aren’t producing single person solutions and your product doesn’t have any performance issues, you can either count yourself lucky to be working with great engineers.
This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
To make it more concrete, if you take a bunch of heuristics like scanning for while(true) {}, scanning whether there are any loops at all, discarding primitive foreach loops that have a linear relationship to the input data amount, etc, you have built a rudimentary halting problem decider that has 3 outputs: "will halt", "won't halt", "I don't know". You can make it better with lots of research, SAT3 solvers, etc, but ultimately you will have to accept that there will always be programs that the decider will output "I don't know" for.
The law should be treated literally, in general case of all possible programs running with infinite amount of resources. If you take a program and you don't know anything about it and it has infinite amount of memory and you have to tell whether it executes or not, in general, it is not possible.
On the other hand knowing a little bit about the program already can make this statement not apply. As a simple example, restricting amount of memory makes it possible to construct a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources.
Real life programs are even easier to work with. Consider a CPU that increments a separate register for every executed instruction and terminates when the register overflows. We can easily tell that every program running on that CPU has to terminate.
As you see, it is rather silly to use general mathematical properties of programs and apply them to real life programs without considering for how real life programs are different from mathematical concepts. Real life programs are not spherical cows in vacuum, they don't have infinite time and memory to execute and the CPUs executing them are not perfect Turing machines.
I feel like "finite" is doing a lot of work there.
So, read it the following way:
Mathematically, you can construct a program that, using finite amount of steps and finite amount of memory tells whether another program terminates or not IF you know this other program has finite amount of memory to use.
Obviously, we know that even with very small amount of memory this is going to take huge amount of time. Just look at Busy Beaver function to appreciate how quickly this grows with amount of available memory: https://en.wikipedia.org/wiki/Busy_beaver
Basically, Busy Beaver function tells how long a program, given an amount of memory, can execute and still terminate.
This fantastic function is my favorite function if we ever play a game of "who can think a function that grows faster".
As a corollary, since every real life program has finite memory, it is not possible to construct a non-terminating program that will not repeat its output. Knowing this you just construct a simple program that looks for cycle in the program state.
You could think about this way: hardcoding a constant (moving it from heap to compiled code) doesn't magically cause the program to use less memory.
Thinking it in a different way, from purely physical point of view, every bit of information can be translated to some minimum amount of energy or mass (mass energy equivalence).
Since state ("state", not "possible states") of Turing machine is bits of information, you can't have a Turing machine with infinite size of state. Now, "possible states" are capped because if the state is finite in size, the number of possible states is less or equal than all permutations of it (permutations == possible states).
It is largely philosophical question which is "memory" available to the program and which is "Turing machine state". In case of real programs we see that memory can be reassigned depending on requirements.
There are some cases when the distinction becomes important in reality. Consider a trained AI that gets "baked in" and shipped to the user to compress/decompress images.
Let's say it does fantastic job at compression and decompression but takes 2GB of disk storage and memory when executing.
If you just compress a single small image you realistically need to send 2GB of the AI plus the very small image, but when you have billions of images this static cost of the AI gets amortized.
The same way happens when you run any real program on an operating system. In reality the program is much larger because even if it prints Hello World it still needs to do a bunch of data like recognize your monitor it is talking to. We conveniently package the common parts of the program as "Operating System" and then just let exchanging the small part that will make sense when coupled with correct OS.
That's also how you can have very small webpage that takes GBs of memory to execute... sadly...
It started to sound like "I read one Wikipedia article on the halting problem, so I'm a computer scientist...Allow me to show you how I am smarter than all of my colleagues who are only scientists."
When you can make assumptions about a program and its inputs, the halting problem doesn't apply. I mean, just simple observation shows that if you can't make whether your program terminates a condition inside your program, then the halting problem ambiguity as stated can't apply -- you may still not be able to determine if it halts or not, but with enough constraints or assumptions that can be taken as true, you absolutely can know if your program halts or not without executing it.
I'd be more inclined to replace it with "any non-trivial" in this case.
It's about requirements, corner cases, knowing and using the right tech, and the zillion or so things that can go weird or wrong and how to elegantly handle them.
Well before anyone coined the term 'monorepo' we had built one, and the architect and some of the leads noticed that each time we added another module to a TogetherJ project, the time to open the project shot way, way up.
I got on the case, and determined that with about 80% of our project loaded it took 28 hours to open the project. At this point I reported it to Together, and they said it was something to do with scanning the data for each module and the workaround was to keep all the data at the monorepo level. That got the load time back down to 20 minutes (less if you ejected some of the less interesting modules from the project). They also fixed the problem in the next release.
About this time I actually sat down and plotted the trend line, it fell almost exactly on an O(n^5) curve. I've seen n!, I've seen x^n loads, but I don't think I've ever seen n^5 before or since.