Re: [Lhms-devel] [PATCH 0/7] Fragmentation Avoidance V19

["Martin J. Bligh" <mbligh@mbligh.org>]

> For amusement, let me put in some tritely oversimplified math. For the
> sake of arguement, assume the free watermarks are 8MB or so. Let's assume
> a clean 64-bit system with no zone issues, etc (ie all one zone). 4K pages.
> I'm going to assume random distribution of free pages, which is 
> oversimplified, but I'm trying to demonstrate a general premise, not get
> accurate numbers.
> 
> 8MB = 2048 pages.
> 
> On a 64MB system, we have 16384 pages, 2048 free. Very rougly speaking, for
> each free page, chance of it's buddy being free is 2048/16384. So in 
> grossly-oversimplified stats-land, if I can remember anything at all,
> chance of finding one page with a free buddy is 1-(1-2048/16384)^2048, 
> which is, for all intents and purposes ... 1.
> 
> 1 GB. system, 262144 pages 1-(1-2048/16384)^2048 = 0.9999989
> 
> 128GB system. 33554432 pages. 0.1175 probability
> 
> yes, yes, my math sucks and I'm a simpleton. The point is that as memory
> gets bigger, the odds suck for getting contiguous pages. And would also
> explain why you think there's no problem, and I do ;-) And bear in mind
> that's just for order 1 allocs. For bigger stuff, it REALLY sucks - I'll
> spare you more wild attempts at foully-approximated math.
> 
> Hmmm. If we keep 128MB free, that totally kills off the above calculation
> I think I'll just tweak it so the limit is not so hard on really big 
> systems. Will send you a patch. However ... larger allocs will still 
> suck ... I guess I'd better gross you out with more incorrect math after
> all ...

Ha. Just because I don't think I made you puke hard enough already with
foul approximations ... for order 2, I think it's

1-(1-(free_pool/total)^3)^free_pool 

because all 3 of his buddies have to be free as well.
(and generically ... 2^order - 1)

ORDER: 1

1024MB system, 8MB pool = 1.000000
131072MB system, 8MB pool = 0.117506
1024MB system, 128MB pool = 1.000000
131072MB system, 128MB pool = 1.000000

ORDER: 2

1024MB system, 8MB pool = 0.000976
131072MB system, 8MB pool = 0.000000
1024MB system, 128MB pool = 1.000000
131072MB system, 128MB pool = 0.000031

ORDER: 3

1024MB system, 8MB pool = 0.000000
131072MB system, 8MB pool = 0.000000
1024MB system, 128MB pool = 0.015504
131072MB system, 128MB pool = 0.000000

ORDER: 4

1024MB system, 8MB pool = 0.000000
131072MB system, 8MB pool = 0.000000
1024MB system, 128MB pool = 0.000000
131072MB system, 128MB pool = 0.000000


------------------------

I really should learn not to post my rusty math in such public places ...
but I still think the point is correct. Anyway, I'm sure somewhere in
the resultant flamewar, someone will come up with some better approx ;-)

And yes, I appreciate the random distribution thing is wrong. But it's
still not going to work for bigger allocs. Fixing the free watermarks
will help us a bit though.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/