Potato paradox • Hacker News Board

Re: Potato paradox

#101

Post by calinet6 » Thu, Jul 16, 2015, 1:29 PM UTC

netcan wrote: post #89

amelius wrote: post #77

Earlier quoted context omitted.

This just shows that the percentage of total time a function takes is really not the thing you should be looking at when optimizing code and you want to know how much faster your code really is. For example, say your function f() takes 100% of the time. You then make it twice as fast. You look at the percentage, and, surprise, it still is taking 100% of the time!

Naturally, if you can look at a program which is now twice as fast and be unimpressed you are looking at the wrong metric. It's understandable though in the context of the sequence of actions you might be going through as a tinkerer (as opposed to a scientist). You start with a list of functions and the % of time they take. Improving the top one will have the biggest effect, so this is a good thing to look at when de…

> Naturally, if you can look at a program which is now twice as fast and be unimpressed you are looking at the wrong metric.

Or, a computer scientist would say, the right one. The actual speed doesn't matter as much as the complexity.

In reality, it does, in the end; but it's also important to consider the type of optimization you're doing, and not just stop at being impressed with twice as fast.

For example, a primitively optimized function that's twice as fast for input size 100 would still be twice as fast for input size 100,000, but a function optimized to be an order less complex could be twice as fast for size 100, and a thousand or so times as fast for size 100,000.

The latter optimization would be significantly better, objectively, and thus, it would make a lot of sense to look at the first program and be unimpressed with a mere linear doubling in speed.

Re: Potato paradox

#102

Post by ryangittins » Thu, Jul 16, 2015, 1:30 PM UTC

eCa wrote: post #83

wobbleblob wrote: post #76

Earlier quoted context omitted.

Well yeah, just add a wait loop somewhere else

I thought they were speed-up loops... http://thedailywtf.com/articles/The-Speedup-Loop

Hah, this is great! It reminds me of the classic

  static char buffer[1024*1024*2];

story from a few years back.

http://www.dodgycoder.net/2012/02/coding-tricks-of-game-deve...

Re: Potato paradox

#103

Post by blueblob » Thu, Jul 16, 2015, 1:41 PM UTC

ot wrote: post #98

jakobegger wrote: post #60

Earlier quoted context omitted.

This is an interesting observation, and confirms the way I optimise code: 1) Create a benchmark (some code that performs the task that I want to optimise), and measure the absolute time it needs. 2) Use a profiler to see where most of the time is spent. Optimise that code. 3) Run benchmark to see if your optimisation are effective. Or, in other words: the percentage tells you where to focus your effort. The absolute…

This is the obvious strategy, but it's not always applicable. For example when profiling a long-running service, or a kernel, there's no "absolute time it needs", you need other proxies of running time such as the CPU usage percentage, but even that is not noise-free. So if you just run "perf" on it, you need to be aware of this fallacy.

I am pretty much a novice in program optimization, but doesn't `perf` sample clock cycles? So in effect CPU usage percentage doesn't matter as much since it's not using wall clock time?

Re: Potato paradox

#104

Post by blueblob » Thu, Jul 16, 2015, 1:44 PM UTC

wobbleblob wrote: post #72

ot wrote: post #37

This is not that uncommon when optimizing code. Your program is slow so you profile it, and find out that f() takes 99% of the time. So you work a lot to optimize f(), and re-profiling shows that now f() takes 98% of the time. Doesn't seem that impressive after all the work you've put into optimizing f(), but your program is actually twice as fast :)

Without knowing your code, I can think of a performance hack to get the running time of f() down to less than 10% of the time.

Me too, move all the code from f() to g() and never call f(). I got the performance of f() down to 0%!

Re: Potato paradox

#105

Post by martincmartin » Thu, Jul 16, 2015, 1:57 PM UTC

gjm11 wrote: post #100

chestervonwinch wrote: post #3

Neat. This bumps up my list of food-related maths from 3 to 4. So far: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Pizza_theorem https://en.wikipedia.org/wiki/Layer_cake_representation

One of the people I went to university with had a little (very short) mental catalogue of "chromatic mathematical fruit jokes". There are exactly two famous ones. "What's purple and commutes?" "An abelian grape." And: "What's yellow and equivalent to the axiom of choice?" "Zorn's lemon." He invented another, which requires more esoteric knowledge: "What's green and determined up to isomorphism by its first Chern clas…

