Patent ID: 7376684

Claim:
A method for an efficient sweep of a memory heap, comprising: distributing a bit vector comprising a plurality of bits of said memory heap among a plurality of sections; scanning each separate section of said plurality of sections of said bit vector in parallel with one from among a plurality of helper threads by: incrementing a separate counter to indicate a number of unmarked bits in an initial consecutive sequence of unmarked bits within said separate section until an end of said separate section is reached or a marked bit is detected; setting a separate prefix value equal to said separate counter, wherein said separate prefix value indicates a number of potentially free bits at the beginning of said separate section; responsive to detecting a marked bit, scanning said separate section of said bit vector to count a consecutive sequence of unmarked bits reaching a sufficient length following said marked bit; responsive to detecting said count of said consecutive sequence of unmarked bits reaching said sufficient length, stopping said count of said consecutive sequence of unmarked bits and fetching a size of a marked object starting at said marked bit; and responsive to said size of said marked object exceeding a size represented by said consecutive sequence of unmarked bits, skipping a remainder of bits representing said marked object and counting a next consecutive sequence of unmarked bits indicating free space until an end of said separate section is reached or a next marked bit is detected, wherein once a marked object is identified as potentially exceeding a threshold size said scan efficiently skips said remainder of bits and continues scanning to count consecutive unmarked bits indicating free space; responsive to reaching an end of said separate section, setting a suffix value to a difference between the current number of unmarked bits following a last marked bit within said separate section and a size of an object associated with said last marked bit; and responsive to said plurality of helper threads completing scanning of said plurality of sections, collecting each separate prefix value, each separate count indicating free space, and each separate suffix value for each of said plurality of sections into a global list identifying free space for said memory heap which specifies free space that spans across a selection of said plurality of sections from each said separate prefix value and each said separate suffix value.