System and hardware module for incremental real time garbage collection and memory management

• US 5,560,003 A
• Filed: 12/21/1992
• Issued: 09/24/1996
• Est. Priority Date: 12/21/1992
• Status: Expired due to Term

• Current Assignee: Aonix
• Original Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Inventors: Schmidt, William, Nilsen, Kelvin D.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US07/994,517
• Time in Patent Office: 1,373 Days
• Field of Search: 395/425, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence

Abstract

The garbage-collecting memory module (GCMM) functions much like traditional memory in a computer system, thereby permitting the invention to be utilized with a wide variety of computers. It differs from traditional memory in that it automatically cleanses itself of garbage while functioning as traditional memory without causing excessive delays in the execution of application programs by an associated computer. The GCMM can be designed to interface with a computer system via a traditional memory bus and to communicate with the central processing unit (CPU) of the computer using standard communication protocols. The GCMM is comprised of a memory, a means for communicating with the CPU, and a garbage-collecting control unit. The garbage-collecting control unit gives top priority to satisfying the computer'"'"'s requests for memory services. The collection of garbage takes place during the intervals between memory service requests. Garbage collection is accomplished by copying live objects that are stored in one region of memory to a second region thereby leaving dead objects behind in the first region. When the copying process has been completed, the dead objects are disposed of, and the garbage-collecting process continues with the copying of live objects in the second region back to the first. An up-to-date list of live objects is maintained by the CPU and forwarded to the GCMM at the start of each garbage-collection cycle.

Claims

1. A garbage-collecting memory module (GCMM) for use with a computer system having one or more digital processors, said digital processor(s) maintaining list(s) of source descriptors pointing to regions of memory in said GCMM containing live objects, said GCMM comprising:

a memory for the storage of objects;

a means for communicating with said digital processor(s);

a garbage-collecting control unit which (1) allocates space for and stores an object in said memory upon request by one of said digital processor(s), (2) causes an object to be retrieved from said memory and returned to one of said digital processor(s) upon request, and (3) collects garbage from said memory utilizing said source descriptors supplied by said digital processor(s).

2. The garbage-collecting memory module of claim 1 wherein:

said memory comprises a from-space region and a to-space region for the storage of objects, a designated word of each of said objects being a header that specifies the size of said object and whether said object contains descriptors;

said garbage collecting takes place in cycles, the names and functions of said from-space and to-space regions being interchanged at the start of a garbage-collection cycle, new objects being allocated space in to-space during each of said garbage-collecting cycles, said from-space containing both live and dead objects at the start of a garbage-collecting cycle, said to-space being initialized to contain no objects at the start of a garbage-collection cycle;

said garbage-collecting control unit collects garbage by obtaining said source descriptors from said computer system, entering the objects to which said source descriptors point and slice regions containing data belonging to said objects into a copying queue, said objects being called source-descriptor objects, allocating space in to-space for said objects and slice regions, writing a header and a from-space pointer for each of said objects and slice regions in predetermined memory cells of the to-space memory allocations of said objects and slice regions, said from-space pointers pointing to the locations of said objects and slice regions in from-space, replacing the header of each of said objects and slice regions in from-space with a forwarding pointer to the header in to-space, updating said source descriptors to point to to-space, returning the updated source descriptors to said computer system, and copying the objects and slice regions in said copying queue from from-space to to-space when said GCMM is not performing nor been requested to perform memory services for said computer system.

3. The garbage-collecting memory module of claim 2 wherein the objects stored in said memory include weak-pointer objects, a weak-pointer object being an object containing a weak pointer, objects referenced only by weak pointers being garbage, weak-pointer objects being distinguishable by said GCMM from other objects, said weak-pointer objects being entered into a weak-pointer object postprocessing (WPOP) queue after being entered into said copying queue, postprocessing of the objects in the WPOP queue being performed after all objects in said copying queue have been copied, postprocessing of a weak-pointer object consisting of either (1) updating the weak pointer to reflect the referenced object'"'"'s new location in to-space if the object has been copied into to-space or (2) overwriting the weak pointer with 0 in the weak-pointer field if the object has not been copied into to-space.

4. The garbage-collecting memory module of claim 2 wherein said garbage collecting delays the storage of objects by at most 30 memory cycles, delays the retrieval of objects by at most 50 memory cycles, and delays the allocation of objects near the start of a garbage-collection cycle by at most 25 memory cycles times the number of said source descriptors maintained by said digital processor(s).