I vaguely remember a joke about limit of the supremum (lim sup) involving lime soup. In fact, I brought some lime soup into math class one day in undergrad. It tasted awful. And I can't remember the joke.

Re: Potato paradox

#106

Post by gwern » Thu, Jul 16, 2015, 2:43 PM UTC

philh wrote: post #75

ThrustVectoring wrote: post #66

The solution is much more intuitive if you use odds ratios instead of percentage probabilities. You go from a 99:1 ratio to a 98:2 (or 49:1) ratio. In other words, it's another way of phrasing that it takes twice as much evidence to be 99% sure as it is to be 98% sure. Or that it's twice as hard to have 99% uptime than 98%.

> it takes twice as much evidence to be 99% sure as it is to be 98% sure. Not twice as much evidence. Evidence needs to be measured logarithmically. (Otherwise you'd say it takes twice as much evidence to be 67% sure as 50% sure (2:1 versus 1:1), but the second takes no evidence at all for a binary proposition.) It takes twice as much evidence to be 99% sure as 91% sure. 98% to 99% is 17 decibels to 20 decibels, whic…

This paradox also helps illustrate why you might want to avoid percentages or 0-1 decimal probability in statistics - in some cases, the compression at the end of the range can mask very important phenomenon. (0.01% and 1% look almost the same as percentages or decimals, but can have different implications.) Particularly important if you're doing anything at the tails of the distribution, like thinking about how to increase extreme values (is increasing the proportion of extreme-values from 0.01% to 0.10% extremely important or utterly trivial?)

Re: Potato paradox

#107

Post by will_work4tears » Thu, Jul 16, 2015, 2:47 PM UTC

yummybear wrote: post #56

Looks like I found my new diet.

There's a guy (or maybe more than this guy) that has done just that:

http://www.20potatoesaday.com/

Re: Potato paradox

#108

Post by frogpelt » Thu, Jul 16, 2015, 2:49 PM UTC

martincmartin wrote: post #105

gjm11 wrote: post #100

Earlier quoted context omitted.

One of the people I went to university with had a little (very short) mental catalogue of "chromatic mathematical fruit jokes". There are exactly two famous ones. "What's purple and commutes?" "An abelian grape." And: "What's yellow and equivalent to the axiom of choice?" "Zorn's lemon." He invented another, which requires more esoteric knowledge: "What's green and determined up to isomorphism by its first Chern clas…

I vaguely remember a joke about limit of the supremum (lim sup) involving lime soup. In fact, I brought some lime soup into math class one day in undergrad. It tasted awful. And I can't remember the joke.

You don't need to. This is hilarious.

Re: Potato paradox

#109

Post by stcredzero » Thu, Jul 16, 2015, 3:05 PM UTC

ryangittins wrote: post #102

eCa wrote: post #83

Earlier quoted context omitted.

I thought they were speed-up loops... http://thedailywtf.com/articles/The-Speedup-Loop

Hah, this is great! It reminds me of the classic static char buffer[1024*1024*2]; story from a few years back. http://www.dodgycoder.net/2012/02/coding-tricks-of-game-deve...

From CToGD:

In other words, when a project gets handed down from above to launch in, say, 3 months, there's no way in hell you can get the servers requisitioned, approved, and installed in that time. It became standard practice for each team to slightly over-request server capacity with each project and throwing the excess hosts into a rainy day pool, immediately available and repurposeable as required.

I know of a Social Security Administration acquisition back in the days of 100 MHz processors. The bureaucracy took so long with this, by the time the order could be put out to suppliers, 100 MHz processors were no longer available, so SSA ended up with a bunch of workstations that were 166 MHz processors down-clocked to 100 MHz. (Otherwise, they would have had to start the whole process over again.)

Re: Potato paradox

#110

Post by hagmonk » Thu, Jul 16, 2015, 3:16 PM UTC

leohutson wrote: post #8

chestervonwinch wrote: post #3

Neat. This bumps up my list of food-related maths from 3 to 4. So far: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Pizza_theorem https://en.wikipedia.org/wiki/Layer_cake_representation

You can add https://en.wikipedia.org/wiki/Pancake_sorting

"announced the acceptance by the journal Theoretical Computer Science of a more efficient algorithm for pancake sorting than the one proposed by Bill Gates and Christos Papadimitriou."

Bill Gates!