Lixia Liu ([EMAIL PROTECTED]) and myself started to work on a tool to
recognize STL usage patterns that can be corrected to increase
application performance. We believe this tool should live in
libstdc++-v3. We want to start a GCC branch to share what we have so
far and invite contributors.
libstdc++-v3 maintainers, could you please comment/advise?
Thank you,
Silvius
Overview
========
Goal: Give performance improvement advice based on analysis of dynamic
STL usage.
Method: Instrumentation calls in libstdc++-v3/include/debug/*, runtime
support library in libstdc++-v3/libstladvisor, trace analysis/report
tool in libstdc++-v3/stladvisor.
Timeline: Create branch immediately. Target the next stage 1 for merge.
Motivation
==========
Consider the following example:
1 std::unordered_set<int> s;
2 for (int i = 0; i < 10000000; ++i) {
3 s.insert(i);
4 }
Its execution time is reduced by 38% by changing the first line to:
1 std::unordered_set<int> s(10000000);
There are other STL usage patterns that can be recognized and reported
to the application programmer.
Sample Report
=============
test.cc:187 advice: Changing initial size of unordered_map instance from
193 to 1572869 will reduce execution time by 31469325 rehash operations.
test.cc:192 advice: Changing initial size of unordered_map instance from
193 to 6151 will reduce execution time by 5978 rehash operations.
test.cc:253 advice: Changing initial size of unordered_map instance from
193 to 2 will reduce memory consumption by 15343 * sizeof(void*).
Design
======
The usage model is intended to be similar to -fprofile-generate and
-fprofile-use.
1. Compiler driver
Build with instrumentation: gcc -fstl-advisor=instrument:all foo.cc.
The effect on the compiler is simply "|-D_GLIBCXX_DEBUG
|-D_GLIBCXX_ADVISOR". The effect on the linker is "-lstladvisor".
Run program: ./a.out.
Produce advisory report: gcc -fstl-advisor=use:advise.
2. Instrumentation phase
Use the existing libstdc++-v3 wrapper model documented in
http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch30s04.html.
This model is used currently for functional verification of STL code.
Calls to functions in the instrumentation library will be added in
libstdc++-v3/include/debug/*, guarded by #ifdef _GLIBCXX_ADVISOR.
The instrumentation library would live in libstdc++-v3/libstladvisor, at
the same level as libsupc++.
3. Dump phase
The instrumentation library functions register an "atexit" report
generator. The report is either a dump of the instrumentation trace or
aggregated information. For the unordered_set resizing example above,
the report would be a summary of the cost of rehashes, factored by the
actual call stack at hashtable construction time. This report
references only numeric instruction addresses.
4. Analysis & report phase
In our prototype, this is a python script that performs two functions:
- Digest the instrumentation report and make up advice.
- Map instruction addresses into function names, file paths and line
numbers.
