Issue #22399 has been updated by matz (Yukihiro Matsumoto). I looked at this together with #22405. Seven methods with 37 call forms is more than I want to add now, so let me step back. As far as I can tell, the performance gain in both proposals comes from one thing: skipping bytes while searching for the next bit of a given value. A single search method, something like `bit_index(bit, offset = 0, lsb_first: true)` (name tentative), would be as fast for the sparse and long-run cases in your use cases, and `bit_offsets`, `bit_runs` and `bit_run_length` can be written on top of it in a few lines. About the rest: * `each_bit` and `bits`: a loop over `bit_get` already runs without allocation, and an Array of 0/1 takes 8 bytes per bit. In your examples the Array is immediately folded into an Integer or indexed, so what is really needed there may be reading a bit field as an Integer. * `bit_runs`: one Array per run is heavy when runs are short. Could you reconsider the proposal along these lines? I would also like to see measurements on mruby or PicoRuby, since microcontrollers are the main motivation. Matz. ---------------------------------------- Feature #22399: Iterator Methods for String Bit Operations https://bugs.ruby-lang.org/issues/22399#change-119340 * Author: hasumikin (hitoshi hasumi) * Status: Open ---------------------------------------- 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 the times. Each time is the median of 5 calls on a 1 MiB buffer. The machine is an AMD Ryzen 5 5600X with Ruby 4.1.0dev (master at 2db3072cfb) and this patch, gcc 13.3.0 `-O3`, YJIT off. {{collapse(Benchmark script) ```ruby sparse = "\x00".b * (1 << 20) # 1 MiB, 1,000 set bits 1000.times { sparse.bit_set(it * 8388) } dense = "\xAA".b * (1 << 20) # 1 MiB, every other bit set N = 1 << 23 # 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 / 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 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 { } } ``` }} | | Sparse | Dense | |---------------------------|-------:|-------:| | `bit_set?` loop | 445 ms | 485 ms | | `unpack1("b*")` + `index` | 8.9 ms | 321 ms | | `bit_offsets(1)` | 1.2 ms | 41 ms | | Dense | Array | Block | |----------------------------------------|-------:|-------:| | `bit_get` loop | 419 ms | 354 ms | | `unpack1("b*")` + `bytes`/`each_byte` | 374 ms | 244 ms | | `bits` / `each_bit { }` | 71 ms | 223 ms | `bit_offsets` skips a byte with no matching bit in one step. The block forms gain little, because the block call dominates. Their benefit is that the method allocates nothing. -- https://bugs.ruby-lang.org/