[phobos] More GC stuff

[David Simcha]

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.

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.

On Tue, Feb 22, 2011 at 2:31 PM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> 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.
>
> 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!
>
>
> Andrei
>
>
> On 2/22/11 12:55 PM, David Simcha wrote:
>
>> I'm looking a little more at low-hanging fruit to improve GC
>> performance, and I think I may have found yet another huge performance
>> bug, but I want to make sure I'm not horribly misunderstanding the code
>> before I try to "fix" it.  This one has nothing to do with the patch I
>> already submitted.
>>
>> Someone please take a look the loop on lines 2479-2500 of gcx.d
>> (
>> https://github.com/D-Programming-Language/druntime/blob/master/src/gc/gcx.d
>> ).
>> It looks to me like B_PAGEPLUS blocks of memory are *getting scanned
>> O(N^2) times, completely by accident. *As far as I can tell, the
>> variable u represents the number of pages in the block currently being
>> examined.  o represents some offset from the base of the pool.
>> Therefore, it looks like we're scanning the same memory multiple times
>> for absolutely no reason.  I also wonder if stuff that's not supposed to
>> be getting scanned is.  o can be greater than the base of the block, but
>> we're marking from o to o + u * PAGESIZE, where u * PAGESIZE is the
>> length of the whole block.
>>
>>
>>
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20110222/8a897cea/attachment.html>