16 ms·

14,000x Speedup (2015)

424 points by signa11 6y ago

salmon 6y ago
I find optimization porn like this to be so satisfying.
- Frost1x 6y ago
  The only issue I have with optimization porn is that it often handwaves away the time and thought that went into finding clever optimizations. In some cases it's clear how a problem can be better optimized. In many cases, it's not so clear. It takes someone experienced in development, an understanding of software and computational complexity, and the insight to see optimization opportunities or have used them before. 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.
- CyberDildonics 6y ago
  Step 1: start with something grossly, ridiculously inefficient. Step 2: Brag about your speed up
m4r35n357 6y ago
You could get arbitrarily large improvements by starting with even worse code ;)
- andi999 6y ago
  Exactly. I like the enthusiasm of the author; but the self-congratulatory attitude doesnt go down very well if you should actually be ashamed of the first version. I mean it is only a few inches from:"you know in the old days we had to flip through the telephone directory from front to end to find a name. But you know what: it is actually a sorted list, so we applied a binary search algorithm and are 14000x faster. Tl;dr CS for the win"
  - theamk 6y ago
    You'd be surprised how often "flip through the telephone directory" thing comes out in the real projects. 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.
    - andi999 6y ago
      I agree, and I also think this should be the first solution since it is obviously correct so you can test your faster algo later against this (at least in the post the invariants of the dataset are not spelled out exactly, and we know premature optimization..). But I do not think you should expect a trophy when later fixing it (when profiling shows it is a problem).
nightcracker 6y ago
If your grid is well-behaved enough you can go a lot faster still using locality sensitive hashing.
Aeolun 6y ago
I’m not sure why we can’t map a position in a big grid to a position in a small grid by doing: X = Math.floor(bigX / bigXMax * smallXMax) Is there some magic here I’m not seeing?
- rocqua 6y ago
  Grid doesn't need to be regular
  - etimberg 6y ago
    As an example, see this image of the UTM zones and look at the zones labelled in red. https://upload.wikimedia.org/wikipedia/commons/b/b7/Universal_Transverse_Mercator_zones.svg https://upload.wikimedia.org/wikipedia/commons/b/b7/Universa...
    - alanbernstein 6y ago
      That drives me nuts. I don't see an explanation in the article for why there are just six irregular cells in the whole grid. It does mention that it's "in part to accommodate the southern half of the Kingdom of Norway", despite the system having been developed by the US or maybe Germany. Why Norway? Why only Norway?
  - nightcracker 6y ago
    What the person you're responding to did was a very simple form of locality-sensitive hashing. 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.
- mattmanser 6y ago
  Or, if the grids never change, just store the data of the parent grid with the child grid. 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.
read_if_gay_ 6y ago
> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
- m12k 6y ago
  Correct, not all programs suffer from the Halting Problem.
  - arc0 6y ago
    I think that's kind of a malformed sentence. Programs themselves do not suffer or not suffer from the halting problem, it is only a problem when considering the space of all programs.
    - andi999 6y ago
      I also think some programs can suffer from the halting problem. I mentioned above properties of the decimal reprensentation of pi (like is 123456 in pi)
    - domnomnom 6y ago
      It's not malformed, it's just incorrect. Additionally, the halting problem is about provability. That sort of imprecision of language needs qualifiers at least.
- est31 6y ago
  Yeah there are plenty of programs where you can tell whether they terminate or not. The proof that the halting problem is decidable has a self referential component and most programs aren't self referential like this, nor do they make any library calls to halting problem deciders :). I think it's OK to do this simlification in a simple post like this, but important to keep in mind that it's a simplification. 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.
captain_price7 6y ago
I fantasize about coming across optimization opportunities like this in real life.
- topkai22 6y ago
  As a team lead, my project sees them about once a quarter. This is on a project that fundamentally does form based data collection on a limited set of users. 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.
AshamedCaptain 6y ago
I used to know a professor who switched from the hardware department to the software department. His reason? With hardware I can reduce runtime by 10 or 100. With software I can reduce runtime by log(x).
- michaelmior 6y ago
  It's especially powerful when you have someone with a deep knowledge of both hardware and software who can maximally exploit the performance of the hardware taking into account CPU caches, vectorization, etc. that most application programmers don't think about on a daily basis. Daniel Lemire[0] is a great example of someone who does this well. https://lemire.me/blog/ https://lemire.me/blog/
