# Representing data more compactly but unsafely

**URL:** <https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489>\
**Category:** Community\
**Tags:** runtime, usafe, performance\
**Created:** [September 14, 2021, 12:08pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489 "2021-09-14T12:08:25Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\
**Post date:** [September 14, 2021, 12:08pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/1 "2021-09-14T12:08:25Z")

</div>

I’m collecting cases where people modernized data representation either to store them more compactly or to store some extra data in unused bytes. If it is done using unsafe features of OCaml (or similar language runtime), then it is OK. I will state below a few examples that I found, and I hope that you can add some more.

1. In DSL for relational programming we have values such that every part could be replaced by a logic variable. For example, instead of ground lists `type 'a list = [] | (::) of 'a * 'a list` we write everywhere types like:

2. Another example is from the paper [Full reduction at full throttle](https://hal.inria.fr/hal-00650940/document). There we have a tagged data type which is either a closure or a pair of something.

3. Previous two cases were about storing data in a more compact form. Here is an example how language runtime could have tagged pointers to store extra information.

---

<div class="post-metadata">

**Author:** ![yawaramin](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yawaramin/32/3384_2.png) [@yawaramin](https://discuss.ocaml.org/u/yawaramin)\
**Post date:** [September 14, 2021, 3:30pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/2 "2021-09-14T15:30:41Z")

</div>

Not sure if this is exactly what you were looking for but @Yaron_Minsky wrote about using GADTs to achieve a safe compact array representation: [Jane Street Tech Blog - Why GADTs matter for performance](https://blog.janestreet.com/why-gadts-matter-for-performance/)

As he noted there,

> GADTs are about more than clever typed interpreters; they’re a powerful mechanism for building easy to use abstractions that give you more precise control of your memory representation.

---

<div class="post-metadata">

**Author:** ![zozozo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/zozozo/32/59_2.png) [@zozozo](https://discuss.ocaml.org/u/zozozo)\
**Post date:** [September 14, 2021, 7:40pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/3 "2021-09-14T19:40:24Z")

</div>

Also not sure if it fits with what you have in mind, but some time ago I wrote some code to have somewhat optimized representation of source file locations in Dolmen : [dolmen/loc.ml at master · Gbury/dolmen · GitHub](https://github.com/Gbury/dolmen/blob/master/src/standard/loc.ml)

One part of the compactness actually comes from an algorithmic improvement where instead of having a record of 4 integers (start line, start column, end line, end column), we instead store 2 integers which represent the start and end byte offset of the location, and then use a table that stores the byte offset of each line start to translate these two integers to a full location. Then, one can pack these two integers into a single one (using regular, and somewhat safe arithmetic shifts). However, this limits the range of representable locations (particularly on 32bit archs), so to be complete, we also use the `Obj` module to use an actual record with two separate fields when the two integers cannot be safely packed into one.

So in that sense the use of unsafe features is really minimal but it basically allowed to go from using a 4-words record, which use a total of 6 words per location (pointer + block header + 4 words in the block), to using (most of the time) a single word (an int) per location. With big enough AST where each node has a location attached, it resulted in about 1/3 less memory used when parsing big files.

---

<div class="post-metadata">

**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\
**Post date:** [September 14, 2021, 8:43pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/4 "2021-09-14T20:43:09Z")

</div>

It would be really nice if we could add an annotation that optimized the data layout for us given all options listed in the type. Something like `[@optimize_variants]`. It would really give an advantage to regular variants over their polymorphic cousins.

Regarding nan-boxing, it really is cool. I assume the core team wouldn’t consider it due to the changes required to the language. Though it would dramatically improve the speed of float manipulation, it would impose maximum limits on memory size; cost a little bit of integer speed; take away the 63 bit floats we currently have; and make the runtime radically different for 32-bit and 64-bit platforms.

---

<div class="post-metadata">

**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\
**Post date:** [September 15, 2021, 4:03pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/5 "2021-09-15T16:03:23Z")

</div>

@yawaramin I have seen that link but in this thread I expect something more unsafe and hackery. But thanks for reminding

@zozozo, Thanks, it is exactly the stuff I wanted to find!

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [September 16, 2021, 7:17am UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/6 "2021-09-16T07:17:47Z")

</div>

The [Zarith](https://github.com/ocaml/Zarith/) wrapper around GMP declares a type `t` that could look like

```ocaml
type t =
  | SmallEnough of int
  | TooLarge of mpz_wrapper

```

But none of these two constructors actually exist. The code distinguishes between them using the least significant bit, which is naturally different for values of type `int` and values of type `mpz_wrapper`.

---

<div class="post-metadata">

**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\
**Post date:** [September 16, 2021, 10:36am UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/7 "2021-09-16T10:36:26Z")

</div>

Thanks, silene. But your example seems to be the same as mine number 2 about full throttle.

---

<div class="post-metadata">

**Author:** ![gadmm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gadmm/32/877_2.png) [@gadmm](https://discuss.ocaml.org/u/gadmm)\
**Post date:** [September 16, 2021, 10:55am UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/8 "2021-09-16T10:55:57Z")

</div>

The old `mldonkey` uses `Obj.set_tag` to simulate inline records. This was written before inline records were introduced in OCaml. You might find more examples in my audit of uses of `Obj.set_tag` before it was deprecated: [other/async\_audit/set\_tag · master · gadmm / stdlib-experiment · GitLab](https://gitlab.com/gadmm/stdlib-experiment/-/blob/master/other/async_audit/set_tag).

The paper you cite (Full reduction at full throttle) is actually how Coq’s `native_compute` is still implemented. This implements normalisation-by-evaluation via native OCaml compilation and execution. It is even worse than you describe, both `Lam` and `Accu` are closures, so that they can be applied uniformly without looking at the tag (this is better explained in the paper). It causes some issues for migrating to the new representation of closures in no-naked-pointers mode.

The case mentioned by @silene is more reasonable, and there is work by Chataing and Scherer at the ML workshop to make it possible to express it one day in OCaml: [https://cambium.inria.fr/~scherer/research/constructor-unboxing/constructor-unboxing-ml-workshop-2021.pdf](https://cambium.inria.fr/~scherer/research/constructor-unboxing/constructor-unboxing-ml-workshop-2021.pdf).

It might be useful to know that the two least significant bits of pointers are reserved already, not just one. The second one is used in the runtime to express raising exceptions from C functions by returning an encoded exception (`(e & 0b10) == 1`). The two bits are also used to store information during compaction.

Lastly, storing information in pointers requires to mask this information before dereferencing which is costly in terms of code size and might affect performance (with the possible exception of re-using the non-significant msbs in ARM, but I am not sure of the details).

---

<div class="post-metadata">

**Author:** ![EmileTrotignon](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/emiletrotignon/32/5913_2.png) [@EmileTrotignon](https://discuss.ocaml.org/u/EmileTrotignon)\
**Post date:** [September 16, 2021, 11:54am UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/9 "2021-09-16T11:54:04Z")

</div>

Do you know about separate tagging in OCaml ? That is avoiding boxing by having a tag and its attached payload in separate values. I will show a very simple example, but it is surprising what you can achieve with it.

Here is an example of the different ways of programming a function that take either a float or an int and return the closest int.

```ocaml
type my_adt = TI of int | TF of float

(* Safe but uses unnecessary boxing *)
let f_safe = function TI i -> i | TF f -> int_of_float f

type my_tags = TI | TF

(* very unsafe but no useless boxing *)
let f_unsafe tag n =
  match tag with
  | TI ->
      (Obj.magic n : int)
  | TF ->
      int_of_float (Obj.magic n : float)

type _ my_gadt = TI : int my_gadt | TF : float my_gadt

(* Same runtime behaviour as f_unsafe, but safe. *)
let f_gadt : type t. t my_gadt -> t -> int =
 fun tag n -> 
  match tag with 
  | TI -> n 
  | TF -> int_of_float n

```

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [September 16, 2021, 12:39pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/10 "2021-09-16T12:39:10Z")

</div>

> [@gadmm](#):
>
> It is even worse than you describe, both `Lam` and `Accu` are closures, so that they can be applied uniformly without looking at the tag (this is better explained in the paper). It causes some issues for migrating to the new representation of closures in no-naked-pointers mode.

To be clearer, the main issue is that there is currently no way to efficiently test whether a block has the closure tag. (Coq does not need to distinguish between accumulators and closures in the fast path.) That is why Coq accumulators are stored with tag zero, as it can be efficiently tested. If the OCaml compiler knew how to generate efficient code for `Obj.tag x = Obj.closure_tag`, Coq would not use tag zero for accumulators. Using the proper tag for accumulators (i.e., the closure tag) makes the corresponding tests of FiatCrypto five times slower, even when using custom C code instead of `Obj.tag`.

---

<div class="post-metadata">

**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\
**Post date:** [September 16, 2021, 1:32pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/11 "2021-09-16T13:32:21Z")

</div>

> [@silene](#):
>
> To be clearer, the main issue is that there is currently no way to efficiently test whether a block has the closure tag.

If that’s the only reason for this abominable accumulator hack, I wish I had known about it earlier… It should be very easy for the compiler to expose a function `Obj.is_closure` that is very fast. If the Coq team is interested in having that function, could you open a feature request on the OCaml repo ?

---

<div class="post-metadata">

**Author:** ![gadmm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gadmm/32/877_2.png) [@gadmm](https://discuss.ocaml.org/u/gadmm)\
**Post date:** [September 16, 2021, 1:43pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/12 "2021-09-16T13:43:32Z")

</div>

I also wish I understood that earlier! I think that beyond a fast `Obj.is_closure`, they are interested in the optimised compilation of pattern-matching. There is some discussion there: [Do not rely on accumulators having tag 0 in native compilation. by ppedrot · Pull Request #14048 · coq/coq · GitHub](https://github.com/coq/coq/pull/14048).  
If I understand correctly, they want something like:

```ocaml
type t =
| Closure of u -> u [@unboxed]
| Whatever of v

```

Is that correct?  
Implementing this would also justify the related dirty trick in camlinternalOO.ml mentioned in the above PR. This might fall within the scope of @gasche’s project.

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [September 16, 2021, 2:46pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/13 "2021-09-16T14:46:16Z")

</div>

> [@gadmm](#):
>
> Is that correct?  
> Implementing this would also justify the related dirty trick in camlinternalOO.ml mentioned in the above PR. This might fall within the scope of @gasche’s project.

Yes. In fact, I did explain this exact use case in the corresponding RFC: [https://github.com/ocaml/RFCs/pull/14#issuecomment-674446467](https://github.com/ocaml/RFCs/pull/14#issuecomment-674446467)

> [@gadmm](#):
>
> I think that beyond a fast `Obj.is_closure`, they are interested in the optimised compilation of pattern-matching.

That is right. Currently, due to the way pattern-matching is implemented, testing for a closure with tag zero is basically free:

```ocaml
match foo with
| ClosureWithTag0 _ -> ...
| ActualConstructor1 x -> ...
| ActualConstructor2 x -> ...

```

`Obj.is_closure` would be suitable only if the following pattern-matching would be (almost) as fast:

```ocaml
match foo with
| x when Obj.is_closure x -> ...
| ActualConstructor1 x -> ...
| ActualConstructor2 x -> ...

```

---

<div class="post-metadata">

**Author:** ![gadmm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gadmm/32/877_2.png) [@gadmm](https://discuss.ocaml.org/u/gadmm)\
**Post date:** [September 16, 2021, 3:17pm UTC](https://discuss.ocaml.org/t/representing-data-more-compactly-but-unsafely/8489/14 "2021-09-16T15:17:12Z")

</div>

Heh, there now seems to be a prototype by @nchataing announced right this morning in the RFC you just linked.