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

71–80 of 237 posts

Re: 14,000x Speedup (2015)

#71

Post by bufferoverflow »

neves wrote: post #58
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 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.

What he described has nothing to do with C++, but with the inefficient algorithm that was chosen.

Re: 14,000x Speedup (2015)

#72

Post by qsort »

m12k wrote: post #35
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…

Computer Science is just academic/theoretical programming. While having a relevant education usually beats not having one, real-world experience usually beats theoretical knowledge when it comes to achieving real-world gains. E.g. if I want something computed as quickly as possible I'm probably better off asking an average game engine programmer than an average CS professor, since they'll optimize for cache efficienc…

As someone with CS background but no experience in academia, this is true but only up to a point. Optimizations like cache efficiency and branch predictions are important and often trump big O considerations, but are mostly engine-level issues. If you are normalizing for the average programmer, the #1 reason why their program is slow is that they're using the wrong algorithm (often implicitly with e.g. library functions or database queries). If anything I'd like more people to be aware of how to reason in big O terms rather than less.

Re: 14,000x Speedup (2015)

#73

Post by commandlinefan »

read_if_gay_ wrote: post #7

> 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"?

> Maybe replace "your" with "any given"?

I'd be more inclined to replace it with "any non-trivial" in this case.

Re: 14,000x Speedup (2015)

#74

Post by TYMorningCoffee »

lmm wrote: post #59
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…

So did you measure how much of the speed improvement came from your careful memory copying tuning and how much came from the algorithmic change?

Yeah. The commenter only gave the numbers when both the constant factor and the improved algorithm were applied.

It would be interesting to see them applied separately. The commenters claim that both are important has not been shown by his example yet.

However the results are impressive. Great job with the solution.

Re: 14,000x Speedup (2015)

#75

Post by dharmon »

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…

The second algorithm you are thinking of is probably what is known as "sort-and-sweep". Basically each object takes up an interval along each axis, so a necessary condition for collisions between two objects is that the intersection of the intervals along each axis are non-empty. (which means if there is no overlap of intervals along any axis, you can guarantee they are not colliding).

You compute the bounds along each axis in linear time. The sorting of these bounds can be done in linear time, then you take a pass over each axis looking at the marked intervals, which is also linear.

Re: 14,000x Speedup (2015)

#76

Post by arc0 »

3pt14159 wrote: post #49
est31 wrote: post #12

Earlier quoted context omitted.

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…

The proof that Turing gave never really left me fully convinced. Surely if the Romans had "the answer that denies the former" then clearly some version of it is possible in software.

What part of Turing's proof do you find unconvincing?

Re: 14,000x Speedup (2015)

#77

Post by arc0 »

m12k wrote: post #8
read_if_gay_ wrote: post #7

> 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"?

Correct, not all programs suffer from the Halting Problem.

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.

Re: 14,000x Speedup (2015)

#78

Post by [deleted] »

jdmichal wrote: post #62
colejohnson66 wrote: post #48

Earlier quoted context omitted.

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…

My rule is that the only sort I will ever write by hand is a bubble sort. It's basically impossible to write incorrectly. If and when that breaks performance, then I will bring in an external sorting library and figure out what works the best for the data. It's the equivalent philosophy to always buying the cheapest tool you can the first time around. When you break that tool, then you go out and buy the expensive on…

[deleted]

Re: 14,000x Speedup (2015)

#79

Post by mekoka »

umvi wrote: post #38
m12k wrote: post #35

Earlier quoted context omitted.

Computer Science is just academic/theoretical programming. While having a relevant education usually beats not having one, real-world experience usually beats theoretical knowledge when it comes to achieving real-world gains. E.g. if I want something computed as quickly as possible I'm probably better off asking an average game engine programmer than an average CS professor, since they'll optimize for cache efficienc…

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

They're not just annoying, they possibly don't get the point of big O. The n in O(n) means that at the time of algorithm design the size of the data is unknown and considered unbound. If you already know its upper limit then it becomes O(c) (where c is a known constant). If c is low enough (a discretionary decision) it can possibly be considered O(1). Think of how a theoretical hash map traverses one of its buckets in linear time to find the key's value (if the bucket is implemented as a linked lists), we still consider the overall lookup to be O(1) simply because the upper bound of the bucket is known.

Re: 14,000x Speedup (2015)

#80

Post by CyberDildonics »

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.
Post reply on HN