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

191–200 of 237 posts

Re: 14,000x Speedup (2015)

#191

Post by sdenton4 »

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…

Meanwhile, there's a perception that machine learning is hardware-bound for speed increases, which just isn't true.

I work on a pretty heavy ML system, which a year ago took about a month to 'fully' train. Today we're down to 25 hours training time using the same hardware, based mostly on improvements to the model. The improvements are coming from a combination of signal processing tricks and tricksy model changes. Inference is similarly much faster, too...

Re: 14,000x Speedup (2015)

#192

Post by aaronblohowiak »

dang wrote: post #189
kolbe wrote: post #188

Earlier quoted context omitted.

This was written in 2015. What's worse logic: his code or HN thinking that shit talking him five years later in a forum we don't even know if he sees is constructive?

Obviously I agree, but please don't add to the problem by dumping more nastiness into the thread. Note this guideline also: " Please don't sneer, including at the rest of the community. " It's worth remembering that HN is a statistical cloud of posts, not a person, and so can't think anything. https://news.ycombinator.com/newsguidelines.html

you are a singular individual, dang. thank you for what you do for HN

Re: 14,000x Speedup (2015)

#193

Post by djmips »

sillysaurusx wrote: post #27

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

And I would point out that some of the best Game Devs who make frighteningly fast code don't have CS degrees and are sometimes fixing up after people that do.

Re: 14,000x Speedup (2015)

#194

Post by jjuhl »

colejohnson66 wrote: post #48
umvi wrote: post #38

Earlier quoted context omitted.

People obsessed with big O are super annoying. To them O(1) trumps O(n) even if it's a tiny little set of data where clearly the latter is actually faster (stopwatch time).

It’s good to understand what the “Big O” for your algorithm is, but, yes, people who obsess over it are annoying. If I know I’m processing 100 items very rarely,[a] does it matter if my quick and dirty sorting (no pun intended) algorithm is bubble or quick sort? They both complete in a fraction of a second, and the user (generally) isn’t going to notice a difference between a single frame update delta or two. [a] Key…

I once worked on an application where we (in one common situation) had to sort an array that was always is for large random datasets). But, given the actual data in question, no-one could actually make any other sort perform faster.

Know your data.

Re: 14,000x Speedup (2015)

#195

Post by amenod »

hinkley wrote: post #144
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…

I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…

> On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs).

I assume you mean that these improvements would not be visible on a flame chart because they were not in perf output? (assuming one was built from the other?)

Flame graph by definition shows where the time is spent and is just a (great, imho) visualization of this data. Some people seem to have a beef with it, but their issues are invariably tied to the way the original data is gathered.

Re: 14,000x Speedup (2015)

#196

Post by not2b »

andi999 wrote: post #170
formerly_proven wrote: post #110

Earlier quoted context omitted.

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.

Yes, but any C++ programmer who expects to be hired will have a good understanding of vtables and vtable pointers. They are a lot less tricky to reason about than, say, thunks in Haskell.

Re: 14,000x Speedup (2015)

#197

Post by neves »

vidarh wrote: post #111
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.

Knowing if you're copying or passing references is essential to understanding most languages that supports both. It's scary how many people are unaware of it, though. Not nearly as dramatic as the example above, but I once cut the time spent on page generation for a commercial CMS by 30% my first day in a new job by realising they did excessive new allocation of strings instead of concatenation (which will amortise t…

I agree, but a simple automatically defined copy constructor can spread havoc in a code base.

Re: 14,000x Speedup (2015)

#198

Post by jansan »

CyberDildonics wrote: post #183
jansan wrote: post #141

Earlier quoted context omitted.

No, it works because you keep an array of "active" elements during the sweep. Let's say you sweep from left to right over the elements sorted by their left bounds. For each element you encounter you check if it collides with any of the active elements. While doing so, you check if the active element's right bounds is left of the current sweep line. If so, it cannot collide with any of the remaining elements, so you c…

What you described is what I said. A spatial acceleration structure is meant to skip as many comparisons as possible. What you are talking about is trading less sorting and more comparisons during the queries.

Sorry, I misunderstood the "brute force" part of your comment. You are right, for the active elements the standard implementation uses a brute force on the active elements. I had to implement sort-and-sweep to handle one specific performance problem that took 45 seconds to compute. With the simple sort-and-sweep this went down to 100ms. I also tried sorting the active elements along the secondary axis, but at least in our case this did not yield in any further performance improvements. This probably depends a lot on how many elements there are in the active list.

Re: 14,000x Speedup (2015)

#199

Post by danielvf »

dang wrote: post #166
danielvf wrote: post #140

Earlier quoted context omitted.

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

My apologies. While I don't see the name-calling towards an individual, my previous post did mention possible bad faith, and I would not been glad to have my post written about my code. I also slightly misunderstood what the author's code was doing. I can see how it is not conducive to helpful discussion.

The author optimized their code in a way that was fast enough, and fast enough to massively change the entire business process around their code. It's very commendable. Further optimizations may have not been worth it.

Re: 14,000x Speedup (2015)

#200

Post by ghusbands »

mynegation wrote: post #148
mumblemumble wrote: post #81

Earlier quoted context omitted.

makes me think of https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/

Ha! Great story, thank you! Clearly shows that computational complexity by itself is not very useful without knowing the assumptions. It is one thing to see substring search and immediately pattern match it to something from CS course like Boyer-Moore or Knuth-Morris-Pratt, but these algorithms require pre-processing that makes sense only if you know you are going to search for the same pattern repeatedly. Pure libra…

> pre-processing that makes sense only if you know you are going to search for the same pattern repeatedly

The pre-processing is typically worth it if you're searching through a large string, even just once.

Post reply on HN