[ANN] bstr, slice & bin (bigstring, encoders & decoders for binary formats)

Ecosystem
, , , ,
1

I am delighted to announce the release of bstr.0.1.0, as well as bin.0.1.0 and slice.0.1.0. These releases are the result of a synthetic work between several libraries, aimed at bringing together everything that might be useful to us in implementing formats and protocols within our cooperative. In particular, these libraries offer:

  • a comprehensive module for manipulating what are known as bigstrings (replacing bigstringaf - because the name of that library is too long)
  • a library providing access to bigstrings and bytes (in short, an abstraction of ocaml-cstruct)
  • finally, a library for describing binary formats from which one can derive an encoder and a decoder (in the spirit of what repr can offer)

For those who want to understand the benefits of bigstrings, I’ve previously shared my thoughts on the subject here. Although we’ve since backtracked on the use of ocaml-cstruct, particularly for performance reasons (see this article), bigstrings remain useful in certain cases: they should, fundamentally, be used wisely.

Particular attention has been paid to performance using bechamel (for micro-benchmarking), and we can draw a few conclusions from this:

  • bstr has the edge over bigstringaf as it uses tags that did not exist at the time bigstringaf was developed
bstr bigstringaf
blit 4.4ns 4.8ns
sub 15.4ns 18.9ns
  • slice.bstr performs like ocaml-cstruct (which was to be expected)
  • bin challenges hand-written code in terms of decoding
bin hand-written (ocaml-cstruct) repr angstrom
ipv4 11.9ns 11.9ns 93.9ns 136ns 
let bin =
  let fn vihl tos total_length id ff ttl protocol checksum src dst =
    { version= vihl lsr 4; ihl= vihl land 0x0f; tos; total_length; id
    ; flags= ff lsr 13; frag_offset= ff land 0x1fff; ttl; protocol; checksum
    ; src; dst }
  in
  let open Bin in
  record ~name:"ipv4" fn
  |+ field ~name:"vihl" uint8 (fun t -> (t.version lsl 4) lor t.ihl)
  |+ field ~name:"tos" uint8 (fun t -> t.tos)
  |+ field ~name:"total_length" beuint16 (fun t -> t.total_length)
  |+ field ~name:"id" beuint16 (fun t -> t.id)
  |+ field ~name:"flags_frag" beuint16 (fun t ->
      (t.flags lsl 13) lor t.frag_offset)
  |+ field ~name:"ttl" uint8 (fun t -> t.ttl)
  |+ field ~name:"protocol" uint8 (fun t -> t.protocol)
  |+ field ~name:"checksum" beuint16 (fun t -> t.checksum)
  |+ field ~name:"src" beint32 (fun t -> t.src)
  |+ field ~name:"dst" beint32 (fun t -> t.dst)
  |> sealr

let cstruct cs =
  let vihl = Cstruct.get_uint8 cs 0 in
  let tos = Cstruct.get_uint8 cs 1 in
  let total_length = Cstruct.BE.get_uint16 cs 2 in
  let id = Cstruct.BE.get_uint16 cs 4 in
  let ff = Cstruct.BE.get_uint16 cs 6 in
  let ttl = Cstruct.get_uint8 cs 8 in
  let protocol = Cstruct.get_uint8 cs 9 in
  let checksum = Cstruct.BE.get_uint16 cs 10 in
  let src = Cstruct.BE.get_uint32 cs 12 in
  let dst = Cstruct.BE.get_uint32 cs 16 in
  { version= vihl lsr 4; ihl= vihl land 0x0f; tos; total_length; id
  ; flags= ff lsr 13; frag_offset= ff land 0x1fff; ttl; protocol; checksum
  ; src; dst }

These libraries were driven by the ambition to provide a coherent and consistent set of libraries, particularly for working with bigarrays, whilst making few compromises in terms of performance. Several attempts were made to experiment with functors, GADTs, ADTs and even higher-kinded polymorphism… (even with capabilities).

The result is that a poor man’s functor appears to be sufficient, along with a few tweaks (notably to avoid a few caml_apply2 calls), to achieve something that is fairly competitive compared to hand-written code.

These libraries also encapsulate what may have been missing and/or emerged within the community when it came to working with bigstrings. I have personally contributed to improving these libraries without being entirely satisfied with them: hence the emergence of bstr in particular. A considerable amount of effort has been put into documenting these libraries and into testing them. Fuzzers are also available to verify certain assertions regarding bin (such as isomorphism).

These libraries are currently in use, and this version is certainly not the final one. Indeed, we will continue to improve them as we use them (particularly with regard to the implementation of protocols and formats in OCaml).

