SparseBitvector_intersection.hpp

Go to the documentation of this file.

/*
 * SparseBitvector_intersection.hpp
 *
 * Time-stamp: <05/05/14 21:13:20 lars>
 *
 */

#ifndef __SPARSE_BITVECTOR_INTERSECTION__
#define __SPARSE_BITVECTOR_INTERSECTION__ t

#include <iostream>
using namespace std;

#include "common/debug.hpp"

extern long long numint;
extern long long numlen;

template <bool EARLY_FILTERING>
//inline 
bool intersection(SparseBitvector& result, const SparseBitvector& x, const SparseBitvector& y, const int minimalLength) {
  assert(x.length() > 0);
  assert(y.length() > 0);
  assert(&result != &x);
  assert(&result != &y);
  assert(result.capacity() >= minimalLength);

  // It is a bad idea to perform rowswapping here as this prevents inlining. Now done in the caller.

  // 1. setup stopping criteria.
  SparseBitvector::const_iterator endx = x.end(), endy = y.end();
  if (EARLY_FILTERING && minimalLength > 1) { // nothing can be gained from minimalLength 0 or 1. 
    endx -= minimalLength - 1; 
    endy -= minimalLength - 1;
  }

  // 2. initialize loop
  SparseBitvector::iterator minimalResult = result.beginUnbounded() + minimalLength;


  // 3. loop over all elements
#ifndef BALAZS 
  SparseBitvector::iterator iterResult = result.beginUnbounded();
  SparseBitvector::const_iterator iterx = x.begin(), itery = y.begin();
  int itemx = *iterx;
  int itemy = *itery;
  while (true) {
    if (itemx < itemy) { // miss in x
      ++iterx; if (iterx == endx) break;
      itemx = *iterx;
    } else if (itemx > itemy) { // miss in y
      ++itery; if (itery == endy) break;
      itemy = *itery;
    } else { // if (itemx == itemy) { // match
      *iterResult++ = itemx; 
      if (EARLY_FILTERING && iterResult < minimalResult) {
        ++endx;
        ++endy;
      } 
      ++iterx; if (iterx == endx) break;
      ++itery; if (itery == endy) break;
      itemx = *iterx; itemy = *itery;
      }
  }
#else
#if 0 //BALAZS==1
  register SparseBitvector::iterator iterResult  asm("ebx");
  iterResult = result.beginUnbounded();
  register SparseBitvector::const_iterator iterx asm("esi");
  iterx = x.begin();
  register SparseBitvector::const_iterator itery asm("edi");
  itery = y.begin();
  register int itemx=*iterx;
  register int itemy=*itery;
  //  __builtin_prefetch(iterx);
  //  __builtin_prefetch(iterx+32);
  //  __builtin_prefetch(iterx+64);
  //__builtin_prefetch(itery);
  //__builtin_prefetch(itery+32);
  //  __builtin_prefetch(itery+64);
  while (true) {
    //    numint++;
    //    itemx=*iterx;
    //__builtin_prefetch(iterx+128);
    // *iterResult=itemx;
    if (itemx==itemy) { //this is infrequent
      *iterResult++ = itemx;
      if (EARLY_FILTERING) {
        endx += (iterResult < minimalResult);
        endy += (iterResult < minimalResult);
      }
      iterx++;
      itery++;
      if (iterx == endx) break;
      if (itery == endy) break;
      itemx=*iterx;
      itemy=*itery;
    } else {
      //register unsigned char req asm ("cl");
      //register unsigned char rle asm ("al");
      //register unsigned char rge asm ("ah");
      // register unsigned int ia, ib;
      asm("leal 4(%[xref]),%%eax \n"
          "leal 4(%[yref]),%%edx \n"
          "cmpl %[yvalue],%[xvalue]\n"
          //          "movle %[xvalue],%[output] \n"
        //        "sete %[req] \n"
          // "setge %[rle] \n"
          //"setle %[rge] \n"
          "cmovle %%eax,%[xref] \n"
          "cmovge %%edx,%[yref] \n"
          "cmovle (%%eax),%[xvalue] \n"
          "cmovge (%%edx),%[yvalue] \n"
          : /*[req] "=q"(req),*/ /*[rle] "=q"(rle), [rge] "=q"(rge),*/ [xvalue]"+r" (itemx), [yvalue] "+r" (itemy), [xref] "+r" (iterx), [yref] "+r" (itery) : : "eax","edx");
      if (iterx == endx) break;
      if (itery == endy) break;
    }
    /*    *iterResult=itemx;
    iterResult+=(itemx==itemy);
    if (EARLY_FILTERING) {
      int t=(itemx==itemy)&&(iterResult<minimalResult);
      endx+=t;
      endy+=t;
    }
    iterx+=(itemx<=itemy);
    if (iterx == endx) break;
    itery+=(itemy<=itemx);
    if (itery == endy) break;
    itemx=*iterx;
    itemy=*itery;*/
  }
#else
  register SparseBitvector::iterator iterResult  asm("ebx");
  iterResult = result.beginUnbounded();
  register SparseBitvector::const_iterator iterx asm("esi");
  iterx = x.begin();
  register SparseBitvector::const_iterator itery asm("edi");
  itery = y.begin();
  register int itemx=*iterx;
  register int itemy=*itery;
  while (true) {
    while (itemx < itemy) { // miss in x
      ++iterx; if (iterx == endx) goto exit;
      itemx = *iterx;
    }
    while (itemx==itemy) { // if (itemx == itemy) { // match
      *iterResult++ = itemx; 
      if (EARLY_FILTERING && iterResult < minimalResult) {
        ++endx;
        ++endy;
      } 
      ++iterx; if (iterx == endx) goto exit;
      ++itery; if (itery == endy) goto exit;
      itemx = *iterx; itemy = *itery;
    }
    while (itemx > itemy) { // miss in y
      ++itery; if (itery == endy) goto exit;
      itemy = *itery;
    }
    while (itemx==itemy) { // if (itemx == itemy) { // match
      *iterResult++ = itemx; 
      if (EARLY_FILTERING && iterResult < minimalResult) {
        ++endx;
        ++endy;
      } 
      ++iterx; if (iterx == endx) goto exit;
      ++itery; if (itery == endy) goto exit;
      itemx = *iterx; itemy = *itery;
    }
  }
exit:
#endif
#endif

  result.resizeToEndOf(iterResult);

  return result.length() >= minimalLength;
}

