New branch for STL Advisor

[Silvius Rus]

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.