67

According to Wikipedia, the 90 / 10 rule of program optimization states that “90% of a program execution time is spent in executing 10% of the code” (see the second paragraph here).

I really don't understand this. What exactly does this mean? How can 90% of the execution time be spent only executing 10% of the code? What about the other 90% of the code then? How can they be executed in just 10% of the time?

  • 50
    Some parts of the code may be executed more often than other parts. That is what loops are for, after all. In practice, almost always some parts are executed way more often than others. – Kilian Foth Oct 25 '16 at 8:27
  • 147
    Wait until you hear the 90/10 rule for software project duration: “90% of the project will take up the first 90% of the allotted time; the last 10% of the project will take up the other 90% of the allotted time”. – Paul D. Waite Oct 25 '16 at 11:11
  • 3
    Confusion here: "time is spent executing". Consider a++; for(i=0;i<100;i++){b++;} for(i=0;i<100;i++){print(xyz);}. Sure the first for-loop spends a lot more than the first statement, but the second for-loop spends ~1000x more time than the first for-loop, but not executing. It spends it waiting for print. So there's a difference between time spent on execution, and time the code is responsible for. – Mike Dunlavey Oct 25 '16 at 12:45
  • 32
    @Paul_D._Waite I thought it was that 90% of the project took 90% of the time, 90% of what's left takes another 90% of the time, and so on down a non-convergent series to the conclusion that no project is ever finished or fully de-bugged in less than infinite time. – nigel222 Oct 25 '16 at 15:05
  • 9
    For practical examples, a couple of codes I worked on (scientific models) used a large amount of code (~10K lines) to read in and set up the model, then did a loop through a few hundred lines to do the actual computations. But that short loop was n^4 (three space dimensions iterated through many thousands of time steps), so took days to compute. So the actual ratio was probably more like 99%/1% :-) – jamesqf Oct 25 '16 at 17:30
183

There are two basic principles in play here:

  • Some code is executed much more often than other code. For example, some error handling code might never be used. Some code will be executed only when you start your program. Other code will be executed over and over while your program runs.
  • Some code takes much longer to run than other code. For example, a single line that runs a query on a database, or pulls a file from the internet will probably take longer than millions of mathematical operations.

The 90/10 rule isn't literally true. It varies by program (and I doubt there is any basis to the specific numbers 90 and 10 at all; someone probably pulled them out of thin air). But the point is, if you need your program to run faster, probably only a small number of lines is significant to making that happen. Identifying the slow parts of your software is often the biggest part of optimisation.

This is an important insight, and it means that decisions that seem counterintuitive to a new developer can often be correct. For example:

  • There is lots of code that it is not worth your time to make "better", even if it is doing things in a dumb, simplistic way. Could you write a more efficient search algorithm for application XYZ? Yes, but actually a simple comparison of every value takes a trivial amount of time, even though there are thousands of values. So it's just not worth it. It can be tough for new developers to avoid unnecessary optimisation, because in their degree program so much time was spent on writing the "correct" (meaning most efficient) algorithm. But in the real world, the correct algorithm is any one that works and runs fast enough.
  • Changes that make your code much longer and more complex may still be a performance win. For example, in application FOO it may be worth adding hundreds of lines of new logic, just to avoid a single database call.
  • 6
    Of particular note, with things like sorting functions, it's much faster (in dev time) and easier to make a dumb simple algo do the right thing in all cases than to get an elegant algo fully functional and bugless. (Tho the only reasons to write a sort algo outside of acadamea are if you're building a library or working on a platform without one…) – StarWeaver Oct 25 '16 at 10:13
  • 5
    I think you need to add the link to shouldioptimize.com :) – Ivan Kolmychek Oct 25 '16 at 12:34
  • 13
    I think the 90/10 comes from the well known 80/20 Pareto Principle en.wikipedia.org/wiki/Pareto_principle – fernando.reyes Oct 25 '16 at 16:19
  • 2
    @StarWeaver Which is why languages that make writing super-efficient sorts as easy as or easier than a crappy bubble-sort are important there, like C++. Such "prepackaged" algorithms and code can be really heavily optimized without causing complexity at point of use. – Yakk Oct 25 '16 at 17:18
  • 6
    @IvanKolmychek That site is misleading. Sure, that kind of cost analysis is one factor to consider, but there's other factors like user experience. You might save a lot of money by not optimizing, but you might also miss out on a lot of income if people leave your site frustrated. – jpmc26 Oct 25 '16 at 20:42
