[cfe-dev] Feature proposal: adding optional custom info to clang AST nodes.

[Abramo Bagnara]

Mike Stump ha scritto:
> On Aug 15, 2009, at 10:18 AM, Abramo Bagnara wrote:
>> The library is less general but using a map it would be much less
>> efficient.
> 
> Can you categorize this for us?  Do up your full app using each
> approach, then benchmark it on some real data.  Let us know the %
> slowdown.  If large, we might be able to come up with a better design
> that lets you get more performance.  For now, we just tend to doubt the
> benefit is worth the cost.

With the attached program I've benchmarked std::map vs llvm::DenseMap vs
embedded data, reproducing our typical use.

$ time ./a.out 100000 1000 0

real	0m15.421s
user	0m15.415s
sys	0m0.005s
$ time ./a.out 100000 1000 1

real	0m1.344s
user	0m1.337s
sys	0m0.006s

$ time ./a.out 100000 1000 2

real	0m0.390s
user	0m0.387s
sys	0m0.003s

The test build a collection of 100000 objects and link an int to each
object. After that it makes 1000 lookup for each object to retrieve the
data.

llvm::DenseMap are 11.5 times faster than std::map and embedded data is
3.5 times faster than llvm::DenseMap.

The ratio between embedded data and Densemap is not insignificant but I
confess that I guessed that the performance ratio between embedded data
and DenseMap was far higher.

Many thanks to Mike, Chris and Steve for their help and suggestions.






> 
> There are other ways to get the pointers, for example, you can visit
> things of interest, numbering each as you go sequentially.  Then, you
> can use this number as the index into an array to directly get at the
> data on the side, no searching and as dense as you want.  The cost, an
> extra parameter on visitors and one index for each node reference you
> might want to randomly walk to.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: benchmark_maps.cc
Type: text/x-c++
Size: 1641 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090816/79a36ef0/attachment.bin>