[ruby-core:126279] [Ruby Feature#22231] Add `IO::Buffer#index`
Issue #22231 has been reported by himura467 (Akito Shitara). ---------------------------------------- Feature #22231: Add `IO::Buffer#index` https://bugs.ruby-lang.org/issues/22231 * Author: himura467 (Akito Shitara) * Status: Open ---------------------------------------- ## Use case `IO::Buffer` has no search primitive: no `#index`, no delimiter scan, no substring search. This matters for servers that hand request data to the application as zero-copy `IO::Buffer` views over their own socket read buffer. The zero-copy path ends at the first delimiter scan, such as splitting a query string on `&`, finding a multipart boundary, or scanning a header value, which is where request processing usually begins. The same applies to any protocol parser built on `IO::Buffer`: line framing, chunked transfer encoding, netstrings, length-prefixed records. All of them must find a delimiter before they can decide what to slice. Today there are two ways to do it, and both give up what the buffer was for: ```ruby buffer.get_string.index("&") # copies the whole region to find one offset i = 0 # no copy, but a method call per byte i += 1 while i < buffer.size && buffer.get_value(:U8, i) != 0x26 ``` Searching a 64 KiB body by copying it out is 3.7x slower than searching it in place, and allocates 66 KB per call. The byte loop allocates nothing but is roughly 1570x slower. ## Specification ```ruby buffer.index(object, offset = 0, length = size - offset) # => Integer or nil ``` `object` may be an `Integer` byte value (`0..255`), a `String`, or another `IO::Buffer`. ```ruby buffer = IO::Buffer.for("Hello World") buffer.index("World") # => 6 buffer.index("o".ord) # => 4 buffer.index(IO::Buffer.for("World")) # => 6 buffer.index("!") # => nil buffer.index("o", 5) # => 7 (absolute, not relative to offset) buffer.slice(6, 5).index("o") # => 1 (relative to the slice) ``` - Searching is byte-oriented; a `String`'s encoding is ignored. - An empty `object` matches at `offset`, as with `String#index`. - An `object` longer than the range returns `nil`. - An out-of-range `offset` or `length` raises `ArgumentError` (see below). Single-byte values use `memchr`. Longer values reuse `rb_memsearch`, the portable substring search that already backs `String#index`. ## Open questions ### Out-of-range `offset`/`length` raises, where `String#index` returns `nil`. All ten existing `(offset, length)` methods in `io_buffer.c` route through `io_buffer_validate_range` and raise, and the class never clamps. `String#index` also has no `length` parameter, so matching it does not settle what `length` should do; the Ruby-wide convention there is to clamp, as in `"hello".byteslice(0, 1000)`, which is what `IO::Buffer` declines to do elsewhere. I chose consistency within the class, and am happy to switch if the `String` reading is preferred. ### An `Integer` outside `0..255` raises, where `#clear` masks it. `buffer.clear(256)` fills with `0`, and `String#setbyte` masks too. Masking a value being searched for seems worse than masking one being written, since `index(256)` would quietly search for `\x00` and could return a match. ## Follow-ups `#rindex` for a reverse scan, and an `#each_until(delimiter)` framing iterator yielding successive delimited slices, in the same spirit as the vectorizable `#and!` / `#or!` / `#bit_count` family. Both build on `#index`, so this ticket is scoped to it. -- https://bugs.ruby-lang.org/
Issue #22231 has been updated by matz (Yukihiro Matsumoto). I have no objection to the direction. Finding a delimiter is where a parser begins, and a zero copy buffer that cannot do it stops being zero copy at the first `&`. Please work out the design with @ioquatix, who is in charge of `IO::Buffer`, before proceeding. On the out of range `offset` and `length`: please return `nil`, following `String#index`. Finding nothing and searching an empty range are the same answer, and raising makes ordinary scanning loops awkward. Make sure `offset == size` is a valid empty range so that `i = buffer.index(byte, i + 1)` terminates rather than raises. One thing I want to state clearly, aimed at the follow-ups rather than at this method. `#rindex`, `#each_until`, and whatever follows: if we keep going this way, `IO::Buffer` becomes a second `String` under another name, and I do not want Ruby to have two string classes. Each addition should be justified by what `IO::Buffer` is for, which is working on memory it does not own, and not by `String` having a method of that name. Please propose the follow-ups one at a time, each with its own use case. Matz. ---------------------------------------- Feature #22231: Add `IO::Buffer#index` https://bugs.ruby-lang.org/issues/22231#change-118426 * Author: himura467 (Akito Shitara) * Status: Open ---------------------------------------- ## Use case I am writing nack-ruby (https://github.com/nsgi-org/nack-ruby), a Ruby implementation of NSGI, a host/guest interface for web applications. The host hands each HTTP request field to Ruby as an `IO::Buffer` view over its own socket read buffer, so a request reaches the application without its bytes being copied. That holds right up until the application parses inside a field, which is where request handling actually begins: splitting a query string on `&` and `=`, scanning a body for a multipart boundary, cutting a header value at a delimiter. `IO::Buffer` has no way to find a byte, so at that point the only options are: ```ruby buffer.get_string.index("&") # copies the field to find one offset i = 0 # no copy, but a method call per byte i += 1 while i < buffer.size && buffer.get_value(:U8, i) != 0x26 ``` The first throws away the zero-copy path the host went to the trouble of providing, and allocates a `String` proportional to the field; copying a 64 KiB body out to search it measures 3.7x slower than searching it in place, and produces 66 KB of garbage per call. The second keeps the buffer but is roughly 1570x slower. Either way the buffer stops paying for itself at the first delimiter. This is not specific to NSGI. Any protocol parser built on `IO::Buffer`, such as line framing, chunked transfer encoding, or length-prefixed records, has to find a delimiter before it can decide what to slice. ## Specification ```ruby buffer.index(object, offset = 0, length = size - offset) # => Integer or nil ``` `object` may be an `Integer` byte value (`0..255`), a `String`, or another `IO::Buffer`. ```ruby buffer = IO::Buffer.for("Hello World") buffer.index("World") # => 6 buffer.index("o".ord) # => 4 buffer.index(IO::Buffer.for("World")) # => 6 buffer.index("!") # => nil buffer.index("o", 5) # => 7 (absolute, not relative to offset) buffer.slice(6, 5).index("o") # => 1 (relative to the slice) ``` - Searching is byte-oriented; a `String`'s encoding is ignored. - An empty `object` matches at `offset`, as with `String#index`. - An `object` longer than the range returns `nil`. - An out-of-range `offset` or `length` raises `ArgumentError` (see below). Single-byte values use `memchr`. Longer values reuse `rb_memsearch`, the portable substring search that already backs `String#index`. ## Open questions ### Out-of-range `offset`/`length` raises, where `String#index` returns `nil`. All ten existing `(offset, length)` methods in `io_buffer.c` route through `io_buffer_validate_range` and raise, and the class never clamps. `String#index` also has no `length` parameter, so matching it does not settle what `length` should do; the Ruby-wide convention there is to clamp, as in `"hello".byteslice(0, 1000)`, which is what `IO::Buffer` declines to do elsewhere. I chose consistency within the class, and am happy to switch if the `String` reading is preferred. ### An `Integer` outside `0..255` raises, where `#clear` masks it. `buffer.clear(256)` fills with `0`, and `String#setbyte` masks too. Masking a value being searched for seems worse than masking one being written, since `index(256)` would quietly search for `\x00` and could return a match. ## Follow-ups `#rindex` for a reverse scan, and an `#each_until(delimiter)` framing iterator yielding successive delimited slices, in the same spirit as the vectorizable `#and!` / `#or!` / `#bit_count` family. Both build on `#index`, so this ticket is scoped to it. -- https://bugs.ruby-lang.org/
Issue #22231 has been updated by ioquatix (Samuel Williams). Thanks for creating this issue, I will review the details. ---------------------------------------- Feature #22231: Add `IO::Buffer#index` https://bugs.ruby-lang.org/issues/22231#change-118639 * Author: himura467 (Akito Shitara) * Status: Open ---------------------------------------- ## Use case I am writing nack-ruby (https://github.com/nsgi-org/nack-ruby), a Ruby implementation of NSGI, a host/guest interface for web applications. The host hands each HTTP request field to Ruby as an `IO::Buffer` view over its own socket read buffer, so a request reaches the application without its bytes being copied. That holds right up until the application parses inside a field, which is where request handling actually begins: splitting a query string on `&` and `=`, scanning a body for a multipart boundary, cutting a header value at a delimiter. `IO::Buffer` has no way to find a byte, so at that point the only options are: ```ruby buffer.get_string.index("&") # copies the field to find one offset i = 0 # no copy, but a method call per byte i += 1 while i < buffer.size && buffer.get_value(:U8, i) != 0x26 ``` The first throws away the zero-copy path the host went to the trouble of providing, and allocates a `String` proportional to the field; copying a 64 KiB body out to search it measures 3.7x slower than searching it in place, and produces 66 KB of garbage per call. The second keeps the buffer but is roughly 1570x slower. Either way the buffer stops paying for itself at the first delimiter. This is not specific to NSGI. Any protocol parser built on `IO::Buffer`, such as line framing, chunked transfer encoding, or length-prefixed records, has to find a delimiter before it can decide what to slice. ## Specification ```ruby buffer.index(object, offset = 0, length = size - offset) # => Integer or nil ``` `object` may be an `Integer` byte value (`0..255`), a `String`, or another `IO::Buffer`. ```ruby buffer = IO::Buffer.for("Hello World") buffer.index("World") # => 6 buffer.index("o".ord) # => 4 buffer.index(IO::Buffer.for("World")) # => 6 buffer.index("!") # => nil buffer.index("o", 5) # => 7 (absolute, not relative to offset) buffer.slice(6, 5).index("o") # => 1 (relative to the slice) ``` - Searching is byte-oriented; a `String`'s encoding is ignored. - An empty `object` matches at `offset`, as with `String#index`. - An `object` longer than the range returns `nil`. - An out-of-range `offset` or `length` raises `ArgumentError` (see below). Single-byte values use `memchr`. Longer values reuse `rb_memsearch`, the portable substring search that already backs `String#index`. ## Open questions ### Out-of-range `offset`/`length` raises, where `String#index` returns `nil`. All ten existing `(offset, length)` methods in `io_buffer.c` route through `io_buffer_validate_range` and raise, and the class never clamps. `String#index` also has no `length` parameter, so matching it does not settle what `length` should do; the Ruby-wide convention there is to clamp, as in `"hello".byteslice(0, 1000)`, which is what `IO::Buffer` declines to do elsewhere. I chose consistency within the class, and am happy to switch if the `String` reading is preferred. ### An `Integer` outside `0..255` raises, where `#clear` masks it. `buffer.clear(256)` fills with `0`, and `String#setbyte` masks too. Masking a value being searched for seems worse than masking one being written, since `index(256)` would quietly search for `\x00` and could return a match. ## Follow-ups `#rindex` for a reverse scan, and an `#each_until(delimiter)` framing iterator yielding successive delimited slices, in the same spirit as the vectorizable `#and!` / `#or!` / `#bit_count` family. Both build on `#index`, so this ticket is scoped to it. -- https://bugs.ruby-lang.org/
Issue #22231 has been updated by himura467 (Akito Shitara). Thanks for taking this. Matz asked for out-of-range `offset` and `length` to return `nil` rather than raise. Assuming you have no objection to that direction, there are a few points I would like to think through. The first is whether a `length` running past the end should return `nil` or be clamped to `size - offset`. Under `nil`, one result stands both for a range that was out of range and for a value that is not in the buffer. With clamping, `nil` says only that the value does not occur in the bytes searched, and an over-long `length` reads as "to the end", as `String#byteslice` already does. I mildly prefer clamping. The second is the negative `offset`. `String#index` reads it as end-relative, while `IO::Buffer` rejects negative offsets everywhere. Which should `index` do? I have no strong opinion. One constraint rather than a question: `rb_memsearch` takes `long`, so on LLP64 a range above `LONG_MAX` cannot be searched in a single call, which a mapped buffer can reach. Chunking the range with an `object_size - 1` overlap covers it; `memchr` takes `size_t` and is unaffected. ---------------------------------------- Feature #22231: Add `IO::Buffer#index` https://bugs.ruby-lang.org/issues/22231#change-118642 * Author: himura467 (Akito Shitara) * Status: Open * Assignee: ioquatix (Samuel Williams) ---------------------------------------- ## Use case I am writing nack-ruby (https://github.com/nsgi-org/nack-ruby), a Ruby implementation of NSGI, a host/guest interface for web applications. The host hands each HTTP request field to Ruby as an `IO::Buffer` view over its own socket read buffer, so a request reaches the application without its bytes being copied. That holds right up until the application parses inside a field, which is where request handling actually begins: splitting a query string on `&` and `=`, scanning a body for a multipart boundary, cutting a header value at a delimiter. `IO::Buffer` has no way to find a byte, so at that point the only options are: ```ruby buffer.get_string.index("&") # copies the field to find one offset i = 0 # no copy, but a method call per byte i += 1 while i < buffer.size && buffer.get_value(:U8, i) != 0x26 ``` The first throws away the zero-copy path the host went to the trouble of providing, and allocates a `String` proportional to the field; copying a 64 KiB body out to search it measures 3.7x slower than searching it in place, and produces 66 KB of garbage per call. The second keeps the buffer but is roughly 1570x slower. Either way the buffer stops paying for itself at the first delimiter. This is not specific to NSGI. Any protocol parser built on `IO::Buffer`, such as line framing, chunked transfer encoding, or length-prefixed records, has to find a delimiter before it can decide what to slice. ## Specification ```ruby buffer.index(object, offset = 0, length = size - offset) # => Integer or nil ``` `object` may be an `Integer` byte value (`0..255`), a `String`, or another `IO::Buffer`. ```ruby buffer = IO::Buffer.for("Hello World") buffer.index("World") # => 6 buffer.index("o".ord) # => 4 buffer.index(IO::Buffer.for("World")) # => 6 buffer.index("!") # => nil buffer.index("o", 5) # => 7 (absolute, not relative to offset) buffer.slice(6, 5).index("o") # => 1 (relative to the slice) ``` - Searching is byte-oriented; a `String`'s encoding is ignored. - An empty `object` matches at `offset`, as with `String#index`. - An `object` longer than the range returns `nil`. - An out-of-range `offset` or `length` raises `ArgumentError` (see below). Single-byte values use `memchr`. Longer values reuse `rb_memsearch`, the portable substring search that already backs `String#index`. ## Open questions ### Out-of-range `offset`/`length` raises, where `String#index` returns `nil`. All ten existing `(offset, length)` methods in `io_buffer.c` route through `io_buffer_validate_range` and raise, and the class never clamps. `String#index` also has no `length` parameter, so matching it does not settle what `length` should do; the Ruby-wide convention there is to clamp, as in `"hello".byteslice(0, 1000)`, which is what `IO::Buffer` declines to do elsewhere. I chose consistency within the class, and am happy to switch if the `String` reading is preferred. ### An `Integer` outside `0..255` raises, where `#clear` masks it. `buffer.clear(256)` fills with `0`, and `String#setbyte` masks too. Masking a value being searched for seems worse than masking one being written, since `index(256)` would quietly search for `\x00` and could return a match. ## Follow-ups `#rindex` for a reverse scan, and an `#each_until(delimiter)` framing iterator yielding successive delimited slices, in the same spirit as the vectorizable `#and!` / `#or!` / `#bit_count` family. Both build on `#index`, so this ticket is scoped to it. -- https://bugs.ruby-lang.org/
participants (3)
-
himura467 (Akito Shitara) -
ioquatix (Samuel Williams)
-
matz (Yukihiro Matsumoto)