<div dir="ltr">On Tue, Apr 23, 2013 at 8:07 AM, José Fonseca <span dir="ltr"><<a href="mailto:jose.r.fonseca@gmail.com" target="_blank">jose.r.fonseca@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote"><div><div class="h5">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>> "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><br></div></div></div><div>I looked at it and it looks good AFAICT.</div><div><br></div><div>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></div></div>
</blockquote></div><br></div><div class="gmail_extra" style>I went ahead and did this.</div><div class="gmail_extra" style><br></div><div class="gmail_extra" style>Jose</div></div>