Tracking Issue: Implementation of an Optimized Software Library

[saik0]

This is a tracking issue for optimizations presented by @lemire et al. in arXiv:1709.07821

• bitset -> array (Section 3.1)
  • converting bitsets to arrays Add scalar optimizations from CRoaring / arXiv:1709.07821 section 3 #127
• bitset+array (Section 3.2)
  • setting, flipping or resetting the bits of a bitset at indexes specified by an array, with and without cardinality tracking
  • branchless C equivalent Add scalar optimizations from CRoaring / arXiv:1709.07821 section 3 #127
  • x86 asm Hand tune array-bitset aggregates #166
• bitset (Section 4.1.1)
  • computing the cardinality using a vectorized Harley-Seal algorithm SIMD Harley-Seal Population Count #165
• bitset+bitset (Section 4.1.2)
  • computing AND/OR/XOR/ANDNOT between two bitsets with cardinality Add scalar optimizations from CRoaring / arXiv:1709.07821 section 3 #127
  • using a vectorized Harley-Seal algorithm SIMD Harley-Seal Population Count #165
• array+array (Section 4.2)
  • computing the intersection between two arrays using a vectorized algorithm Add SIMD Array-Array set operations #163
• array+array (Section 4.3)
  • computing the union between two arrays using a vectorized algorithm Add SIMD Array-Array set operations #163
• array+array (Section 4.4)
  • computing the difference between two arrays using a vectorized algorithm Add SIMD Array-Array set operations #163
• array+array (Section 4.5)
  • computing the symmetric difference between two arrays using a vectorized algorithm Add SIMD Array-Array set operations #163
• fast counts (Section 5.9)
  • compute the cardinality of the result of a set operation without materializing a new bitset Add fast counts #167

[saik0]

Closing this tracking issue. All the portable optimizations are done. We can leave #166 open for if/when we want to implement it.