[API suggestion] Avoid `~dummy` flag in favour of `Obj.magic`

[craigfe]

Thanks for this excellent library :-)

I have a suggestion for the API that I'm sure you have considered, but I thought I'd propose it anyway to hear your thoughts on the matter. I have two reasons for disliking the ~dummy idiom:

• it can be somewhat heavy in practice, since the obligation can cascade up the stack to other APIs / users whenever a vector is used polymorphically;
• it places some artificial limits on how the API can be used. For instance, I can't construct a vector of values that contain backpointers to their parent:

type scheduler = { ...; vector: request Vector.t } (* some type with no trivial element *)
and request = { ...; parent: scheduler }

let create_scheduler () = { ...; Vector.create ~dummy:(__doesn't_yet_exist__) 0 }

What do you think of using e.g. Obj.magic None as the dummy value internally, and dropping the requirement for this parameter? I suspect the necessary internal invariants are not too hard to enforce (as the signature already never returns dummy values except for the unsafe_ functions), and am happy to contribute a patch if so.

This would unfortunately prevent taking advantage of implicit float arrays, although these seem to be going out of fashion lately (ocaml/ocaml#1294). To recover the compact float representation, it'd probably be necessary to go the route of Floatarray and make a dedicated Vector.Float module.

Thanks for your time :-)

[backtracking]

I've thought about this for a while, indeed. There are pros and cons. Your arguments are good ones, indeed.
(A good example of a cascading requirement would be a priority queue implemented on top of Vector.)

My main concern about using Obj.magic is, well, that it is about using Obj.magic :-) More seriously, I don't know what the compiler/runtime may do with it. For instance, using Obj.magic None as you suggest may result in the runtime figuring out something wrong about the values stored in the vector just because a non-pointer value was found in the array. May be I'm too paranoid here...

[backtracking]

But since you are offering to provide a patch to get rid of dummy, please do so and I'll be happy to review it and merge it.
Note: I would prefer dummy to be kept as an internal field in the record, even if defined as Obj.magic None. I mean, rather than a global, unique, polymorphic dummy value.

[backtracking]

My main concern about using Obj.magic is, well, that it is about using Obj.magic :-) More seriously, I don't know what the compiler/runtime may do with it. For instance, using Obj.magic None as you suggest may result in the runtime figuring out something wrong about the values stored in the vector just because a non-pointer value was found in the array. May be I'm too paranoid here...

Let me try to be a bit more precise about what I had in mind. Suppose that

• your are storing records in your vector, in such a way that all the values stored into the internal array are pointers;
• you are using a global optimizing compiler that makes monomorphic copies of Vector, one for each type of elements.

Now, when compiling that copy of Vector that contains only pointers, the compiler could follow those pointers (for whatever reason), and that would fail (badly) on Obj.magic None.

Does this makes any sense?

[craigfe]

Thanks for the detail. I completely understand (and share) trepidation around Obj, and you raise a good example of a possible failure case. I've been doing some research on tricks like this, and ran into the nullable-array library by compiler-hacker @chambart. The implementation of this library applies some tricks to avoid various pitfalls:

• using a heap-allocated dummy element to avoid issues with the no-naked-pointers runtime;
• storing this dummy inside the array, to retain sensible behaviour with structural comparison and Marshall;
• using Sys.opaque_identity to ensure that float elements are systematically boxed (even if the analysis pushes past abstraction boundaries).

At this point, I decided that Nullable_array is implemented more carefully than I could ever manage myself, and so wrote an experimental patch (here) to switch uses of Array inside Vector to Nullable_array (which also required a patch). The diff is quite straightforward, with the only real change being that resize now needs an initialisation element (so I added shrink for the special case where this isn't necessary).

Using Nullable_array makes a lot of sense to me, but I'd understand you not wanting to take on an external dependency (particularly one with so much black magic). If not, I think I'd now advocate for sticking with the ~dummy argument after all -- as I'm not a compiler maintainer myself, I can't guarantee that certain Obj tricks will not break on future compiler releases. The nullable-array library itself has a defensive upper bound that is raised after testing each compiler release. (Ultimately, as discussed in this thread, it makes sense for the compiler to provide better primitives here.)

What do you think?

[backtracking]

Thanks for digging out the nullable-array library (and for providing a patch to Vector.)
I had a quick look at nullable-array:

• The use of the 0-cell and the subsequent index shifting is a bit annoying, but I (think I) understand the reasons behind.
• The comment "Designed and tested for OCaml <= 4.04 bytecode and native," is a bit scary but I guess it is simply not up to date.
• I think blit can be improved a little bit; I made an issue (A slightly more efficient unsafe_manual_blitblit? chambart/ocaml-nullable-array#2).

Altogether, I think it is a viable option. (And, beside, there is still another version of my Vector as part of the https://github.com/ocaml-gospel/vocal/ library, so anyone willing to use the dummy API can still move to vocal.)
Please make a PR and I'll be happy to merge it.

Note: Incidentally, the change of API you propose fixes a small bug. Indeed, make should have rather created a 0-length vector, reserving dummy for internal use only, but that was not the case. Instead, dummy was used to initialize the array. What you propose is much better.