Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents

Memory Pool System Project

                                   BIT TABLES
                                 design.mps.bt
                                   draft doc
                                 drj 1997-03-04

    INTRODUCTION

    .readership: Any MPS developer.

    .intro: This is the design of the Bit Tables module.  A Bit Table is a linear
    array of bits.  A Bit Table of length n is indexed using an integer from 0 to
    (but not including) n.  Each bit in a Bit Table can hold either the value 0
    (aka FALSE) or 1 (aka TRUE).  A variety of operations are provided including:
    set, reset, and retrieve, individual bits; set and reset a contiguous range of
    bits; search for a contiguous range of reset bits; making a "negative image"
    copy of a range.

    HISTORY

    .history.0-3: The history for versions 0-3 is lost pending possible
    reconstruction.

    .history.4: Prepared for review.  Added full requirements section.  Made
    notation more consistent throughout.  Documented all functions.  drj 1999-04-29

    DEFINITIONS

    .def.set: Set.  Used as a verb meaning to assign the value 1 or TRUE to a bit.
    Used descriptively to denote a bit containing the value 1.  Note 1 and TRUE are
    synonyms in MPS C code (see design.mps.type(0).bool.value).

    .def.reset: Reset.  Used as a verb meaning to assign the value 0 or FALSE to a
    bit.  Used descriptively to denote a bit containing the value 0.  Note 0 and
    FALSE are synonyms in MPS C code (see design.mps.type(0).bool.value).

    [consider using "fill/empty" or "mark/clear" instead of "set/reset", set/reset
    is probably a hangover from drj's z80 hacking days -- drj 1999-04-26]

    .def.bt: Bit Table.  A Bit Table is a mapping from [0,n) to {0,1} for some n
    represented as a linear array of bits.  .def.bt.justify: They are called bit
    tables because a single bit is used to encode whether the image of a particular
    integer under the map is 0 or 1.

    .def.range: Range.  A contiguous sequence of bits in a Bit Table.  Ranges are
    typically specified as a base--limit pair where the range includes the position
    specified by the base, but excludes that specified by the limit.  The
    mathematical interval notation for half-open intervals, [base, limit), is used.

    REQUIREMENTS

    .req.bit: The storage for a Bit Table of n bits shall take no more than a small
    constant addition to the storage required for n bits.  .req.bit.why: This is so
    that clients can make some predictions about how much storage their algorithms
    use.  A small constant is allowed over the minimal for two reasons: inevitable
    implementation overheads (such as only being able to allocate storage in
    multiples of 32 bits), extra storage for robustness or speed (such as signature
    and length fields).
    .req.create: A means to create Bit Tables.  .req.create.why: Obvious.
    .req.destroy: A means to destroy Bit Tables.  .req.destroy.why: Obvious.
    .req.ops: The following operations shall be supported:
      .req.ops.get: Get.  Get the value of a bit at a specified index.
      .req.ops.set: Set.  Set a bit at a specified index.
      .req.ops.reset: Reset.  Reset a bit at a specified index.
      .req.ops.minimal.why: Get, Set, Reset, are the minimal operations.  All
    possible mappings can be created and inspected using these operations.
      .req.ops.set.range: SetRange.  Set a range of bits.  .req.ops.set.range.why:
    It's expected that clients will often want to set a range of bits; providing
    this operation allows the implementation of the BT module to make the operation
    efficient.
      .req.ops.reset.range: ResetRange.  Reset a range of bits.
    .req.ops.reset.range.why: as for SetRange, see .req.ops.set.range.why.
      .req.ops.test.range.set: IsSetRange.  Test whether a range of bits are all
    set.  .req.ops.test.range.set.why: Mostly for checking.  For example, often
    clients will know that a range they are about to reset is currently all set,
    they can use this operation to assert that fact.
      .req.ops.test.range.reset: IsResetRange.  Test whether a range of bits are
    all reset.  .req.ops.test.range.reset.why: As for IsSetRange, see
    .req.ops.test.range.set.why.
      .req.ops.find: Find a range (which we'll denote [i,j)) of at least L reset
    bits that lies in a specified subrange of the entire Bit Table.  Various find
    operations are required according to the (additional) properties of the
    required range:
        .req.ops.find.short.low: FindShortResetRange.  Of all candidate ranges,
    find the range with least j (find the leftmost range that has at least L reset
    bits and return just enough of that).  .req.ops.find.short.low.why: Required by
    client and VM arenas to allocate segments.  The arenas implement definite
    placement policies (such as lowest addressed segment first) so they need the
    lowest (or highest) range that will do.  It's not currently useful to allocate
    segments larger than the requested size, so finding a short range is
    sufficient.
        .req.ops.find.short.high: FindShortResetRangeHigh.  Of all candidate
    ranges, find the range with greatest i (find the rightmost range that has at
    least L reset bits and return just enough of that).
    .req.ops.find.short.high.why: Required by arenas to implement a specific
    segment placement policy (highest addressed segment first).
        .req.ops.find.long.low: FindLongResetRange.  Of all candidate ranges,
    identify the ranges with least i and of those find the one with greatest j
    (find the leftmost range that has at least L reset bits and return all of it).
    .req.ops.find.long.low.why: Required by the mark and sweep Pool Classes (AMS,
    AWL, LO) for allocating objects (filling a buffer).  It's more efficient to
    fill a buffer with as much memory as is conveniently possible.  There's no
    strong reason to find the lowest range but it's bound to have some beneficial
    (small) cache effect and makes the algorithm more predictable.
        .req.ops.find.long.high: FindLongResetRangeHigh.  Provided, but not
    required, see .non-req.ops.find.long.high.
      .req.ops.copy: Copy a range of bits from one Bit Table to another Bit Table .
    Various copy operations are required:
        .req.ops.copy.simple: Copy a range of bits from one Bit Table to the same
    position in another Bit Table.  .req.ops.copy.why: Required to support copying
    of the tables for the "low" segment during segment merging and splitting, for
    pools using tables (e.g. PoolClassAMS).
        .req.ops.copy.offset: Copy a range of bits from one Bit Table to an offset
    position in another Bit Table.  .req.ops.copy.why: Required to support copying
    of the tables for the "high" segment during segment merging and splitting, for
    pools which support this (currently none, as of 2000-01-17).
        .req.ops.copy.invert: Copy a range of bits from one Bit Table to the same
    position in another Bit Table inverting all the bits in the target copy.
    .req.ops.copy.invert.why: Required by colour manipulation code in PoolClassAMS
    and PoolClassLO.
    .req.speed: Operations shall take no more than a few memory operations per bit
    manipulated.  .req.speed.why: Any slower would be gratuitous.
    .req.speed.fast: The following operations shall be very fast:

    .req.speed.fast.find.short:
    FindShortResRange (the operation used to meet .req.ops.find.short.low)
    FindShortResRangeHigh (the operation used to meet .req.ops.find.short.high)

    .req.speed.fast.find.short.why: These two are used by the client arena
    (design.mps.arena.client) and the VM arena (design.mps.arena.vm) for finding
    segments in page tables.  The operation will be used sufficiently often that
    its speed will noticeably affect the overall speed of the MPS.  They will be
    called with a length equal to the number of pages in a segment.  Typical values
    of this length depend on the pool classes used and their configuration, but we
    can expect length to be small (1 to 16) usually.  We can expect the Bit Table
    to be populated densely where it is populated at all, that is set bits will
    tend to be clustered together in subranges.

    .req.speed.fast.find.long:
    FindLongResRange (the operation used to meet .req.ops.find.long.low)

    .req.speed.fast.find.long.why:
    Used in the allocator for PoolClassAWL (design.mps.poolawl(1)), PoolClassAMS
    (design.mps.poolams(2)), PoolClassEPVM (design.mps.poolepvm(0)).  Of these AWL
    and EPVM have speed requirements.  For AWL the length of range to be found will
    be the length of a Dylan table in words.  According to
    mail.tony.1999-05-05.11-36(0), only <entry-vector> objects are allocated in AWL
    (though not all <entry-vector> objects are allocated in AWL), and the mean
    length of an <entry-vector> object is 486 Words.  No data for EPVM alas.

    .req.speed.fast.other.why: We might expect mark and sweep pools to make use of
    Bit Tables, the MPS has general requirements to support efficient mark and
    sweep pools, so that imposes general speed requirements on Bit Tables.

    NON REQUIREMENTS

    The following are not requirements but the current design could support them
    with little modification or does support them.  Often they used to be
    requirements, but are no longer, or were added speculatively or experimentally
    but aren't currently used.

      .non-req.ops.test.range.same: RangesSame.  Test whether two ranges that
    occupy the same positions in different Bit Tables are the same.  This used to
    be required by PoolClassAMS, but is no longer.  Currently (1999-05-04) the
    functionality still exists.
      .non-req.ops.find.long.high: FindLongResetRangeHigh.  (see .req.ops.find) Of
    all candidate ranges, identify the ranges with greatest j and of those find the
    one with least i (find the rightmost range that has at least L reset bits and
    return all of it).  Provided for symmetry but only currently used by the BT
    tests and cbstest.c.

    BACKGROUND

    .background: Originally Bit Tables were used and implemented by PoolClassLO
    (design.mps.poollo).  It was decided to lift them out into a separate module
    when designing the Pool to manage Dylan Weak Tables which is also a mark and
    sweep pool and will make use of Bit Tables (see design.mps.poolawl).
    .background.analysis: analysis.mps.bt(0) contains some of the analysis of the
    design decisions that were and were not made in this document.

    CLIENTS

    .clients: Bit Tables are used throughout the MPS but the important uses are: In
    the client and VM arenas (design.mps.arena.client(0) and
    design.mps.arena.vm(1)) a bit table is used to record whether each page is free
    or not; several pool classes (PoolClassLO, PoolClassEPVM, PoolClassAMS) use bit
    tables to record which locations are free and also to store colour.

    OVERVIEW

    .over: Mostly, the design is as simple as possible.  The significant
    complications are iteration (see .iteration below) and searching (see
    .fun.find-res-range below) because both of these are required to be fast.

    INTERFACE

    .if.representation.abstract: A Bit Table is represented by the type BT.

    .if.declare: The module declares a type BT and a prototype for each of the
    functions below.  The type is declared in impl.h.mpmtypes, the prototypes are
    declared in impl.h.mpm.  Some of the functions are in fact implemented as
    macros in the usual way (doc.mps.ref-man.if-conv(0).macro.std).

    .if.general.index: Many of the functions specified below take indexes.  If
    otherwise unspecified an index must be in the interval [0,n) (note, up to, but
    not including, n) where n is the number of bits in the relevant Bit Table (as
    passed to the BTCreate function).  .if.general.range: Where a range is
    specified by two indexes base and limit, base, which specifies the beginning of
    the range, must be in the interval [0,n), limit, which specifies the end of the
    range, must be in the interval [1,n] (note can be n), and base must be strictly
    less than limit (empty ranges are not allowed).  Sometimes i and j are used
    instead of base and limit.

    .if.create:
    Res BTCreate(BT *btReturn, Arena arena, Count n)

    Attempts to create a table of length n in the arena control pool, putting the
    table in '*btReturn'. Returns ResOK if and only if the table is created OK.
    The initial values of the bits in the table are undefined (so the client should
    probably call BTResRange on the entire range before using the BT).  Meets
    .req.create.

    .if.destroy:
    void BTDestroy(BT t, Arena arena, Count n);

    Destroys the table t, which must have been created with BTCreate (.if.create).
    The value of argument n must be same as the value of the argument passed to
    BTCreate.  Meets .req.destroy.

    .if.size:
    size_t BTSize(Count n);

    BTSize(n) returns the number of bytes needed for a Bit Table of n bits.
    BTSize is a macro, but (BTSize)(n) will assert if n exceeds COUNT_MAX -
    MPS_WORD_WIDTH + 1.  This is used by clients that allocate storage for
    the BT themselves.  Before BTCreate and BTDestroy were implemented that
    was the only way to allocate a Bit Table, but is now deprecated.

    .if.get:
    int BTGet(BT t, Index i);

    BTGet(t, i) returns the ith bit of the table t (i.e. the image of i under the
    mapping).  Meets .req.ops.get.

    .if.set:
    void BTSet(BT t, Index i);

    BTSet(t, i) sets the ith bit of the table t (to 1).  BTGet(t, i) will now
    return 1.  Meets .req.ops.set.

    .if.res:
    void BTRes(BT t, Index i);

    BTRes(t, i) resets the ith bit of the table t (to 0).  BTGet(t, i) will now
    return 0.  Meets .req.ops.res.

    .if.set-range:
    void BTSetRange(BT t, Index base, Index limit);

    BTSetRange(t, base, limit) sets the range of bits [base, limit) in the table
    t.  BTGet(t, x) will now return 1 for base<=x<limit.  Meets .req.ops.range.set.

    .if.res-range:
    void BTResRange(BT t, Index base, Index limit);

    BTResRange(t, base, limit) resets the range of bits [base, limit) in the table
    t.  BTGet(t, x) will now return 0 for base<=x<limit.  Meets .req.ops.range.res.

    .if.test.range.set:
    Bool BTIsSetRange(BT bt, Index base, Index limit);

    Returns TRUE if all the bits in the range [base, limit) are set, FALSE
    otherwise.  Meets .req.ops.test.range.set.

    .if.test.range.reset:
    Bool BTIsResRange(BT bt, Index base, Index limit);

    Returns TRUE if all the bits in the range [base, limit) are reset, FALSE
    otherwise.  Meets .req.ops.test.range.reset.

    .if.test.range.same:
    Bool BTRangesSame(BT BTx, BT BTy, Index base, Index limit);

    returns TRUE if BTGet(BTx,i) equals BTGet(BTy,i) for i in [base, limit), and
    false otherwise.  Meets .req.ops.test.range.same

    .if.find.general: There are four functions (below) to find reset ranges.  All
    the functions have the same prototype (for symmetry):
    Bool find(Index *baseReturn, Index *limitReturn,
              BT bt,
              Index searchBase, Index searchLimit,
              Count length);

    bt is the Bit Table in which to search.  searchBase and searchLimit specify a
    subset of the Bit Table to use, the functions will only find ranges that are
    subsets of [searchBase, searchLimit) (when set *baseReturn will never be less
    than searchBase and *limitReturn will never be greater than searchLimit).
    searchBase, searchLimit specify a range that must conform to the general range
    requirements for a range [i,j), as per .if.general.range modified
    appropriately.  length is the number of contiguous reset bits to find; it must
    not be bigger than searchLimit - searchBase (that would be silly).  If a
    suitable range cannot be found the function returns FALSE (0) and leaves
    *baseReturn and *limitReturn untouched.  If a suitable range is found then the
    function returns the range's base in *baseReturn and its limit in *limitReturn
    and returns TRUE (1).

    .if.find-short-res-range:
    Bool BTFindShortResRange(Index *baseReturn, Index *limitReturn,
                             BT bt,
                             Index searchBase, Index searchLimit,
                             Count length);

    BTFindShortResRange(&base, &limit, table, searchBase, searchLimit, length)
    finds a range of reset bits in the table, starting at searchBase and working
    upwards.  This function is intended to meet .req.ops.find.short.low so it will
    find the leftmost range that will do, and never finds a range longer than the
    requested length (the intention is that it will not waste time looking).

    .if.find-short-res-range-high:
    Bool BTFindShortResRangeHigh(Index *baseReturn, Index *limitReturn,
                                 BT bt,
                                 Index searchBase, Index searchLimit,
                                 Count length);

    BTFindShortResRangeHigh(&base, &limit, table, searchBase, searchLimit, length)
    finds a range of reset bits in the table, starting at searchLimit and working
    downwards. This function is intended to meet .req.ops.find.short.high so it
    will find the rightmost range that will do, and never finds a range longer than
    the requested length.

    .if.find-long-res-range:
    Bool BTFindLongResRange(Index *baseReturn, Index *limitReturn,
                            BT bt,
                            Index searchBase, Index searchLimit,
                            Count length);

    BTFindLongResRange(&base, &limit, table, searchBase, searchLimit, length) finds
    a range of reset bits in the table, starting at searchBase and working
    upwards.  This function is intended to meet .req.ops.find.long.low so it will
    find the leftmost range that will do and returns all of that range (which can
    be longer than the requested length).

    .if.find-long-res-range-high:
    Bool BTFindLongResRangeHigh(Index *baseReturn, Index *limitReturn,
                                BT bt,
                                Index searchBase, Index searchLimit,
                                Count length);

    BTFindLongResRangeHigh(&base, &limit, table, searchBase, searchLimit, length)
    finds a range of reset bits in the table, starting at searchLimit and working
    downwards.  This function is intended to meet .req.ops.find.long.high so it
    will find the rightmost range that will do and returns all that range (which
    can be longer than the requested length).

    .if.copy-range:
    extern void BTCopyRange(BT fromBT, BT toBT, Index base, Index limit);

    overwrites the ith bit of toBT with the ith bit of fromBT, for all i in [base,
    limit).  Meets .req.ops.copy.simple.

    .if.copy-offset-range:
    extern void BTCopyOffsetRange(BT fromBT, BT toBT, Index fromBase, Index
    fromLimit, Index toBase, Index toLimit);

    overwrites the ith bit of toBT with the jth bit of fromBT, for all i in [toBase,
    toLimit) and corresponding j in [fromBase, fromLimit).  Each of these 2
    ranges must be the same size. This might be significantly less efficient than
    BTCopyRange. Meets .req.ops.copy.offset.

    .if.copy-invert-range:
    extern void BTCopyInvertRange(BT fromBT, BT toBT, Index base, Index limit);

    overwrites the ith bit of toBT with the inverse of the ith bit of fromBT, for
    all i in [base, limit).  Meets .req.ops.copy.invert.

    DETAILED DESIGN

    DataStructures

    .datastructure: Bit Tables will be represented as (a pointer to) an array of
    Words.  A plain array is used instead of the more usual design convention of
    implementing an ADT as a structure with a signature etc (see
    guide.impl.c.adt(0)).  .datastructure.words.justify: Words are used as these
    will probably map to the object that can be most efficiently accessed on any
    particular platform.  .datastructure.non-adt.justify: The usual ADT conventions
    are not followed because a) The initial design (drj) was lazy, b) Bit Tables
    are more likely to come in convenient powers of two with the extra one or two
    words overhead.  However, the loss of checking is severe.  Perhaps it would be
    better to use the usual ADT style.

    Functions

    .fun.size: BTSize.
    Since Bit Tables are an array of Words, the size of a Bit Table of n bits is
    simply the number of Words that it takes to store n bits times the number of
    bytes in a Word.  This is ceiling(n/MPS_WORD_WIDTH)*sizeof(Word).
    .fun.size.justify: Since there can be at most MPS_WORD_WIDTH-1 unused bits in
    the entire table, this satisfies .req.bit.

    .index: The designs for the following functions use a decomposition of a
    bit-index, i, into two parts, iw, ib.  .index.word: iw is the "word-index"
    which is the index into the word array of the word that contains the bit
    referred to by the bit-index.  iw = i / MPS_WORD_WIDTH.  Since MPS_WORD_WIDTH
    is a power-of-two, this is the same as iw = i >> MPS_WORD_SHIFT.  The latter
    expression is used in the code.  .index.word.justify: The compiler is more
    likely to generate good code without the divide.  .index.sub-word: ib is the
    "sub-word-index" which is the index of the bit referred to by the bit-index in
    the above word.  ib = i % MPS_WORD_WIDTH.  Since MPS_WORD_WIDTH is a
    power-of-two, this is the same as ib = i & ~((Word)-1<<MPS_WORD_SHIFT).  The
    latter expression is used in the code.  .index.sub-word.justify: The compiler
    is more likely to generate good code without the modulus.

    .index.justify.dubious: The above justifications are dubious; gcc 2.7.2 (with
    -O2) running on a sparc (zaphod) produces identical code for the following two
    functions:

    unsigned long f(unsigned long i)
    { return i/32 + i%32; }

    unsigned long g(unsigned long i)
    { return (i>>5) + (i&31); }

    .iteration: Many of the following functions involve iteration over ranges in a
    Bit Table. This is performed on whole words rather than individual bits,
    whenever possible (to improve speed). This is implemented internally by the
    macros ACT_ON_RANGE & ACT_ON_RANGE_HIGH for iterating over the range forwards
    and backwards respectively. These macros do not form part of the interface of
    the module, but are used extensively in the implementation.  The macros are
    often used even when speed is not an issue because it simplifies the
    implementation and makes it more uniform.  The iteration macros take the
    parameters (base, limit, single_action, bits_action, word_action).

      base, limit are of type Index and define the range of the iteration
      single_action is the name of a macro which will be used for iterating over
    bits in the table individually. This macro must take a single Index parameter
    corresponding to the index for the bit.  The macro must not use break or
    continue because it will be called from within a loop from the expansion of
    ACT_ON_RANGE.
      bits_action is the name of a macro which will be used for iterating over
    part-words. This macro must take parameters (wordIndex, base, limit) where
    wordIndex is the index into the array of words, and base & limit define a range
    of bits within the indexed word.
      word_action is the name of a macro which will be used for iterating over
    whole-words. This macro must take the parameter (wordIndex) where wordIndex is
    the index of the whole-word in the array.  The macro must not use break or
    continue because it will be called from within a loop from the expansion of
    ACT_ON_RANGE.

    .iteration.exit: The code in the single_action, bits_action, and word_action
    macros is allowed to use 'return' or 'goto' to terminate the iteration early.
    This is used by the test (.fun.test.*) and find (.fun.find.*) operations.

    .iteration.small: If the range is sufficiently small only the single_action
    macro will be used as this is more efficient in practice.  The choice of what
    constitutes a small range is made entirely on the basis of experimental
    performance results (and currently, 1999-04-27, a "small range" is 6 bits or
    fewer.  See change.mps.epcore.brisling.160181 for some justification).
    Otherwise (for a bigger range) bits_action is used on the part words at either
    end of the range (or the whole of the range it if it fits in a single word),
    and word_action is used on the words that comprise the inner portion of the
    range.

    The implementation of ACT_ON_RANGE (and ACT_ON_RANGE_HIGH) is simple enough.
    It decides which macros it should invoke and invokes them.  single_action and
    word_action are invoked inside loops.

    .fun.get: BTGet.
    The bit-index will be converted in the usual way, see .index.  The relevant
    Word will be read out of the Bit Table and shifted right by the sub-Word index
    (this brings the relevant bit down to the least significant bit of the Word),
    the Word will then be masked with 1 producing the answer.

    .fun.set: BTSet

    .fun.res: BTRes

    In both BTSet and BTRes a mask is constructed by shifting 1 left by the
    sub-word-index (see .index).  For BTSet the mask is ORed into the relevant word
    (thereby setting a single bit).  For BTRes the mask is inverted and ANDed into
    the relevant word (thereby resetting a single bit).

    .fun.set-range: BTSetRange
    ACT_ON_RANGE (see .iteration above) is used with macros that set a single bit
    (using BTSet), set a range of bits in a word, and set a whole word.

    .fun.res-range: BTResRange
    This is implemented similarly to BTSetRange (.fun.set-range) except using BTRes
    & reverse bit masking logic.

    .fun.test.range.set: BTIsSetRange
    ACT_ON_RANGE (see .iteration above) is used with macros that test whether all
    the relevant bits are set; if some of the relevant bits are not set then
    'return FALSE' is used to terminate the iteration early and return from the
    BTIsSetRange function.  If the iteration completes then TRUE is returned.

    .fun.test.range.reset: BTIsResRange
    As for BTIsSetRange (.fun.test.range.set above) but testing whether the bits
    are reset.

    .fun.test.range.same: BTRangesSame
    As for BTIsSetRange (.fun.test.range.set above) but testing whether
    corresponding ranges in the two Bit Tables are the same.  Note there are no
    speed requirements, but ACT_ON_RANGE is used for simplicity and uniformity.

    .fun.find: The four external find functions (BTFindShortResRange,
    BTFindShortResRangeHigh, BTFindLongResRange, BTFindLongResRangeHigh) simply
    call through to one of the two internal functions: BTFindResRange,
    BTFindResRangeHigh.   BTFindResRange and BTFindResRangeHigh both have the
    following prototype (with a different name obviously):

    Bool BTFindResRange(Index *baseReturn, Index *limitReturn,
                        BT bt,
                        Index searchBase, Index searchLimit,
                        Count minLength,
                        Count maxLength)

    There are two length parameters, one specifying the minimum length of the range
    to be found, the other the maximum length.  For BTFindShort* maxLength is equal
    to minLength when passed; for BTFindLong* maxLength is equal to the maximum
    possible range (searchLimit - searchBase).

    .fun.find-res-range: BTFindResRange
    Iterate within the search boundaries, identifying candidate ranges by searching
    for a reset bit.  The Boyer-Moore algorithm (reference please?) is used (it's
    particularly easy when there are only two symbols, 0 and 1, in the alphabet).
    For each candidate range, iterate backwards over the bits from the end of the
    range towards the beginning.  If a set bit is found, this candidate has failed
    and a new candidate range is selected.  If when scanning for the set bit a
    range of reset bits was found before finding the set bit, then this (small)
    range of reset bits is used as the start of the next candidate.  Additionally
    the end of this small range of reset bits (the end of the failed candidate
    range) is remembered so that we don't have to iterate over this range again.
    But if no reset bits were found in the candidate range, then iterate again
    (starting from the end of the failed candidate) to look for one.  If during the
    backwards search no set bit is found, then we have found a sufficiently large
    range of reset bits; now extend the valid range as far as possible up to the
    maximum length by iterating forwards up to the maximum limit looking for a set
    bit.  The iterations make use of the ACT_ON_RANGE & ACT_ON_RANGE_HIGH macros
    using of 'goto' to effect an early termination of the iteration when a
    set/reset (as appropriate) bit is found.  The macro ACTION_FIND_SET_BIT is used
    in the iterations, it efficiently finds the first (that is, with lowest index
    or weight) set bit in a word or subword.

    .fun.find-res-range.improve: Various other performance improvements have been
    suggested in the past, including some from request.epcore.170534.  Here is a
    list of potential improvements which all sound plausible, but which have not
    led to performance improvements in practice:

    .fun.find-res-range.improve.step.partial: When the top index in a candidate
    range fails, skip partial words as well as whole words, using
    e.g. lookup tables.

    .fun.find-res-range.improve.lookup: When testing a candidate run,
    examine multiple bits at once (e.g. 8), using lookup tables for (e.g)
    index of first set bit, index of last set bit, number of reset bits,
    length of maximum run of reset bits.

    .fun.find-res-range-high: BTFindResRangeHigh
    Exactly the same algorithm as in BTFindResRange (see .fun.find-res-range
    above), but moving over the table in the opposite direction.

    .fun.copy-simple-range: BTCopyRange.
    Uses ACT_ON_RANGE (see .iteration above) with the obvious implementation.
    Should be fast.

    .fun.copy-offset-range: BTCopyOffsetRange.
    Uses a simple iteration loop, reading bits with BTGet and setting them with
    BTSet. Doesn't use ACT_ON_RANGE because the two ranges will not, in general, be
    similarly word-aligned.

    .fun.copy-invert-range: BTCopyInvertRange.
    Uses ACT_ON_RANGE (see .iteration above) with the obvious implementation.
    Should be fast - although there are no speed requirements.

    TESTING

    .test: The following tests are available / have been used during development.

    .test.btcv: MMsrc!btcv.c.  This is supposed to be a coverage test, intended to
    execute all of the module's code in at least some minimal way.

    .test.cbstest: MMsrc!cbstest.c.  This was written as a test of the CBS module
    (design.mps.cbs(2)).  It compares the functional operation of a CBS with that
    of a BT so is a good functional test of either module.

    .test.mmqa.120: MMQA_test_function!210.c.  This is used because it has a fair
    amount of segment allocation and freeing so exercises the arena code that uses
    Bit Tables.

    .test.bttest: MMsrc!bttest.c.  This is an interactive test that can be used to
    exercise some of the BT functionality by hand.

    .test.dylan: It is possible to modify Dylan so that it uses Bit Tables more
    extensively.  See change.mps.epcore.brisling.160181 TEST1 and TEST2.

## A. References

## B. Document History

2002-06-07 | RB | Converted from MMInfo database design document.

## C. Copyright and License

This document is copyright © 1995-2002 Ravenbrook Limited. All rights reserved. This is an open source license. Contact Ravenbrook for commercial licensing options.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Redistributions in any form must be accompanied by information on how to obtain complete source code for the this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs.

This software is provided by the copyright holders and contributors "as is" and any express or implied warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.

`$Id: //info.ravenbrook.com/project/mps/version/1.111/design/bt/index.html#2 $`

Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents