Changeset 3189 for trunk


Ignore:
Timestamp:
May 26, 2013, 11:21:01 AM (6 years ago)
Author:
cameron
Message:

Add optimized BitBlockScanner?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock_iterator.hpp

    r3148 r3189  
    99  bitblock_iterator.hpp
    1010
    11   Created on: Sept 2011
    12   Author: Ken Herdy
     11  Created on: Sept 2011, revised May 2013
     12  Authors: Ken Herdy and Rob Cameron
    1313
    1414  Description:
     
    1717        the 'scanwords' of a 'bitblock'. Scanner classes are templated
    1818        on bitblock type and scanword type.
     19
     20*/
     21
     22
     23//
     24// The following implementation of BitBlockScanner is optimized
     25// to eliminate branch mispredictions during scanning.  Only the
     26// essential methods are included.   RDC May 2013.
     27//
     28// Usage:
     29//   (1) declare:  BitBlockScanner myscanner;
     30//   (2) initialize:  myscanner.init(&mybitblock);
     31//   (3) iterate:  while (myscanner.has_next()) { pos = myscanner.scan_to_next();  ...}
     32//
     33
     34//
     35// We could use FW=32 bit scan units, but 8 seems to be faster.
     36#define FW 8
     37#define _FW _8
     38template <class bitblock_t, class scanblock_t>
     39class BitBlockScanner {
     40public:
     41        BitBlockScanner() {}
     42
     43        IDISA_ALWAYS_INLINE int init(const BitBlock *s) {
     44                remaining._bitblock = *s;
     45                mask = hsimd<FW>::signmask(simd<FW>::sub(simd<1>::constant<0>(), remaining._bitblock));
     46        }
     47
     48        IDISA_ALWAYS_INLINE int has_next() {
     49               
     50                     return mask != 0;
     51        }
     52
     53        IDISA_ALWAYS_INLINE int scan_to_next() {
     54               
     55                     int item_pos = scan_forward_zeroes(mask);
     56                     uint32_t scan_item = remaining._FW[item_pos];
     57                     int bitpos = scan_forward_zeroes(scan_item);
     58                     scan_item = scan_item & (scan_item - 1);
     59                     remaining._FW[item_pos] = scan_item;
     60                     // We could recalculate the mask, but updating it is faster.
     61                     // Note that this update code compiles to a SETcc instruction.
     62                     mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
     63                     int pos = item_pos * FW + bitpos;
     64                     return pos;
     65        }
     66        // It slows things down to store the position.
     67        //IDISA_ALWAYS_INLINE int32_t get_pos() { return pos;}
     68private:
     69        union {bitblock_t _bitblock;
     70               uint8_t _8[sizeof(bitblock_t)];
     71               uint32_t _32[sizeof(bitblock_t)/sizeof(uint32_t)];} remaining;
     72        scanblock_t mask;                       
     73};
     74#undef _FW
     75#undef FW
     76
     77/*=============================================================================
     78
     79   Deperecated:
    1980
    2081        BitBlock iterator classes provide Standard Template Library (STL)
Note: See TracChangeset for help on using the changeset viewer.