Storing more information , while preserving memory alignment in bitvectors that map objects
Original Publication Date: 2002-Aug-16
Included in the Prior Art Database: 2003-Jun-21
Disclosed is a mapping algorithm for storing more information on bit vectors, using additional properties of the mapped objects. The algorithm can save both memory and memory operations (C&S commands). In many types of heap usage, one needs to add attributes to objects, where each object has a fixed number of attributes , denoted by the letter k. One way to do this is by adding fields inside the objects (degragates access time). An alternative is to use an additional structure, which provides faster access and usually consumes less memory. Typically, such a data structure is a bit array, in which each bit maps to a possible start of an object in the heap. Such data structures are called bitvectors . For example, many garbage collectors use the markbits or allocbits bitvectors. In such environments, the object cannot start at any given location on the heap, but must obey some memory granularity restrictions, namely each object must start at an aligned address. The level of alignment (4 bytes, 8 bytes, 16 bytes, etc.) is called the granularity of alignment, or slotSize of an object. Usually, the object is also of a minimal size minSize ), and by definition is not less than slotSize . When minSize is bigger than slotSize, it is usually defined to be a multiple of slotSize. We may therefore define a factor minSlotsPerObject , where slotSize minSlotsPerObject minSize . Our mapping is applicable only when there exists some constant c , a power of 2, such that minSlotsPerObject c k . The applications using such bitvectors may be multi-threaded, and attempt to update these vectors in a multi-threaded, safe, and efficient manner. This is usually done by using a lightweight atomic operation, such as Compare and Swap C&S ), which can simultaneously change all the bits in a memory word (a memory word is usually 32 bits in size). C&S is atomic in the sense that it gets as input both the previous value and the next value of the memory word. The C&S operation can change the memory word only from the old value to the new value. If the original value was different, then the C&S operation does nothing and returns a failure value.