- deleted 6y ago
  [deleted]
dumbfounder 6y ago
Computer Science for the... loss? 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.
- pc86 6y ago
  I'm biased because I studied Poli Sci, I'd like to think I'm a pretty successful software architect and senior developer, and for a long time I had a big chip on my shoulder because I didn't study Comp Sci (and barely graduated college at all if we're being honest). 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.
- arcticbull 6y ago
mlang23 6y ago
Most code is bad code. And if it is not algorithmically bad, there are many other errors lurking in dark corners. 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 :-)
- gridlockd 6y ago
  > ...not really representative for the scientific computing community. I disagree. Source: dude, trust me.
  - Tomminn 6y ago
    Agree, it definitely is representative. 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.
jp0d 6y ago
Nice one. I'm one of those non-CS background person in IT. Although, I'm not a dev, I do write a lot of code in SQL and Python for data analysis. People like me can benefit a lot from understanding algorithms. Especially because we often deal with huge amounts of data. Cheers.
sillysaurusx 6y ago
Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to render. 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 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 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.
- sp332 6y ago
  That's a quadtree, or an octree in 3D.
  - sdbrown 6y ago
    A k-D tree?
dancemethis 6y ago
Sorry, but FTW will always mean "f... the world".
- davidmurdoch 6y ago
  I've never seen it used that way. In WTF and FML, yes, but never in FTW.
  - lmm 6y ago
    In the dim and distant past it was used to mean that. See e.g. https://www.kayfabenews.com/study-majority-of-wrestling-fans-over-40-dont-realize-ftw-means-something-different-nowadays/ https://www.kayfabenews.com/study-majority-of-wrestling-fans...
mynegation 6y ago
Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. 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.
- brilee 6y ago
  I realized the same thing when trying to compute F1-optimized thresholds; scanning through all possible threshold scores is O(n^2) but computing f1 score inline while scanning through the sorted array is O(n). https://www.moderndescartes.com/essays/auc_intuition/ 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
  - Phemist 6y ago
    Interesting! Thanks for the write-up. In the field of Biometrics we often use the library BOB to compute scores like AUC's and EER's, or other measures over stuff like DET curves. 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 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.
gbrits 6y ago
A Geohash (https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash), a (decoding of a) recursive spacing-filling curve, would be much faster still: you literally slash a couple of characters of the tail of the hash to end up with your bigger cell, etc. It does mandate the way in which the grid/globe is subdivided though, which may not be suitable for the stated case.
lanecwagner 6y ago
Trying to get Bootcamp grads to learn CS is like pulling teeth. The worst thing I hear as an employer is, "I dropped out of my CS degree because the last couple years of classes weren't applicable to daily programming". I've started Qvault to try to address the problem... We'll see where it goes. https://app.qvault.io https://app.qvault.io
- moron4hire 6y ago
  My senior year of CS classes may not have been applicable to "daily programming", but are certainly applicable to "monthly programming". 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".
gridlockd 6y ago
The next level is "Google for the win", in which you realize that this particular part of your problem (nearest neighbor search) is so ubiquitous that there is library for it in pretty much any language.
- Tarq0n 6y ago
  For spatial data there's also specialized libraries that do things like geohashing and spatial joins. R, the language he's using, has access to high quality implementations in multiple mature libraries.
  - mlang23 6y ago
    Thanks for pointing at R. I was actually idly wondering what language that is. The <- seemed to point at Haskell, but the parens for application immediately killed that theory. While I have dabbled in many languages, I haven't had a single look at R code yet.
