Rotate lower n bits

General Usage Performance
1

I would like to rotate the lower n bits of an integer x by r.
Here is my current solution :

function rotate_lower(x::Int, n::Int, r::Int)
    mask = (1 << n) - 1
    lower_bits = x & mask
    rotated_bits = (lower_bits >> r) | (lower_bits << (n - r))
    rotated_bits &= mask
    return (x & ~mask) | rotated_bits
end

Is there a more efficient way to go ? is it possible to do that faster ?

2

You might want to look into bitrotate().

3 Likes
3

You want lower_bits >>> r for correctness if n=64 (logical right shift, not arithmetic right shift).

You should specify / think about desired behavior for “nonsensically large” n and k values. There is a long sorry story about shift left shl producing poison values for stuff like 1<<65, due to a mix of old x86 and C-language idiosyncracies, which leads to slow code on x86 (the specific julia semantics for 1<<65 are a bad match for both x86 and C, and hence llvm).

3 Likes
4

:100:

AFAIK RISC-V uses the same semantics, so I’m guessing this may not be just an “old x86 idiosyncrasy”. C is not relevant here, except as a comparison.

Again, this doesn’t make sense. LLVM uses the same semantics as C, and this is completely OK, both for Julia and in general. It’s just that performance requires some care.

1 Like
5

If you have 0 <= r <= n < 64, the following is faster:

function rotate_lower2(x::Int, n::Int, r::Int)
    n &= 63
    r &= 63
    s = (n-r) & 63
    mask = (1 << n) - 1
    lower_bits = x & mask
    rotated_bits = (lower_bits >>> r) | (lower_bits << s)
    rotated_bits &= mask
    return (x & ~mask) | rotated_bits
end

julia> x, n, r = rand(Int), 37, 12;
julia> @b rotate_lower($x, $n, $r)
4.750 ns

julia> @b rotate_lower2($x, $n, $r)
2.639 ns

This works because the bit shift operators check for “nonsensically large” and negative values. If the shifts are known to be between 0 and 63, then the test is omitted in the final code.

1 Like
6

One possible semantics of x << n for large n that make sense is “implementation defined”, i.e. “whatever the hardware can do best”. Due to C being C, it is instead “undefined” which translates to llvm “poison”.

In other words, it would be valid to compile

void foo(){
   int x = (( (uint64_t) 1) << 65 ) ? 0 : 1);
   return;
}

into void foo(){abort();}.

This is bullshit and not acceptable for julia.

It might have been acceptable for julia to have sensible but hardware-dependent semantics of << for large n. A standard precedent is propagation of NaN payloads in floating point ops – this is not quite defined and hardware dependent, but it is not poison either.

AFAIK aarch64 also uses the same semantics, presumably in order to go with the mainstream. Of course armv7 et al do x << (n & 0xff), so we’re still hosed.

1 Like
7

IMO “implementation defined behavior” isn’t any better than “undefined behavior”.

I think Julia made the only good choice for a modern high-level language. Especially because the performance is easy, in principle, to regain using something like an unreachable instruction. Although such a feature isn’t yet available to users at a high-level in Julia (except like in my package UnsafeAssume.jl, which has its drawbacks), I hope it’ll be available one day.

2 Likes