>> This significantly helps fragmentation in programs with dynamic memory usage, e.g. long running programs.

> On which programs? The fragmentation of the memory depends a lot on how the program allocates memory. For example, if a program has no "temporary memory peak", it should not be a victim of the memory fragmentation.

"Long running programs."  E.g. web servers and so on.  Where there is a churn in memory usage.  As objects are allocated and released with some sort of churn.  New objects will be allocated from lower-address pages, where higher address pages are increasingly likely to be freed as no-longer used objects are released.  This is the second best thing to a sliding-block allocator and is motivated by the same requirements that makes such an sliding-block allocator (such as pypy uses) desirable in the first place. 


> To measure the improvment of such memory allocator, more benchmarks (speed and fragmentation) should be run than a single test (memcruch.py included in the test) written to benchmark the allocator.

Yes.  Memcrunch was specifically written to simulate a case where objects are continuously created and released, such as might be expected in a server, with a peak in memory usage followed by lower memory usage, and to demonstrate that the pages allocated during the peak will be released later as memory churn causes memory usage to migrate toward lower addresses.

However, following Antoine's advice I ran the Benchmarks testsuite and found an adverse effect in the n-body benchmark.  That can have two causes:
a) the insertion cost of the block when a block moves from 'full' to 'used'.  This is a rare event and should be unimportant.  I will instrument this for this test and see if it is really the reason
b) Cache effects because a newly 'used' block is not immediately allocated from.  Again, it happens rarely that a block is linked at the head so this shouldn't be significant.

Because of this, this change isn't yet ready to be applied.
If however I manage to change the policy so that memory usage becomes better while still preserving performance of the benchmark tests, I will report back :)