Memory-block coalescing based on run-time demand monitoring

A storage medium containing instructions readable, by a computer system that makes allocation requests, to configure the computer system to operate as an allocator that:

• A) maintains an inventory of memory blocks available for dynamic allocation;
• B) for each of a plurality of size ranges, derives a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
• C) in response to release requests that specify respective memory blocks, adds those memory blocks to the inventory, whereby memory-block runs occur when the release requests specify memory blocks adjacent to memory blocks already in the inventory;
• D) for each of at least some groups of memory blocks within a memory-block run, makes a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated;
• E) coalesces such groups of memory blocks into composite memory blocks only upon a positive outcome of the coalescing decision made therefor;
• and
• F) in response to at least some allocation requests, allocates such composite memory blocks.

A computer system that makes allocation requests, includes computer memory, and comprises:

• A) memory locations, included in the computer memory, that contain instructions directing the computer system to maintain an inventory of memory blocks available for dynamic allocation;
• B) memory locations, included in the computer memory, that contain instructions directing the computer system to respond to release requests specifying respective memory blocks by adding those memory blocks to the inventory;
• C) memory locations, included in the computer memory, that contain instructions directing the computer system to add those memory blocks to the inventory in response to release requests that specify respective memory blocks, whereby memory-block runs occur when the release requests specify memory blocks adjacent to memory blocks already in the inventory;
• D) memory locations, included in the computer memory, that contain instructions directing the computer system to make a coalescing decision, for each of at least some groups of memory blocks within a memory-block run, that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated;
• E) memory locations, included in the computer memory, that contain instructions directing the computer system to coalesce such groups of memory blocks into a composite memory blocks only upon a positive outcome of the coalescing decision made therefor;
• and
• F) memory locations, included in the computer memory, that contain instructions directing the computer system to respond to at least some allocation requests by allocating such composite memory blocks.

A computer signal representing sequences of instructions that, when executed by a computer system, cause it to operate as an allocator that:

• A) maintains an inventory of memory blocks available for dynamic allocation;
• B) for each of a plurality of size ranges, derives a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
• C) in response to release requests that specify respective memory blocks, adds those memory blocks to the inventory, whereby memory-block runs occur when the release requests specify memory blocks adjacent to memory blocks already in the inventory;
• D) for each of at least some groups of memory blocks within a memory-block run, makes a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated;
• E) coalesces such groups of memory blocks into composite memory blocks only upon a positive outcome of the coalescing decision made therefor;
• and
• F) in response to at least some allocation requests, allocates such composite memory blocks.

A computer system that makes allocation requests, includes computer memory, and includes:

• A) means for maintaining an inventory of memory blocks available for dynamic allocation;
• B) means for deriving, for each of a plurality of size ranges, a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
• C) means for, in response to release requests that specify respective memory blocks, adding those memory blocks to the inventory, whereby memory-block runs occur when the release requests specify memory blocks adjacent to memory blocks already in the inventory;
• D) means for making, for each of at least some groups of memory blocks within a memory-block run, a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated;
• E) means for coalescing such groups of memory blocks into composite memory blocks only upon a positive outcome of the coalescing decision made therefor;
• and
• F) means for allocating such composite memory blocks in response to at least some allocation requests.