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

[José Fonseca]

On Tue, Apr 23, 2013 at 8:07 AM, José Fonseca <jose.r.fonseca at gmail.com>wrote:

>
> 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?
>

I went ahead and did this.

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