[ANN] nullable-array 0.1 (initial release)

chambart · May 23, 2017, 3:57pm

This is a small library providing a type intended to be used instead of `‘a option array’.

It is written in a style you shouldn’t copy (whoever you are, well maybe except Xavier or Mark). There are far too many Obj for it to be considered sane. I wrote that to be as efficient as it is currently possible in OCaml. I intend to update it to future potential changes.
You could also consider that this is a good example of why you really shouldn’t use Obj.

I will probably publish quite soon some reasonably efficient vector (in the meaning of C++) and queue based on it.

I also took the opportunity to test discuss.

Have fun trying to break it!

chambart · May 23, 2017, 3:58pm

I just submitted an opam package: https://github.com/ocaml/opam-repository/pull/9280

Drup · May 23, 2017, 8:53pm

Nice package! I think you forgot the link in the first post.

chambart · May 23, 2017, 9:13pm

Here it is, with some links.

Also, I used that library as an excuse to test jbuilder. Thanks @jeremiedimino, that makes releasing a breeze. And it also works out of the box on windows (according to Appveyor when he doesn’t randomly fail to download some file…)

Yaron_Minsky · May 23, 2017, 10:21pm

We have a very similar module in Core_kernel:

github.com

janestreet/core_kernel/blob/master/src/option_array.mli

(** ['a Option_array.t] is a compact representation of ['a option array]: it avoids
    allocating heap objects representing [Some x], usually representing them with [x]
    instead.  It uses a special representation for [None] that's guaranteed to never
    collide with any representation of [Some x]. *)

open! Import

type 'a t [@@deriving sexp, bin_io]

val empty : _ t

(** Initially filled with all [None] *)
val create : len:int -> _ t


val init_some : int -> f:(int -> 'a       ) -> 'a t
val init      : int -> f:(int -> 'a option) -> 'a t

val length : _ t -> int

This file has been truncated. show original

Which is in turn based on:

github.com

janestreet/core_kernel/blob/master/src/uniform_array.mli

(** Same semantics as ['a Array.t], except it's guaranteed that the representation array
    is not tagged with [Double_array_tag], the tag for float arrays.  This means it's
    safer to use in the presence of [Obj.magic], but it's slower than normal [Array] if
    you use it with floats.

    It can often be faster than [Array] if you use it with non-floats.

    Also see [Base.Obj_array] for the same implementation, but specialized to holding
    [Obj.t] rather than being polymorphic.
*)

open! Import

(** See [Core_kernel.Array] for comments. *)
type 'a t [@@deriving bin_io, sexp]


val empty : _ t

val create : len:int -> 'a -> 'a t

This file has been truncated. show original

whose only point is to guarantee that you avoid the double-specialized array representation.

I think it would be great to get the core of this into the compiler proper. This is not the kind of thing that one should build on one’s own…

chambart · May 23, 2017, 10:49pm

nullable-array is a bit more complex and expensive to handles correctly combinations of marshaling/unmarshaling and polymorphic comparison (with and without the no-naked-pointers runtime).

I certainly agree that we could push something like that upstream, but it is always simpler to experiment and prove usefulness outside of the compiler before adding something to the stdlib. Pushing upstream would also allow for a slightly faster implementation.

In particular, to avoid problems with the no-naked-pointer runtime, I couldn’t represent None as the 0 pointer which loose 1 field per array. This could be lifted by not following null pointers in the no-naked-pointer variant, but at the cost of adding a test in the GC fast path (but probably well predicted by the CPU).

Yaron_Minsky · May 24, 2017, 12:20am

I’m not that excited about marshal and polymorphic compare, both of which I think of as warts on the language, but I can see why you’d want them for completeness. Certainly, having efficient data structures like Queues built on top of this makes sense, and we use it in various places in Core_kernel for just this reason.

Indeed, we’d like to get some of these faster data structures into Base, but have resisted doing so because of the concern about having too much Obj.magic in Base.

lpw25 · May 24, 2017, 6:00am

This could be lifted by not following null pointers in the no-naked-pointer variant, but at the cost of adding a test in the GC fast path (but probably well predicted by the CPU).

I was talking about this with Mark the other day. I think we should add this, as well as appropriate behaviours in marshalling and polymorphic compare, and then add an Obj.null value. This would make things like this much easier to implement.

As for Uniform_array, I really think that we should merge the array data types pull request, which would make that trivial to implement, and allow us to get rid of the float array hack.

Topic		Replies	Views
[ANN] varray 0.2 Ecosystem announce	1	526	November 25, 2023
Adding Dynamic Arrays / Vectors to StdLib Ecosystem	52	6690	October 31, 2023
[ANN] vec 0.2.0 Community announce	9	1195	May 25, 2021
Standardized mutable data structures Ecosystem	34	2188	October 29, 2022
Some SIMD in your OCaml Community	29	4256	September 15, 2020

[ANN] nullable-array 0.1 (initial release)

Related Topics