12

In university, at our algorithms courses, we learn how to precisely compute the complexity of various simple algorithms that are used in practice, such as hash tables or quick sort.

But now in a big software project, when we want to make it faster, all we do is look at individual pieces -a a few nested loops there that can be replaces by a faster hash table, a slow search here that can be sped up by a more fancy technique- but we never compute the complexity of our whole pipeline.

Is there any way to do that? Or are people in practice just relying on "locally" using a fast algorithm, to make the whole application faster, instead of globally considering the application as whole?

(Because it seems to me to be nontrivial to show that if you pile up a large number of algorithms that are known to be very fast on their own, you also end up with a fast application as a whole.)

I am asking this, because I'm tasked with speeding up a large project someone else has written, where a lot of algorithms are interacting and working on input data, so it is unclear to me how the impact of making on single algorithm faster on the whole application.

user7088941
  • 569
  • 2
  • 12
  • **1)** This requires a testing approach, to find the points to improve. Benchmark testing, Durability testing, Dynamic testing( by monitoring memory/CPU metrics of each component). **2)** After finding the points to improve, you will find the root cause for those points. **3)** Find a solution to solve the root cause, maintaining correctness. – overexchange May 25 '18 at 00:31
  • you need some tools for these tests mentioned in point 1 – overexchange May 25 '18 at 00:38
  • 1
    Big O analysis doesn't tell you how an algorithm will perform. It tells you how the performance will *scale*, as `n` increases. – John Wu May 26 '18 at 00:53

3 Answers3

13

The standard, tried and tested way is to profile the code. You perform dynamic analysis of the running system to measure timings, memory usage etc. Then analyse the results to find performance bottlenecks.

Those bottlenecks are then experimentally rewritten and the result profiled once more to determine that a speed increase, reduction in memory use etc has been achieved. This process is then repeated until an acceptable performance gain is achieved.

David Arno
  • 38,972
  • 9
  • 88
  • 121
  • 1
    This solves the performance problem, which is why we do it, but doesn't answer the original question. I think in particular worst case time or space complexity would best be figured out using a static program analysis tool, which may be missing. Performance tests are great for specific scenarios, but they don't tell you much about the worst possible situations. – Frank Hileman May 24 '18 at 16:49
  • 3
    @FrankHileman I think the point here is that performance is a *practical* concern and can only be measured practically. You don’t use math to find your software’s bottleneck, even if you might solve it once found using math (algorithms). – Wildcard May 24 '18 at 17:12
  • On a related note, in old time slideshow presentation (glass slides), there was a whole pretended technology of how to painstakingly compute the average density of a lantern slide mathematically to determine the brightness of light to use. Completely useless: if the picture doesn’t show up well, you get a brighter light! – Wildcard May 24 '18 at 17:16
  • @Wildcard While performance can only be measured at run time, it can be predicted statically. A poor choice of a data structure may look fine, performance wise, in performance tests, but fail miserably in edge cases that could be predicted in a static analysis. This is the same reason we look at worst case complexity analyses for data structures in general. – Frank Hileman May 24 '18 at 17:57
  • @Wildcard: you are correct, however Frank is also very correct that this post does not answer the question. – Doc Brown May 24 '18 at 18:46
  • @FrankHileman, if you feel that this answer doesn't answer the question, rather than whinging about it in the comments, may I politely suggest you make the effort to write your own answer. Thanks. – David Arno May 24 '18 at 18:49
  • @DocBrown, please see my comment above as it applies to you too. Thanks. – David Arno May 24 '18 at 18:49
  • @DavidArno: be patient, I am working on it ;-) – Doc Brown May 24 '18 at 19:06
  • I prefer whinging. Actually I was hoping someone would point out such a tool; I don't know of any. – Frank Hileman May 25 '18 at 00:01
  • @FrankHileman Static analysis would decrease cyclomatic complexity(E - N + 2*P). But, static analysis(part of code based testing) is development phase activity. when you analyse your own code – overexchange May 25 '18 at 00:36
6

Large software projects consist of many different components, and not all of them are typically a bottleneck. Quite the opposite: for almost any program have seen in my life where low performance was an issue, the Pareto principle applied: more than 80% of the performance gains can be achieved by optimizing less than 20% of the code (in reality, I think the numbers were often more 95% to 5%).

So starting to look at individual pieces is often the best approach. That is why profiling (as explained in David Arno's answer) is fine, since it helps you to identify the mentioned 5% of the code where optimizing will give you the "biggest bang for the buck". Optimizing "the whole application" bears a certain risk of overengineering, and if you optimize those 95% even by a factor of 10, it would often have no measurable effect. Note also that profiling tells you way more than any hypothetical algorithm complexity estimation, since a simple algorithm which needs O(N^3) steps can still be faster than a complex algorithm which requires O(N log(N)) as long as N is small enough.

After profiling revealed the hot spots, one can optimize them. Of course, a "hot spot" can be bigger than just one or two lines of code, sometimes one has to replace a whole component to make it faster, but that will be typically still a small part of the code base in a larger program.

Typical optimiziation techniques include

  • improving the use of algorithms and data structures

  • fine tuning of the former

  • micro-optimizations at some real hot spots

  • recoding critical sections using assembly code or CUDA

Note these techniques are working on different levels of abstraction, some of them viewing a component more "as a whole" than others. So it depends on what you mean by "all we do is look at individual pieces" - if you only had micro-optimizations in mind, I disagree that "we" work only on that. But if you mean applying those full-scale optimizations on isolated parts or components, than "we" are probably working on the right parts, and you should question your expectations.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
3

Although the other answers are correct and provide some guidance, I do think they miss a step. In a complex system like you are working with now, understanding the different components that make up the system is key to understanding why something is slow.

My first step would be to get my hands on a detailed architecture diagram or create one myself. Figure out what steps are taken by what components in the software and how long each step takes.

Also, figure out how the components interact with each other. This can make all the difference.

For example, I've seen code in C# where the interface between two components was passing an IEnumerable built by the first component, which was then enumerated by the second component. In C# this requires context switching, which can be costly under certain circumstances. Solving it has no impact on the algorithm. A simple .ToList() make sure the result is collected before the next step solves this issue.

Another thing to consider is the impact on the system you are running the code on. Hardware interactions can obviously be a factor in complex systems. Look for Disk IO, Large Memory allocations, and Network IO. Sometimes these can be solved more efficiently by tweaking the system or even replacing hardware.

Jonathan van de Veen
  • 608
  • 3
  • 10