Processor support for select operations

[Paul Elschot]

Aleksey,

On 11-11-14 14:27, Aleksey Shipilev wrote:
>  ...
> What method are referring to? We can only safely intrinsify methods with
> clear and stable semantics, i.e. those in standard library. I don't see
> any, and so I guess the very first thing to do is prototype the Java
> function like that in, say, java.lang.Long.

Java code, also available from:
https://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/BitUtil.java?revision=1636913

  /** Select a 1-bit from a long. See also LUCENE-6040.
   * @return The index of the r-th 1 bit in x. This bit must exist.
   */
  public static int select(long x, int r) {
    long s = x - ((x & 0xAAAAAAAAAAAAAAAAL) >>> 1); // pairwise bitsums

    // nibblewise bitsums
    s = (s & 0x3333333333333333L) + ((s >>> 2) &
                                      0x3333333333333333L);
    // bytewise bitsums, cumulative
    s = ((s + (s >>> 4)) & 0x0F0F0F0F0F0F0F0FL) * L8_L;

    // bit position of byte with r-th 1 bit.
    int b = (Long.numberOfTrailingZeros(
              (s + psOverflow[r-1]) & (L8_L << 7)) >> 3) << 3;
    long l = r - (((s << 8) >>> b) & 0xFFL); // bit rank in byte at b

    // Select bit l from byte (x >>> b):
    int selectIndex = (int) (((x >>> b) & 0xFFL) | ((l-1) << 8));
    int res = b + select256[selectIndex];
    return res;
  }

  private final static long L8_L = 0x0101010101010101L;

The java code to initialize the arrays is at the link above.

When the bit to be selected does not exist, the semantics are undefined.
Normally a Long.bitCount(x) is done beforehand to avoid that.


There is C code ("The fastest code") here, it works in much the same way:
http://vigna.di.unimi.it/Sux/select.php


Regards,
Paul Elschot