Provide an API for performant bulk or sequential read/writes

[fzhinkin]

trafficstars

As stated in https://github.com/Kotlin/kotlinx-io/issues/132, kotlinx-io don't include Okio APIs aimed for performant sequential and bulk ops (like, UnsafeCursor).

Such API is required to implement previously removed functionality (like select) efficiently. It's also required for integration with platform-specific APIs (like hash functions implementation using Java's MessageDigest API).

This issue claims the intent to provide such functionality, but the actual API will be discussed later.

[whyoleg]

Just wanted to mention, that from my perspective this should be implemented taking into account future feature from #131: different memory types (in addition to byte arrays) Buffers are built upon (like NIO ByteBuffers on JVM); Use-case: https://github.com/ktorio/ktor-io/issues/7 Ideally it should be possible to use JDK MessageDigest/Cipher API for Buffer with multiple underlying segments of different types like ByteBuffer, ByteArray, MemorySegment and even Netty ByteBuf (which allows to get ByteBuffer from it).

[fzhinkin]

An implementation will definitely take different memory types into account, otherwise, it'll be hard to make performant reads/writes.

[rnett]

I am trying to implement a custom HashingSink (using Guava's hash functions, but it doesn't really matter) and found that implementing a custom sink is rather difficult because it's not easy to read (groups of) bytes from a Buffer yourself, especially without "consuming" them (so I can forward to the "real" sink). This makes it very hard to implement custom sinks or sources. It seems like this issue would be the feature responsible for solving this, is that correct? If not I'll create a new one.

[fzhinkin]

@rnett, that's correct. Once solved, this issue should allow more easily implementing things like HashingSink. I'm currently finalizing the design and will post it soon.

[fzhinkin]

Here's an update with the details on an API we will implement.

Intro

In general, there are two groups of cases when existing public API works poorly both performance- and convenience-wise:

• integration with other frameworks/libraries/platform APIs;
• custom extensions.

The first group usually requires taking as much data as possible and passing it down to other API, or, reserving some empty space in advance and then supply it to the underlying API to fill it up. For example, POSIX declares vectorized-io functions, readv and writev, allowing to read/write multiple chunks of data using a single system call (if you're familiar with Java NIO API, Gathering- and ScatteringChannel provide the same functionality). If one wants to integrate kotlinx-io with such an API, there is no efficient way to do that as data stored within a buffer could only be accessed by copying.

The second group is about various extensions that need to access some variadic amount of bytes in an efficient manner. For example, to read LEB128-encoded value, one has to read data byte by byte until either the value is fully decoded or an error condition is detected. The only way to implement such an extension right now is by calling Source::readByte which, when called sequentially multiple times, has a significant overhead for such a scenario compared to direct access to the buffer's underlying bytes. Yet another example from this group is computing a checksum/digest over the buffer's content without consuming it: one must somehow iterate over the buffer's content and pass it to some API, like Java's MessageDigest. There's no way it could be implemented efficiently with the existing API.

Proposed API

One of the goals we're trying to achieve with an unsafe/bulk API is to provide a way to write efficient code, meaning, among anything else, that the amount of data copying should be minimal. That requires segment data to be directly accessible. However, we also want to have an abstraction layer above existing byte-array backed segments so we can change the underlying container from byte array to Java ByteBuffer/native off-heap buffer/Wasm linear memory/etc in the future without breaking client's code. There are not so many ways to guarantee zero-copy on access and, at the same time, fully abstract the underlying type away. Instead, we decided to split the API into three logical tiers, where only one of them provides direct access to segment's internal container, and it's zero-copy on a best-effort basis only. With that weak guarantee, an API returning/consuming byte arrays continues to work even after segments change its underlying container, just with reduced performance. And, if the underlying container type changes on one of the platforms, corresponding zero-copy accessors will be provided there.

The proposed API consists of the following three tiers:

1. a bulk API for reading/writing data from/to buffers
2. an API to iterate over buffer's segments
3. an API to read segments data / append data into a buffer with a byte granularity

These tiers are intertwined, and sometimes boundaries are fuzzy. I'm mentioning them mostly to structure the document and make it more approachable.

1. A Bulk API

The API aimed for integration with other APIs and consists of the following functions:

• UnsafeBufferOperations.moveToTail(buffer: Buffer, bytes: ByteArray, startIndex: Int = 0, endIndex: Int = bytes.size): Unit
• UnsafeBufferOperations.readFromHead(buffer: Buffer, readAction: (ByteArray, Int, Int) -> Int): Unit
• UnsafeBufferOperations.writeToTail(buffer: Buffer, minimumCapacity: Int, writeAction: (ByteArray, Int, Int) -> Int): Unit

On JVM, the following extensions will be provided:

• UnsafeBufferOperations.readFromHead(buffer: Buffer, readAction: (ByteBuffer) -> Unit): Unit
• UnsafeBufferOperations.readBulk(buffer: Buffer, iovec: Array<ByteBuffer?>, readAction: (Array<ByteBuffer?>, Int) -> Long): Unit
• UnsafeBufferOperations.writeToTail(buffer: Buffer, minimumCapacity: Int, writeAction: (ByteBuffer) -> Unit): Unit

There will be no writeBulk at the moment, but it might be added later.

Additionally, there's a SegmentReadContext.withData function allowing to access segment data. This function makes sense in the context of buffer iteration (the next section), but I'm mentioning it here as it provides bulk access.

Note that for Native, extensions similar to JVMs could also be provided.

2. Buffer iteration API

To iterate over buffer segments, we're going to make Segment and some of its properties public. Yet another change aimed to simplify iteration and allow it to be done without any allocations is that segments will no longer be organized into a cicrualar queue, as it was previously. Instead, there will be separate head/tail references inside the buffer, segments continue referencing their predecessors and successors, but now the head's previous segment will be null, as well as the tail's next segment.

Will all that being said, one can start iteration from either buffer's head or a segment covering a specific offset:

• UnsafeBufferOperations.iterate

These functions supply a BufferIterationContext that could be used to get a next segment. If there is no segment next, the next call returns null.

BufferIterationContext extends SegmentReadContext, allowing to both get whole segment's data using withData and reading bytes individually using getUnchecked.

3. Byte-granular read/write API

Given a SegmentReadContext (that could be obtained by calling readFromHead or iterate), one can access individual segment bytes using getUnchecked.

Given a SegmentWriteContext (could be obtained by calling writeToTail), one can write individual bytes into uncommitted part of a tail segments using setUnchecked.

Total number of readable bytes always lies in range 0..Segment.size.

A total number of writable bytes is always within 0..Segment.remainingCapacity.

Alternatives

Several alternatives were considered, namely:

Using Okio's UnsafeCursor

UnsafeCursor is a really nice API, but it has to expose a reference to the underlying data container so that does not solve one of the major challenges we have with this API.

Providing some Iterator over segments

Iterators work well on JVM, thanks to the advanced JIT compilers, but on ART, it results in excessive memory allocations, which significantly slow down existing code.

Exposing the underlying container as Any

... so that users could check if the container has an appropriate type, cast it to that type and then simply use it.

That approach fails short when it comes to testing: there should always be a code path that somehow handles a segment when its data type is not what was expected (for instance, it's not a ByteArray). Until there are polymorphic segments (and we're not implementing them yet), these paths are effectively untestable.

The plan

Assuming there will be no concerns with the proposed API, internal API changes will be rolled out first and then the public API will follow.

[lppedd]

If kotlinx-benchmarks is in a good state, it would also be nice to add benchmarks for JS and Native, to see how they compare over time.