20

This isn't a law of nature, but a rule of thumb born out by wide experience. It is also known as the 80/20 rule, and is only ever a rough approximation.

Loops, Branches and other flow control.

Each place that has an if, you will have one branch that is taken more often than the other branch. Thus more of the execution time is spent executing that part of the program, and not the other part.

Each place that has a loop that runs more than once, you have code that gets executed more than surrounding code. Thus more time is spent there.

As an example, consider:

def DoSomeWork():
    for i in range(1000000):
        DoWork(i)
    except WorkExeption:
        print("Oh No!")

Here the print("Oh No!") will only ever run a maximum of once, and often never, whereas the DoWork(i) will occur about a million times.

  • 7
    Calling it the 80/20 rule can cause confusion with the Pareto principle, which applies more broadly than just to programming. Maybe 90 and 10 are just convenient numbers that don't have this overlap in meaning. – trichoplax Oct 25 '16 at 9:58
  • 29
    It's an instance of the Pareto principal. Both pairs of numbers are equally arbitrary – Caleth Oct 25 '16 at 10:00
  • 2
    There's a mathematical basis to the 80/20 split in the Pareto principle. They're not just some imaginary figures to represent "a lot" and "a little". – Moyli Oct 25 '16 at 13:59
  • 1
    @Moyli - Yes, "There is a mathematical basis to the 80/20 split ...", but in the real world, it will never (OK, by coincidence, rarely) be exactly 80/20. – Kevin Fegan Oct 25 '16 at 18:24
  • 2
    @trichoplax the pareto principle applies very well here. 20% of the causes (the code lines) causes 80% of the effects (the runtime) – njzk2 Oct 25 '16 at 19:21
16

Loops.

I'm tempted to stop there! :-)

Consider this program

1. do_something

2. loop 10 times
3.    do_another_thing

4.    loop 5 times
5.        do_more_stuff

Line 1 is executed once whilst line 3 is executed 10 times. Looking at each line in turn

1 1   0.8%
2 10  8.3%
3 10  8.3%
4 50 41.3%
5 50 41.3%

