I have spent significant time on performance issues and have been in search of a book that can summarize the diversity of issues and techniques well. I hoped that Optimized C++: Proven Techniques for Heightened Performance would provide some of the guidance I want and
This book is not quite it. There is good material here, yet I found repeatedly thinking that the author was not aware of the past 10(?) years of changes to the field. Not an issue of the book was from the early 2000s, but it was published last year.
A key step in improving the performance of programs is measuring it. There are a variety of techniques for doing so. Tools based on instrumentation and tools based on sampling profiling. I find greater value to using the sampling profiling tools (for measuring performance) due to their lower overhead and ability to pinpoint where in a function this cost exists. Yet the book's focus is limited to gprof-esque approaches. I tell students that this approach is best with deep call trees, which may be a greater issue for C++ programming specifically.
The author is somewhat dismissive to compiler optimizations and emphasizes that his observed benefit has been particularly limited to function inlining. There are many more optimizations, and you should care about them. But again, I wonder if his experience of C++ has been deep call trees that could particularly benefit from inlining.
In a take it or leave it, this work also discourages the use of dynamic libraries. Yes, they impose a performance penalty, but they also provide valuable functionality. It all depends on your use case for whether you should statically or dynamically link your code. Code that is reused by separate executables should be in a dynamic library, as it reduces the memory requirements when running and reduces the effort to patch and update those executables. Components that are only used by a single executable should be statically linked, unless the components are of significant size such that decoupling can still benefit memory usage and the updating process.
The author related that replacing printf with puts to just print a string has performance advantages, due to printf being a complicated "God function". The basic point is valid that printf has significant functionality; however, the anecdote should be taken with a grain of salt. Current compilers will do this optimization (replace printf with puts) automatically.
While most of the work provides small examples, the final chapters on concurrency (?) and memory management do not. The concurrency chapter reads as a reference book, as it lists the various APIs available and what each does. It would be better for the book to assume that the readers are familiar with these calls (as the author does with many other topics) and discuss possible optimizations within this scope.
To conclude, the book is not bad, but I also cannot say it is accurate on every point. Especially with performance, programmers are apt to make prompt design decisions based on "their experience" or "recent publications". Measure your code's performance. Only then can you discern which techniques will provide value.
Showing posts with label optimizations. Show all posts
Showing posts with label optimizations. Show all posts
Monday, March 13, 2017
Wednesday, February 8, 2017
Conference Attendance CGO (etc) 2017 - Day 3
Today is the last day for the conference. I attended several more talks today and my student took 2nd in the student research competition. So it has been a good attendance and I have received some interesting and valuable feedback on my own work, as well as finding some possible collaborations for the future.
Optimistic Loop Optimization
The compiler wants to optimize loops in the program. However, C and LLVM IR have many complex characteristics that the Polyhedral model cannot represent, such as aliasing, wrapping, or out of bound accesses. Rather than just assuming that these characteristics are not present, instead, the code can be analyzed to determine which violating characteristics may be present. These assumptions are placed in the code, and can then be reduced to the set of preconditions for which the optimized loop can be executed. Should the assumptions fail, the code instead can branch to the original version. These optimizations can also be optimized (for example N < 127 implies N < 128). For SPEC200x, the assumptions fail about 2% of the time and impose 4% runtime overhead.
Software Prefetching for Indirect Memory Accesses
What should we prefetch in software? A[x + N] is easy for hardware, A->next is hard for everyone, while A[B[x + N]] is easy for software and hard for hardware to predict. So given a loop (such as exists in NAS is) that has this indirect structure, then prefetches can be inserted that will speedup the loop. Yet, there are three key points for inserting these prefetch instructions.
- You have to prefetch both the A[B[]] and B[]. Otherwise, the prefetch will block on the B[].
- Having both prefetches requires that they are both offset from the actual access as well as each other. Too close and they are not parallel. Too far and the data is evicted before use.
- The first point raised that there is an actual load (not prefetch) of B[] and therefore needs to be bounds checked.
Optimistic Loop Optimization
The compiler wants to optimize loops in the program. However, C and LLVM IR have many complex characteristics that the Polyhedral model cannot represent, such as aliasing, wrapping, or out of bound accesses. Rather than just assuming that these characteristics are not present, instead, the code can be analyzed to determine which violating characteristics may be present. These assumptions are placed in the code, and can then be reduced to the set of preconditions for which the optimized loop can be executed. Should the assumptions fail, the code instead can branch to the original version. These optimizations can also be optimized (for example N < 127 implies N < 128). For SPEC200x, the assumptions fail about 2% of the time and impose 4% runtime overhead.
Software Prefetching for Indirect Memory Accesses
What should we prefetch in software? A[x + N] is easy for hardware, A->next is hard for everyone, while A[B[x + N]] is easy for software and hard for hardware to predict. So given a loop (such as exists in NAS is) that has this indirect structure, then prefetches can be inserted that will speedup the loop. Yet, there are three key points for inserting these prefetch instructions.
- You have to prefetch both the A[B[]] and B[]. Otherwise, the prefetch will block on the B[].
- Having both prefetches requires that they are both offset from the actual access as well as each other. Too close and they are not parallel. Too far and the data is evicted before use.
- The first point raised that there is an actual load (not prefetch) of B[] and therefore needs to be bounds checked.
Tuesday, February 7, 2017
Conference Attendance CGO (etc) 2017 - Day 2
Several of the talks were great and very interesting. Other talks particularly needed further presentation practice. Unfortunately, sometimes this may come from English as a second language. And so I am torn between wanting presenters to have practice and be open to a wider pool of researches, while also wanting to be able to easily understand the presentations.
Tapir: Embedding Fork-Join Parallelism into LLVM’s Intermediate Representation
Let's start by considering code that normalizes a vector. This code takes 0.3s to run. Then switch the "for" with a "cilk_for", and the execution time improves to 180s (w/ 18 cores). When the compiler sees "cilk_for" or other parallel keywords, generally it converts these into runtime function calls that take in a function pointer for the parallel component. (Similar to thread create routines taking in a function to execute). With the function call, many optimization passes cannot cross the call, while previously being able to cross the "for".
Instead, let's propose three new instructions to include in the LLVM IR. Supporting these lines required approximately 6000 lines of changes. When the updated LLVM compiles a set of parallel programs, most can now reach 99+% work efficiency, which indicates that the parallel overhead is near 0.
Prior work would create parallel tasks symmetrically, for example each task would represent separate paths in the classic "diamond" CFG. The problem is that the parallel program is actually taking both paths concurrently, which is not an expected behavior of the control flow. Instead, the IR is asymmetric so that compilers can continue to reason about the basic blocks as a sequential code would appear.
Incremental Whole Program Optimization and Compilation
This covers the feature within Microsoft's Visual Studio compiler. Each component stores hashes of the components on which it depends. When a file is changed, it generates different hashes, which the compiler then can use to determine that its dependencies need to be re-analyzed and code gen'd. These hash changes can then either propagate, if changed, or the compilation process will complete.
Optimizing Function Placement for Large-Scale Data-Center Applications
The common binaries for facebook are 10s-100s MBs in size. These binaries have IPCs less than 1.0 (recall that processors can run above 2.0 and higher is better), and are experiencing frequent front-end stalls that are attributable to iTLB and I$ misses (as high as 60 per 1000, eww). Hardware profilers can then determine the hot functions. This information is then processed to determine the hot functions that should be clustered together. These clusters are mapped to separate loader sessions that will load them using huge pages.
Minimizing the Cost of Iterative Compilation with Active Learning
There are too many possibilities for optimization. Let's ask machine learning to figure this out. The danger is always finding the right level of training to provide valuable insights without overfitting, etc.
Tapir: Embedding Fork-Join Parallelism into LLVM’s Intermediate Representation
Let's start by considering code that normalizes a vector. This code takes 0.3s to run. Then switch the "for" with a "cilk_for", and the execution time improves to 180s (w/ 18 cores). When the compiler sees "cilk_for" or other parallel keywords, generally it converts these into runtime function calls that take in a function pointer for the parallel component. (Similar to thread create routines taking in a function to execute). With the function call, many optimization passes cannot cross the call, while previously being able to cross the "for".
Instead, let's propose three new instructions to include in the LLVM IR. Supporting these lines required approximately 6000 lines of changes. When the updated LLVM compiles a set of parallel programs, most can now reach 99+% work efficiency, which indicates that the parallel overhead is near 0.
Prior work would create parallel tasks symmetrically, for example each task would represent separate paths in the classic "diamond" CFG. The problem is that the parallel program is actually taking both paths concurrently, which is not an expected behavior of the control flow. Instead, the IR is asymmetric so that compilers can continue to reason about the basic blocks as a sequential code would appear.
Incremental Whole Program Optimization and Compilation
This covers the feature within Microsoft's Visual Studio compiler. Each component stores hashes of the components on which it depends. When a file is changed, it generates different hashes, which the compiler then can use to determine that its dependencies need to be re-analyzed and code gen'd. These hash changes can then either propagate, if changed, or the compilation process will complete.
Optimizing Function Placement for Large-Scale Data-Center Applications
The common binaries for facebook are 10s-100s MBs in size. These binaries have IPCs less than 1.0 (recall that processors can run above 2.0 and higher is better), and are experiencing frequent front-end stalls that are attributable to iTLB and I$ misses (as high as 60 per 1000, eww). Hardware profilers can then determine the hot functions. This information is then processed to determine the hot functions that should be clustered together. These clusters are mapped to separate loader sessions that will load them using huge pages.
Minimizing the Cost of Iterative Compilation with Active Learning
There are too many possibilities for optimization. Let's ask machine learning to figure this out. The danger is always finding the right level of training to provide valuable insights without overfitting, etc.
Subscribe to:
Posts (Atom)