5. The garbage-collecting memory module of claim 2 wherein said garbage-collecting control unit identifies descriptors resident within objects in said copying queue, said descriptors being called resident descriptors, adds the objects to which said resident descriptors point to said copying queue unless said resident-descriptor objects have already been copied or placed in said copying queue, allocates space in to-space for said objects, writes a header and a from-space pointer for each of said objects in predetermined memory cells of the to-space memory allocations of said objects, replaces the header of each of said objects in from-space with a forwarding pointer to the header in to-space, and updates said resident descriptors to point to to-space.

6. The garbage-collecting memory module of claim 5 wherein said source-descriptor objects include only those weak-pointer objects from which the data fields are fetched by one of said digital processor(s) during garbage collection, a weak-pointer object being an object containing a weak pointer, objects referenced only by weak pointers being garbage, weak-pointer objects being distinguishable by said GCMM from other objects.

7. The garbage-collecting memory module of claim 6 wherein said digital processor(s) may enquire into the value of a weak pointer and the status of the object referenced by the weak pointer without causing said weak-pointer objects to be included with said source-descriptor objects.

8. The garbage-collecting memory module of claim 5 wherein a slice region comprises a header and a plurality of subregions, all subregions except the first and last having the same number of memory cells, the sum of the numbers of memory cells in the first and last subregions being equal to the number of memory cells in each of the other subregions, said garbage-collecting control unit placing each copied slice object in a scanning queue, entering initial values for a slice region control block into the former slice region in from-space for each slice region copied to to-space, and temporarily replacing the slice region'"'"'s title in to-space with a pointer to said slice region control block in from-space, said slice region control block consisting of a pointer to the slice region in to-space, a number specifying the number of memory cells occupied by the slice region, a pointer to the slice region control block for the previous slice region copied, and a plurality of subregion control blocks, each subregion control block consisting of a first-cell pointer to the first memory cell referenced by slice objects pointing into said subregion and a length which, when added to said pointer, corresponds to the last memory cell occupied by any slice object pointing into said subregion, said garbage-collecting control unit scanning the slice objects in said scanning queue after said copying queue empties and postprocessing said slice region control blocks after said scanning queue empties, said scanning resulting in the entry of final values in said slice region control blocks for each slice region referenced by a slice object in said scanning queue and the restoration of the title of each slice region following the entry of final values in the associated slice region control block, said postprocessing resulting in the examination of each slice region control block for garbage-containing memory regions, and the separation of slice regions having garbage-containing memory regions into multiple slice regions provided said garbage-containing slice regions are large enough to accept slice region headers.

9. The garbage-collecting memory module of claim 8 wherein the number of memory cells in said first subregion is changed at the start of each garbage-collection cycle.

10. The garbage-collecting memory module of claim 8 wherein said garbage-collecting control unit includes an object space manager for from-space and an object space manager for to-space, the object space manager for the region of memory called to-space generating and storing an object locator code for each memory cell allocated to an object, said object locator code being retrievable by said garbage-collecting control unit and translatable into the address of the memory cell in which said object header is located.

11. The garbage-collecting memory module of claim 10 wherein each of said memory regions contains L₁ memory cells, the individual memory cells being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, L₁ having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to L₁, an object being allocated memory cells from S₁ to S₂, each of said object space managers comprising:

an object space manager memory;

an encoder which generates an object locator code [M(S), S₁ modulo N_M(S) ] for each memory cell S in the range S₁ to S₂, S₁ and S₂ being inputs to said encoder, S₁ being the memory cell occupied by the header of the object, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), INT() being the integer portion of the quantity in parentheses, said object locator code being outputted to said object space manager memory for storage;

an object locator which accepts a memory cell address S allocated to said object as input, retrieves the object locator code from said object space manager memory, and produces said S₁ as output, S₁ being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S)).

12. The garbage-collecting memory module of claim 8 wherein said garbage-collecting control unit includes a plurality of from-space and a plurality of to-space object space managers, said from-space object space managers being assigned contiguous regions of equal size of from-space, said to-space object space managers being assigned contiguous regions of equal size of to-space, an object space manager generating and storing an object locator code for each memory cell allocated to an object in its assigned region, said object locator code being retrievable by said garbage-collecting control unit and translatable into the address of the memory cell in which said object header is located.

