Block allocator patch

[Andrew Cheadle]

Hi Simon

On Mon, 6 Jun 2005, Simon Marlow wrote:

>On 05 June 2005 15:37, Andrew Cheadle wrote:
>
>> Here's a patch for the block allocator that reduces the coalescing
>> algorithm from O(N^2) to N.
>>
>> I created the mods and tested them on my 6.2 builds and then prop'd
>> them to the current 6.4 CVS HEAD. When I get a chance and HEAD is
>> unb0rked I'll test them on it. Hopefully the attached patch as is
>> fine though ;-) Any problems/bugs/idiocy let me know!
>
>Thanks Andy.  I'm busy with papers for the Haskell workshop right now,
>but I'll review and hopefully commit the patch next week.  Did you do
>any measurements with the change - did it help?

I'd say it helped :-D

Here's some very basic, but pleasing results:

Test 1

Original N^2:

   262136 107532288 107472956  0.86  0.97    4.49    8.39    0    0  (Gen:  1)
   262136 215171072 215109700  1.73  1.98    7.51   11.77    0    0  (Gen:  1)
   262144 351531008 105336576  2.11  2.20   15.98   20.72    0    0  (Gen:  1)
   262128 168726528  39236108  1.76  1.76   20.91   25.82    0    0  (Gen:  1)
   262128  62590976  14622792  0.19  0.19   22.28   27.25    0    0  (Gen:  1)

New N:

   262136 107532288 107472956  0.61  0.74    5.55   12.53    0    0  (Gen:  1)
   262136 215171072 215109700  1.25  1.51    8.18   15.46    0    0  (Gen:  1)
   273276 351596544 105320648  0.46  0.63   15.22   23.05    0    0  (Gen:  1)
   334744 168734720  39234796  0.19  0.19   18.75   26.74    0    0  (Gen:  1)
   273280  62504960  14558784  0.07  0.08   20.08   28.12    0    0  (Gen:  1)


Test 2

Original N^2:

   262136  26800128  26744344  0.14  0.16    4.10   10.66    0    0  (Gen:  1)
   262136  53710848  53654564  0.23  0.35    4.64   11.36    0    0  (Gen:  1)
   262136 107532288 107472956  0.77  0.92    6.06   12.97    0    0  (Gen:  1)
   262136 215171072 215109700  1.79  1.97    9.18   16.35    0    0  (Gen:  1)
   262140 348938240 148243600  2.60  2.77   17.66   25.35    0    0  (Gen:  1)
   263200 236085248  86880476  2.40  2.39   24.27   32.10    0    0  (Gen:  1)
   262104 138145792  51525032  0.61  0.60   27.35   35.27    0    0  (Gen:  1)
   344064  81887232  31352980  0.31  0.31   29.12   37.09    0    0  (Gen:  1)
   262140  49463296  17681740  0.12  0.12   30.15   38.14    0    0  (Gen:  1)
   263200  27783168   9963824  0.05  0.04   30.70   38.70    0    0  (Gen:  1)
   262144  15380480   6969140  0.03  0.02   31.01   39.02    0    0  (Gen:  1)
   262104  10780672   3524228  0.02  0.01   31.23   39.24    0    0  (Gen:  1)
   262128   5390336   2412592  0.01  0.01   31.33   39.35    0    0  (Gen:  1)

New N:

   262136  26800128  26744344  0.11  0.16    2.45    7.29    0    0  (Gen:  1)
   262136  53710848  53654564  0.26  0.32    3.04    7.96    0    0  (Gen:  1)
   262136 107532288 107472956  0.67  0.74    4.37    9.40    0    0  (Gen:  1)
   262136 215171072 215109700  1.18  1.50    6.92   12.31    0    0  (Gen:  1)
   262128 348540928 148185356  0.71  0.87   13.84   19.63    0    0  (Gen:  1)
   262144 235364352  86962440  0.42  0.42   18.69   24.65    0    0  (Gen:  1)
   262128 137834496  50102084  0.25  0.24   21.53   27.59    0    0  (Gen:  1)
   262104  79261696  29667492  0.14  0.14   23.20   29.29    0    0  (Gen:  1)
   655872  47022080  17737456  0.07  0.07   24.19   30.30    0    0  (Gen:  1)
   262112  27344896   9990072  0.04  0.04   24.76   30.88    0    0  (Gen:  1)
   263200  15532032   5348868  0.02  0.02   25.06   31.19    0    0  (Gen:  1)
   286688   8151040   3836208  0.02  0.02   25.25   31.38    0    0  (Gen:  1)
   278488   5627904   2297508  0.01  0.01   25.36   31.50    0    0  (Gen:  1)

Enjoy!

Andy

*********************************************************************
*  Andrew Cheadle                    email:  a.cheadle at doc.ic.ac.uk *
*  Department of Computing           http://www.doc.ic.ac.uk/~amc4/ *
*  Imperial College                                                 *
*  University of London                                             *
*********************************************************************