Issue #22405 has been updated by matz (Yukihiro Matsumoto). Please see my comment in #22399#note-3. I'd like to consider the two proposals together. Matz. ---------------------------------------- Feature #22405: Run-Length Methods for String Bit Operations https://bugs.ruby-lang.org/issues/22405#change-119341 * Author: hasumikin (hitoshi hasumi) * Status: Open ---------------------------------------- PR: (WIP) ### What this adds This ticket adds the run-length methods of the String bit operation API. A run is a maximal sequence of consecutive bits with the same value. The methods build on the region arguments of #22279 and on the iterator conventions of #22399: ``` String#bit_run_length(bit, offset, lsb_first: true) -> Integer | nil String#each_bit_run(lsb_first: true) {|bit, offset, length| ... } -> self String#each_bit_run(offset, length, lsb_first: true) {|bit, offset, length| ... } -> self String#each_bit_run(range, lsb_first: true) {|bit, offset, length| ... } -> self String#each_bit_run(lsb_first: true) -> Enumerator String#each_bit_run(offset, length, lsb_first: true) -> Enumerator String#each_bit_run(range, lsb_first: true) -> Enumerator String#bit_runs(lsb_first: true) -> Array String#bit_runs(offset, length, lsb_first: true) -> Array String#bit_runs(range, lsb_first: true) -> Array String#bit_runs(lsb_first: true) {|bit, offset, length| ... } -> self String#bit_runs(offset, length, lsb_first: true) {|bit, offset, length| ... } -> self String#bit_runs(range, lsb_first: true) {|bit, offset, length| ... } -> self ``` `each_bit_run` and `bit_runs` visit every run of the region as `[bit, offset, length]`. The runs come in increasing order of offset. `bit_run_length` returns the length of the run of `bit` that begins at `offset`. ```ruby data = "\x0F\x01".b data.bit_runs # => [[1, 0, 4], [0, 4, 4], [1, 8, 1], [0, 9, 7]] data.bit_runs(8..) # => [[1, 8, 1], [0, 9, 7]] data.bit_run_length(1, 0) # => 4 data.bit_run_length(0, 0) # => 0 data.bit_run_length(1, 16) # => nil data.each_bit_run.size # => 4 ``` The pairing follows `each_bit` / `bits`. The `each_*` form returns `self` with a block. Without a block, it returns an Enumerator. The Array form returns an Array. With a block, it behaves like the `each_*` form. ### Use cases #### Bitstream parsing (MSB-first) - **Rice codes for sensor logs.** A battery device logs the differences between consecutive samples. Small differences are frequent, so a Rice code stores each value as a unary quotient followed by `k` remainder bits. The unary part is a run of set bits, so `bit_run_length(1, pos, lsb_first: false)` reads it in one call. The region form of `bits` then reads the remainder from the position where the run ended. ```ruby # Rice code, MSB-first. A value n is stored as: # q = n >> k set bits, one cleared bit, then the k low bits of n # bs is the bitstream (a binary String) and pos is a bit offset in it. # Returns the value and the bit offset of the next code. def read_rice(bs, pos, k) q = bs.bit_run_length(1, pos, lsb_first: false) # count the set bits pos += q + 1 # skip them and the cleared bit # Read k bits and build an Integer from them, MSB first r = bs.bits(pos, k, lsb_first: false).inject(0) {|acc, b| acc * 2 + b } [(q << k) | r, pos + k] end # "\x79\x14" = 0111 1001 0001 0100, decoded with k = 2: # pos unary q remainder value # 0 0 0 11 0 << 2 | 3 = 3 # 3 110 2 01 2 << 2 | 1 = 9 # 8 0 0 00 0 << 2 | 0 = 0 # 11 10 1 10 1 << 2 | 2 = 6 # (bit 15 is padding) bs = "\x79\x14".b pos = 0 values = [] 4.times do value, pos = read_rice(bs, pos, 2) # pass the returned offset to the next call values << value end values # => [3, 9, 0, 6] pos # => 15 ``` #### 1 bpp frame buffers - **E-paper partial refresh.** An e-paper panel refreshes a small window much faster than the full screen, and each refresh costs power. A driver keeps the previous frame and sends only the pixels that changed. `bitwise_xor` of the previous row and the new row marks the changed pixels. `bit_runs` of the result gives the changed spans. Most panel controllers accept a window only at byte boundaries. Thus the driver widens each span to a multiple of 8 and refreshes one window per span. The same pattern applies to a monochrome LCD with a page or row buffer. ```ruby # 32 pixels, MSB-first (the high bit of each byte is the left pixel), 1 = black old_row = "\xFF\x00\xF0\x0F".b new_row = "\xFF\x3C\xF0\x00".b # XOR sets a bit only where the pixel changed: # pixel: 0 8 16 24 # old_row: 1111 1111 0000 0000 1111 0000 0000 1111 # new_row: 1111 1111 0011 1100 1111 0000 0000 0000 # changed: 0000 0000 0011 1100 0000 0000 0000 1111 # ^^^^ ^^^^ # 10..13 28..31 changed = old_row.bitwise_xor(new_row) # bit_runs gives [bit, offset, length] for each run: # [[0, 0, 10], [1, 10, 4], [0, 14, 14], [1, 28, 4]] # Keep the runs of 1 (the changed spans) and convert them to Ranges. spans = changed.bit_runs(lsb_first: false).select {|bit, _, _| bit == 1 } .map {|_, x, width| x...(x + width) } spans # => [10...14, 28...32] # Widen each span to byte boundaries for the panel controller: # round the begin down and the end up to a multiple of 8. # 10...14 -> (10 / 8 * 8)...((14 + 7) / 8 * 8) = 8...16 # 28...32 -> (28 / 8 * 8)...((32 + 7) / 8 * 8) = 24...32 spans.map {|r| (r.begin / 8 * 8)...((r.end + 7) / 8 * 8) } # => [8...16, 24...32] ``` #### Columnar data (LSB-first) - **Bulk copies over valid ranges.** An Apache Arrow validity bitmap marks the null elements. Where the valid elements form long runs, a kernel copies each run as one slice and does not test every element. `bit_runs(0, length)` gives the runs within the column length. `bit_run_length(1, i)` tells how many valid elements start at `i`, for a loop that advances by run. ```ruby validity = "\xFC\x0F".b # 12 elements, elements 0 and 1 are null validity.bit_runs(0, 12).select {|bit, _, _| bit == 1 } .map {|_, off, len| off...(off + len) } # => [2...12] ``` #### Microcontrollers - **Block allocators.** A memory allocator or a page map keeps a bitmap of the used blocks. A first-fit allocation for `n` blocks is the first run of cleared bits with a sufficient length. Such an allocator is written in Ruby in two settings. One is a program assuming Spinel compiles AOT to native code, where a bitmap walk in Ruby becomes a plain loop. The other is a microcontroller program that manages a pool of slots. In both cases `each_bit_run` walks the bitmap and allocates nothing. ```ruby bitmap = "\xFF\x0F\xC0\x00".b # 32 blocks, 1 = in use def first_fit(bitmap, n) bitmap.each_bit_run do |bit, off, len| return off if bit.zero? && len >= n end nil end first_fit(bitmap, 8) # => 12 first_fit(bitmap, 20) # => nil ``` - **Pulse widths from a sampled input.** A program samples a GPIO pin at a fixed rate into a bitmap. This turns a signal into runs. `bit_runs` converts the capture into level and width pairs. These pairs are the input of an IR remote decoder (NEC and similar protocols distinguish bits by pulse width) or of a logic analyzer view. ```ruby capture = "\x01\x00\xFF\x0F".b # one sample per bit, LSB-first capture.bit_runs.map {|level, _, width| [level, width] } # => [[1, 1], [0, 15], [1, 12], [0, 4]] ``` ### API Contracts The three methods follow the rules of the earlier tickets. `each_bit_run` and `bit_runs` take the region arguments of #22279 and share every contract of `each_bit` in #22399. In particular, reads clamp, offsets are absolute, errors are raised without a block, the Enumerator validates again on use, and frozen receivers work. `bit_run_length` takes a lone `offset` like `bit_get` in #22118 and a `bit` argument like `each_bit_offset` in #22399. Encoding, `lsb_first:` and the out-of-range errors are as in #22118 and #22279. The contracts below are the ones specific to runs. 1. **Runs are cut at the region boundaries.** The first run starts at the region start, even if the same bit continues before it. The last run ends at the region end. 2. **Each run is one Array** `[bit, offset, length]`, with `bit` as `0` or `1`. A block with three parameters receives the three values. A block with one parameter, or a lambda, receives the Array, as with `Hash#each`. `to_a` and `bit_runs` collect the Arrays. 3. **`bit_run_length` returns `nil`, `0` or a count.** It returns `nil` when `offset` is at or beyond the end of the string. It returns `0` when the bit at `offset` differs from `bit`. Otherwise it counts up to the first differing bit or the end of the string. 4. **Enumerator#size** is the number of runs in the region, computed on demand from the current contents of the receiver. 5. **The block can modify the receiver.** The iteration reads each run from the current contents of the string when it visits the run. It clamps the length of the run to the current end and stops there. A longer receiver does not extend the iteration beyond the original region. ### 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 few = ("\xFF".b * 4096 + "\x00".b * 4096) * 128 # 1 MiB, 256 runs many = "\xAA".b * (1 << 20) # 1 MiB, 8 Mi runs # The alternatives build the same [bit, offset, length] Arrays as bit_runs. def by_chunk_while(s) off = 0 s.bits.chunk_while {|a, b| a == b }.map {|c| [c[0], off, c.size].tap { off += c.size } } end def by_scan(s) off = 0 s.unpack1("b*").scan(/0+|1+/).map {|m| [m.ord - 48, off, m.size].tap { off += m.size } } end 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 { few:, many: }.each do |name, s| raise unless by_chunk_while(s) == s.bit_runs && by_scan(s) == s.bit_runs printf "%-4s chunk_while %.4f\n", name, median { by_chunk_while(s) } printf "%-4s scan %.4f\n", name, median { by_scan(s) } printf "%-4s bit_runs %.4f\n", name, median { s.bit_runs } printf "%-4s size %.4f\n", name, median { s.each_bit_run.size } end printf "index %.6f\n", median { few.unpack1("b*").index("0") } printf "bit_run_length %.6f\n", median { few.bit_run_length(1, 0) } ``` }} | | Few runs | Many runs | |--------------------------|---------:|----------:| | `bits` + `chunk_while` | 700 ms | 2,210 ms | | `unpack1("b*")` + `scan` | 36 ms | 2,440 ms | | `bit_runs` | 1.1 ms | 260 ms | | `each_bit_run.size` | 1.1 ms | 26 ms | | | Few runs | |----------------------------|---------:| | `unpack1("b*").index("0")` | 8.4 ms | | `bit_run_length(1, 0)` | 4 us | The methods skip a byte of all `0` or all `1` bits in one step. In the many-runs case, the Array for each run bounds the time. `each_bit_run.size` makes no Array, so it is 10 times faster there. -- https://bugs.ruby-lang.org/