68

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?

Peter Mortensen
  • 1,050
  • 2
  • 12
  • 14
Rakshith Ravi
  • 765
  • 1
  • 5
  • 15
  • 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 08:27
  • 1
    related: [How to see what parts of your code are run most often?](http://softwareengineering.stackexchange.com/questions/207819/how-to-see-what-parts-of-your-code-are-run-most-often) – gnat Oct 25 '16 at 10:00
  • 1
    As already commented, the point is how often (relatively) various paths through the code are traversed. If 10% of the code gets invoked over and over again, while 90% is just sitting there in case it's needed, then the 90-10 rule makes sense. – Walter Mitty Oct 25 '16 at 10:35
  • So your title indicates, like, upspeak? – Carsten S Oct 25 '16 at 10:58
  • 148
    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
  • as stated in at least 1 answer the numbers 10 and 90 are not going to be exact, they are commonly used when referring to things like this. Another one I have heard is 90% of users only use 10% of the functions of a program – Topher Brink Oct 25 '16 at 13:53
  • 1
    @PaulD.Waite But wait, doesn't that add up to more than one hundr- oooooh! Got it. ;-) – Ajedi32 Oct 25 '16 at 14:32
  • 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
  • The point of the second time joke is that most project times are ridiculously underestimated. – WGroleau Oct 25 '16 at 15:11
  • 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
  • @jamesqf That's been my general experience with profilers--the vast majority of time is spent in a few small areas--either IO related or deeply nested loops. – Loren Pechtel Oct 25 '16 at 20:09
  • @MikeDunlavey, I have *never* heard that definition. That's still part of the execution time, aka the duration of the functions execution. Which parts are spend in I/O, or cache fetches, or CPU, or GPU, or whatever is still part of its execution – Paul Draper Oct 26 '16 at 05:30
  • 2
    I would say it should be called "98/2 rule" – BЈовић Oct 26 '16 at 06:27
  • @PaulDraper: Sure you can split hairs on the definition. You can say if a program waits all day in a scanf for me to type something, it is "executing". If fact it may be "executing", just in a different CPU, an I/O processor. But which program is "executing"? Every function on the call stack? My preference is to say "execution" means executing instructions, but that the program is "responsible for" time it causes to be spent elsewhere. – Mike Dunlavey Oct 26 '16 at 13:09
  • 1
    The 90/10 rule: For all X and Y, 90% of the X takes 10% of the Y. – user253751 Oct 26 '16 at 19:30
  • Related: [Latency Numbers Every Programmer Should Know](https://gist.github.com/jboner/2841832) – Wildcard Oct 27 '16 at 06:48
  • The first rule of the 90/10 rule is that it's not a real rule. ;) – Bradley Thomas Oct 27 '16 at 13:51

9 Answers9

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…) – Weaver Oct 25 '16 at 10:13
  • 5
    I think you need to add the link to http://www.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 https://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
  • @StarWeaver Once in a blue moon you end up having to reinvent wheels to work around system limitations--say, data that exceeds available memory, or cases where you can exploit knowledge of the data to increase performance. (ie, many years ago I knew that while items might be added to the file a snapshot of the index taken at startup would always contain anything the operator needed. Preload the index and I got my data in one disk read. Production reality meant new items could never show up that day and the machine was powered off at night.) – Loren Pechtel Oct 25 '16 at 20:06
  • 2
    @StarWeaver Or even better, **use your language's built in algorithms** (or failing the existence of those, a popular third party library). They may not be the ideal algorithm for your use case, but you can rest assured that they are time tested and optimized well enough to give reasonable performance in a vast majority of cases. – jpmc26 Oct 25 '16 at 20:34
  • 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
  • @jpmc26 yes; and on the other hand, there is not a direct relationship between runtime and cost in many applications. Often the (hardware) cost of a less efficient algorithm is zero. –  Oct 26 '16 at 06:48
  • 1
    @dan1111 Perhaps another wording for "correct" that "most efficient" is usually measured in wall time. New developers coming from academia are usually not trained to consider this. – Thorbjørn Ravn Andersen Oct 26 '16 at 10:13
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.

Caleth
  • 10,519
  • 2
  • 23
  • 35
  • 7
    Calling it the 80/20 rule can cause confusion with the [Pareto principle](https://en.wikipedia.org/wiki/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 is on Codidact now Oct 25 '16 at 09:58
  • 29
    It's an instance of the Pareto principal. Both pairs of numbers are equally arbitrary – Caleth Oct 25 '16 at 10:00
  • I think, you should add a paragraph on recursion: After all it's a way of looping that's all too easily missed because it's implicit looping. – cmaster - reinstate monica Oct 25 '16 at 12:30
  • 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
  • Thanks everyone for explaining. I won't delete my initial comment in case this comment thread helps others with the same misconception. – trichoplax is on Codidact now Oct 25 '16 at 19:35
  • @Moyli no, there's nothing magical about 80 and 20, they're just numbers that are roughly true some of the time. Different distributions have different tails, and the 80-20 numbers change accordingly. The Pareto principle is just a reminder that lots of things can be approximated by a Pareto distribution with an exponent of slightly more than 1. – hobbs Oct 26 '16 at 04:38
  • 1
    (from the linked wikipedia article: "The term 80–20 is only a shorthand for the general principle at work. In individual cases, the distribution could just as well be, say, nearer to 80–10 or 80–30.") – hobbs Oct 26 '16 at 04:47
  • Not totally arbitrary though, something closer to 50-50 loses the meaning of the principle. It's majority of product of work vs. majority of time to work. – OJFord Oct 26 '16 at 07:26
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

Nick Keighley
  • 754
  • 4
  • 7
  • 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](https://www.youtube.com/watch?v=fCn8zs912OE). – 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.

Sergey
  • 263
  • 2
  • 10
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.

Lucas
  • 298
  • 1
  • 4
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.

JB King
  • 16,795
  • 1
  • 40
  • 76
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.

SusanW
  • 1,035
  • 10
  • 14
Marshall Tigerus
  • 550
  • 5
  • 13
  • 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 09: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
  • @TheGreatDuck point was, that you _can_ have rarely executed code that is also performant. True, the two not need be linked, but, again, I don't think that was the point Peter Mortensen was making. – VLAZ Oct 28 '16 at 17:45
  • @vlaz I know, he was making the point that reused code isn't always needed to be efficient. My point was: But the code/functions that *are* reused often need to be at the forefront of optimization. If your program relies heavily on list operations, then you better optimize those list operations as much as possible. – user64742 Oct 28 '16 at 18:31
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.

Bradley Thomas
  • 5,090
  • 6
  • 17
  • 26
  • 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? – Bradley Thomas Oct 27 '16 at 01:28
  • If you actually *read* the wikipedia article you'd see that the quote referred to by the asker has this citation: https://www.amazon.com/Every-Computer-Performance-Book-Computers/dp/1482657759/ 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 01: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? – Bradley Thomas Oct 27 '16 at 01:35
  • dude, you're just being rude at this point. Guess what, your answer is completely false. Give me an actual piece of physical evidence showing me that loops cause code run more often. You cant? Fine then, but your answer is false. – user64742 Oct 27 '16 at 01:38
  • I only responded to your post because it sounded incredibly rude to the asker, and because people recognize it a lot in this question meaning it has to be a term people use. I never said it was a true term, just that people use it. – user64742 Oct 27 '16 at 01:39
  • Again, I'm just asking you to show me the evidence 90/10 is in widespread "use" (whatever that means - I'll let you pick) Thats' all. Otherwise its' just a claim and a link to a book. – Bradley Thomas Oct 27 '16 at 01:40
  • The Wikipedia book citation you quote is referring to Pareto Principle and not 90/10 anyway. So still, I see no evidence that the 90/10 concept is used as a rule of thumb, or that it's more than just two numbers pulled out of thin air by someone who edited Wikipedia. Basically it looks to me like you just didn't like my answer sounding dismissive so you decided to comment some unsupported BS about people supposedly using 90/10. Of course my answer is dismissive. Calling 90/10 a "rule" is ridiculous of OP, IMO. Wikipedia isn't gospel. Citing opinions as fact without research is just sloppy. – Bradley Thomas Oct 27 '16 at 13:39
  • 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
  • "widely cited, with the numbers 90 and 10, many years before Wikipedia existed". And they keep coming, another unsubstantiated claim. Can you show me *real* evidence of this, if so I'll happily agree there's some merit to the argument you and TheGreatDuck are making. I am struggling to find on the web anything about 90/10 in software pre 2013. – Bradley Thomas Oct 27 '16 at 18:50
  • Although I do find it *in Wikipedia* as early as 2003. Go figure. – Bradley Thomas Oct 27 '16 at 19:11
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

imnota4
  • 123
  • 5