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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20110222/40dc4a2d/attachment.html>

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

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>