Feature #22399
Updated by hasumikin (hitoshi hasumi) 16 days ago
PR URL: https://github.com/ruby/ruby/pull/19161
### What this adds
The original proposal (#22082) listed this iterator group. Matz asked for a minimal subset in #22082#note-13, and the proposal deferred the group in #22082#note-14. The methods build on the single-bit methods of #22118 and on the region arguments of #22279:
```
String#each_bit(lsb_first: true) {|bit| ... } -> self
String#each_bit(offset, length, lsb_first: true) {|bit| ... } -> self
String#each_bit(range, lsb_first: true) {|bit| ... } -> self
String#each_bit(lsb_first: true) -> Enumerator
String#each_bit(offset, length, lsb_first: true) -> Enumerator
String#each_bit(range, lsb_first: true) -> Enumerator
String#bits(lsb_first: true) -> Array
String#bits(offset, length, lsb_first: true) -> Array
String#bits(range, lsb_first: true) -> Array
String#bits(lsb_first: true) {|bit| ... } -> self
String#bits(offset, length, lsb_first: true) {|bit| ... } -> self
String#bits(range, lsb_first: true) {|bit| ... } -> self
String#each_bit_offset(bit, lsb_first: true) {|offset| ... } -> self
String#each_bit_offset(bit, offset, length, lsb_first: true) {|offset| ... } -> self
String#each_bit_offset(bit, range, lsb_first: true) {|offset| ... } -> self
String#each_bit_offset(bit, lsb_first: true) -> Enumerator
String#each_bit_offset(bit, offset, length, lsb_first: true) -> Enumerator
String#each_bit_offset(bit, range, lsb_first: true) -> Enumerator
String#bit_offsets(bit, lsb_first: true) -> Array
String#bit_offsets(bit, offset, length, lsb_first: true) -> Array
String#bit_offsets(bit, range, lsb_first: true) -> Array
String#bit_offsets(bit, lsb_first: true) {|offset| ... } -> self
String#bit_offsets(bit, offset, length, lsb_first: true) {|offset| ... } -> self
String#bit_offsets(bit, range, lsb_first: true) {|offset| ... } -> self
```
`each_bit` and `bits` visit every bit of the region. They give each bit as `0` or `1`. `each_bit_offset` and `bit_offsets` visit the offsets of the bits that are equal to `bit`. The `bit` argument is `0`, `1`, `true` or `false`. The offsets come in increasing order.
```ruby
data = "\xAA\xCC".b
data.bits(8, 4) # => [0, 0, 1, 1]
data.bit_offsets(1) # => [1, 3, 5, 7, 10, 11, 14, 15]
data.bit_offsets(0, 8..) # => [8, 9, 12, 13]
data.bit_offsets(1, lsb_first: false) # => [0, 2, 4, 6, 8, 9, 12, 13]
data.each_bit_offset(1).size # => 8
```
The pairing follows `each_byte` / `bytes`. The `each_*` form returns `self` with a block. Without a block, it returns an Enumerator. The Array form returns an Array. Like `bytes`, the Array form also accepts a block. With a block, it behaves like the `each_*` form.
### Use cases
#### Columnar data (LSB-first)
Apache Arrow stores validity bitmaps and boolean columns as LSB-first packed bitmaps. Arrow pads a bitmap buffer to a multiple of 64 bytes. The padding bits have no defined value, so a read must stop at the column length. The region forms express this limit directly. The typical read patterns are:
- **Null positions:** `bit_offsets(0, 0, length)` gives the indexes of the null elements of a column. A Ruby loop over `bit_set?` is not necessary. Without the region, the result includes the padding bits as nulls.
```ruby
validity = "\xFD\x03".b # 10 elements, element 1 is null, bits 10..15 are padding
validity.bit_offsets(0) # => [1, 10, 11, 12, 13, 14, 15]
validity.bit_offsets(0, 0, 10) # => [1]
```
- **Boolean columns:** `bits(0, length)` converts a packed column into an Array of `0` and `1` values.
- **Slices:** The region forms scan only the chunk of a bitmap that a batch covers. The offsets stay absolute. Thus they work with `bit_set?` and the mutation methods without adjustment.
#### Microcontrollers and wire formats
The `each_*` forms walk a buffer and do not allocate an Array. The region forms (with `offset..` or `(offset, length)`) continue from any bit offset. They do not unpack the whole buffer. On CRuby this matters for large buffers. `bits` on a 1 MiB buffer builds an Array of 8 million elements. `each_bit` with a block allocates nothing in the method itself.
The same property helps implementations for microcontrollers (mruby, PicoRuby). These implementations take the core API as their specification. On such devices, a String is often the only buffer a program has.
- **Protocol headers:** RFC protocol diagrams number bits MSB-first. `bits(offset, length, lsb_first: false)` returns a header field in wire order. A decoder can follow the diagram directly and does not reverse bits.
```ruby
hdr = "\x12\x34\x81\x80".b # DNS header: ID, then the 16 flag bits
flags = hdr.bits(16, 16, lsb_first: false)
qr, rd, ra = flags[0], flags[7], flags[8] # => 1, 1, 1
```
- **Huffman and other prefix codes:** A decoder reads a code stream one bit at a time and descends a tree. `each_bit` with a region reads the packed codes in the order the encoder wrote them. The decoder allocates nothing per bit. Bit-serial formats differ in packing order. JPEG entropy-coded segments and CCITT fax pack MSB-first, so they need `lsb_first: false`. DEFLATE packs LSB-first and reads with the default.
```ruby
tree = ["a", ["b", ["c", "d"]]] # 0 => a, 10 => b, 110 => c, 111 => d
stream = "\x5B\x80".b # 0 10 110 111 = "abcd", 9 bits
node = tree
out = +""
stream.each_bit(0, 9, lsb_first: false) do |bit|
node = node[bit]
if node.is_a?(String)
out << node
node = tree
end
end
out # => "abcd"
```
- **Bit-banged buses:** A shift-register chain receives a multi-byte frame MSB-first. `each_bit(lsb_first: false)` over the frame gives one GPIO write per bit. The program does not split the frame into Integers first.
- **1 bpp frame buffers:** A display such as the SSD1306 stores a page as one byte per column. Bit 0 is the top pixel. With the bitwise methods of #22118, `bit_offsets(1)` turns a pixel test into a coordinate list. `bitwise_and` of a sprite and the background keeps only the overlapping pixels. `bit_offsets(1)` yields their positions. `i / 8` is the column and `i % 8` is the row within the page.
```ruby
sprite = "\x00\x3C\x3C\x00".b
background = "\x00\x00\x30\xFF".b
hits = sprite.bitwise_and(background)
hits.bit_offsets(1).map { |i| [i / 8, i % 8] } # => [[2, 4], [2, 5]]
```
#### Why not String#unpack?
`unpack1("b*")` and `unpack1("B*")` already give the bits as a `"0"`/`"1"` String. That form has four limits:
- It allocates a String eight times the size of the receiver.
- It moves only by whole bytes with `@`.
- It cannot list the offsets of the set or cleared bits.
- It returns characters, where `bit_get` returns Integers.
The iterators read in place. They take bit regions. They list offsets directly. Their results compose with the rest of the bit API.
### API Contracts
1. **Region arguments** are the same as for `bit_count`: no argument (the whole string), `(offset, length)`, or a Range, plus `lsb_first:`. A lone `offset` raises `ArgumentError`, as for `bit_count`.
2. **Reads clamp.** The methods cut a region that extends past the end of the string down to the bits that exist. A region that begins at or beyond the end yields nothing. An empty or inverted region yields nothing. `bit_count`, the other read-only region method, has the same behavior.
3. **Offsets are absolute.** `each_bit_offset` and `bit_offsets` yield offsets relative to the start of the string, in the numbering that `lsb_first:` selects. Thus `data.bit_set?(i, lsb_first: x)` is true for every `i` that `data.each_bit_offset(1, lsb_first: x)` yields.
4. **The `bit` argument** accepts `0`, `1`, `true` or `false`. The method converts any other object with `to_int`, as for an index, with the same exceptions. An Integer other than `0` or `1` raises `ArgumentError`. An object without `to_int` raises `TypeError`.
5. **Errors are raised without a block.** The method validates the arguments before it creates the Enumerator. Thus `"".each_bit(-1, 4)` raises `IndexError` immediately, not on the first `each`. The Enumerator validates the arguments again when it iterates or computes its size. Thus `to_int` conversions can run more than once.
6. **Enumerator#size** is the number of bits in the region for `each_bit`. For `each_bit_offset`, it is the number of matching bits. The Enumerator computes the size on demand from the current contents of the receiver.
7. **The block can modify the receiver.** The iteration reads the string again for every bit. It stops at the current end of the string. A longer receiver does not extend the iteration beyond the original region.
8. **Out-of-range arguments** follow #22279. A negative offset raises `IndexError`. A negative length raises `ArgumentError`. A position or length beyond `2**64 - 1` raises `ArgumentError`.
9. **Frozen receivers** work, because all four methods only read.
10. **Encoding** has no effect. The methods treat the receiver as a byte sequence, as in #22118.
11. **`lsb_first` changes only the bit numbering within each byte.** The byte order does not change, as in #22118 and #22279. The value must be `true` or `false`. Any other value raises `ArgumentError`, as in #22118.
### Performance
The script below gives `each_bit_offset` and `bit_offsets` mask each byte against the times. Each time is region. They skip the median of 5 calls on bytes with no matching bit. Thus they scan a 1 MiB buffer. sparse bitmap byte by byte, not bit by bit.
The machine is measurements use an AMD Ryzen 5 5600X 5600X, a 1 MiB buffer, and ruby 4.1.0dev with Ruby 4.1.0dev (master at 2db3072cfb) and this patch, gcc 13.3.0 `-O3`, YJIT off.
{{collapse(Benchmark script)
```ruby
YJIT changes the loop times by less than 15%, because the C method calls dominate the loops. Each alternative produces the same result as the new method. Thus its time includes the conversion of the `unpack1("b*")` bit String to Integers or offsets. The sparse = "\x00".b * (1 << 20) # 1 MiB, buffer has 1,000 set bits
1000.times { sparse.bit_set(it * 8388) }
bits. The dense = "\xAA".b buffer is `"\xAA" * (1 << 20) # 1 MiB, every other bit set
N = 1 << 23 MiB`.
# The alternatives give the same result as the new methods.
def offsets_by_loop(s) = (0...N).select { s.bit_set?(it) }
def bits_by_loop(s) = Array.new(N) { s.bit_get(it) }
def each_by_loop(s) = N.times { s.bit_get(it) }
def offsets_by_unpack(s)
b = s.unpack1("b*")
offsets = []
i = -1
offsets << i while (i = b.index("1", i + 1))
offsets
end
def bits_by_unpack(s) = s.unpack1("b*").bytes.map { it - 48 }
def each_by_unpack(s) = s.unpack1("b*").each_byte { it - 48 }
def median(n = 5)
Array.new(n) {
t = Process.clock_gettime(Process::CLOCK_MONOTONIC)
yield
Process.clock_gettime(Process::CLOCK_MONOTONIC) - t
}.sort[n | Operation | `bit_get` / 2]
end
{ sparse:, dense: }.each do |name, s|
raise unless offsets_by_loop(s) == s.bit_offsets(1) && offsets_by_unpack(s) == s.bit_offsets(1)
printf "%-6s offsets `bit_set?` loop %.4f\n", name, median { offsets_by_loop(s) }
printf "%-6s offsets unpack %.4f\n", name, median { offsets_by_unpack(s) }
printf "%-6s bit_offsets %.4f\n", name, median { s.bit_offsets(1) }
end
raise unless bits_by_loop(dense) == dense.bits && bits_by_unpack(dense) == dense.bits
printf "bits loop %.4f\n", median { bits_by_loop(dense) }
printf "bits unpack %.4f\n", median { bits_by_unpack(dense) }
printf "bits %.4f\n", median { dense.bits }
printf "each loop %.4f\n", median { each_by_loop(dense) }
printf "each unpack %.4f\n", median { each_by_unpack(dense) }
printf "each_bit %.4f\n", median { dense.each_bit { } }
```
}}
| `unpack1("b*")` based | Sparse New method | Dense |
|---------------------------|-------:|-------:| |--------------------------------------------|--------|----------|----------------------------|
| `bit_set?` loop Offsets of the set bits, sparse buffer | 445 ms 0.56 s | 485 ms 0.0125 s |
`bit_offsets(1)`: 0.0015 s | `unpack1("b*")` + `index` | 8.9 ms | 321 ms |
| `bit_offsets(1)` Offsets of the set bits, dense buffer | 1.2 ms 0.61 s | 41 ms 0.29 s |
| Dense | Array `bit_offsets(1)`: 0.052 s | Block |
|----------------------------------------|-------:|-------:|
| `bit_get` loop All bits as an Integer Array, dense buffer | 419 ms 0.63 s | 354 ms 0.43 s | `bits`: 0.072 s |
| `unpack1("b*")` + `bytes`/`each_byte` All bits yielded to a block, dense buffer | 374 ms 0.35 s | 244 ms 0.51 s |
| `bits` / `each_bit { }` }`: 0.27 s | 71 ms | 223 ms |
`bit_offsets` skips a byte with no matching bit in one step. The block forms gain little, little speed over a `bit_get` loop, because the block call dominates. Their benefit is that the method itself allocates nothing.