13. The garbage-collecting memory module of claim 12 wherein said from-space and to-space memory regions each contain L₁ memory cells, the individual memory cells being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, the number of object space managers for each of the two regions being equal to L₁ /F, F being a submultiple of L₁, the object space managers being represented by the integers from 0 to L₁ /F-1, a from-space or to-space memory cell L being assigned to object space manager INT(L/F) where INT() is the integer portion of the quantity in parentheses, F having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to F, an object being allocated memory cells from S₁ to S₂, an object space manager comprising:

an object space manager memory;

an encoder which generates an object locator code [M(S), S₁ modulo N_M(S) ] for each from-space or to-space memory cell S assigned to said object space manager and in the range S₁ to S₂, S₁ and S₂ being inputs to said encoder, S₁ being the memory cell occupied by the header of the object, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), said object locator code being [Z, S₁ modulo F] if INT(S₁ /F) is less than INT(S/F), Z being the difference between INT(S₁ /F) and INT(S/F), said object locator code being outputted to said object space manager memory for storage;

an object locator which accepts a memory cell address S allocated to said object as input, S being within said object space manager'"'"'s assigned region of memory, retrieves the object locator code from said object space manager memory, and produces said S₁ as output, S₁ being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S)) if the first term of said object locator code is a positive integer, S₁ being equal to [INT(S/F)]F+ZF+(S₁ modulo F) if the first term of said object locator code is a negative integer.

14. The garbage-collecting memory module of claim 8 wherein said scanning comprises the steps:

reading the slice region pointer of the first slice object in said scanning queue;

finding the header of the referenced slice region;

finding the control block associated with said slice region, said header being the pointer to said control block;

identifying the subregion containing the first address referenced by said slice object;

updating said first-cell pointer and said length field within the control block of said subregion;

restoring the title of said slice object and removing said slice object from said scanning queue;

updating each descriptor in said slice region referenced by said slice object to point to to-space.

15. The garbage-collecting memory module of claim 8 wherein said postprocessing comprises the steps:

searching said subregion control blocks from first to last for contiguous segments of live data;

overwriting the memory preceding each contiguous segment of live data found with an appropriate slice data header.

16. The garbage-collecting memory module of claim 2 wherein said garbage-collecting control unit includes a from-space and a to-space object space manager, each of said object space managers generating and storing an object locator code for each memory cell occupied by an object, said object locator code being retrievable by said garbage-collecting control unit and translatable into the address of the memory cell in which said object header is located.

17. The garbage-collecting memory module of claim 16 wherein each of said memory regions contains L₁ memory cells, the individual memory cells being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, L₁ having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to L₁, an object being allocated memory cells from S₁ to S₂, each of said object space managers comprising:

an object space manager memory;

an encoder which generates an object locator code [M(S), S₁ modulo N_M(S) ] for each memory cell S in the range S₁ to S₂ allocated to said object, S₁ and S₂ being inputs to said encoder, S₁ being the memory cell occupied by the header of the object, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), INT() being the integer portion of the quantity in parentheses, said object locator code being outputted to said object space manager memory for storage;

an object locator which accepts a memory cell number S allocated to said object as input, retrieves the object locator code [M(S), S₁ modulo N_M(S) ] from said object space manager memory, and produces said S₁ as output, S₁ being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S)).

18. The garbage-collecting memory module of claim 2 wherein said garbage-collecting control unit includes a plurality of from-space and a plurality of to-space object space managers, said from-space object space managers being assigned contiguous regions of equal size of from-space, said to-space object space managers being assigned contiguous regions of equal size of to-space, an object space manager generating and storing an object locator code for each memory cell occupied by an object in its assigned region, said object locator code being retrievable by said garbage-collecting control unit and translatable into the address of the memory cell in which said object header is located.

19. The garbage-collecting memory module of claim 18 wherein said from-space and to-space memory regions each contains L₁ memory cells, the individual memory cells being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, the number of from-space object space managers and the number of to-space object space managers each being equal to L₁ /F, F being a submultiple of L₁, the object space managers being represented by the integers from 0 to (L₁ /F)-1, a from-space or to-space memory cell L being assigned to object space manager INT(L/F) where INT() is the integer portion of the quantity in parentheses, the quantity F having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to F, an object being allocated memory cells from S₁ to S₂, an object space manager comprising:

an object space manager memory;

