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.