If you appreciate our work, you can make a donation via GitHub or directly to our charity. Bighappy hacking!

2

Thank you for the release! There are indeed not enough examples, especially when working with slices. And there are various best practices for organizing typical code for encoding and decoding. I’m very interested in the project, because my Bytream is based on your work. But the current version only uses bigstring buffers. Slices are represented by their own tuple type. To what extent does this generic approach make sense? And for what tasks is the performance difference between Bstr and Bytes significant?

3

The main aim of Slice is to provide a set of useful functions for this type. In short, the type is neither new nor exceptional (especially if you are familiar with and have maintained ocaml-cstruct for years). Slice essentially offers what Bstr offers at its core: so switching from one type to the other is not that difficult.

What Slice brings that is new is the abstraction of the buffer and the ability to use both bigstrings and bytes. It is for this reason that Slice_bstr and Slice_bytes are provided.

The question was how to share a common implementation between these two modules without compromising on performance: and according to my results, the poor man’s functor (where one occurrence is replaced by another) seems to be the best compromise for avoiding code duplication. After that, it’s a matter of testing and documentation (which is a job in itself).

My response to that has always been that it depends :slight_smile: . It’s quite difficult to give a precise, well-reasoned answer. I think what I described at the time still holds true and provides quite a lot of information that helps to understand the pros and cons of bytes versus bigstrings.

To give a practical example, we recently worked on implementing a TCP/IP stack in OCaml, where we didn’t want to repeat certain errors we’d observed with mirage-tcpip. In particular, we chose to switch to strings above the IP layer rather than continuing to manipulate bigarrays at the TCP layer. This inevitably involves copying (which, by definition, makes it impossible to implement a zero-copy TCP/IP stack with such a choice), but we also realised that even mirage-tcpip involved copying (and it currently does so far more than mnet). Our conclusion is quite simple: zero-copy requires a rather precise alignment of the planets, which, in practice, is far too restrictive.

This experience leads me to highlight an issue with bigarrays: sharing. Since bigarrays introduce the concept of a ‘view’ and Bstr.sub currently does not make a copy, it is quite easy to share the same buffer between two tasks; all it takes is for one of them to want to write whilst the other treats the buffer as an immutable value, and we’re faced with a sneaky bug…

Another issue that’s always difficult to describe concerns allocation. Bigstrings exist on the C heap, and during certain tests, it’s sometimes hard to understand in detail how the GC behaves with bigstrings (particularly when it deallocates them). This has led to some rather bizarre proposals.

The fact is (and this is what we discovered with regard to MirageVPN) that one should not systematically use bigarrays, ocaml-cstruct or Slice_bstr, but rather know at precisely what point a copy is definitely necessary, so as to ultimately handle only bytes and strings. At any rate, this is currently the approach we’re taking within our cooperative, without necessarily rejecting bigarrays altogether.

Finally, it is important to bear in mind that strings and bytes are generally relatively inexpensive to work with: whilst Bstr.sub does not make a copy, Bytes.create 0x7ff is much faster (as it involves a minor on-heap allocation) than its Bstr counterpart.

That said, all this is very much a matter of idiom, and only a benchmark (such as using bechamel for micro-benchmarks or as we did with iperf3) can really settle the matter. In short, I hope I haven’t confused you too much, but it is mainly experimentation and experience that have led us to these conclusions.

4

It’s a pleasure to receive such a detailed response from you. Thank you for answering my questions! :astonished_face: :flushed_face:

Speaking of my tasks, I use a Bstr buffer that was once allocated. Data is read into the buffer (without copying, thanks to the bigarray feature) and then decoded into values. In other words, no additional memory is allocated for reading an infinite I/O stream.

And to represent a slice of the buffer, I use

type chunk =  buffer:buffer * offset:int * length:int

To overcome cost of a bigarray’s view allocation.

That’s why I am considering whether to change the API of my library, breaking compatibility for the sake of generality, while there is such an opportunity, or leaving it as it is. But if functors are truly zero cost, then it makes sense to redesign them. Start using Bstr’s slices. :thinking:

5

Yes, to be very precise, that’s what we do in mnet too: a buffer is allocated just once and then manipulated.

Next, regarding performance, a Slice_bstr.sub will always be faster than a Bstr.sub (and Bigarray.Array1.sub is even slower as it is more general - hence the difference between Bstr and Bigstringaf).

Finally, functors, unless you use flambda, unfortunately come at a cost, hence our poor man’s functor (see here). I would advise against (if speed is really important) using a functor (hence, here too, the abstraction that Slice provides over bytes and bigstrings).