Feature #22482: String#bit_index, a bit search for String bit operations

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

[hasumikin (hitoshi hasumi)]

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.

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.

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.

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) 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.

  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.

  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.

  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.

Benchmark scriptBenchmark script

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.

Benchmark script for PicoRubyBenchmark script for PicoRuby

# 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.

[hasumikin (hitoshi hasumi)]

• Description updated (diff)