an encoder which generates an object locator code [M(S), S₁ modulo N_M(S) ] for each from-space or to-space memory cell S assigned to said object space manager and in the range S₁ to S₂, S₁ and S₂ being inputs to said encoder, S₁ being the memory cell occupied by the header of the object, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), said object locator code being [Z, S₁ modulo F] if INT(S₁ /F) is less than INT(S/F), Z being the difference between INT(S₁ /F) and INT(S/F), said object locator code being outputted to said object space manager memory for storage;

an object locator which accepts a memory cell number S allocated to said object as input, S being within said object space manager'"'"'s assigned region of memory, retrieves the object locator code from said object space manager memory, and produces said S₁ as output, S₁ being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S)) if the first term of said object locator code is a positive integer, S₁ being equal to [INT(S/F)]F+ZF+(S₁ modulo F) if the first term of said object locator code is a negative integer.

20. The garbage-collecting memory module of claim 2 wherein said garbage-collecting control unit maintains the rate of memory allocation for new objects at a level equal to or less than the rate of garbage collection.

21. The garbage-collecting memory module of claim 20 wherein said garbage-collecting control unit includes a ScanBalance register for monitoring the rate of garbage collection vis a vis the rate of memory allocations for new objects, the contents of said register being initialized to 0 at the start of a garbage-collecting cycle, said register being decremented by one for each operation performed on a word in memory in connection with said garbage collection, said register being incremented by 2 nK for each allocation of memory for a new n-word object, K being a constant, the quantity 2 nK being the number of garbage-collection operations that must be performed to collect n words of garbage, said garbage-collecting control unit making a memory allocation for a new object only if said allocation will not cause the contents of said register to exceed 0.

22. A process for collecting garbage in a memory and providing memory services to a computer system, said memory comprising a from-space region and a to-space region for the storage of objects, a designated word of each object being a header that specifies the size of said object and whether said object contains descriptors, said computer system maintaining a list of source descriptors pointing to regions of said memory containing live objects, said process comprising the steps:

performing a memory service at the request of said computer system, said memory service consisting of allocating space for an object in said to-space region of memory;

performing a memory service at the request of said computer system, said memory service consisting of storing an object in said to-space region of memory;

performing a memory service at the request of said computer system, said memory service consisting of retrieving an object from memory and returning said object to said computer system;

obtaining said source descriptors from said computer system;

entering the objects to which said source descriptors point and slice regions containing data belonging to said objects into a copying queue, said objects being called source-descriptor objects;

allocating space in to-space for said objects and slice regions;

writing a header and a from-space pointer for each of said objects and slice regions in predetermined memory cells of the to-space memory allocations of said objects and slice regions, said from-space pointers pointing to the locations of said objects and slice regions in from-space;

replacing the header of each of said objects and slice regions in from-space with a forwarding pointer to the header in to-space;

updating said source descriptors to point to to-space;

returning the updated source descriptors to said computer system;

copying the objects and slice regions in the copying queue from from-space to to-space when not performing or requested to perform memory services for said computer system.

23. The process of claim 22 wherein the objects stored in said memory include weak-pointer objects, a weak-pointer object being an object containing a weak pointer, objects referenced only by weak pointers being garbage, weak-pointer objects being distinguishable from other objects, said process comprising the additional steps:

entering weak-pointer objects into a weak-pointer object postprocessing (WPOP) queue when weak-pointer objects are entered into said copying queue;

postprocessing of the objects in the WPOP queue, said postprocessing being performed after all objects in said copying queue have been copied, postprocessing of a weak-pointer object consisting of either (1) updating the weak pointer to reflect the referenced object'"'"'s new location in to-space if the object has been copied into to-space or (2) overwriting the weak pointer with 0 in the weak-pointer field if the object has not been copied into to-space.

24. The process of claim 22 wherein each word of an object has a tag that identifies the word as either a descriptor or terminal word, said process comprising the additional steps:

identifying the descriptors resident within objects in the copying queue, said descriptors being called resident descriptors, the identification being made as the objects are copied;

adding the objects to which said resident descriptors point to said copying queue, said objects being called resident-descriptor objects;

allocating space in to-space for said resident-descriptor objects;

updating said resident descriptors to point to to-space.

25. An electronic circuit for practicing the process of claim 24.

26. The process of claim 24 wherein said source-descriptor objects include only those weak-pointer objects from which the data fields are fetched by said computer system during garbage collection, a weak-pointer object being an object containing a weak pointer, objects referenced only by weak pointers being garbage, weak-pointer objects being distinguishable from other objects.

