Browse Prior Art Database

Storing more information , while preserving memory alignment in bitvectors that map objects

IP.com Disclosure Number: IPCOM000015821D
Original Publication Date: 2002-Aug-16
Included in the Prior Art Database: 2003-Jun-21
Document File: 2 page(s) / 70K

Publishing Venue

IBM

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

  Storing more information , while preserving memory alignment in bitvectors that map objects

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.

    The proposed mapping function maps each one of k attributes of object o into a bitvector index. heapBase is the first address of our memory heap (assuming a continuous memory heap). For the i'th attribute of object obj at address objAddress, the index is:
indexAddress(objAddress, i) = ((objAddress - heapBase) / slotSize) xor i

    This mapping ensures several necessary beneficial properties: Each live object is mapped into k unique indices (i.e., no two live objects have some property that is m...