hnaccy 6y ago
I was lucky enough to come upon a similar speedup in some code that was used a fair bit at first job; multiple order of magnitude speed up by applying some data structure knowledge. 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.
cestith 6y ago
Hacking through this and thinking himself so superior because he understands CS just makes the article feel pompous and self-aggrandizing. It's highlighting a personal win with notes about the shorter runtime being a team win. 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.
roter 6y ago
> In climate science we do a lot of downscaling. We take temperature and precipitation readings from a coarse scale Global Climate Model grid and map them to a fine scale local grid. Let’s say the global grid is 50x25 and the local grid is 1000x500. For each grid cell in the local grid, we want to know to which grid cell in the global grid it corresponds. 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.
- Ultimatt 6y ago
  You're not wrong. This entire article is a classic example of Computer Science failure. It's someone who knows program optimisation in the abstract and nothing about the actual target problem from a domain knowledge perspective. They went about optimising bad code as in quality of thought level, rather than actually getting to grips with the true requirement first. Though perhaps a computer science win, but a software engineer fail.
  - mlyle 6y ago
    In a lot of ways, the original implementation makes a lot more sense than this "optimized" solution. Something like the original brute force, compare all the points' distances variant is how I'd be inclined to write one of my unit tests for the grid alignment routines. Trying a few dozen points on a few dozen grid variants is a way to make sure I've not completely screwed up math-- whether off by one, rounding problems, etc, while applying sanity checks on the overall grid code base. 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.
    - 6y ago
ekzy 6y ago
> But when it comes to developing software, I get the distinct impression that people think, “Hey, how hard could this be?! We just write down a few instructions about what we want the computer to do, hit the execute button and the, ‘Blamo!’, we get our answer!” 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.
- sgillen 6y ago
  In my experience with scientists/mathematicians a lot of them look down on software as an easy and unimportant detail of their work. Certainly not all of course.
deleted 6y ago
[deleted]
PaulHoule 6y ago
Then there is the time that I wrote a program that would have taken 100 years to run and found a (perfectly useful) approximation I could calculate in 20 minutes, for a 2.6 million (x) speedup. Even counting 16 hours of programmer time that is a 55,000 (x) speedup.
- Jtsummers 6y ago
  My most significant optimization was showing that the thing they wanted computed was not possible. Not just "will keep running and finish soon after the universe expires", but actually impossible to compute (in the general case, which was their case, if they restricted the inputs it was feasible). Apparently they had no mathematicians evaluating the requirements. The guy who brought the problem to me had been working on it off and on for months. So I saved him from having to think about it for the rest of his time maintaining that system.
  - PaulHoule 6y ago
    Yep, that's the heart of Computer Science.
