This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

New branch for STL Advisor



Lixia Liu (lixialiu@google.com) 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.



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]