i#1187: whole-callstack cache prototype

Reviewer: zhaoqin@gogole.com
i#1187: whole-callstack cache prototype

i#1187: add a whole-callstack cache.

Prototype implementation: suggestions for improvement?

The performance numbers show that while it has benefits in the absence of
the i#1186 find_next_fp single-frame cache, it is not as effective, so we
want both.  When combined with the single-frame cache it actually causes a
slight slowdown on cfrac and a slight speedup on perlbench diffmail.

fpra_cache_check() shows up in profiling.  For every frame on a new
callstack walk, we have to iterate the whole cache to look for a tail
match.  Any ideas on how to improve this?

[bruening, 2013-04-17 15:09:13]

Running drheapstat on cfrac w/ and w/o this feature and comparing
callstack.log: 195 unique callstacks w/o, 216 w/: seems like there's a
correctness problem.  Unless you can see something I'm missing here, I may
abandon this as it will take a bunch more work to ensure correctness and there's
still no guarantee of a perf win (though in theory it seems like we should be
able to get a win).

[bruening, 2013-04-17 15:15:16]

perf summary:

cfrac full mode:

base (w/o i#1186 find_next_fp cache or i#1187 cstack cache):
51.26user 0.04system 0:51.42elapsed 99%CPU (0avgtext+0avgdata 11108maxresident)k

w/ i#1186 find_next_fp cache:
38.75user 0.04system 0:38.88elapsed 99%CPU (0avgtext+0avgdata 11108maxresident)k

w/ i#1187 cstack cache:
45.29user 0.04system 0:45.43elapsed 99%CPU (0avgtext+0avgdata 11840maxresident)k

w/ both:
39.23user 0.04system 0:39.36elapsed 99%CPU (0avgtext+0avgdata 11108maxresident)k


perlbench diffmail:

base (w/o either):
3359.52user 5.47system 56:14.44elapsed 99%CPU (0avgtext+0avgdata
425808maxresident)k

w/ i#1186 find_next_fp cache:
1833.59user 5.72system 30:45.28elapsed 99%CPU (0avgtext+0avgdata
429768maxresident)k

w/ both:
1719.92user 5.65system 28:51.26elapsed 99%CPU (0avgtext+0avgdata
429740maxresident)k

[bruening, 2013-04-17 15:30:51]

This is being abandoned for now.