Several new (or old) feature-branches proposed for upstream merge

[José Fonseca]

On Fri, Apr 12, 2013 at 7:17 PM, Carl Worth <cworth at cworth.org> wrote:

> > "Use skiplist-based FastCallSet within trace::CallSet"
> >
> > This is a complex change that changes trace::CallSet. I'll need more
> > time to review it. Feel free to commit the others.
>
> OK. Do take a look at it. As mentioned in the commit log, the basic
> skip-list implementation has been well-tested within cairo, so I trust
> it to be quite sound.
>
> The extension of the skip-list to support a range at each node, (in
> "Extend trim::CallSet with a new range-based add method.") is new here
> and could definitely use some good review.
>
> Eric did ask me in person why I chose a skip-list here rather than
> something like a bitset. A bit-set could also be used, but I did not
> think of it originally. For a call-set that's not sparse, (such as the
> final result of calls needed after trimming with dependencies), a simple
> bit-set could have both memory and performance advantages over the
> skip-list, (though I haven't measured).
>
> For a very sparse callset, (such as what you might have with something
> on the command-line like "--calls=297653-"), a naive bit-set
> implementation would be quite wasteful of memory. One could add various
> optimizations for compressing large ranges of 1s and 0s in the bit-set,
> but I can imagine the code getting more complex than the current
> skip-list code for similar performance on sparse sets.
>
> Another option would be to use something else in STL other than
> std::set<unsigned> which I measured to perform quite badly on my system
> at least. Perhaps vector<bool>?
>
> I don't really care what the final implementation uses as long as it
> performs well. The current linear search with std::list<CallRange> in
> class CallSet is definitely inadequate for use cases I am hitting
> regularly now.


I looked at it and it looks good AFAICT.

However it fails to build on windows due to random(). Could you modify
random_level() to use rand() , or add a os::random() abstraction that does
something sensible for windows?

If you can't build windows yourself easily, just throw me a patch and I'll
test it.

Jose
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/apitrace/attachments/20130423/c04ed497/attachment.html>