Feature #22279: Region (Length / Range) Arguments for String Bit Operations

• Status: Open
• Assignee: -
• Target version: -

[hasumikin (hitoshi hasumi)]

PR URL: https://github.com/ruby/ruby/pull/18562

What this adds

Region overloads for the methods introduced in #22118, so they act on a contiguous run of bits in a single call:

String#bit_set(offset, length, lsb_first: true)    -> self
String#bit_set(range, lsb_first: true)             -> self
String#bit_clear(offset, length, lsb_first: true)  -> self
String#bit_clear(range, lsb_first: true)           -> self
String#bit_flip(offset, length, lsb_first: true)   -> self
String#bit_flip(range, lsb_first: true)            -> self
String#bit_count(offset, length, lsb_first: true)  -> Integer
String#bit_count(range, lsb_first: true)           -> Integer

Existing single-offset forms and the no-argument bit_count are unchanged.

Use cases

Apache Arrow stores validity masks and boolean columns as LSB-first packed bitmaps (the same layout as Ruby's default lsb_first: true) and touches them a range at a time.

Writing a buffer: mark a contiguous run of elements valid or null in one call (the equivalent of Arrow C++'s bit_util::SetBitsTo), or invert a boolean column:

validity.bit_set(start, run)     # mark [start, start+run) valid
validity.bit_clear(start, run)   # mark them null
column.bit_flip(0...n_elements)  # boolean NOT

Reading a buffer: null_count is length - bit_count, a rank query over the mask. An Arrow array is an O(1) slice with an arbitrary bit offset, so a slice's null_count counts a range that starts and ends mid-byte:

null_count = slice_length - validity.bit_count(slice_offset, slice_length)

API Contracts

• (offset, length) and a Range are equivalent; passing both is an ArgumentError. The positional form follows String#[](start, length).
• Endless / beginless ranges work as usual (0.. = to the last bit). An empty region (length == 0, or an empty Range) is a no-op for the mutations and 0 for bit_count. For the mutations, even an empty region must begin within 0..bit_size: "\x00".bit_set(9, 0) and "\x00".bit_set(9...9) both raise IndexError, mirroring how "abc"[4, 0] is nil while "abc"[3, 0] is "".
• Mutations require the whole region to be in range and raise IndexError on overrun without modifying any bits; bit_count clamps to the bits that exist: the same read/write split as #22118.
• bit_count returns 0 (not nil) for a region that lies entirely beyond the end. It is an aggregate, not a slice or a single-position lookup: the "reads return nil" rule of #22118 exists because bit_get has no in-domain value for "no such bit", whereas the count of set bits in an empty intersection is legitimately 0, and the result is meant to feed arithmetic (length - bit_count(...)). This also keeps one rule for clamping: whatever part of the region exists is counted, and an empty part counts as 0.
• Mutations raise FrozenError on a frozen receiver even for an empty region, following [].freeze.push and "".freeze.concat. An out-of-range region is still detected first (IndexError), as in String#setbyte.
• Negative offsets and Range endpoints raise IndexError, with no count-from-end normalization, as in #22118. A negative length raises ArgumentError, following the decision in #22881.
• An inverted Range (5..2) is treated as empty, like "abcd"[2..0] returning "".
• Bit positions beyond 2**64 - 1 raise ArgumentError even for the clamping bit_count (the representable-range rule of #22118 applies before clamping).
• A lone offset keeps its #22118 single-bit meaning, so it is valid only for the mutations (bit_set(offset) etc.). bit_count has no single-bit form: it takes no argument (whole string), (offset, length), or a Range, and bit_count(offset) raises ArgumentError. A one-bit count would return the same 0/1 as bit_get(offset), and reading it as "from offset to the end" would contradict String#[](index); counting to the end is spelled bit_count(offset..).
• An explicit nil is an argument, not an omission: bit_set(0, nil) and bit_count(0, nil) raise TypeError, as "abc"[0, nil] does.
• lsb_first only changes the bit-to-position mapping within a byte.

Performance

A region call lets the implementation use memset / byte-wide popcount instead of a Ruby-level per-bit loop. On an AMD Ryzen 5 5600X (x86_64-linux, gcc, --zjit), with buf = "\x00".b * 2**20 (1 MiB), setting 8,388,600 bits at an unaligned offset:

buf.bit_set(4, 8388600)                 # 15 us
8388600.times { buf.bit_set(4 + it) }   # 440 ms    (~29,000x slower)

Most of that gap is the per-call overhead of 8 million Ruby method calls rather than the per-byte work; the point is that a region call removes the loop entirely, not that the single-bit form is slow.

For bit_count the point is addressing rather than raw speed: with data = Random.bytes(4096), a region such as data.bit_count(12347, 1000) cannot be expressed with byteslice at all, because it starts and ends mid-byte. Even for a byte-aligned region the region form avoids the intermediate String: data.bit_count(12344, 1008) 90 ns vs data.byteslice(1543, 126).bit_count 130 ns.

[hasumikin (hitoshi hasumi)]

• Description updated (diff)