Feature #22482
Updated by hasumikin (hitoshi hasumi) about 7 hours ago
Impl: (WIP) This is a reply to the comment of Matz in #22399#note-3. It replaces the seven methods of #22399 and #22405 with one search method. The deferred methods can be written on top of it in Ruby, and the last section gives the measurements on PicoRuby that Matz asked for. The region form of `bit_get`, which replaces the Integer fold of `bits`, is proposed separately in #22483. #XXXXX. ### What this adds ``` String#bit_index(bit, offset = 0, lsb_first: true) -> Integer | nil String#bit_index(bit, offset, length, lsb_first: true) -> Integer | nil String#bit_index(bit, range, lsb_first: true) -> Integer | nil ``` `bit_index` returns the offset of the first bit at or after `offset` that is equal to `bit`, or `nil`. The `bit` argument is `0`, `1`, `true` or `false`. A byte that holds no matching bit is skipped in one step. A `length` or a `range` limits the search to a window, with the region arguments of #22279. ```ruby data = "\xF0\xAA".b data.bit_index(1) # => 4 data.bit_index(0, 4) # => 8 data.bit_index(1, lsb_first: false) # => 0 data.bit_index(1, 0...4) # => nil "\x00".b.bit_index(1) # => nil ``` ### The deferred methods, written on top `bit_offsets`, `bit_runs` and `bit_run_length` can be written on top of a search method in a few lines. This is the case. ```ruby def bit_offsets(s, bit) offsets = [] i = -1 offsets << i while (i = s.bit_index(bit, i + 1)) offsets end def bit_run_length(s, bit, offset) current = s.bit_get(offset) return nil if current.nil? return 0 if current != bit (s.bit_index(1 - bit, offset) || s.bytesize * 8) - offset end def each_bit_run(s) i = 0 size = s.bytesize * 8 while i < size bit = s.bit_get(i) j = s.bit_index(1 - bit, i) || size yield bit, i, j - i i = j end end ``` `each_bit` and `bits` are replaced by a `bit_get` loop. Where the examples in #22399 folded the Array into an Integer, the region form of `bit_get` (#22483) (#XXXXX) reads the Integer directly. ### Use cases - **Null positions in columnar data (LSB-first).** An Apache Arrow validity bitmap marks the null elements. An Arrow array is a slice over a shared bitmap, so the window is the slice, and the padding bits are never read. ```ruby validity = "\xFD\x03".b # 10 elements, element 1 is null, bits 10..15 are padding nulls = [] pos = 0 while (i = validity.bit_index(0, pos...10)) nulls << i pos = i + 1 end nulls # => [1] ``` - **Block allocators.** A first-fit allocation for `n` blocks is the first run of cleared bits with a sufficient length. The loop allocates nothing. ```ruby bitmap = "\xFF\x0F\xC0\x00".b # 32 blocks, 1 = in use def first_fit(bitmap, n) size = bitmap.bytesize * 8 i = 0 while (i = bitmap.bit_index(0, i)) j = bitmap.bit_index(1, i) || size return i if j - i >= n i = j end nil end first_fit(bitmap, 8) # => 12 first_fit(bitmap, 20) # => nil ``` - **Variable-length codes (MSB-first).** A Rice code stores a value as a unary run of set bits, a cleared bit, and `k` remainder bits. `bit_index(0, pos, lsb_first: false)` finds the end of the run, and the region form of `bit_get` reads the remainder. ```ruby def read_rice(bs, pos, k) stop = bs.bit_index(0, pos, lsb_first: false) # the cleared bit after the run q = stop - pos r = bs.bit_get(stop + 1, k, lsb_first: false) [(q << k) | r, stop + 1 + k] end bs = "\x79\x14".b # 0111 1001 0001 0100 pos = 0 values = [] 4.times do value, pos = read_rice(bs, pos, 2) values << value end values # => [3, 9, 0, 6] ``` - **Changed spans of an e-paper frame** are the runs of set bits in `old_row.bitwise_xor(new_row)`, found by the loop of `each_bit_run` above. **A pending interrupt** or **a free block** is found with one call and handled, with no loop at all. ### API Contracts 1. **Arguments** follow #22118 and #22279. A negative `offset` raises `IndexError`. A negative `length` raises `ArgumentError`. A position or length beyond `2**64 - 1` raises `ArgumentError`. The `lsb_first` value must be `true` or `false`. A Range with a `length` raises `ArgumentError`, as in `bit_count`. 2. **The `bit` argument** accepts `0`, `1`, `true` or `false`. Any other object is converted with `to_int`, as for an index. An Integer other than `0` or `1` raises `ArgumentError`. 3. **The result is an absolute offset** in the numbering that `lsb_first:` selects, so `s.bit_set?(i, lsb_first: x)` is true for `i = s.bit_index(1, lsb_first: x)`. An `offset` at or beyond the end returns `nil`, like `bit_get`. 4. **A window clamps.** A `length` or a `range` is a window with the region rules of `bit_count`: a window that extends past the end is clamped to the end of the string, as the search of `String#index` is. A window with no matching bit returns `nil`, and so does an empty window. 5. **Frozen receivers** work. **Encoding** has no effect. The method treats the receiver as a byte sequence, as in #22118. ### Scope: no iterator in this ticket `bit_index` follows the cursor idiom of `String#index`. The idiom has a known cost: a scan of single bits in dense data runs the loop body once per matching bit in Ruby, and the method call bounds the loop. The measurements below show this. On CRuby the loop is 4 times slower than the `bit_offsets` of #22399 on a dense buffer, and on the Pico 2 W a run of 1 bit gives the search nothing to skip, so the loop is a little slower than a `bit_get` loop there. This ticket targets the sparse and the run cases, which Matz named, and accepts the dense scan. I measured C iterator prototypes with a block (`each_bit_index`, `each_bit_run`): a block call costs about as much as a method call, so they gain 1.0 to 1.6 times on CRuby and 2 to 3 times on the Pico. If an iterator is wanted later, the use cases point to `each_bit_run {|bit, offset, length| }`, with the window forms of `bit_index`, and it can be added on top of the same C search. `bit_run_length(bit, offset)` was considered as the primitive instead of `bit_index`: the two carry the same information, but `bit_index` is the idiom of `String#index` and the one that `each_bit_run` would build on. ### Performance on CRuby Each time is the median of 5 calls. 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 runs = "".b # 1 MiB, 1,024 runs of 8,192 bits 1024.times { |i| runs << ((i.even? ? "\x00" : "\xFF").b * 1024) } N = 1 << 23 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 # bit_offsets on top of bit_index, against the alternatives of #22399 def offsets_by_loop(s) = (0...N).select { s.bit_set?(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 offsets_by_bit_index(s) offsets = [] i = -1 offsets << i while (i = s.bit_index(1, i + 1)) offsets end # bit_run_length and bit_runs on top of bit_index def run_length_by_loop(s, offset) bit = s.bit_get(offset) i = offset + 1 i += 1 while i < N && s.bit_get(i) == bit i - offset end def run_length_by_bit_index(s, offset) bit = s.bit_get(offset) (s.bit_index(1 - bit, offset) || N) - offset end def runs_by_loop(s) result = [] i = 0 while i < N bit = s.bit_get(i) j = i + 1 j += 1 while j < N && s.bit_get(j) == bit result << [bit, j - i] i = j end result end def runs_by_bit_index(s) result = [] i = 0 while i < N bit = s.bit_get(i) j = s.bit_index(1 - bit, i) || N result << [bit, j - i] i = j end result end def count_runs_by_loop(s) count = 0 i = 0 while i < N bit = s.bit_get(i) i += 1 i += 1 while i < N && s.bit_get(i) == bit count += 1 end count end def count_runs_by_bit_index(s) count = 0 i = 0 while i < N bit = s.bit_get(i) i = s.bit_index(1 - bit, i) || N count += 1 end count end { sparse:, dense: }.each do |name, s| raise unless offsets_by_loop(s) == offsets_by_bit_index(s) && offsets_by_unpack(s) == offsets_by_bit_index(s) 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 offsets bit_index %.4f\n", name, median { offsets_by_bit_index(s) } end printf "run_length loop %.4f\n", median { 1000.times { run_length_by_loop(runs, 0) } } printf "run_length bit_index %.4f\n", median { 1000.times { run_length_by_bit_index(runs, 0) } } raise unless runs_by_loop(runs) == runs_by_bit_index(runs) printf "runs loop %.4f\n", median { runs_by_loop(runs) } printf "runs bit_index %.4f\n", median { runs_by_bit_index(runs) } raise unless count_runs_by_loop(dense) == N && count_runs_by_bit_index(dense) == N printf "short runs loop %.4f\n", median { runs_by_loop(dense) } printf "short runs bit_index %.4f\n", median { runs_by_bit_index(dense) } printf "short runs loop, count %.4f\n", median { count_runs_by_loop(dense) } printf "short runs bit_index, count %.4f\n", median { count_runs_by_bit_index(dense) } ``` }} **Offsets of the set bits of 1 MiB** (`bit_offsets` written on top of `bit_index`): | | Sparse | Dense | |------------------------------------------------------------|--------:|-------:| | `bit_set?` loop | 461 ms | 493 ms | | `unpack1("b*")` + `index` | 8.9 ms | 351 ms | | `bit_index` loop | 0.7 ms | 176 ms | | `bit_offsets` in C, no block (#22399 patch, for reference) | 1.2 ms | 41 ms | For sparse data, the Ruby loop over `bit_index` is as fast as the C method of #22399. For dense data, the method call per bit bounds the loop, and the C method is 4 times faster. The loop is still faster than `unpack`. **Runs of 1 MiB with 1,024 runs** (`bit_run_length` and `bit_runs` written on top of `bit_index`): | | `bit_get` loop | `bit_index` | |-------------------------------|---------------:|------------:| | `bit_run_length(1, 0)` x1,000 | 358 ms | 1.0 ms | | all 1,024 runs | 293 ms | 1.0 ms | For long runs, `bit_index` gives the same speed as the C methods of #22405 (1.1 ms for the same buffer shape). **Short runs of 1 MiB with 8 Mi runs of 1 bit** (the dense buffer). This is the data of the memory concern of Matz about `bit_runs`: one Array per run. The first row builds that Array, the second row only counts the runs. | | `bit_get` loop | `bit_index` loop | C method of #22405, no block (for reference) | |-----------------------------|---------------:|-----------------:|---------------------------------------------:| | all runs, one Array per run | 1,224 ms | 942 ms | 256 ms (`bit_runs`) | | all runs, count only | 646 ms | 543 ms | 25.5 ms (`each_bit_run.size`) | For short runs, `bit_index` gives no gain over `bit_get`: two method calls per run bound the loop. The Array per run costs about 400 to 600 ms in Ruby and 230 ms in C. ### Performance on PicoRuby I ported `bit_index` to the mruby VM of PicoRuby (`mruby-string-bitops`, which already has the methods of #22118 and #22279) and ran the same comparisons on a board. - Board: Raspberry Pi Pico 2 W (RP2350, Cortex-M33 at 150 MHz) - Firmware: R2P2 4.0.6, PicoRuby master at a90afd12 plus this patch, mruby VM, `MRB_INT64`, release build - Buffers: 8 KiB (65,536 bits), so that every variant fits in RAM. Each time is the median of 5 runs, measured with `Machine.uptime_us`. {{collapse(Benchmark script for PicoRuby) ```ruby # bitbench - benchmark String#bit_index require 'benchmark' SIZE = 8 * 1024 BITS = SIZE * 8 REPEAT = 5 sparse = "\x00" * SIZE # 64 set bits i = 0 while i < 64 sparse.bit_set(i * 1024 + 3) i += 1 end dense = "\xAA" * SIZE # every other bit set runs = "" # 8 runs of 8,192 bits i = 0 while i < 8 runs << ((i % 2 == 0) ? "\x00" : "\xFF") * 1024 i += 1 end def offsets_by_loop(s) sum = 0 i = 0 while i < BITS sum += i if s.bit_set?(i) i += 1 end sum end def offsets_by_bit_index(s) sum = 0 i = -1 while (i = s.bit_index(1, i + 1)) sum += i end sum end def run_length_by_loop(s, offset) bit = s.bit_get(offset) i = offset + 1 i += 1 while i < BITS && s.bit_get(i) == bit i - offset end def run_length_by_bit_index(s, offset) bit = s.bit_get(offset) (s.bit_index(1 - bit, offset) || BITS) - offset end def runs_by_loop(s) count = 0 i = 0 while i < BITS bit = s.bit_get(i) j = i + 1 j += 1 while j < BITS && s.bit_get(j) == bit count += 1 i = j end count end def runs_by_bit_index(s) count = 0 i = 0 while i < BITS bit = s.bit_get(i) j = s.bit_index(1 - bit, i) || BITS count += 1 i = j end count end puts "== offsets of the set bits (bit_offsets equivalent) ==" Benchmark.bm(28, repeat: REPEAT) do |x| x.report("sparse: bit_set? loop") { offsets_by_loop(sparse) } x.report("sparse: bit_index loop") { offsets_by_bit_index(sparse) } x.report("dense: bit_set? loop") { offsets_by_loop(dense) } x.report("dense: bit_index loop") { offsets_by_bit_index(dense) } end puts "== run length at offset 0 (bit_run_length equivalent, x10) ==" Benchmark.bm(28, repeat: REPEAT) do |x| x.report("bit_get loop") { i = 0; while i < 10; run_length_by_loop(runs, 0); i += 1; end } x.report("bit_index") { i = 0; while i < 10; run_length_by_bit_index(runs, 0); i += 1; end } end puts "== all 8 runs (bit_runs equivalent) ==" Benchmark.bm(28, repeat: REPEAT) do |x| x.report("bit_get loop") { runs_by_loop(runs) } x.report("bit_index loop") { runs_by_bit_index(runs) } end puts "== all #{BITS} runs of 1 bit (bit_runs equivalent, short runs) ==" Benchmark.bm(28, repeat: REPEAT) do |x| x.report("bit_get loop") { runs_by_loop(dense) } x.report("bit_index loop") { runs_by_bit_index(dense) } end ``` }} **Offsets of the set bits of 8 KiB** (`bit_offsets` written on top of `bit_index`): | | Sparse | Dense | |------------------|---------:|---------:| | `bit_set?` loop | 2,172 ms | 2,222 ms | | `bit_index` loop | 4.2 ms | 1,195 ms | **Runs of 8 KiB with 8 runs** (`bit_run_length` and `bit_runs` written on top of `bit_index`): | | `bit_get` loop | `bit_index` | |----------------------------|---------------:|------------:| | `bit_run_length(1, 0)` x10 | 2,841 ms | 3.2 ms | | all 8 runs | 2,268 ms | 2.6 ms | **Short runs of 8 KiB with 65,536 runs of 1 bit** (the dense buffer; the rows count the runs and make no Array): | | `bit_get` loop | `bit_index` loop | |-----------------|---------------:|-----------------:| | all 65,536 runs | 4,387 ms | 4,647 ms | For short runs, the `bit_index` loop is a little slower than the `bit_get` loop on the microcontroller. A run of one bit gives the search in C nothing to skip, and a `bit_index` call costs a little more than the `bit_get` call it replaces. The ratios are the same as on CRuby, but the absolute times matter more here. A `bit_set?` loop over 8 KiB takes 2.2 seconds on the microcontroller. The `bit_index` loop takes 4.2 ms for sparse data, which is the difference between a usable and an unusable bitmap scan. None of the variants allocates per element, so the heap in use did not change beyond GC noise (within 8 KiB) during any row.