27. The garbage-collecting memory module of claim 26 wherein said computer system may enquire into the value of a weak pointer and the status of the object referenced by the weak pointer without causing said weak-pointer objects to be included with said source-descriptor objects.

28. The process of claim 24 wherein said updating step for each of said resident descriptors comprises the steps:

obtaining the pointer to the header of the resident-descriptor object;

calculating the to-space location of the resident descriptor by adding said header to the difference in said resident descriptor and said header pointer.

29. The process of claim 24 comprising the additional steps:

generating an object locator code [M(S), S₁ modulo N_M(S) ] for each memory cell S in the range S₁ to S₂ allocated to an object entering said copying queue, S₁ being the memory cell occupied by the header of the object, said from-space and to-space regions of memory each containing L₁ memory cells, the individual memory cells in each of said regions being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, L₁ having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to L₁, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), INT() being the integer portion of the quantity in parentheses;

saving said object locator code.

30. The process of claim 29 wherein said updating step for each of said resident descriptors comprises the steps:

obtaining the pointer to the header of a resident-descriptor object;

calculating the to-space location of said resident descriptor by adding said header to the difference in said resident descriptor and said header pointer.

31. The process of claim 30 wherein said header pointer obtaining step comprises the steps:

translating the resident descriptor into the memory cell number S;

retrieving the object locator code corresponding to S;

decoding the object locator code into the memory cell number containing the header of the resident-descriptor object, said memory cell number being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S));

translating said header memory cell number into said header pointer.

32. The process of claim 24 comprising the additional steps:

generating an object locator code [M(S), S₁ modulo N_M(S) ] for each memory cell S in the range S₁ to S₂ allocated to an object entering said copying queue, S₁ being the first word of said object, said from-space and to-space regions of memory each containing L₁ memory cells, the individual memory cells in each of said regions being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, each of said regions consisting of L₁ /F subregions numbered from 0 to L₁ /F-1, each of said subregions having F memory cells, F being a submultiple of L₁, a memory cell L being located in subregion INT(L/F) where INT() is the integer portion of the quantity in parentheses, F having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to F, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), said object locator code being [Z, S₁ modulo F] if INT(S₁ /F) is less than INT(S/F), Z being the difference between INT(S₁ /F) and INT(S/F);

saving said object locator code.

33. The process of claim 32 wherein said updating step for each of said resident descriptors comprises the steps:

obtaining the pointer to the header of a resident-descriptor object;

calculating the to-space location of said resident descriptor by adding said header to the difference in said resident descriptor and said header pointer.

34. The process of claim 33 wherein said header pointer obtaining step comprises the steps:

translating the resident descriptor into the memory cell number S;

retrieving the object locator code corresponding to S;

decoding the object locator code into the memory cell number containing the header of the resident-descriptor object, said memory cell number being equal to [INT(S/N_M(S))]NM(S)+(S₁ modulo N_M(S)) if the first term of said object locator code is a positive integer, said memory cell number being equal to [INT(S/F)]F+ZF+(S₁ modulo F) if the first term of said object locator code is a negative integer;

translating said first-word memory cell number into said header pointer.

35. An electronic circuit for practicing the process of claim 34.

36. The process of claim 24 comprising the additional step:

generating and saving an object locator code for each object and slice region added to said copying queue, said object locator code enabling the address of any memory cell within the memory allocation of an object or slice region to be decoded into the number of the memory cell in which the header of said object or slice region is located.

37. The process of claim 36 wherein a slice region comprises a header and a plurality of subregions, all subregions except the first and last having the same number of memory cells, the sum of the numbers of memory cells in the first and last subregions being equal to the number of memory cells in each of the other subregions, said process comprising the additional steps:

placing each copied slice object in a scanning queue;

entering initial values for a slice region control block into the slice region in from-space for each copied slice region and temporarily replacing the slice region'"'"'s title in to-space with a pointer to said slice region control block, said slice region control block consisting of a pointer to the slice region in to-space, a number specifying the number of memory cells occupied by the slice region, a pointer to the slice region control block for the next slice region copied, and a plurality of subregion control blocks, each subregion control block consisting of a first-cell pointer to the first memory cell referenced by slice objects pointing into said subregion and a length which, when added to said pointer, corresponds to the last memory cell occupied by any slice object pointing into said subregion;