netmonk 6y ago
This reminds me an old shell script used to housecleaning, which was performing first "for" loop based on an sql select to perform another "for" loop based on another sql select and itering on returned items from the first request. 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.
innagadadavida 6y ago
> global grid is 50x25 and the local grid is 1000x500. For each grid cell in the local grid, we want to know to which grid cell in the global grid it corresponds Isn’t this just a simple quantization? (Lat/20,Lon/20) should do it?
foota 6y ago
It sound like this performed well enough, but it seems like a more efficient solution would be to crawl the grid from left to right and at each point only search the neighbors of the previous closest grid from the larger grid, assuming that a local grid cell will never be have a height or width greater than a global cell. This would be linear in the number of local grid cells.
CogentHedgehog 6y ago
That's a good speedup but why are they not using locality-sensitive hashing? Or doing some basic math to convert X and Y to binned indices for a lookup table -- you can easily precompute values for a few million cells and hold them in memory. If the lookup table is small enough it would even fit in a single CPU cache, and lookup would be nearly instant. Both of these approaches provide O(1) lookup for grid cells rather than O(log n). 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.
deleted 6y ago
[deleted]
jariel 6y ago
Software is not about writing code or optimizing algorithms. 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.
thenewwazoo 6y ago
I read this and chewed on it for a while, and I think it points to a deeper problem with how we teach computer programming. While, yes, computer scientists need to know about binary search vs linear search and how to iterate through collections, I propose that most programmers do not. Lots of people do programming that aren't, and shouldn't aspire to be, computer scientists (because they have other, more important, shit to do). 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.
noisy_boy 6y ago
I remember many years ago I came upon a giant shell script doing some data processing (data not even that large, maybe few GBs) that took close to 25 mins (mainly due to unnecessary I/O due to tons of temp file creation) - written by "developers". I re-wrote it in Perl and it completed in less than a minute (and it wasn't even optimized because I was a non-CS newbie who was just learning Perl). I even setup a cronjob to compare the output from both and email to the concerned folks. It was never adopted because I was new and Perl was considered "too-risky".
- ignoramous 6y ago
  > It was never adopted because I was new and Perl was considered "too-risky". What's not to love about bureaucracy?
bovermyer 6y ago
Related: if I had a bit of open source code that I wrote that I was convinced was poorly optimized, how would I go about getting someone to take a look at it and help me improve it?
chrismorgan 6y ago
Point of document implementation: please don’t use <script type="math/tex">…</script> for equations, or else the equations are simply missing in environments where MathJax doesn’t run (e.g. JS disabled, text mode browser, or JS fails to load—all up, it’s more common than you realise). Use a form of markup that will fail visible rather than fail invisible. TeX mathematics notation is far better than a void. 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.
- thangalin 6y ago
  > please don’t use <script type="math/tex">…</script> for equations 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 https://github.com/DaveJarvis/keenwrite [1]: https://github.com/DaveJarvis/JMathTeX https://github.com/DaveJarvis/JMathTeX [2]: http://jmathtex.sourceforge.net http://jmathtex.sourceforge.net
- deleted 6y ago
  [deleted]
- 6y ago
lkbm 6y ago
I thought this was going to be "How to Speed up a Python Program 114,000 times"[0]. It's an hour-long talk, but quite enjoyable. 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. [0] https://www.youtube.com/watch?v=e08kOj2kISU https://www.youtube.com/watch?v=e08kOj2kISU
acaloiar 6y ago
The optimizations here are uncannily similar to the ones I performed for an algorithm we developed for application in bioinformatics. It began with a statistics post-doc who knew some R. It was very brute-force. https://arxiv.org/pdf/1509.00549.pdf 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.
fzimmermann 6y ago
I see some issues with the problem description and the solution: The author assumes the problem can be split in x and y independently. Firstly, this has not to be true for all projections and grids. Secondly, the solution minimizes Manhattan distance in lat/long., not actual distance (you can construct points where the minima are different). This will not matter if you can approximate both grids as regular (equidistant and rectangular grids). But in that case, you could easily calculate for each point in one grid the corrosponding point in the other grid by scaling and rounding...
hinkley 6y ago
I think I've related this before, but one of my favorite bug reports, and the most interesting Order of Complexity I've ever documented was one I filed for TogetherJ. 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.
dang 6y ago
All: some comments are finding fault with the article and the author in ways that aren't in the intended spirit of HN. When someone made a mistake or didn't find the best answer, it's great to explain why and supply correct information, but please avoid mixing in putdowns, and if your comment is just a putdown, please don't post. 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. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
ultra_nick 6y ago
That sounds a lot like the "Find the point nearest to this one on a 2s plane" interview question. Neat.
blisterpeanuts 6y ago
Years ago, I was a contract programmer at a large university, working on Perl reporting scripts for the library system. 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.
thamer 6y ago
Recently I got a speedup that was literally 6-7 orders of magnitude by changing a few characters in a regex, which made it match its input in linear time instead of O(k^N) due to a crazy backtrack. 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.
- vecter 6y ago
  What was the actual change?
  - thamer 6y ago
    It was a long regex, made of multiple parts with two OR'd together that looked very similar except for the last few characters. These two parts were trying to match a structured format, think of something like a domain name for example; it's not just [a-z0-9.-]+ since you can't have the - or . at the start or at the end, and maybe the end part has a limited length (say you want to match only short TLDs). I can't really say what these strings were but they had these sorts of restrictions and a range that was a bit larger than what domains can use (like capital letters). 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})? Actually kind of like that, but with multiple ()? and (){N} wrapping the different layers. 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 (again, where STRUCTURED is replaced with the whole long regex from above). Meaning that the regex engine, as it consumes the first characters that potentially match the structured string, can't tell whether it's in the left or right branch of this OR until it reaches either the `.foo` or `.bar` suffix. The change I made was simply to match it with: STRUCTURED(\.foo|\.bar) In this case the engine can consume each character of the input and make its way through STRUCTURED without having to maintain k branches per character (given as k=2 in the example above but it was much more than that). I hope the general idea still comes through despite the simplification and required obfuscation.
rladd 6y ago
We can easily reduce this to effectively time=0 which is an infinite speedup. 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).
tumblewit 6y ago
In machine learning for trading class, a python for loop code was turned into numpy array where the code went from something like over 4 minutes to a few milliseconds. Its astounding how much you can improve on code just by a vastly better algorithm. Note: I know numpy is C and faster than python but that was not the point. The point was using vectors vs bruteforce.
ncmncm 6y ago
I don't know whose law says something like, "The amount of optimization left to do is proportional to the improvement you got on the last round". 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.

