From: "A.Appleyard" <A DOT APPLEYARD AT fs2 DOT mt DOT umist DOT ac DOT uk>
To: DJGPP AT SUN DOT SOE DOT CLARKSON DOT EDU
Date: Wed, 16 Aug 1995 13:23:41 BST
Subject: djgpp\libsrc\c\lib\malloc.c (Heap management)

  As I said before, I wrote a Gnu C++ program (a text editor) that gets and
frees a lot of pieces of heap storage. After a while, if editing big files, it
starts thrashing and being slow, due to needed pieces of heap being mixed with
unneeded freed pieces of heap. The obvious remedy would be for me to:-
  (1) Write all my heap working to temporary files.
  (2) Free all the heap that I know where the pointers to it are.
  (3) Re-read from the temporary files to the heap, in the hope that this will
serve in the same way as defragmenting a DOS disk by `saving it and deleting
it and restoring it'.
  But this will not happen, as after a lot of malloc()'ing and free'ing, the
freed pieces of heap will be chained in random order and not with (all the
pieces on the same page consecutively on their chain); and as the heap matter
is restored from the temporary files the heap pieces will be allocated in
chain order and not by using up all of each page before starting another page.
  (It seems from the source form that there is a hidden array nextf[]. Each
nextf[i] points to a chain of heap pieces which are each 8*pow(2,i) bytes long
including each piece's pointer to the next piece in the chain. Each of those
chains is called a `bucket'.) A page seems to be 2048 bytes long.
  So I have written (but not tested) this routine:-
/*-----*/
/* rearrange chained free pieces in each bucket so that all free places in the
same page are in consecutive order in the chain */
void tidyfreeheap(){
int bucket=0,amt=8,pagesize=getpagesize(),i,j,k,n; union overhead *op;
NEXT: for(op=nextf[bucket],n=0;op;op=op->ov_next) n++;
/* n = how many free places in this bucket */
if(n>1) {union overhead *place[n]; /* NOT on the heap! */
    for(k=i=n;i>0;i--) if(k) for(k=0,j=1;j<=i;j++) if(place[j-1]>place[j]) {
        k=1; op=place[j-1]; place[j-1]=place[j]; place[j]=op;} /* sort */
    nextf[bucket]=place[0];
    for(i=0;i<n-1;i++) place[i]->ov_next=place[i+1]; place[n-1]->ov_next=0;}
bucket++; amt<<1; if(amt<pagesize) goto NEXT;}
/*-----*/
  How much is this likely to help?