Browse Prior Art Database

Efficient Method for Providing Virtually Unlimited Length Arrays in Systems that Support Virtual Memory Segments

IP.com Disclosure Number: IPCOM000104846D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 122K

Publishing Venue

IBM

Related People

Campbell, DL: AUTHOR [+4]

Abstract

Programming most interesting applications requires that arrays must be used to store information to be manipulated later. For example, we have written a C program to handle menu processing. It needs arrays to hold various header lines, trailer lines and items among which the user can choose. Traditional methods require us to choose some arbitrary limit to the size of these arrays, if we want to use the efficient array operations built into most procedural languages. The problem is that a situation almost always comes up where the limit is too small. If the limit we choose is too large, the run time size of the module becomes proportionately larger. This can make undue demands on memory resources for other purposes (such as "heap" space).

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

Efficient Method for Providing Virtually Unlimited Length Arrays in Systems that Support Virtual Memory Segments

      Programming most interesting applications requires that arrays
must be used to store information to be manipulated later.  For
example, we have written a C program to handle menu processing.  It
needs arrays to hold various header lines, trailer lines and items
among which the user can choose.  Traditional methods require us to
choose some arbitrary limit to the size of these arrays, if we want
to use the efficient array operations built into most procedural
languages.  The problem is that a situation almost always comes up
where the limit is too small.  If the limit we choose is too large,
the run time size of the module becomes proportionately larger.  This
can make undue demands on memory resources for other purposes (such
as "heap" space).

      If the programming language we use supports pointers to
arbitrary blocks of memory, we can use linked lists.  However, using
linked lists adds an unnecessary level of complexity to the
programming itself as the programmer must maintain the pointers, etc.
This can be partially overcome by the use of encapsulation, i.e., by
writing functions that hide the linked-list implementation from the
programmer.  However, hiding the complexity from the programmer does
not hide it from the system.  Implementing variable-length arrays
using linked lists is relatively expensive in terms of both extending
the list and manipulating information stored in the list.  Linked
lists also require additional memory for each element in the array to
store the pointer(s) along with the data.  Allocating memory at run
time imposes additional processing overhead, especially if "garbage
collection" could occur.

      The invention disclosed here first involves the use of virtual
memory segments to provide virtually unlimited length arrays in
programs.  The method involves using a segment for each unlimited
length array that is simultaneously needed.

      This segment can be dynamically extended when necessary when
the array itself is extended.  Since the memory behaves just like any
other memory in the system, subsequent manipulations do not suffer
any perfor mance penalty.  Also, memory usage over and above that for
the elements themselves is kept low.  Only a single block of memory
need be allocated to store information about the array (detailed
below), regardless of the size of the array.

      Like the linked-list method, there is some additional
programming complexity imposed on the programmer.  We have

"encapsulated" (i.e., hidden) most of this complexity through a set
of abstract functions:

1.  CreateArray -
       This function is used to allocate a memory segment and
    associate it
       with a variable length array.  It returns  array information
    that
       includes the associated memory segment identifier and the
    curr...