I actually think I figured it out by reading more of the code.  This is probably a leftover bit of cruft from when the GC design was different.  The thing to realize is that, from looking at mark(), the scan bit only gets set for the base address of a block of memory.  While that loop would be O(N^2) if the scan bits were getting set for all offsets, they aren't.  Therefore, (I think) it has no effect except cluttering up the code.<br>
<br>At any rate, now that I'm storing all the offsets for B_PAGEPLUS stuff instead of using linear search to compute it, this routine can be optimized significantly by jumping straight over B_PAGEPLUS allocations.<br>
<br><div class="gmail_quote">On Tue, Feb 22, 2011 at 2:31 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:andrei@erdani.com">andrei@erdani.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I know nothing about the algorithm involved but a cursory look doesn't show anything suspiciously redundant. Maybe if you showed the implementation of the outer loop as you think should be, that would help.<br>
<br>
Anyway, we're looking at a log N blowup because the inner loop iterates bits in a number. It would, of course, still be nice to get rid of that!<br>
<br>
<br>
Andrei<div><div></div><div class="h5"><br>
<br>
On 2/22/11 12:55 PM, David Simcha wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div></div><div class="h5">
I'm looking a little more at low-hanging fruit to improve GC<br>
performance, and I think I may have found yet another huge performance<br>
bug, but I want to make sure I'm not horribly misunderstanding the code<br>
before I try to "fix" it.  This one has nothing to do with the patch I<br>
already submitted.<br>
<br>
Someone please take a look the loop on lines 2479-2500 of gcx.d<br>
(<a href="https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d" target="_blank">https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d</a>).<br>
It looks to me like B_PAGEPLUS blocks of memory are *getting scanned<br>
O(N^2) times, completely by accident. *As far as I can tell, the<br>
variable u represents the number of pages in the block currently being<br>
examined.  o represents some offset from the base of the pool.<br>
Therefore, it looks like we're scanning the same memory multiple times<br>
for absolutely no reason.  I also wonder if stuff that's not supposed to<br>
be getting scanned is.  o can be greater than the base of the block, but<br>
we're marking from o to o + u * PAGESIZE, where u * PAGESIZE is the<br>
length of the whole block.<br>
<br>
<br>
<br></div></div>
_______________________________________________<br>
phobos mailing list<br>
<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/phobos" target="_blank">http://lists.puremagic.com/mailman/listinfo/phobos</a><br>
</blockquote>
_______________________________________________<br>
phobos mailing list<br>
<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/phobos" target="_blank">http://lists.puremagic.com/mailman/listinfo/phobos</a><br>
</blockquote></div><br>