template <bool EARLY_FILTERING>
inline 
int cardinalityOfIntersection(const SparseBitvector& x, const SparseBitvector& y, const int minimalLength) {
  assert(x.length() > 0);
  assert(y.length() > 0);

  // It is a bad idea to perform rowswapping here as this prevents inlining. Now done in the caller.

  // 1. setup stopping criteria.
  SparseBitvector::const_iterator endx = x.end(), endy = y.end();
  if (EARLY_FILTERING && minimalLength > 1) { // nothing can be gained from minimalLength 0 or 1. 
    endx -= minimalLength - 1; 
    endy -= minimalLength - 1;
  }

  // 2. initialize loop
  SparseBitvector::const_iterator iterx = x.begin(), itery = y.begin();
  int itemx = *iterx;
  int itemy = *itery;
  int resultLength = 0;

  // 3. loop over all elements


  while (true) {
#ifndef BALAZS
    if (itemx < itemy) { // miss in x
      ++iterx; if (iterx == endx) break;
      itemx = *iterx;
    } else if (itemx > itemy) { // miss in y
      ++itery; if (itery == endy) break;
      itemy = *itery;
    } else { // if (itemx == itemy) { // match
      ++resultLength;
      if (EARLY_FILTERING && resultLength < minimalLength) {
        ++endx;
        ++endy;
      } 
      ++iterx; if (iterx == endx) break;
      ++itery; if (itery == endy) break;
      itemx = *iterx; itemy = *itery;
      }

#else
    //*iterResult=itemx;
    numlen++;
    resultLength+=(itemx==itemy);
    if (EARLY_FILTERING) {
      int t=(itemx==itemy)&&(resultLength<minimalLength);
      endx+=t;
      endy+=t;
    }
    iterx+=(itemx<=itemy);
    if (iterx == endx) break;
    itery+=(itemy<=itemx);
    if (itery == endy) break;
    itemx=*iterx;
    itemy=*itery;
#endif
  }

  if (resultLength < minimalLength) // due to early filtering resultLength might not be correct if it is < minimalLength; so set it to 0.
    resultLength = 0;

  return resultLength;
}


#endif

---