Skip to content

Use bit-twiddling tricks to make choose-by-bandwith algorithm even more time-invariant

See #6537 (moved) for discussion. There's a branch in the middle of our node selection algorithm, which is bad for time-invariance. Furthermore, a sufficiently clever compiler might decide to reinsert the break statement that 6537 so carefully removed. (I have not yet found a compiler this clever, but better safe than sorry!)

We can probably do better by using a bit-twiddling approach to setting i_chosen. For example, rransom wrote:

  i_chosen = 0;
  i_hasnt_been_chosen = ~0;
  for (...) {
     int64_t choose_this_i;
     tmp += int_bandwidths[i];
    choose_this_i = rand_bw - (tmp+1);
    choose_this_i = choose_this_i >> 63;
    /* choose_this_i = -1 if rand_bw < (tmp+1); choose_this_i = 0 otherwise */
    i_chosen |= (i & choose_this_i & i_hasnt_been_chosen);
    i_hasnt_been_chosen &= ~choose_this_i;
 }
 i = i_chosen;

This looks okay to me; more eyes are needed here, though.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information