424 points by signa11 6y ago

salmon 6y ago

I find optimization porn like this to be so satisfying.

Frost1x 6y ago
The only issue I have with optimization porn is that it often handwaves away the time and thought that went into finding clever optimizations. In some cases it's clear how a problem can be better optimized. In many cases, it's not so clear. It takes someone experienced in development, an understanding of software and computational complexity, and the insight to see optimization opportunities or have used them before. 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.
CyberDildonics 6y ago
Step 1: start with something grossly, ridiculously inefficient. Step 2: Brag about your speed up

m4r35n357 6y ago

You could get arbitrarily large improvements by starting with even worse code ;)

andi999 6y ago
Exactly. I like the enthusiasm of the author; but the self-congratulatory attitude doesnt go down very well if you should actually be ashamed of the first version. I mean it is only a few inches from:"you know in the old days we had to flip through the telephone directory from front to end to find a name. But you know what: it is actually a sorted list, so we applied a binary search algorithm and are 14000x faster. Tl;dr CS for the win"
- theamk 6y ago
  You'd be surprised how often "flip through the telephone directory" thing comes out in the real projects. 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.
  - andi999 6y ago
    I agree, and I also think this should be the first solution since it is obviously correct so you can test your faster algo later against this (at least in the post the invariants of the dataset are not spelled out exactly, and we know premature optimization..). But I do not think you should expect a trophy when later fixing it (when profiling shows it is a problem).

nightcracker 6y ago

If your grid is well-behaved enough you can go a lot faster still using locality sensitive hashing.

Aeolun 6y ago

I’m not sure why we can’t map a position in a big grid to a position in a small grid by doing: X = Math.floor(bigX / bigXMax * smallXMax) Is there some magic here I’m not seeing?

rocqua 6y ago
Grid doesn't need to be regular
- etimberg 6y ago
  As an example, see this image of the UTM zones and look at the zones labelled in red. https://upload.wikimedia.org/wikipedia/commons/b/b7/Universal_Transverse_Mercator_zones.svg https://upload.wikimedia.org/wikipedia/commons/b/b7/Universa...
  - alanbernstein 6y ago
    That drives me nuts. I don't see an explanation in the article for why there are just six irregular cells in the whole grid. It does mention that it's "in part to accommodate the southern half of the Kingdom of Norway", despite the system having been developed by the US or maybe Germany. Why Norway? Why only Norway?
- nightcracker 6y ago
  What the person you're responding to did was a very simple form of locality-sensitive hashing. 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.
mattmanser 6y ago
Or, if the grids never change, just store the data of the parent grid with the child grid. 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.

read_if_gay_ 6y ago

> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?

m12k 6y ago
Correct, not all programs suffer from the Halting Problem.
- arc0 6y ago
  I think that's kind of a malformed sentence. Programs themselves do not suffer or not suffer from the halting problem, it is only a problem when considering the space of all programs.
  - andi999 6y ago
    I also think some programs can suffer from the halting problem. I mentioned above properties of the decimal reprensentation of pi (like is 123456 in pi)
  - domnomnom 6y ago
    It's not malformed, it's just incorrect. Additionally, the halting problem is about provability. That sort of imprecision of language needs qualifiers at least.
est31 6y ago
Yeah there are plenty of programs where you can tell whether they terminate or not. The proof that the halting problem is decidable has a self referential component and most programs aren't self referential like this, nor do they make any library calls to halting problem deciders :). I think it's OK to do this simlification in a simple post like this, but important to keep in mind that it's a simplification. 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.

captain_price7 6y ago

I fantasize about coming across optimization opportunities like this in real life.

topkai22 6y ago
As a team lead, my project sees them about once a quarter. This is on a project that fundamentally does form based data collection on a limited set of users. 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.

AshamedCaptain 6y ago

I used to know a professor who switched from the hardware department to the software department. His reason? With hardware I can reduce runtime by 10 or 100. With software I can reduce runtime by log(x).

michaelmior 6y ago
It's especially powerful when you have someone with a deep knowledge of both hardware and software who can maximally exploit the performance of the hardware taking into account CPU caches, vectorization, etc. that most application programmers don't think about on a daily basis. Daniel Lemire[0] is a great example of someone who does this well. https://lemire.me/blog/ https://lemire.me/blog/
deleted 6y ago
[deleted]