scanning the slice objects in said scanning queue after said copying queue empties, said scanning resulting in the entry of final values in said slice region control blocks for each slice region referenced by a slice object in said scanning queue and the restoration of the title of each slice region following the entry of final values in the associated slice region control block;

postprocessing said slice region control blocks after said scanning queue empties, said postprocessing resulting in the examination of each slice region control block for garbage-containing memory regions and the separation of slice regions having garbage-containing memory regions into multiple slice regions provided said garbage-containing slice regions are large enough to accept slice region headers.

38. An electronic circuit for practicing the process of claim 37.

39. The process of claim 37 comprising the additional step:

changing the number of memory cells in said first subregion at the start of each garbage-collection cycle.

40. The process of claim 37 wherein said object locator code is [M(S), S₁ modulo N_M(S) ] for each memory cell S in the range S₁ to S₂ allocated to a slice region entering said copying queue, S₁ being the memory cell occupied by the header of the slice region, said from-space and to-space regions of memory each containing L₁ memory cells, the individual memory cells in each of said regions being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, L₁ having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to L₁, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), INT() being the integer portion of the quantity in parentheses.

41. The process of claim 40 wherein said scanning step includes the steps:

reading the slice region pointer of the first slice object in said scanning queue;

translating said slice region pointer into a memory cell number S in the referenced slice region;

retrieving the object locator code corresponding to S;

decoding the object locator code into the memory cell number containing the header of said slice region, said memory cell number being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S));

translating said header memory cell number into a pointer to said slice region header.

42. The process of claim 37 wherein said object locator code is [M(S), S₁ modulo NM(S)] for each memory cell S in the range S₁ to S₂ allocated to a slice region entering said copying queue, S₁ being the memory cell occupied by the header of the slice region, said from-space and to-space regions of memory each containing L₁ memory cells, the individual memory cells in each of said regions being represented by the integers from 0 to L₁ -1, the addresses of the individual memory cells being the memory cell integers plus an integer offset, said offset being different for from-space and to-space, the difference in offsets for the two regions of memory being equal to or greater than L₁, each of said regions consisting of L₁ /F subregions numbered from 0 to L₁ /F-1, each of said subregions having F memory cells, F being a submultiple of L₁, a memory cell L being located in subregion INT(L/F) where INT() is the integer portion of the quantity in parentheses, F having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to F, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), said object locator code being [Z, S₁ modulo F] if INT(S₁ /F) is less than INT(S/F).

43. An electronic circuit for practicing the process of claim 42.

44. The process of claim 42 wherein said scanning step includes the steps:

reading the slice region pointer of the first slice object in said scanning queue;

translating said slice region pointer into a memory cell number S in the referenced slice region;

retrieving the object locator code corresponding to S;

decoding the object locator code into the memory cell number containing the header of said slice region, said memory cell number being equal to [INT(S/N_M(S))]N_M(S) +(S₁ modulo N_M(S)) if the first term of said object locator code is a positive integer, said memory cell number being equal to [INT(S/F)]F+ZF+(S₁ modulo F) if the first term of said object locator code is a negative integer;

translating said header memory cell number into a pointer to said slice region header.

45. The process of claim 37 wherein for each slice object in said scanning queue said scanning step includes the steps:

reading the slice region pointer of the first slice object in said scanning queue;

finding the header of the referenced slice region;

finding the control block associated with said slice region, said header being the pointer to said control block;

identifying the subregion

containing the first address referenced by said slice object;

updating said first-cell pointer and said length field within the control block of said subregion;

restoring the title of said slice object and removing said slice object from said scanning queue;

updating each descriptor in said slice region referenced by said slice object to point to to-space.

46. The process of claim 37 wherein said postprocessing step comprises the steps:

searching said subregion control blocks from first to last for contiguous segments of live data;

overwriting the memory preceding each contiguous segment of live data found with an appropriate slice data header.

47. The process of claim 22 comprising the additional step:

maintaining the rate of allocating memory for new objects in to-space equal to or less than the rate at which garbage is collected.

48. The process of claim 47 wherein said maintaining step comprises the steps:

counting downward in unit increments from 0 at the beginning of a garbage-collection cycle for each operation performed on a word in memory while collecting garbage;

counting upward by a 2 nK increment each time a memory allocation for a new n-word object is made, K being a predetermined constant, the quantity 2 nK being the number of garbage-collection operations that must be performed to collect n words of garbage;

enabling memory allocation for new objects only if the count that results from counting upward and downward is less than or equal to 0.