Primitive that occupies 8 bits in OCaml

user_344199 0
Viewed 83

I was surprised to discover, when using Spacetime to profile my OCaml, that my char and even bool arrays used a word to represent each element. That's 8 bytes on my 64 bit machine, and causes way too much memory to be used.

I've substituted char array with Bytes where possible, but I also have char list and dynamic arrays (char BatDynArray). Is there some primitive or general method that I can use across all of these vector data structures and get an underlying 8 bit representation?

ocaml
1 Answers

Edit: I read your question too fast: it’s possible you already know that; sorry! Here is a more targeted answer.

I think the general advice for storing a varying numbers of chars of varying number (i.e. when doing IO) is to use buffers, possibly resizable. Module Buffer implements a resizable character buffer, which is better than both char list (bad design, except for very short lists perhaps) and char BatDynArray (whose genericity incurs a memory penalty here, as you noticed).

Below is the original answer.

That’s due to the uniform representation of values. Whatever their type , every OCaml value is a machine word: either an immediate value (anything that can fit a 31- or 63-bit integer, so int, char, bool, etc.), or a pointer to a block, i.e. a sequence of machine words (a C-fashion array), prefixed with a header. When the value is a pointer to a block we say that it is “boxed”.

Cells of OCaml arrays are always machine words.

In OCaml, like in C++ but without the ad-hoc overloading, we just define specializations of array in the few cases where we actually want to save space. In your case:

  • instead of char array use string (immutable) or bytes (mutable) or Buffer.t (mutable appendable and resizable); these types signal to the GC that their cells are never pointers, so they can pack arbitrary binary data;
  • Unfortunately, the standard library has no specialization for bool array, but we can implement one (e.g. using bytes); you can find one in several third-party libraries, for instance module CCBV (“bitvectors”) in package containers-data.

Finally, you may not have realized it, but floats are boxed! That’s because they require 64 bits (IEEE 754 double-precision), which is more than the 31 or even 63 bits that are available for immediates. Fortunately(?), the compiler and runtime have some adhoc-ery to avoid boxing them as much as possible. In particular float array is specially optimized, so that it stores the raw floating-point numbers instead of pointers to them.

Some more background: we can distinguish between pointers and immediates just by testing one bit. Uniform representation is highly valuable for:

  • implementing garbage collection,
  • free parametric polymorphism (no code duplication, by contrast with what you’d get in a template language such as C++).
user_46151790
Related