dumbfounder 6y ago

Computer Science for the... loss? 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.

pc86 6y ago
I'm biased because I studied Poli Sci, I'd like to think I'm a pretty successful software architect and senior developer, and for a long time I had a big chip on my shoulder because I didn't study Comp Sci (and barely graduated college at all if we're being honest). 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.
arcticbull 6y ago

mlang23 6y ago

Most code is bad code. And if it is not algorithmically bad, there are many other errors lurking in dark corners. 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 :-)

gridlockd 6y ago
> ...not really representative for the scientific computing community. I disagree. Source: dude, trust me.
- Tomminn 6y ago
  Agree, it definitely is representative. 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.

jp0d 6y ago

Nice one. I'm one of those non-CS background person in IT. Although, I'm not a dev, I do write a lot of code in SQL and Python for data analysis. People like me can benefit a lot from understanding algorithms. Especially because we often deal with huge amounts of data. Cheers.

sillysaurusx 6y ago

Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to render. 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 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 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.

sp332 6y ago
That's a quadtree, or an octree in 3D.
- sdbrown 6y ago
  A k-D tree?

dancemethis 6y ago

Sorry, but FTW will always mean "f... the world".

davidmurdoch 6y ago
I've never seen it used that way. In WTF and FML, yes, but never in FTW.
- lmm 6y ago
  In the dim and distant past it was used to mean that. See e.g. https://www.kayfabenews.com/study-majority-of-wrestling-fans-over-40-dont-realize-ftw-means-something-different-nowadays/ https://www.kayfabenews.com/study-majority-of-wrestling-fans...

mynegation 6y ago

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. 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.

brilee 6y ago
I realized the same thing when trying to compute F1-optimized thresholds; scanning through all possible threshold scores is O(n^2) but computing f1 score inline while scanning through the sorted array is O(n). https://www.moderndescartes.com/essays/auc_intuition/ 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
- Phemist 6y ago
  Interesting! Thanks for the write-up. In the field of Biometrics we often use the library BOB to compute scores like AUC's and EER's, or other measures over stuff like DET curves. 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 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.

gbrits 6y ago

A Geohash (https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash), a (decoding of a) recursive spacing-filling curve, would be much faster still: you literally slash a couple of characters of the tail of the hash to end up with your bigger cell, etc. It does mandate the way in which the grid/globe is subdivided though, which may not be suitable for the stated case.

lanecwagner 6y ago

Trying to get Bootcamp grads to learn CS is like pulling teeth. The worst thing I hear as an employer is, "I dropped out of my CS degree because the last couple years of classes weren't applicable to daily programming". I've started Qvault to try to address the problem... We'll see where it goes. https://app.qvault.io https://app.qvault.io

moron4hire 6y ago
My senior year of CS classes may not have been applicable to "daily programming", but are certainly applicable to "monthly programming". 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".

gridlockd 6y ago

The next level is "Google for the win", in which you realize that this particular part of your problem (nearest neighbor search) is so ubiquitous that there is library for it in pretty much any language.

Tarq0n 6y ago
For spatial data there's also specialized libraries that do things like geohashing and spatial joins. R, the language he's using, has access to high quality implementations in multiple mature libraries.
- mlang23 6y ago
  Thanks for pointing at R. I was actually idly wondering what language that is. The <- seemed to point at Haskell, but the parens for application immediately killed that theory. While I have dabbled in many languages, I haven't had a single look at R code yet.

hnaccy 6y ago

I was lucky enough to come upon a similar speedup in some code that was used a fair bit at first job; multiple order of magnitude speed up by applying some data structure knowledge. 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.

cestith 6y ago

Hacking through this and thinking himself so superior because he understands CS just makes the article feel pompous and self-aggrandizing. It's highlighting a personal win with notes about the shorter runtime being a team win. 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.

roter 6y ago

> In climate science we do a lot of downscaling. We take temperature and precipitation readings from a coarse scale Global Climate Model grid and map them to a fine scale local grid. Let’s say the global grid is 50x25 and the local grid is 1000x500. For each grid cell in the local grid, we want to know to which grid cell in the global grid it corresponds. 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.

