Date: Thu, 15 Sep 94 12:14:13 EDT
From: peprbv AT cfa0 DOT harvard DOT edu (Bob Babcock)
To: djgpp AT sun DOT soe DOT clarkson DOT edu
Subject: GO32 paging algorithm
Reply-To: babcock AT cfa DOT harvard DOT edu

When GO32 has to kick a page out of memory to make room for another one, how
does it decide what gets swapped out?  I ask because I have a program which
seems to interact badly with the paging algorithm.

I'm sorting a disk catalog with qsort by permuting an index array.
  250,000 records sort in 1 minute without paging
  360,000 records sort in 20 minutes with continuous paging (40 minutes if
    swapping to a compressed partition)

If I sort the data in two equal halves, then merge the two halves, the two
sorts take a total of 3 minutes while the merge takes 8 minutes.  Everything
here is done in (virtual) memory.  The individual sorts definitely fit in
memory.  I can see the disk activity as everything gets paged in, then a
period of inactivity until the next step causes more paging.  Also, the data
selection pass which runs through all the data once seems to take unusually
long, about 80 seconds.

The question is, why does the merge take so long?  I might not be doing it
optimally, but when I am not paging, the two part sort plus merge actually
takes 5-10% less time than sorting everything at once so I don't think I
coded it too badly.  My suspicion is that some memory is getting repeatedly
shuffled between disk and RAM.  There is a brief discussion of paging in
internal.doc, but I couldn't find anything about the paging algorithm.