Method and apparatus for memory allocation in a multi-threaded virtual machine

A method for allocating memory shared by multiple threads in a multi-threaded computing system, the method comprising:

• partitioning the shared memory into a plurality of blocks;
• grouping the multiple threads into at least a first group of threads and a second group of threads, wherein grouping the multiple threads into the first group and the second group includes identifying a particular thread selected from the multiple threads and determining whether the particular thread is a fast allocating thread, wherein when it is determined that the particular thread is fast allocating, the particular thread is grouped into the first group and the particular thread attempts to allocate objects relatively often, and wherein when it is determined that the particular thread is not fast allocating, the particular thread does not attempt to allocate objects relatively often and is grouped into the second group;
• and
• allocating a first block selected from the plurality of blocks to a thread selected from the multiple threads, the selected thread being arranged to attempt to allocate an object in the selected first block, wherein allocation of the selected first block to the selected thread is based at least partially upon whether the selected thread is a part of the first group or the second group.

A method for allocating memory shared by multiple threads in a multi-threaded computing system, the method comprising:

• partitioning the shared memory into a plurality of blocks;
• grouping the multiple threads into at least a first group of threads and a second group of threads, wherein grouping the multiple threads into the first group and the second group includes identifying a particular thread selected from the multiple threads and determining whether the particular thread is a fast allocating thread, wherein determining whether the particular thread is a fast allocating thread includes determining a number of times the particular thread has caused selected blocks included in the plurality of blocks to overflow;
• and
• allocating a first block selected from the plurality of blocks to a thread selected from the multiple threads, the selected thread being arranged to attempt to allocate an object in the selected first block, wherein allocation of the selected first block to the selected thread is based at least partially upon whether the selected thread is a part of the first group or the second group.

A method for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the method comprising:

• partitioning the shared memory into a plurality of blocks;
• assigning a first block selected from the plurality of blocks as a block which is accessible to both the first thread and the second thread, wherein the first thread is arranged to attempt to allocate a first object in the first block and the second thread is arranged to attempt to allocate a second object in the first block;
• determining when the first block has overflowed;
• determining whether an attempt by the first thread to allocate the first object in the first block caused the first block to overflow when it is determined that the first block has overflowed;
• assigning a second block selected from the plurality of blocks to the first thread when it is determined that the attempt by the first thread to allocate the first object in the first block caused the first block to overflow, wherein assigning the second block to the first thread is arranged to cause the first thread to no longer attempt to allocate objects in the first block;
• determining when one of the first block and the second block have overflowed;
• assigning a third block selected from the plurality of blocks to the first thread when it is determined that the second block overflowed;
• and
• assigning the third block to the second thread and assigning a four block selected from the plurality of blocks to replace the first block when it is determined that the first block overflowed;
• and
• determining whether the plurality of blocks includes the fourth block, wherein when it is determined that the plurality of blocks includes the fourth block, the fourth block is assigned to replace the first block.

A method for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the method comprising:

• partitioning the shared memory into a plurality of blocks;
• assigning a first block selected from the plurality of blocks as a block which is accessible to both the first thread and the second thread, wherein the first thread is arranged to attempt to allocate a first object in the first block and the second thread is arranged to attempt to allocate a second object in the first block;
• determining when the first block has overflowed;
• determining whether an attempt by the first thread to allocate the first object in the first block caused the first block to overflow when it is determined that the first block has overflowed;
• assigning a second block selected from the plurality of blocks to the first thread when it is determined that the attempt by the first thread to allocate the first object in the first block caused the first block to overflow, wherein assigning the second block to the first thread is arranged to cause the first thread to no longer attempt to allocate objects in the first block;
• and
• determining whether the plurality of blocks includes the second block, wherein when it is determined that the plurality of blocks includes the second block, the second block is assigned to the first thread.

A method for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the method comprising:

• partitioning the shared memory into a plurality of blocks;
• assigning a first block selected from the plurality of blocks as a block which is accessible to both the first thread and the second thread, wherein the first thread is arranged to attempt to allocate a first object in the first block and the second thread is arranged to attempt to allocate a second object in the first block;
• determining when the first block has overflowed;
• determining whether an attempt by the first thread to allocate the first object in the first block caused the first block to overflow when it is determined that the first block has overflowed;
• assigning a second block selected from the plurality of blocks to the first thread when it is determined that the attempt by the first thread to allocate the first object in the first block caused the first block to overflow, wherein assigning the second block to the first thread is arranged to cause the first thread to no longer attempt to allocate objects in the first block;
• and
• incrementing a counter associated with the first thread when it is determined that the first thread caused the first thread to overflow, the counter being arranged to indicate when the second block is to be assigned to the first thread.