Ultimatt 6y ago
You're not wrong. This entire article is a classic example of Computer Science failure. It's someone who knows program optimisation in the abstract and nothing about the actual target problem from a domain knowledge perspective. They went about optimising bad code as in quality of thought level, rather than actually getting to grips with the true requirement first. Though perhaps a computer science win, but a software engineer fail.
- mlyle 6y ago
  In a lot of ways, the original implementation makes a lot more sense than this "optimized" solution. Something like the original brute force, compare all the points' distances variant is how I'd be inclined to write one of my unit tests for the grid alignment routines. Trying a few dozen points on a few dozen grid variants is a way to make sure I've not completely screwed up math-- whether off by one, rounding problems, etc, while applying sanity checks on the overall grid code base. 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.
  - 6y ago

ekzy 6y ago

> But when it comes to developing software, I get the distinct impression that people think, “Hey, how hard could this be?! We just write down a few instructions about what we want the computer to do, hit the execute button and the, ‘Blamo!’, we get our answer!” 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.

sgillen 6y ago
In my experience with scientists/mathematicians a lot of them look down on software as an easy and unimportant detail of their work. Certainly not all of course.

deleted 6y ago

[deleted]

PaulHoule 6y ago

Then there is the time that I wrote a program that would have taken 100 years to run and found a (perfectly useful) approximation I could calculate in 20 minutes, for a 2.6 million (x) speedup. Even counting 16 hours of programmer time that is a 55,000 (x) speedup.

Jtsummers 6y ago
My most significant optimization was showing that the thing they wanted computed was not possible. Not just "will keep running and finish soon after the universe expires", but actually impossible to compute (in the general case, which was their case, if they restricted the inputs it was feasible). Apparently they had no mathematicians evaluating the requirements. The guy who brought the problem to me had been working on it off and on for months. So I saved him from having to think about it for the rest of his time maintaining that system.
- PaulHoule 6y ago
  Yep, that's the heart of Computer Science.

netmonk 6y ago

This reminds me an old shell script used to housecleaning, which was performing first "for" loop based on an sql select to perform another "for" loop based on another sql select and itering on returned items from the first request. 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.

innagadadavida 6y ago

> global grid is 50x25 and the local grid is 1000x500. For each grid cell in the local grid, we want to know to which grid cell in the global grid it corresponds Isn’t this just a simple quantization? (Lat/20,Lon/20) should do it?

foota 6y ago

It sound like this performed well enough, but it seems like a more efficient solution would be to crawl the grid from left to right and at each point only search the neighbors of the previous closest grid from the larger grid, assuming that a local grid cell will never be have a height or width greater than a global cell. This would be linear in the number of local grid cells.

CogentHedgehog 6y ago

That's a good speedup but why are they not using locality-sensitive hashing? Or doing some basic math to convert X and Y to binned indices for a lookup table -- you can easily precompute values for a few million cells and hold them in memory. If the lookup table is small enough it would even fit in a single CPU cache, and lookup would be nearly instant. Both of these approaches provide O(1) lookup for grid cells rather than O(log n). 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.

deleted 6y ago

[deleted]

jariel 6y ago

Software is not about writing code or optimizing algorithms. 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.

thenewwazoo 6y ago

I read this and chewed on it for a while, and I think it points to a deeper problem with how we teach computer programming. While, yes, computer scientists need to know about binary search vs linear search and how to iterate through collections, I propose that most programmers do not. Lots of people do programming that aren't, and shouldn't aspire to be, computer scientists (because they have other, more important, shit to do). 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.

noisy_boy 6y ago

