Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

14,000x Speedup (2015)

james.hiebert.name

Post reply on HN
Print view View original

161–170 of 237 posts

Re: 14,000x Speedup (2015)

#161

Post by ath92 »

andruby wrote: post #120
mynegation wrote: post #109

Earlier quoted context omitted.

At the time, yes, but I do not have those numbers anymore. Trying my best to remember - I would estimate that the speedup of 360 / 4 = 90x is approximately: 4x multithreading (it was pretty linear speedup), 7x the algorithm and 3x the memory inefficiencies. EDIT: fixed my math, thank you andruby

Sorry to correct your math here, but going from 6 hours (6*60=360 minutes) to 4 minutes is a 90x improvement, not 900x.

Interestingly, a speedup of 2 orders of magnitude seems to be about what you'd expect if you only apply the algorithmic optimization (going from N^2 to Nlog(N) with N being in the range of a few thousand, like OP said)

Re: 14,000x Speedup (2015)

#162

Post by Marazan »

roter wrote: post #65

> 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…

Yeah, I genuinely don't get the problem statement. As you say as stated the solution to the problem as stated is a single line piece of basic math.

I can o lump resume the problem is badly described to miss some subtly.

I hope.

Re: 14,000x Speedup (2015)

#163

Post by [deleted] »

danielvf wrote: post #140
roter wrote: post #65

> 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…

I've upvoted this. Even the "optimized" solution here is so horrible that I almost thought the article was satire when I first read it. Maybe it is. 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 h…

[deleted]

Re: 14,000x Speedup (2015)

#164

Post by mlyle »

Ultimatt wrote: post #103
roter wrote: post #65

> 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…

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 softwar…

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.

Re: 14,000x Speedup (2015)

#166

Post by dang »

danielvf wrote: post #140
roter wrote: post #65

> 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…

I've upvoted this. Even the "optimized" solution here is so horrible that I almost thought the article was satire when I first read it. Maybe it is. 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 h…

Please post your improved and correct perspectives without name-calling. Doing otherwise makes the community worse, even if you're right.

https://news.ycombinator.com/newsguidelines.html

Re: 14,000x Speedup (2015)

#167

Post by dang »

Ultimatt wrote: post #103
roter wrote: post #65

> 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…

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 softwar…

Please don't post supercilious dismissals of other people or their work, even if they made a mistake and/or were supercilious in their own right. It just contributes to making this a nasty place.

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.

https://news.ycombinator.com/newsguidelines.html

Re: 14,000x Speedup (2015)

#168

Post by tetha »

8ytecoder wrote: post #134
mynegation wrote: post #39

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…

This is at the very least a clever and involved optimization. Let me tell you the story of my similar 10h to 10min fix. We had this cronjob that was supposed to run every hour, detect all changes to the customers and related table and sync with the marketing saas tool. It was written in Rails and took 10 mins at first. As we grew the time taken by this job also grew linearly. To a point where it took 10 hours and we…

This is when being the guy knowing a few database tricks is fun.

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.

Re: 14,000x Speedup (2015)

#169

Post by qayxc »

User23 wrote: post #139
qayxc wrote: post #68

Earlier quoted context omitted.

I'd argue that not knowing the language you're working with is a problem that's not exclusive to C++. 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...

C++ has a famously complex standard though, to the point that, last I checked, there are no fully standards conforming C++ compilers. I know one member of the standards body and he is an excellent software engineer, a subject matter expert, and just wicked smart too, and he still confesses he doesn't really understand C++. There's a reason why Google doesn't actually have C++ as a supported language, but rather a cur…

I concur, but using and knowing a reasonable subset is enough to be productive.

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...

Re: 14,000x Speedup (2015)

#170

Post by andi999 »

formerly_proven wrote: post #110
neves wrote: post #58

Earlier quoted context omitted.

This is a usual problem with C++ and why I hate it. There's a lot going on under the hoods, and you must be really knowledgeable of the language to prevent stupid things. Following some idioms you can really avoid it, but it is useless since your coworkers will fall into the language traps.

There's very little going on under the hood with C++, if it even has a hood.

Vtable and vtable pointer is under the hood.
Post reply on HN