Two lines account for 83% of the execution time (assuming all lines take about the same time to run. So 40% of the program takes >80%.

With larger more real world examples this rises so only a small amount of lines accounts for much of the run-time.

The 90/10 rule (or as it's sometimes put 80/20) is a "rule of thumb"- only approximately true.

See also Pareto Principle

  • 2
    Instead of saying it's only approximately true, I'd say that in many cases, at least 90% of the time will be spent executing a tiny fraction of the code--at most 10%. Obviously it would be possible to have programs where all portions spent about the same amount of time executing, but that's rare. – supercat Oct 25 '16 at 17:47
  • +1 for referencing the Pareto Principle. More in-depth explanation can be seen in this fantastic Vsauce video. – Radu Murzea Oct 27 '16 at 14:39
5

As you asked about the execution time only, this example might be helpful:

int main() {
    sleep(90); // approximately 10% of the program.
    // other 90% of the program:
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    return 0;
}

If to be a little more serious, it means that in real-life code you almost always call a heavy function in a loop (instead of sleep(90);), while the rest 10% of time you perform some single-pass computations.

Another example is error handling in some HA service. Any highly-available service is designed to work infinite amount of time under normal conditions. It operates normally 99% of time, but occasionally, in case of an error, it runs some error handling and recovery, which may be even more logically complex than the service itself.

  • Nice, I was hoping someone would post this extreme example, that shows the difference clearly. – djechlin Oct 27 '16 at 16:34
3

The 90/10 reasoning means a small part of you code will be repeated or used more than others. This is often used to suggest that you should concentrate 90% of your development/ optimization effort in this 10% of your code.

Think a normal text processor, like Microsoft Word or OpenOffice:

  • The preferences dialog, is not used much;
  • The subroutines that draw characters are used all the time.

This saying is also used in management sciences... This is a lesson to life itself... Meaning: concentrate most of your efforts where gives you more result.

  • 6
    If Microsoft Word is simple, what is an example of a complex one? – Peter Mortensen Oct 25 '16 at 19:22
  • @PeterMortensen that makes no sense. – user64742 Oct 26 '16 at 23:26
  • @PeterMortensen Emacs, obviously. – muru Oct 28 '16 at 5:57
2

Imagine a program like this:

print "H"
print "e"
print "l"
print "l"
print "o"
for i=0 to 1,000,000
    print "How long now?"
next
print "B"
print "y"
print "e"

Notice how there are 11 lines here where 3 out of the 11 are the for loop, where how much time is spent on this rather small piece of code? Quite a bit while the other 8 lines are merely printing a single character. Thus, beware that while some code may be short, that doesn't tell you how often is it executed and how much time it'll take.

0

In addition to looping, as mentioned by other great answers, there's also DRY principles to consider. Well written, Object Oriented code has a lot of reusable parts. Those parts that are reused, by definition, get used at least twice as often as something that is only executed once. If you have a lot of OO code, you could potentially be reusing a few classes and methods many times, and a few other pieces of code only once.

As mentioned in other answers, it is probably better to spend effort making the code that is used more often better than improving the code that is only used a single time.

  • 2
    You could reuse a lot of code, but all of it could be executed infrequently (while still being crucial). – Peter Mortensen Oct 25 '16 at 19:25
  • @PeterMortensen "crucial but not often" isn't the same as "reused almost every second and needing to be as fast as possible" – user64742 Oct 26 '16 at 23:27
  • @TheGreatDuck and I don't think that's what he meant. Because you can have code that is executed infrequently but you want it to happen as fast as possible. For an example, let's take error recovery - depending on the application, it might be fine to take some time (5 minutes, an hour, maybe more) for the system to be operational again. However, if, say, a flight system encounters an error, you really do want it up as fast as possible. Because if it doesn't it will "go down" and "crash" in a very literal sense. – VLAZ Oct 28 '16 at 9:19
  • This seems to imply that DRY requires OO, which is of course not true. Reuse is equally facilitated by free functions, etc. – underscore_d Oct 28 '16 at 11:31
  • @vlaz that is true, but the thing is that in an airplane.... EVERYTHING needs to run fast. – user64742 Oct 28 '16 at 16:24
0

That's not a rule, that's just some dude who's edited Wikipedia with a couple of numbers pulled out of thin air and called it a rule. Compare with Pareto Principle, which is more firmly established in other contexts. I'd like to see what research has been done (if any) on the accuracy of this "rule".

But basically the answer to your question is, some code gets executed much much more frequently than other code. Loops are often the reason for this. Other reasons are time-consuming calls e.g. to external resources like web services or storage media.

  • It is a legitimate thing that people use as a rule of thumb. – user64742 Oct 26 '16 at 23:25
  • If you're suggesting this is in widespread use as a rule of thumb, I'd be interested to see evidence for that also! Or is that just yet another opinion pulled out of thin air but implied as factual? – Brad Thomas Oct 27 '16 at 1:28
  • If you actually read the wikipedia article you'd see that the quote referred to by the asker has this citation: amazon.com/Every-Computer-Performance-Book-Computers/dp/… I've never personally seen it in use, but you're post came across as rude and dismissing in my opinion so I responded. Obviously 10% is a number somebody made up. I can make it whatever number I want by making my program inefficient. However, whether or not it is a term used in software engineering is clearly not debatable seeing as how many people here agree to its existence. – user64742 Oct 27 '16 at 1:33
  • Well I'm not about to go buy the book just to see the research it supposedly refers to... can you post a quote from it that shows the evidence? Or have you in fact seen none? – Brad Thomas Oct 27 '16 at 1:35
  • 1
    @BradThomas: Evidence against the theory that 90-10 rule was invented by someone who was editing Wikipedia is that it was widely cited, with the numbers 90 and 10, many years before Wikipedia existed; the real principle isn't that exactly 10% of the code accounts for 90% of the runtime, but rather that in most programs a small portion of the code--10% or less, accounts for such a large portion of the runtime--90% or more that even a 10% improvement in the performance of that small part of the code would reduce overall execution time more than a 1000x improvement in everything else. – supercat Oct 27 '16 at 17:56
0

It's an reinterpretation of the "Pareto principle", which states "for many events, roughly 80% of the effects come from 20% of the causes.", also known as the 80/20 rule. This rule is mostly applied to economics, so it makes sense that it'd be re purposed for programming.

It's just a pattern that has been observed over a long period of time.

Here's a very nice video on patterns like this, and it also explains the Pareto Principle.

https://www.youtube.com/watch?v=fCn8zs912OE&ab_channel=Vsauce

Not the answer you're looking for? Browse other questions tagged or ask your own question.