ziglang / zig

General-purpose programming language and toolchain for maintaining robust, optimal, and reusable software.
https://ziglang.org
MIT License
35.16k stars 2.57k forks source link

There are too many ring buffer implementations in the standard library #19231

Open ifreund opened 8 months ago

ifreund commented 8 months ago

As of commit e2cbbd0c264b323a422ef6dc8c586c287aec845a I count at least 4 separate ring buffer implementations:

The current std.RingBuffer implementation is not generic and only supports buffers of u8. It also only supports fixed-length ring buffers while std.fifo.LinearFifo supports a dynamically growable buffer. I think one of two things needs to happen here:

The flate and lzma internal ring buffer implementations are both specialized to the code using them which is fine. However, I suspect they could benefit by using a more generic implementation as a backing data structure.

I don't know exactly what the resolution to this issue should look like, quality API design is quite tricky. However, I think it is important to address before stabilizing the standard library.

dweiller commented 8 months ago

I think a good first step will be for someone (probably easiest for the implementers) to describe the requirements of ring buffers in the various compression implementations. We can then think about what a unified API for a ring buffer that satisfies all these use cases would look like. I think we should remain open to the possibility that a unified ring buffer supporting all the use cases we have may not make sense to implement as there are many trade-offs you can make that may be preferred by the different compression APIs or a 'generic' one like std.fifo.LinearFifo.

For a start, here are features of the std.RingBuffer API that I don't think std.fifo.LinearFifo adequately supports at present:

Note that std.RingBuffer was originally written for the Zstandard implementation and I'd consider it specialized for use cases desiring the above properties with a known (but not compile-time known) maximum size; perhaps it or something similar could be used for all LZ77-style compression schemes.

I think one of two things needs to happen here:

  • std.fifo.linearFifo and std.RingBuffer need to make clear the tradeoffs between the APIs/implementations and present a meaningful choice between the two.

  • Either std.fifo.linearFifo or std.RingBuffer should have its functionality merged into the other and be deleted.

A third option is to move std.RingBuffer to std.compress.zstd.RingBuffer.

[^1]: The Zstandard implementation does not need anything like a 'read the next item' API—they are just convenience functions for users of low-level APIs that decode into a ring buffer. The Zstandard implementation does currently make a single call to std.RingBuffer.readFirstAssumeLength in the reader interface, though a minor refactor could remove this. As far as the internals of std.compress.zstd are concerned a ring buffer that only tracks a write position but not a read position would be fine.