14,000x Speedup (2015) • Hacker News Board

Re: 14,000x Speedup (2015)

#101

Post by PaulHoule » Tue, Oct 13, 2020, 2:42 PM UTC

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…

One time I had a famous computer science professor mail me a C program (maybe 200 lines of code) that would compile OK but would crash when I would try to run it.

I set a breakpoint at the beginning of the main() method and it crashed before it even got to main().

That had me scratching my head for a minute, then I realized that the program was static initializing a 2^32 byte array. The prof had a 64-bit computer (probably DEC Alpha) which you could do that on, but it didn't work on my 32-bit x86 machine.

It turned out that the program never used the array that it allocated so deleting one line from the code got it to run.

Most CS profs never have to really finish the systems they work on so they lack many of the skills and attitudes of the professional programmer. Some of them are artisans with code, but mostly they making a living writing papers and teaching classes and the code is tertiary.

Re: 14,000x Speedup (2015)

#102

Post by cyphar » Tue, Oct 13, 2020, 2:43 PM UTC

arethuza wrote: post #96

ls65536 wrote: post #64

Earlier quoted context omitted.

The way in which I like to often think about these things in practice is with "hidden" constant factors. For example, you can think of the O(1) algorithm as really taking O(1 * K1) time, and the O(n) algorithm taking O(n * K2) time to complete. For different algorithms, K1 and K2 will almost certainly be distinct, and may even differ by significant amounts. Of course, if K1 is less than K2, then the value of "n" is i…

Isn't that already built into the definition of O? "f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0" Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0? https://en.wikipedia.org/wiki/Big_O_notation Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-) Edi…

You are correct, the point being made was that a lot of people aren't aware of that and just take it as gospel that O(1) algorithms must be faster than O(n) ones -- but, as you said, big-O notation only says that is true after n goes above some threshold n0 which may be (and usually is) very large.

After all, the most efficient (in terms of big-O) known algorithm for multiplying two numbers uses a 1729-dimensional Fourier transform and only becomes more efficient once the numbers involved are significantly larger than the number of atoms in the universe[1].

[1]: https://en.wikipedia.org/wiki/Galactic_algorithm

Re: 14,000x Speedup (2015)

#103

Post by Ultimatt » Tue, Oct 13, 2020, 2:49 PM UTC

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 software engineer fail.

Re: 14,000x Speedup (2015)

#104

Post by mynegation » Tue, Oct 13, 2020, 2:49 PM UTC

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.

C++, while complicated, is actually pretty transparent about it. The difference between pass-by-value and pass-by-reference is one sigil, but at least you see it there and you have at least some idea that it is there for a reason.

Compare it with lazy evaluation languages like Haskell or declarative languages like SQL where oftentimes you have to run query planner explanation to troubleshoot the performance problems.

Re: 14,000x Speedup (2015)

#105

Post by arethuza » Tue, Oct 13, 2020, 2:51 PM UTC

cyphar wrote: post #102

arethuza wrote: post #96

Earlier quoted context omitted.

Isn't that already built into the definition of O? "f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0" Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0? https://en.wikipedia.org/wiki/Big_O_notation Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-) Edi…

You are correct, the point being made was that a lot of people aren't aware of that and just take it as gospel that O(1) algorithms must be faster than O(n) ones -- but, as you said, big-O notation only says that is true after n goes above some threshold n0 which may be (and usually is) very large. After all, the most efficient (in terms of big-O) known algorithm for multiplying two numbers uses a 1729-dimensional Fo…

That "significantly" is quite the understatement!

Re: 14,000x Speedup (2015)

#106

Post by foota » Tue, Oct 13, 2020, 2:53 PM UTC

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.

Re: 14,000x Speedup (2015)

#107

Post by topkai22 » Tue, Oct 13, 2020, 2:54 PM UTC

captain_price7 wrote: post #9

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

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.

Re: 14,000x Speedup (2015)

#108

Post by lmilcin » Tue, Oct 13, 2020, 2:59 PM UTC

arc0 wrote: post #67

lmilcin wrote: post #30

Earlier quoted context omitted.

At this point we are still talking mathematical terms. So, read it the following way: Mathematically, you can construct a program that, using finite amount of steps and finite amount of memory tells whether another program terminates or not IF you know this other program has finite amount of memory to use. Obviously, we know that even with very small amount of memory this is going to take huge amount of time. Just lo…

The busy beaver function assumes infinite memory, it is defined as a function of the number of states of the Turing machine (in a programming language this is program size). If it was memory then it would not be an undecidable sequence.

In general, when you want to implement some kind of algorithm in real life the state of the Turing machine must be stored somewhere between ticks and this storage can be considered memory.

You could think about this way: hardcoding a constant (moving it from heap to compiled code) doesn't magically cause the program to use less memory.

Thinking it in a different way, from purely physical point of view, every bit of information can be translated to some minimum amount of energy or mass (mass energy equivalence).

Since state ("state", not "possible states") of Turing machine is bits of information, you can't have a Turing machine with infinite size of state. Now, "possible states" are capped because if the state is finite in size, the number of possible states is less or equal than all permutations of it (permutations == possible states).

It is largely philosophical question which is "memory" available to the program and which is "Turing machine state". In case of real programs we see that memory can be reassigned depending on requirements.

There are some cases when the distinction becomes important in reality. Consider a trained AI that gets "baked in" and shipped to the user to compress/decompress images.

Let's say it does fantastic job at compression and decompression but takes 2GB of disk storage and memory when executing.

If you just compress a single small image you realistically need to send 2GB of the AI plus the very small image, but when you have billions of images this static cost of the AI gets amortized.

The same way happens when you run any real program on an operating system. In reality the program is much larger because even if it prints Hello World it still needs to do a bunch of data like recognize your monitor it is talking to. We conveniently package the common parts of the program as "Operating System" and then just let exchanging the small part that will make sense when coupled with correct OS.

That's also how you can have very small webpage that takes GBs of memory to execute... sadly...

Re: 14,000x Speedup (2015)

#109

Post by mynegation » Tue, Oct 13, 2020, 2:59 PM UTC

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?

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

Re: 14,000x Speedup (2015)

#110

Post by formerly_proven » Tue, Oct 13, 2020, 2:59 PM UTC

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.

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