Browse Prior Art Database

Efficient In-Place Reordering of Virtual Memory Data

IP.com Disclosure Number: IPCOM000113145D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 80K

Publishing Venue

IBM

Related People

Robinson, JT: AUTHOR

Abstract

Disclosed is a method for efficient in-place reordering of N records residing in virtual memory using page table modification.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient In-Place Reordering of Virtual Memory Data

      Disclosed is a method for efficient in-place reordering of N
records residing in virtual memory using page table modification.

This method requires at most 2N-P record moves (where P is the number
of pages occupied by the N records), whereas 3(N-1) record moves are
required by a straightforward method using exchanges.

      Consider the problem of reordering a collection of records
residing in virtual memory, for example in order to sort the records,
merge two or more ordered subsets of the records, etc.  Furthermore,
assume that it is necessary, due to (1) the size and number of
records and (2) available memory space, to reorder the records
in-place, i.e., move records from one existing record location to
another using only a small additional amount of memory.  A
straightforward way to do this is via exchanges using a single record
buffer to temporarily hold records.  Using this method, records are
moved to their final position in order by successively exchanging the
next record to be moved with whatever record is currently in its
target position.  If there are N records, this straightforward method
requires moving records 3(N-1) times.  A more efficient method for
use in virtual memory systems will now be described.

      For simplicity, assume that record size evenly divides page
size, and that the first record starts on a page boundary.  The
larger the record size, the more efficient the method described here
will be.  Therefore, in order to have a concrete example, assume that
records are 1024 bytes long, and that page size is 4096 bytes (thus
there are 4 records per page).  The general case, in which records
are of abitrary size, not necessarily on page boundaries, etc., can
be developed in a straightforward way by refining the method
presented here for this particular example.

      The method is illustrated in the Figure.  Assume that the first
four records in order sh...