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

141–150 of 237 posts

Re: 14,000x Speedup (2015)

#141

Post by jansan »

CyberDildonics wrote: post #80
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…

If you sort bounding boxes in only one dimension by their min values you still have to brute force test their max values and their other dimensions unless you make a secondary space partition or acceleration structure.

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 can remove it from the active elements. This way the number of active elements usually stays small and you have to check each element only against few other elements.

Re: 14,000x Speedup (2015)

#142

Post by mesarvagya »

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…

Sounds like classic n+1 problem

Re: 14,000x Speedup (2015)

#143

Post by lkbm »

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

Re: 14,000x Speedup (2015)

#144

Post by hinkley »

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 diffuse - they're literally everywhere, and they don't always show up on a flame graph. On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs).

C is particularly a bigger issue once you consider Amdahl's law. A 20% slowdown in a linear part of the code can show up as a second-for-second slowdown in response times, while a search algorithm that's only a small part of an overall process, or parallelized, you can make it 10 times faster and might only see a 2% improvement in response times. If you avoid allocating more servers, for a new feature, nobody celebrates your achievement. You have to do it wrong the first time for anyone to notice you.

Re: 14,000x Speedup (2015)

#145

Post by mlang23 »

Tarq0n wrote: post #91
gridlockd wrote: post #45

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.

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.

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.

Re: 14,000x Speedup (2015)

#146

Post by antisthenes »

mumblemumble wrote: post #81
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…

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

That was a great read for someone who's used VBA to solve business cases, including InStr.

Anecdata, but most of my strings were indeed short (searching for manufacturer SKUs inside arrays of other SKUs).

Re: 14,000x Speedup (2015)

#147

Post by acaloiar »

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

Re: 14,000x Speedup (2015)

#148

Post by mynegation »

mumblemumble wrote: post #81
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…

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 library function cannot make that assumption, and REPNE instruction is just an icing on a cake.

Re: 14,000x Speedup (2015)

#149

Post by kadoban »

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…

I'd argue that none of that is the hardest part of programming, or at least what I'd focus on in terms of what comes up the most and what effects users and developers and suits the most.

Judging by those, the most important hard parts are around planning and estimating work, and correctly understanding when those make no sense, and in validating code for correctness, especially over time.

If we ignore importance and just go with what's the hardest single task: naming things.

Re: 14,000x Speedup (2015)

#150

Post by WoodenChair »

lmilcin wrote: post #56
dumbfounder wrote: post #16

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…

So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product that would fit all requirements I decided to write one. Now, you can imagine smart algorithms, trees, hashes... Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all…

It's a great anecdote that shows why we shouldn't ONLY worry about the CS side, but it doesn't mean the system wouldn't have been even more robust/faster/more scalable using better data structures/algorithms. Just because doing the simplest darn thing gets the job done, doesn't mean it's the best way to do it.

Obviously you chose this solution because it made the most sense given your constraints (time/money/knowledge/microcontroller limitations). But that doesn't mean it was an optimal solution nor that with slightly more time/money/knowledge a significantly better solution couldn't have been found.

Post reply on HN