Design of a ZSTD compression library in otherlibs/

[xavierleroy]

Context

Since release 5.1.1, the OCaml compilers use the ZSTD data compression library to reduce the size of compilation artifacts, but the runtime machinery developed to support this is not accessible from OCaml programs. We floated around the idea of adding an "other library" (similar to Unix or Str) to the core distribution that would provide user access to ZSTD compression. Below is a proposal for the API of such a library. I hope an API design can be agreed upon quickly enough for possible inclusion in OCaml 5.2.

Meta-context

I find pull requests to be the wrong place for discussing new libraries, as they mix API design with actual implementation, and the discussions are neither productive nor pleasant. To try something else, I'm using a Github discussion and I'm focusing on the API and its design rationale. I have code but will not update it and show it until an API is agreed upon. I'm expecting the discussions to be as abusive as for a regular PR, but at least there will be less back and forth on the implementation.

Package name

The library will be part of the OCaml core distribution, so there will be no OPAM package for it. However, it still needs a name for ocamlfind use and for the subdirectory in ocamlc -where. Two proposals:

• zstd (more specific; conflicts with https://github.com/ygrek/ocaml-zstd)
• compression (more generic, perhaps too generic; no known conflicts)

Main module name

Here, I think ZSTD works fine and gives clear qualified names ZSTD.compress, ZSTD.decompress, ZSTD.Marshal.to_channel, etc.

Compression leads to less nice names: Compression.compression, Compression.decompression.

Simple interface

Just two functions operating over whole strings:

val compress: ?level: int -> string -> string
val decompress: string -> string

I don't think we need to provide variants for bytes, sub-strings, sub-bytes, etc. Copying these two/from strings is quite cheap compared with the actual compression or decompression. If memory usage is to be minimized, the advanced streaming API below should be used.

Marshaling

The initial motivation for this library is to support compressed data marshaling in the style of the Marshal standard library module. So, we'll implement the same interface as this Marshal module, just with on-the-fly compression/decompression:

module Marshal: sig
  type extern_flags = Marshal.extern_flags =
  | No_sharing                          (** Don't preserve sharing *)
  | Closures                            (** Send function closures *)
  | Compat_32                           (** Ensure 32-bit compatibility *)
  val to_channel : out_channel -> 'a -> extern_flags list -> unit
  val to_bytes : 'a -> extern_flags list -> bytes
  val to_string : 'a -> extern_flags list -> string
  val to_buffer : bytes -> int -> int -> 'a -> extern_flags list -> int
  val from_channel : in_channel -> 'a
  val from_bytes : bytes -> int -> 'a
  val from_string : string -> int -> 'a
  val header_size : int
  val data_size : bytes -> int -> int
  val total_size : bytes -> int -> int
end

Low-level streaming interface

In streaming mode, the input data for compression or decompression can be submitted one piece at a time, with successive function calls, and the compressed/decompressed output can be extracted and e.g. written to a file one piece at a time, without building the whole output in memory. This is useful when dealing with very large data.

The ZSTD streaming APIs for compression and decompression are similar, so I propose to present both operations as an abstract "data transformer":

type transformer
val compressor: ?level: int -> unit -> transformer
val decompressor: unit -> transformer

(Internally, a transformer will probably be a record of functions, but I'd rather not expose the implementation.)

The main operation on a transformer is to give it N bytes of input and space for M bytes of output, and let it consume some input and produce some output. This returns a pair (N', M') where N' ∈ [0,N] is the number of input bytes consumed, and M' ∈ [0,M] the number of output bytes produced.

val transform:
      transformer -> 
      src: bytes -> src_pos: int -> src_len: int ->
      dst: bytes -> dst_pos: int -> dst_len: int ->
      int * int

When we're done sending input to a transformer, we need to ask it to flush its internal buffers, possibly producing more output:

val finish:
      transformer ->
      dst: bytes -> dst_pos: int -> dst_len: int ->
      int * bool

The result is the number of output bytes produced, and a Boolean indicating whether all internal data was flushed (true) or whether finish must be called again with more output space (false).

(Note that ZSTD streaming compression has a "flush" operation that terminates the current block and empties internal buffers, but does not write the end-of-compressed-text block. I'm not sure how to use this, and it has no equivalent for decompression, so I'd rather not expose this "flush" operation.)

A transformer remains usable after a finish. It can be more efficient memory-wise to reuse a transformer instead of creating a new one. Symmetrically, it can be more efficient memory-wise to tell ZSTD that we no longer need a transformer and that its internal buffers can be freed, rather than waiting for the OCaml GC to do it via finalization:

val free: transformer -> unit

If applied to an already-freed transformer, transform and finish operations raise an exception, and free does nothing.

The low-level streaming API is hard to use, esp. to manage output buffering. I propose two higher-level streaming APIs for common use cases: outputting to a file, and outputting to an in-memory string buffer. These may be omitted from the first implementation of this library, if there's not enough time or too much bickering.

Streaming to an output channel

module Out_channel: sig
  type t
  val create: Stdlib.out_channel -> transform -> t

An Out_channel.t is just a regular output channel, plus a transformer (compressor or decompressor), plus an internal bytes array to buffer the output.

  val flush: t -> unit
  val close: t -> unit

Flushing finishes the transformer, making sure all output has reached the underlying out_channel. The Out_channel.t remains usable and can accept more input. Closing finishes the transformer but also frees it and frees the internal byte buffer, so the Out_channel.t becomes unusable. (There's no reason to close the underlying output channel, so the name close is not great.)

Some or all the output functions from Stdlib.Out_channel can be provided:

  val output_char : t -> char -> unit
  val output_byte : t -> int -> unit
  val output_string : t -> string -> unit
  val output_bytes : t -> bytes -> unit
  val output_subbytes : t -> bytes -> int -> int -> unit
  val output_substring : t -> string -> int -> int -> unit
end

Streaming to an in-memory string buffer

module Buffer: sig
  type t
  val create: ?size: int -> transformer -> t

A Buffer.t is a transformer plus an extensible byte array in the style of the stdlib Buffer. The ?size is the initial size of the byte array.

  val flush: t -> string
  val close: t -> string

flush performs a finish on the underlying buffer, then returns all the data that has accumulated in the buffer as a string, then empties the buffer. This is unlike Buffer.contents from the stdlib, which keeps the buffer intact and returns it as part of the next call to Buffer.contents. I think the "don't return the same output data twice" policy makes more sense for compression, where headers and trailers are added around the output data.

close (find a better name?) is like flush, but in addition it frees the transformer and destroys the internal buffer, making the Buffer.t unusable. In contrast, after a Buffer.flush, the Buffer.t remains usable for further compression / decompression.

Some of the "add" functions from Stdlib.Buffer can be provided:

  val add_char : t -> char -> unit
  val add_string : t -> string -> unit
  val add_bytes : t -> bytes -> unit
  val add_substring : t -> string -> int -> int -> unit
  val add_subbytes : t -> bytes -> int -> int -> unit

Optional support?

What if the ZSTD C library is not available? We can choose to skip the build of the OCaml library and to not install it, like we used to do with Graphics when it was part of the core distribution and Xlib was not available. Or we can choose to build and install the library with reduced functionality, like we do with the Unix library under Windows. The "reduced functionality" could probably be:

• Marshaling that does not compress, but works like the Stdlib.Marshal module
• All other functions would fail.
• The library would define val supported: bool.

Related work

I'm aware of two bindings to the ZSTD library:

• zstandard (https://github.com/janestreet/zstandard): comprehensive, exposes a large part of the C library; multiple kinds of data sources and data sinks.
• zstd (https://github.com/ygrek/ocaml-zstd): minimalistic (just whole-string compression and decompression); length of decompressed data must be provided by the user to the decompression function, which is impractical

The API proposed here falls somewhere between these two bindings in terms of exposed functionality.

None of these bindings provides support for compressed marshaling, beyond the memory-inefficient "marshal to a string and compress it".

[c-cube]

Transforms

The transform API looks nice (it's basically a push-based stream, I think?). I'm just sad to see a new, custom made Out_channel.t type proposed instead of making Stdlib.Out_channel.t . I do understand it's easier to do, but it's another reminder of the insufficiency of the stdlib's IO system.

Buffer

  val flush: t -> string
  val close: t -> string

This copies the buffer's content into a string, which presumably is going to immediately be consumed (written somewhere, a socket, a file, something like that). Could there be a way that skips this intermediate copy, like this (pardon the terrible names)?

val flush_without_clearing : t -> unit
val content_slice : t -> bytes * int (** only after flush_without_clearing *)

[xavierleroy]

I'm just sad to see a new, custom made Out_channel.t type proposed instead of making Stdlib.Out_channel.t [work with compression]

I agree that your modular I/O proposal would work fine for streaming compression / decompression to/from channels. I don't mind removing the ZSTD.Out_channel part of my proposal from the first implementations, until we better understand where we want to go with I/O.

This copies the buffer's content into a string, which presumably is going to immediately be consumed (written somewhere, a socket, a file, something like that).

Stdlib.Buffer also forces this extra copy, and nobody seems worried about it.

Could there be a way that skips this intermediate copy, like this (pardon the terrible names)?

There's something like that in my Cryptokit library:
https://github.com/xavierleroy/cryptokit/blob/fe2961775e5ece18cbe85c48909d535e8d005a00/src/cryptokit.mli#L86-L106

get_substring gives the user access to the current state of the buffer, then empties it. So we're putting a lot of responsibility on the caller to copy or use immediately the data. Also note get_string, which copies the buffer, so it's safer. Both functions can be called as often as you want, even before the transform is flushed, so as to get the output in smaller chunks, if it can help keep memory usage low. The downside is an API that is kind of hard to use, e.g. the user needs to remember to flush before extracting the final output.

Again, we don't need to export ZSTD.Buffer for the first iteration of this design, but note that something like it is required to implement ZSTD.uncompress in the case where the compressed data does not carry the length of the original data.

[dbuenzli]

I'm not sure I understand the idea behind providing this API – not that I'm not interested in zstd; I might actually use it for a design very soonish.

But it seems that during the past decade upstream rather had the idea to remove stuff from otherlibs (dbm, labltk, graphics, num) and sticked to the idea of being "tech" agnostic which I personally find to be a good idea. Now suddenly we get this addition of a random specific compression technique.

What is the principle here ?

Also I'm not sure having it as a depopt is going to provide a very good user experience, e.g. in the case where zstd was not installed and suddenly becomes available I don't want the whole switch to recompile. Basically optional libraries in what effectively constitutes the root of my package install seems a rather bad idea to me.

My impression is that OCaml would be better of making its use of zstd its personal matter (if only because it allows to evolve its uses in compilation artifacts the way it sees it fit).

Package name

Just follow the eco-system conventions. Install the library in its own zstd directory in your package's lib directory and call the library ocaml.zstd.

[xavierleroy]

But it seems that during the past decade upstream rather had the idea to remove stuff from otherlibs (dbm, labltk, graphics, num) and sticked to the idea of being "tech" agnostic

Yes, I'm the one who pushed hard to move these libraries outside of the core OCaml distribution, because they had no compelling reasons to be there. But other libraries in otherlibs/ such as unix and systhreads will stay there forever because they have close ties with the internals of the runtime system, making maintenance difficult if they were separate projects instead.

What is the principle here ?

1. It would be good to expose the compressed marshaling functionality that is used by the OCaml compilers since 5.1 to users who have similar needs. I'm thinking of Coq, Frama-C, or any other OCaml application that uses marshaling to persist large data structures. (And don't tell me they should use JSON or sexps or binprot or anything else; the OCaml marshaler is the only game in town when it comes to preserving sharing.)

2. Compressed marshaling ties into the runtime system in nonobvious (and not very elegant) ways, so that's the kind of dependency on the runtime system that deserves inclusion in the core system.

3. If we provide an OCaml library that provides compressed marshaling and builds on top of the ZSTD C library, it makes sense to provide some more functions for compression and decompression, such as whole-string compression/decompression, and access to the ZSTD streaming API. User programs can easily use whole-string operations, and higher-level libraries can build on top of the low-level streaming API. It's cheap in terms of extra code and extra build infrastructure, and makes the library more useful.

Also I'm not sure having it as a depopt is going to provide a very good user experience

I'm not sure what is a depopt of what. Either the new library is always installed (but may fail at run-time if ZSTD wasn't available at compile-time), or it is installed only if ZSTD was available at compile-time (just like systhreads used to not be installed if POSIX threads weren't available at compile-time). I don't feel strongly either way; I'd just like to understand which provides the better "user experience".

a random specific compression technique.

Of course, I chose ZSTD at random. That's how stupid I am. You should really watch your choices of words.

[Package name] Just follow the eco-system conventions. Install the library in its own zstd directory in your package's lib directory and call the library ocaml.zstd.

I'm certainly ignorant of the eco-system conventions, but I don't understand your advice. If I do ocamlfind list on my OPAM installation, I see a bunch of names, none of which is prefixed by ocaml. For example, the zstd OPAM package results in two ocamlfind names, zstd and zstd.stubs, and the Unix library is unix. Are you really suggesting the new library should have ocamlfind name ocaml.zstd? While the Unix library is unix and not ocaml.unix?

[dbuenzli]

(Given the tone of your response, I don't feel like discussing this anymore, here's a final answer from me to clarify a few points)

3. If we provide an OCaml library that provides compressed marshaling and builds on top of the ZSTD C library, it makes sense to provide some more functions for compression and decompression, such as whole-string compression/decompression, and access to the ZSTD streaming API.

Personally I don't see the argument here. Compressed marshaling is it's own unstable format. You may want to change it in the future, perhaps not using zstd. At which point you will have to carry on with this library.

I'm not sure what is a depopt of what.

Having zstd as an optional dependency of the compiler. That is the fact the ocaml.zstd library may be absent.

Of course, I chose ZSTD at random. That's how stupid I am. You should really watch your choices of words.

I'm not exactly sure where you read that I suggested you chose zstd at random. What I wrote is that having a Zstd module in otherlibs looks random. That is, if you had chosen say sqlite or zip files as a file format for compilation artefact and followed the same path then we would have a library for sqlite or zip files in otherlibs and that looks random and unprincipled.

Are you really suggesting the new library should have ocamlfind name ocaml.zstd? While the Unix library is unix and not ocaml.unix?

Yes. It has been suggested for ages that upstream moves to namespace it's libraries under the ocaml prefix. Like everyone does nowadays with its own libraries. The problem you have now about choosing this name may suggest you why this is a good idea.

[Octachron]

I tend to agree with @dbuenzli that the choice of zstd as the compression library for compressed marshalling is a rather contingent choice.

It is seems pretty clear to me that in 20 years, we will probably still want to provide a compressed marshall library for reading cmi files.
I don't know if such library will still use zstd 20 years later.

Thus, it might make sense to focus the library initial design on exposing the compiler support for compressed marshalling without coupling this library too strongly to the compression algorithm.

Another way to word it is that would rather avoid people starting to depend on the marshalled compression library when all they use is the zstd binding.

In other words, I would rather see the library organized as

• Compressed_marshal, the main module which implements module type of Marshal.
  • a Compression submodule which implements a nameless compression scheme
  • maybe a Compression module type?

to make sure that we only expose the features that we intend to maintain the future.

[xavierleroy]

It has been suggested for ages that upstream moves to namespace it's libraries under the ocaml prefix. Like everyone does nowadays with its own libraries.

I just installed a bunch of OPAM packages -- those with dbuenzli appearing in the OPAM files -- and I don't see much name spacing going on (see below for ocamlfind list results). What about doing what you preach before lecturing upstream?

asetmap             (version: 0.8.1)
astring             (version: 0.8.5)
astring.top         (version: 0.8.5)
bos                 (version: 0.2.1)
bos.setup           (version: 0.2.1)
bos.top             (version: 0.2.1)
brr                 (version: 0.0.6)
brr.ocaml_poke      (version: 0.0.6)
brr.ocaml_poke_ui   (version: 0.0.6)
brr.poke            (version: 0.0.6)
brr.poked           (version: 0.0.6)
cmarkit             (version: 0.3.0)
cmdliner            (version: v1.2.0)
down                (version: 0.1.0)
ezxmlm              (version: 1.1.0)
fmt                 (version: 0.9.0)
fmt.cli             (version: 0.9.0)
fmt.top             (version: 0.9.0)
fmt.tty             (version: 0.9.0)
fpath               (version: 0.7.3)
fpath.top           (version: 0.7.3)
gg                  (version: 1.0.0)
gg.top              (version: 1.0.0)
hmap                (version: 0.8.1)
htmlit              (version: 0.1.0)
jsonm               (version: 1.0.2)
logs                (version: 0.7.0)
logs.browser        (version: 0.7.0)
logs.cli            (version: 0.7.0)
logs.fmt            (version: 0.7.0)
logs.threaded       (version: 0.7.0)
logs.top            (version: 0.7.0)
mtime               (version: 2.0.0)
mtime.clock         (version: 2.0.0)
mtime.clock.os      (version: 2.0.0)
mtime.top           (version: 2.0.0)
note                (version: 0.0.3)
note.brr            (version: 0.0.3)
odig                (version: 0.0.9)
odig.support        (version: 0.0.9)
omod                (version: 0.0.3)
omod.support        (version: 0.0.3)
otfm                (version: v0.4.0)
prr                 (version: 0.1.1)
ptime               (version: 1.1.0)
ptime.clock         (version: 1.1.0)
ptime.clock.os      (version: 1.1.0)
ptime.top           (version: 1.1.0)
qrc                 (version: 0.1.0)
react               (version: 1.2.2)
react.top           (version: 1.2.2)
rresult             (version: 0.7.0)
rresult.top         (version: 0.7.0)
tgls                (version: v0.8.6)
tgls.tgl3           (version: v0.8.6)
tgls.tgl3.top       (version: v0.8.6)
tgls.tgl4           (version: v0.8.6)
tgls.tgl4.top       (version: v0.8.6)
tgls.tgles2         (version: v0.8.6)
tgls.tgles2.top     (version: v0.8.6)
tgls.tgles3         (version: v0.8.6)
tgls.tgles3.top     (version: v0.8.6)
topkg               (version: 1.0.7)
topkg.care          (version: 1.0.7)
tsdl                (version: v1.0.0)
tsdl.top            (version: v1.0.0)
ttweetnacl          (version: 0.1.0)
uucd                (version: v15.1.0)
uucp                (version: 15.1.0)
uuidm               (version: v0.9.8)
uunf                (version: 15.1.0)
uunf.string         (version: n/a)
uuseg               (version: 15.1.0)
uuseg.string        (version: n/a)
uutf                (version: 1.0.3)
vg                  (version: v0.9.4)
vg.htmlc            (version: v0.9.4)
vg.pdf              (version: v0.9.4)
vg.svg              (version: v0.9.4)
webbrowser          (version: 0.6.1)
webbrowser.cli      (version: 0.6.1)
xmlm                (version: 1.4.0)
zipc                (version: 0.1.0)

[kit-ty-kate]

on the contrary, i see plenty of them. They are where they make sense IMO, i'm not sure what you're trying to say.

Also was the snaky comment really necessary?

[xavierleroy]

This discussion went on a tangent about what "everyone" is doing with library names -- or not. At any rate, there's not enough interest for this proposal for a compression library in the core system distribution, so let me close it. I'll probably implement all of this as one of my personal projects. I duly noted that I should give my library the name xavier's.zstd, to show my utmost respect for namespacing things, and to annoy everyone with a single quote in a directory name.

[gasche]

The way I understand the concerns that were raised is as follows:

• If the service that is about to be provided is "Marshal with compression", we don't need and probably do not want the API to specify a specific algorithm, for example because it allows to change algorithms later if desirable. So a module named compression makes sense, and given that it is specifically compression for the ocaml runtime a name such as ocaml.compression would make sense.
• If the service that is about to be provided is "a nice binding to zstd", then this could be a library just named zstd or whatever. It could be distributed (from a user perspective) independently of the ocaml package. We could store the source in the compiler distribution (other projects do this by providing separate .opam files for separate packages versioned together), and use it vendored in the compiler, and yet pretend to the opam-repository that this is a separate package.

Then there is the question of the effect on the opam-repository ecosystem of having the compiler provide an external dependency whose status is not explicitly indicated by the user in the switch description (as, say, TSan is), but implicitly auto-detected by the compiler configure script. This may result in an unpleasant experience in practice, I don't have enough knowledge of contemporary opam packaging issues to tell.

[dbuenzli]

@xavierleroy for someone who asks others to "keep it professional and effective" I could return the "what about doing what you preach before lecturing others" advice.

In this discussion:

1. You aggressively threatened me to watch my words based on something I never said.
2. You aggressively pretend I tell upstream to do something I don't do and insinuate no one really does.

Regarding 2. not only it is not the case for me as @kit-ty-kate kindly pointed¹, but most of the eco-system also does it because that's what dune installs do by default.

That is each package installs in its own library prefix named after the package name, sub libraries install into sub directories, and ocamlfind names are made to match the hierarchy of directory names. If you are interested in knowing why you may want to have a read at the library linking proposal. There was a great opportunity to do this when #11007 got devised but upstream shied away.

The result is that for us spending a great deal of time trying to improve the eco-system experience with tooling we constantly have or had to special case the ocaml package (including in opam and ocamlfind).

Regarding your level of aggressivity towards me I'm not sure what justifies it. If you want to discuss this in private feel free to shoot me an email.

Footnotes

1. Some of my packages may still install library archives at the root of the package rather than in their own sub-directory directory but that's either due to release lag or because I forgot, feel free to open issue on packages that do not. ↩