I remember many years ago I came upon a giant shell script doing some data processing (data not even that large, maybe few GBs) that took close to 25 mins (mainly due to unnecessary I/O due to tons of temp file creation) - written by "developers". I re-wrote it in Perl and it completed in less than a minute (and it wasn't even optimized because I was a non-CS newbie who was just learning Perl). I even setup a cronjob to compare the output from both and email to the concerned folks. It was never adopted because I was new and Perl was considered "too-risky".

ignoramous 6y ago
> It was never adopted because I was new and Perl was considered "too-risky". What's not to love about bureaucracy?

bovermyer 6y ago

Related: if I had a bit of open source code that I wrote that I was convinced was poorly optimized, how would I go about getting someone to take a look at it and help me improve it?

chrismorgan 6y ago

Point of document implementation: please don’t use <script type="math/tex">…</script> for equations, or else the equations are simply missing in environments where MathJax doesn’t run (e.g. JS disabled, text mode browser, or JS fails to load—all up, it’s more common than you realise). Use a form of markup that will fail visible rather than fail invisible. TeX mathematics notation is far better than a void. 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.

thangalin 6y ago
> please don’t use <script type="math/tex">…</script> for equations 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 https://github.com/DaveJarvis/keenwrite [1]: https://github.com/DaveJarvis/JMathTeX https://github.com/DaveJarvis/JMathTeX [2]: http://jmathtex.sourceforge.net http://jmathtex.sourceforge.net
deleted 6y ago
[deleted]
6y ago

lkbm 6y ago

I thought this was going to be "How to Speed up a Python Program 114,000 times"[0]. It's an hour-long talk, but quite enjoyable. 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. [0] https://www.youtube.com/watch?v=e08kOj2kISU https://www.youtube.com/watch?v=e08kOj2kISU

acaloiar 6y ago

The optimizations here are uncannily similar to the ones I performed for an algorithm we developed for application in bioinformatics. It began with a statistics post-doc who knew some R. It was very brute-force. https://arxiv.org/pdf/1509.00549.pdf 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.

fzimmermann 6y ago

I see some issues with the problem description and the solution: The author assumes the problem can be split in x and y independently. Firstly, this has not to be true for all projections and grids. Secondly, the solution minimizes Manhattan distance in lat/long., not actual distance (you can construct points where the minima are different). This will not matter if you can approximate both grids as regular (equidistant and rectangular grids). But in that case, you could easily calculate for each point in one grid the corrosponding point in the other grid by scaling and rounding...

hinkley 6y ago

I think I've related this before, but one of my favorite bug reports, and the most interesting Order of Complexity I've ever documented was one I filed for TogetherJ. 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.

dang 6y ago

All: some comments are finding fault with the article and the author in ways that aren't in the intended spirit of HN. When someone made a mistake or didn't find the best answer, it's great to explain why and supply correct information, but please avoid mixing in putdowns, and if your comment is just a putdown, please don't post. 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. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html

ultra_nick 6y ago

That sounds a lot like the "Find the point nearest to this one on a 2s plane" interview question. Neat.

blisterpeanuts 6y ago

Years ago, I was a contract programmer at a large university, working on Perl reporting scripts for the library system. 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.

thamer 6y ago

Recently I got a speedup that was literally 6-7 orders of magnitude by changing a few characters in a regex, which made it match its input in linear time instead of O(k^N) due to a crazy backtrack. 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.

vecter 6y ago
What was the actual change?
- thamer 6y ago
  It was a long regex, made of multiple parts with two OR'd together that looked very similar except for the last few characters. These two parts were trying to match a structured format, think of something like a domain name for example; it's not just [a-z0-9.-]+ since you can't have the - or . at the start or at the end, and maybe the end part has a limited length (say you want to match only short TLDs). I can't really say what these strings were but they had these sorts of restrictions and a range that was a bit larger than what domains can use (like capital letters). 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})? Actually kind of like that, but with multiple ()? and (){N} wrapping the different layers. 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 (again, where STRUCTURED is replaced with the whole long regex from above). Meaning that the regex engine, as it consumes the first characters that potentially match the structured string, can't tell whether it's in the left or right branch of this OR until it reaches either the `.foo` or `.bar` suffix. The change I made was simply to match it with: STRUCTURED(\.foo|\.bar) In this case the engine can consume each character of the input and make its way through STRUCTURED without having to maintain k branches per character (given as k=2 in the example above but it was much more than that). I hope the general idea still comes through despite the simplification and required obfuscation.

rladd 6y ago

We can easily reduce this to effectively time=0 which is an infinite speedup. 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).

tumblewit 6y ago

In machine learning for trading class, a python for loop code was turned into numpy array where the code went from something like over 4 minutes to a few milliseconds. Its astounding how much you can improve on code just by a vastly better algorithm. Note: I know numpy is C and faster than python but that was not the point. The point was using vectors vs bruteforce.

ncmncm 6y ago

I don't know whose law says something like, "The amount of optimization left to do is proportional to the improvement you got on the last round". 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.