<div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">On Fri, Apr 12, 2013 at 7:17 PM, Carl Worth <span dir="ltr"><<a href="mailto:cworth@cworth.org" target="_blank">cworth@cworth.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="im">> "Use skiplist-based FastCallSet within trace::CallSet"<br>

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