A method for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the method comprising:

• partitioning the shared memory into multiple blocks, the multiple blocks including a plurality of blocks of a first size and least one block of a second size;
• assigning a first block selected from the plurality of blocks of the first size to the first thread wherein the first thread is arranged to attempt to allocate a first object in the first block;
• assigning a second block selected from the plurality of blocks of the first size to the second thread, wherein the second thread is arranged to attempt to allocate a second object in the second block;
• determining when one of the first block and the second block has overflowed;
• determining whether a third block of the second size is available;
• assigning the third block to the first thread when it is determined that the third block is available and when it is determined that the first block has overflowed;
• and
• assigning the third block to the second thread when it is determined that the third block is available and when it is determined that the second block has overflowed wherein the first thread is not arranged to attempt to allocate objects in the second block and the second thread is not arranged to attempt to allocate objects in the first block, and wherein the second thread is not arranged to attempt to allocate objects in the third block when the third block is assigned to the first thread, and the first thread is not arranged to attempt to allocate objects in the third block when the third block is assigned to the second thread.

A method for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the method comprising:

• partitioning the shared memory into multiple blocks, the multiple blocks including a plurality of blocks of a first size and at least one block of a second size;
• assigning a first block selected from the plurality of blocks of the first size to the first thread wherein the first thread is arranged to attempt to allocate a first object in the first block;
• assigning a second block selected from the plurality of blocks of the first size to the second thread, wherein the second thread is arranged to attempt to allocate a second object in the second block;
• determining when one of the first block and the second block has overflowed;
• determining whether a third block of the second size is available;
• assigning the third block to the first thread when it is determined that the third block is available and when it is determined that the first block has overflowed;
• assigning the third block to the second thread when it is determined that the third block is available and when it is determined that the second block has overflowed;
• and
• performing a garbage collection to clear the multiple blocks when it is determined that the third block is not available.

A multi-threaded computer system including memory, a first thread, and a second thread, the memory being accessible to both the first thread and the second thread, the computer system being arranged to allocate the memory, the computer system comprising:

• a first processor associated with the first thread;
• a second processor associated with the second thread;
• a memory partitioner arranged to partition the memory into a plurality of blocks;
• a block assigner arranged to assign a first block selected from the plurality of blocks as a block which is accessible to both the first thread and the second thread, wherein the first thread is arranged to attempt to allocate a first object in the first block and the second thread is arranged to attempt to allocate a second object in the first block;
• a first determination mechanism arranged to determine when the first block has overflowed;
• a second determination mechanism arranged to determine whether an attempt by the first thread to allocate the first object in the first block caused the first block to overflow when it is determined that the first block has overflowed;
• a second block assigner arranged to assign a second block selected from the plurality of blocks to the first thread when it is determined that the attempt by the first thread to allocate the first object in the first block caused the first block to overflow, wherein assigning the second block to the first thread is arranged to cause the first thread to no longer attempt to allocate objects in the first block;
• a third determination mechanism arranged to determine whether the plurality of blocks includes the second block;
• a garbage collector arranged to free memory space associated with the first block when it is determined that the plurality of blocks does not include the second block;
• and
• a third block assigner arranged to assign a new first block selected from the plurality of blocks to be accessible to both the first thread and the second thread.

A multi-threaded computer system arranged to allocate shared memory associated with the multi-threaded computer system, the multi-threaded computer system including at least a first thread and a second thread, the multi-threaded comprising:

• a first processor, the first processor being associated with the first thread;
• a second processor, the second processor being associated with the second thread;
• a memory allocator arranged to partition the shared memory into multiple blocks, the multiple blocks including a plurality of blocks of a first size and least one block of a second size, wherein the plurality of blocks of the first size have a larger size than the at least one block of the second size;
• a first assigning mechanism arranged to assign a first block selected from the plurality of blocks of the first size to the first thread wherein the first thread is arranged to attempt to allocate a first object in the first block;
• a second assigning mechanism arranged to assign a second block selected from the plurality of blocks of the first size to the second thread, wherein the second thread is arranged to attempt to allocate a second object in the second block;
• a first determining mechanism arranged to determine when one of the first block and the second block has overflowed;
• a second determining mechanism arranged to determine whether a third block of the second size is available;
• and
• a third assigning mechanism arranged to assign the third block to the first thread when it is determined that the third block is available and when it is determined that the first block has overflowed, the third assigning mechanism further being arranged to assign the third block to the second thread when it is determined that the third block is available and when it is determined that the second block has overflowed.

A multi-threaded computer system arranged to allocate shared memory associated with the multi-threaded computer system, the multi-threaded computer system including at least a first thread and a second thread, the multi-threaded comprising:

• a first processor, the first processor being associated with the first thread;
• a second processor, the second processor being associated with the second thread;
• a memory allocator arranged to partition the shared memory into multiple blocks, the multiple blocks including a plurality of blocks of a first size and at least one block of a second size;
• a first assigning mechanism arranged to assign a first block selected from the plurality of blocks of the first size to the first thread wherein the first thread is arranged to attempt to allocate a first object in the first block;
• a second assigning mechanism arranged to assign a second block selected from the plurality of blocks of the first size to the second thread, wherein the second thread is arranged to attempt to allocate a second object in the second block;
• a first determining mechanism arranged to determine when one of the first block and the second block has overflowed;
• a second determining mechanism arranged to determine whether a third block of the second size is available;
• a third assigning mechanism arranged to assign the third block to the first thread when it is determined that the third block is available and when it is determined that the first block has overflowed, the third assigning mechanism further being arranged to assign the third block to the second thread when it is determined that the third block is available and when it is determined that the second block has overflowed;
• and
• a garbage collector arranged to clear the multiple blocks when it is determined that the third block is not available.

A computer program product for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the computer program product comprising:

• computer code for partitioning the shared memory into a plurality of blocks;
• computer code for assigning a first block selected from the plurality of blocks as a block which is accessible to both the first thread and the second thread, wherein the first thread is arranged to attempt to allocate a first object in the first block and the second thread is arranged to attempt to allocate a second object in the first block;
• computer code for determining when the first block has overflowed;
• computer code for determining whether an attempt by the first thread to allocate the first object in the first block caused the first block to overflow when it is determined that the first block has overflowed;
• computer code for assigning a second block selected from the plurality of blocks to the first thread when it is determined that the attempt by the first thread to allocate the first object in the first block caused the first block to overflow, wherein assigning the second block to the first thread is arranged to cause the first thread to no longer attempt to allocate objects in the first block;
• computer code for determining when one of the first block and the second block have overflowed;
• computer code for assigning a third block selected from the plurality of blocks to the first thread when it is determined that the second block overflowed;
• and
• computer code for assigning the third block to the second thread when it is determined that the first block overflowed;
• computer code for determining whether the plurality of blocks includes the second block;
• and
• a computer readable medium that stores the computer codes.

A computer program product for allocating shared memory in a multi-threaded computing system, the multi-threaded computing system including at least a first thread and a second thread, the computer program product comprising:

• computer code that partitions the shared memory into multiple blocks, the multiple blocks including a plurality of blocks of a first size and least one block of a second size;
• computer code that assigns a first block selected from the plurality of blocks of the first size to the first thread wherein the first thread is arranged to attempt to allocate a first object in the first block;
• computer code that assigns a second block selected from the plurality of blocks of the first size to the second thread, wherein the second thread is arranged to attempt to allocate a second object in the second block;
• computer code that determines when one of the first block and the second block has overflowed;
• computer code that determines whether a third block of the second size is available;
• computer code that assigns the third block to the first thread when it is determined that the third block is available and when it is determined that the first block has overflowed;
• computer code that assigns the third block to the second thread when it is determined that the third block is available and when it is determined that the second block has overflowed;
• computer code that determines when one of the second block and the third block has overflowed;
• computer code that assigns a new block of the second size to the first thread when it is determined that third block has overflowed;
• computer code that assigns the new block of the second size to the second thread when it is determined that the second block has overflowed;
• and
• a computer readable medium that stores the computer codes.