WIP
In this article, I am going to introduce some basic concepts and methods on performance engineering.
Basic Workflow
- Measure the performance of Program A
- Calculate the theoretical peek performance of Program A with current input and hardware
- Profile Program A
- Think about possible changes and how much they would theoretically improve the performance
- Make a change to Program A to produce a hopefully faster Program A*
- Measure the performance of Program A*
- Compare the output of A* to that of A
- If A* get the same output as that of A and is faster than A, set A = A*
- If A is still not fast enough, go to Step 3
Measure and Profiling
The “performance” here specifically refers to the latency and throughput of a program. I will not cover other metrics like QPS.
Theoretical Performance
We all know a modern computer under the von Neumann architecture at least has a CPU, a main memory and some I/O devices such as disk, network, screen or keyboard. A typical lifetime of a program would be like below:
- our programs and data are loaded from I/O devices to the main memory.
- Then the instructions and data will be read by CPU then executed and the results will be stored to the memory.
- The results will be eventually written from the memory to I/O devices.
Roofline Model
The Ways to Optimization
If we want our programs run faster, what can we do ? Let me get straight, there are only three ways:
- Reducing computing requirements
- Add or upgrade hardware
- Maximize the utility of hardware
Reducing computing requirements
The fastest program is to do nothing. We can see several different methods in this area, including lossless and lossy methods.
Less Work (Improving Algorithm Complexity)
This is the actually the hardest way because usually only computer scientists invent new algorithms which improve something dramatically. But in practice, we just need to know for a specific problem, what is the best algorithm to solve it. Familiar right ? All leetcode problems are training you this capability. In most cases, we only have to come up with a sub-optimal algorithm first just not to be too stupid. Improving algorithm complexity really matters especially on a large input. For example, if we have a N=1,000,000 size input, then we replace the current O(N^2) algorithm with a O(N * log(N)) one, the program should be cost only 1/50000 time of the previous one.
Usually faster algorithms give us the exactly same result as slower ones which means they are lossless algorithms. But sometimes we can only find approximate algorithm, which means we can accept losing a bit accuracy but saving a lot of time. These algorithms are lossy, such as JPEG for image and H.265 for video. However, sometimes we can not get a faster but also good enough algorithm. For example, a lot of Attention or Transformer variances improve the Attention complexity from O(n^2) to O(n) but not get a similar model performance to the original Attention.