deprecate bitwise `or` in favor of `bitor` (+ other bitwise operators); `withBitOperators` macro

[timotheecour]

this is super error prone [1], another gotcha to learn, can complicate generic code in some cases, and makes it harder to search.

These should be deprecated in favor of bitor, etc.
These are some examples:

proc `or`*(x, y: int): int {.magic: "BitorI", noSideEffect.}
proc `xor`*(x, y: int): int {.magic: "BitxorI", noSideEffect.}
proc `not`*[T: SomeUnsignedInt](x: T): T {.magic: "BitnotI", noSideEffect.}
proc `and`*[T: SomeUnsignedInt](x, y: T): T {.magic: "BitandI", noSideEffect.}
proc `xor`*[T: SomeUnsignedInt](x, y: T): T {.magic: "BitxorI", noSideEffect.}
proc `not`*(x: int): int {.magic: "BitnotI", noSideEffect.}

proposal:

• every proc foo defined with .magic: "BitXXX" is deprecated and aliased to a proc named bitfoo
• eventually will become an error
• EDIT define a withBitOperators template that allows using C-style operators | & ^ ~ or short names or etc in a scope (benefit: doesn't pollute namespace, makes it clear when bitwise operations are used; also, withBitOperators can be used in manually porting code after this deprecation as an alternative to nimfix):

withBitOperators: # defines C-style | & ^ ~
  let a1 = 1 | 2 # only valid in scope
  let a2 = 1 or 2 # only valid in scope
  let a3 = 1 bitor 2 # this still works

NOTE: this withBitOperators idea was inspired by this: https://forum.nim-lang.org/t/1188#7366 that defines pointer arithmetics

ptrMath:
    var a: array[0..3, int]
    for i in a.low..a.high:
      a[i] += i
    var p = addr(a[0])
    p += 1
    p[0] -= 2
    echo p[0], " ", p[1]

EDIT added this:
[1] error prone behavior: this code delete both files instead of just 1, because execCmd returns by int status instead of bool (success/fail), so bitwise semantics are used instead of logical semantics, and and or don't short-circuit in this case.

import osproc
echo execCmd("grep DELETEME foo.txt") and execCmd("rm foo.txt") or execCmd("rm backup.txt")

[Bulat-Ziganshin]

Writing low-level bit-manipulation code will be even harder after that change. I would like to have C-style | & ^ ~ operators with proper priorities.

[timotheecour]

Writing low-level bit-manipulation code will be even harder after that change

I disagree, it'll make it more obvious, and less easily confused for logical operators.

I would like to have C-style | & ^ ~ operators with proper priorities.

I'd rather use more explicit names like bitor (which are also easier to search). I don't like reserving all these 4 symbols just for narrow (in scope) use case of bit operations, when simply using bitor + friends can take care of it.

Here's a much better solution that doesn't pollute namespace: see withBitOperators above

[Bulat-Ziganshin]

It's more likely that I would need ptrMath+withBitOperators for en entire low-level module, but otherwise it's OK for me - C was developed 50 years ago and even at this time it explicitly targeted writing low-level code, so we don't need to copy its specific operator set in the modern application language :)

but, @Araq, it's once again raises the question of providing user-defined operator priorities

[Araq]

Why are these "super error prone" and a problem for "generic programming"? I don't like them too much either but have yet to see a bug that isn't caught by Nim's type checker on these.

[Araq]

@Bulat-Ziganshin We can add | etc to the bitops module.

There is nothing "convenient" about x &= ~(1 << n) though, that's a clearBit(x, n) operation. C's specific operator set is just badly designed and it already was bad 50 years ago. setBit, clearBit, flipBit are more useful for low level programming and have to be remembered as specific patterns in C.

[Bulat-Ziganshin]

Sorry, @Araq but don't teach me low-level programming ;) I use everything a processor can do, and AND/OR operations

1. more efficient than setbit/testbit, at least on Intel x86
2. carry more tasks, in particular extracting parts of value for different purposes

[Araq]

I'm teaching you that you have done some much low level programming that you don't see misdesigns anymore.

1. Ridiculous, you can map clearBit to the most efficient instruction sequence.
2. By that logic we don't need + because you can always use the more general - operator (a + b is the same as a - (-b))

[Bulat-Ziganshin]

@Araq

We can add | etc to the bitops module.

I don't know where it should belong, but I would like to see | & ^ ~ >> << plus ROL/ROR operations (f.e. as <<< >>>) plus their op= counterparts with C-inspired priorities, compiled directly to corresponding C/C++ equivalents, so we can expect the same performance.

Even more interesting would be to have ability to define them myself. AFAIK, now the only barrier to do it is the lack of user-defined op priorities (sorry for reminding that too often). And there are other operators too that I would like to define in my programs.

Why are these "super error prone" and a problem for "generic programming"?

BTW, one problem with existing and/or is their too-low priority. In my feeling, for bitOr/bitAnd it should be higher than +/-.

I'm teaching you that you have done some much low level programming that you don't see misdesigns anymore.

I like to learn, but single-bit operation clearly can't extract multi-bit field from a number. Just a small sample (all masks are computed based on hash size and similar run-time parameters):

#define hash_index(h)                 ((h)&hashsize1)                      /* compute chunkarr[] index for given hash value h;  we prefer to use lower bits since higher ones may be shared with stored_hash value */

#define chunkarr_value(hash,chunk)    ((Chunk(hash)&hash_mask)+(chunk))    /* combine hash and number of chunk into the one Chunk value for storing in the chunkarr[] */
#define get_hash(value)               ((value)&hash_mask)                  /* get hash from the combined value */
#define get_chunk(value)              ((value)&chunknum_mask)              /* get chunk number from the combined value */

And a longer sample, sorry for russian comments:

  // Маска для значения, сохраняемого в хеш-таблице, позволяющая извлечь достаточно бит для адресации позиции в dict[]
  const TIndex matchmask  =  (sizeof(TIndex)<8?  0  :  roundup_to_power_of(MatchBounds.dictsize,2)) - 1;
  // Маска для значения хеш-функции / в хеш-таблице, позволяющая извлечь биты, не пересекающиеся ни с hashmask, ни с matchmask
  const HTValue tagmask   =  (sizeof(TIndex)<8?  HTValue(-1)<<32  :  ~HTValue(matchmask | hashmask));
  // При sizeof(TIndex)<8 старшее слово 64-битного match_candidates_buf->hash используется как tag, а младшее & hashmask - как индекс в hasharr[]

  TIndex last_match_end = MatchBounds.bufstart;   // points to the end of last match written, we shouldn't start a new match prior to this point

  // ОСНОВНОЙ ЦИКЛ, НАХОДЯЩИЙ ПОВТОРЯЮЩИЕСЯ СТРОКИ ВО ВХОДНЫХ ДАННЫХ
  for (MatchCandidatesProvider match_candidates(L, SEGMENT_SIZE, match_candidates_buf, MatchBounds); ; )
  {
    TCandidate::Hash  hash;
    if (match_candidates.LookaheadFutureMatchCandidate (&hash)) {
      TIndex index  =  hash & hashmask; // Индекс в хеш-таблице потенциального матча спустя INMEM_PREFETCH чанков
      prefetch (hasharr[index]);        // Prefetch the hasharr[] by INMEM_PREFETCH cycles ahead
    }

    // Проверяем совпадение в лучшем на следующие L байт блоке длины SEGMENT_SIZE
    TIndex  src;                        // Позиция начала потенциального матча
    if (! match_candidates.GetNextMatchCandidate (L, &src, &hash))  return;   // Exit function if there are no more match candidates left
    TIndex  index = hash & hashmask;    // Индекс в хеш-таблице потенциального матча, уже найденного в collect_match_candidates()
    HTValue tag   = hash & tagmask;     // Тег потенциального матча

    if (src < last_match_end) {         // Проверяем совпадение только если предыдущее найденное совпадение уже кончилось
      hasharr[index] = src | tag;       // Иначе - просто заносим в хеш-таблицу этот блок
    } else {
      HTValue prev_value = src | tag;
      TIndex  match_distance0 = 0,  match_len0 = 0,  lit_len0 = 0;  // to fill with best match info

      for (NUMBER i = 0;  i < HASHARR_BUCKET_SIZE;  ++i, ++index)
      {
        // Shift the entire hasharr[] bucket backward by one position
        HTValue next_value = hasharr[index];
        hasharr[index] = prev_value;
        prev_value = next_value;

        if unlikely ((next_value & tagmask) == tag)
        {
          TIndex dest = next_value & matchmask;       // Позиция потенциального совпадения с src
.....

PS: If you mean that I should use *bit ops whenever possible - yeah, I found a part in my program where it should really improve the speed, thank you! ;) But the style is never an issue for these codes, it's only speed that matters.

[Bulat-Ziganshin]

But all my codes above doesn't bit ops too much. These are examples of more intensive operations, all from the single CRC manipulation module:

#define update_CRC(crc,CRCTable,c)  (CRCTable[((crc)^(c)) & 0xFF] ^ ((crc)>>8))
...
  for (NUMBER i=64; i; i/=2)
    CRCTable[i] = crc = (crc >> 1) ^ (CrcPolynomial & -(crc&1));    // crc = (crc*x) % CrcPolynomial
...
  //  for( i=0; i<32; i++ ) if( crc&(1<<i) ) out ^= mat[i];
  //  for( i=0; i<32; i++,crc>>=1 ) if( crc&1 ) out ^= mat[i];
    for( i=0; i<32; i++,crc>>=1 )  out ^= (mat[i] & -(crc&1));
...
    for( uint i=0; len; i++,len>>=1 ) if( len&1 ) crc=crc_mul(crc,crc_pad[i]);
...
    // process 16 bytes in every cycle (Slicing-by-16)
    while (length >= 16)
    {
      uint32_t a0 = *current++ ^ crc;
      uint32_t a1 = *current++;
      uint32_t a2 = *current++;
      uint32_t a3 = *current++;
      crc  = Crc32Tables[ 0][ a3>>24        ] ^
             Crc32Tables[ 1][(a3>>16) & 0xFF] ^
             Crc32Tables[ 2][(a3>> 8) & 0xFF] ^
             Crc32Tables[ 3][ a3      & 0xFF] ^
             Crc32Tables[ 4][ a2>>24        ] ^
             Crc32Tables[ 5][(a2>>16) & 0xFF] ^
             Crc32Tables[ 6][(a2>> 8) & 0xFF] ^
             Crc32Tables[ 7][ a2      & 0xFF] ^
             Crc32Tables[ 8][ a1>>24        ] ^
             Crc32Tables[ 9][(a1>>16) & 0xFF] ^
             Crc32Tables[10][(a1>> 8) & 0xFF] ^
             Crc32Tables[11][ a1      & 0xFF] ^
             Crc32Tables[12][ a0>>24        ] ^
             Crc32Tables[13][(a0>>16) & 0xFF] ^
             Crc32Tables[14][(a0>> 8) & 0xFF] ^
             Crc32Tables[15][ a0      & 0xFF];
      length -= 16;
    }

[Bulat-Ziganshin]

Ridiculous, you can map clearBit to the most efficient instruction sequence.

No, it's impossible. x.clearBit(n) maps to x & ~(1<<n) which isn't even close as efficient as x & mask where mask is precomputed based on n (and stored in an object). It's a part of special low-level programming knowledge :)

EDIT: just checked Agner instruction tables: on modern CPUs (Core2+, Ryzen) BT/BTS/BTR/BTC operations are performed in 1 cycle like AND/OR/XOR/TEST, but populated on 1-2 ports vs 3-4 ports for basic ops. Except that on Ryzen, BTS/BTR/BTC are 2 microops and have 2 cycle delay.

[timotheecour]

No, it's impossible. x.clearBit(n) maps to x & ~(1<<n) which isn't even close as efficient as x & mask where mask is precomputed based on n (and stored in an object)

just replying to this single point in isolation here:

• couldn't we achieve same with a clearBit overload that takes n as static[int] instead of int ?
• also IIUC, the order of arguments in proc clearBit is flipped, and probably should be fixed to allow x.clearBit(n):
  proc clearBit(nr: int; dest: var uint32) {.inline.} =...

[Bulat-Ziganshin]

@timotheecour I talk about situation when n is computed at run-time.

OTOH, when n is fixed, good compiler should map it to AND asm operation, and Nim probably does it - one way or other (i.e. it should be hard to encode operation in such a way that C compiler can't optimize it :) )

[awr1]

I've never really had much problem with or/and/etc. working for both integers and booleans. In cases where you have

if someInlineBitwiseNonsenseGoesHere or someBool and someOtherBool:

a healthy dose of parentheses or moving stuff into variables should be done anyway (and is more than likely required for correct parsing).

Enhancing bitops seems like a good idea. I'd like to make a list of useful procs to be added, as the ones @Araq mentioned appear to be absent. So far in the thread:

type intrange = range[0 .. sizeof(int) * 8]
proc setBit(x: int; at: intrange): int
proc clearBit(x: int; at: intrange): int
proc flipBit(x: int; at: intrange): int

Suggesting a few others based on the use cases in this thread:

proc intersects(x, y: int): bool # x and y != 0
proc xor(n: varargs[int]): int   # n[0] xor n[1] xor n[2] .. (lisp-ish, non-operator overloading, because `xor`() is limited to two arguments)
proc or(n: varargs[int]): int    # ditto
proc and(n: varargs[int]): int   # ditto