Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Whish: inline integer field into variant tag (unboxing like) #8881

Open
recoules opened this issue Aug 21, 2019 · 7 comments

Comments

@recoules
Copy link

commented Aug 21, 2019

For optimisation, I would like to have a way to tell the compiler that an integer field could be (at least partially) inlined into the tag of a variant.

Here is an example to illustrate what I mean:

type t =
       | A of int [@variant:tag]
       | B of string

With this kind of annotation, the compiler may try to generate internally new variants to avoid the boxing of the integer, for instance:

type t =
       | A0 (* Obj.repr A0 = Obj.repr 0 *)
       | A1 (* Obj.repr A0 = Obj.repr 1 *)
       (* ... *)
       | Ax of int (* for integer > bound *)
       | B of string

Ideally, it would unbox completely all values such as Ax would not be needed any more (bound = max_int) but I suppose it has the same difficulty than supporting integer range ( #8504).
Edit: as @gasche said, in this case, [@unboxed] should work to distinguish A of B

Of course, constructions and pattern-matchings should be internally changed accordingly.

Note: this is inspired by the implementation of zarith (which represents "small" integer with native integer) but yet, its type is abstract and can not be pattern-matched...

This annotation may also be used with block-like variant:

type t =
       | A of int 
       | B of string * int [@variant:tag]

Internally equivalent to:

type t =
       | A of int 
       | Bx of string * int (* for integer 0, 1, or > xxx *)
       | B2 of string
       | B3 of string
       (* ... *)
       | Bxxx of string (* where xxx is the last valid tag, actually 245 I think *)

And both can be combined as long as there is no more than one unboxing for integer-like variants and one for block-like variants:

type t =
       | X
       | Y
       | Z
       | A of int [@variant:tag]
       | T of bool
       | B of string * int [@variant:tag]
       | U of char

Internally equivalent to:

type t =
       | X
       | Y
       | Z
       | A3 (* Obj.repr A3 = Obj.repr 3 *)
       | A4 (* Obj.repr A4 = Obj.repr 4 *)
       (* ... *)
       | Ax of int (* for integer 0, 1, 2 or > bound *)
       | T of bool
       | Bx of string * int (* for integer 0, 1, 2, 3 or > xxx *)
       | U of char
       | B4 of string
       | B5 of string
       (* ... *)
       | Bxxx of string

I am sorry if something similar has already been proposed or refuted.

@gasche

This comment has been minimized.

Copy link
Member

commented Aug 21, 2019

The very first example seems much easier to deal with than the rest: if you have a type with only non-constant constructors, you could ask to "unbox" at most one of those non-constant constructors, provided it has a single argument that is an immediate type. The representation of type t = A of immediate [@unboxed] | <non-constant constructors> would be the disjoint union of the immediate values and the non-constant constructors (tagging of the word value can be used to distinguish immediates from pointers).

@recoules

This comment has been minimized.

Copy link
Author

commented Aug 21, 2019

Thank you for the quick answer.
I already have tried the [@unboxed] annotation but it did not work for me. Does it requires flambda?
Because the [@@unboxed] on a single variant type works without (but, of course, it is simpler).

Here is what I get (with 4.05.0 and 4.07.1, both with toplevel or ocamlopt):

# type t =
  | A of int [@unboxed]
  | B of int * int;;
type t = A of int | B of int * int

# type u = C of int [@@unboxed];;
type u = C of int [@@unboxed]

# let _ = Format.printf "%b@." Obj.(is_int (repr (A 0)));;
false
- : unit = ()

# let _ = Format.printf "%b@." Obj.(is_int (repr (C 0)));;
true
- : unit = ()
@gasche

This comment has been minimized.

Copy link
Member

commented Aug 21, 2019

Sorry I was unclear. The extension I proposed in my previous message is not currently implemented in the OCaml compiler, and it would be (as for the ones you propose) some amount of work to get consensus on the design and implement in the compiler. I was just pointing it as a simple design, much simpler than some of your more advanced proposals.

@recoules

This comment has been minimized.

Copy link
Author

commented Aug 21, 2019

In fact, what you proposed is exactly what I thought/wanted (the same "behavior" as zarith).

Here is the case I am really interested in:

type 'a t =
  | A of int [@unboxed]
  | B of 'a * int (* with int expected to be < 128 most of the time *)

I only proposed advanced examples to show it could be generalized in case the values are expected to be small, and so fits into tag and saves one quadword.

Well, for small record, it could save 1/3 of memory... but I am not sure it is worth it.

@keleshev

This comment has been minimized.

Copy link
Contributor

commented Aug 26, 2019

By the way, @alainfrisch has written a blog post that talks about this optimization: https://www.lexifi.com/ocaml/about-unboxed-float-arrays/

@keleshev

This comment has been minimized.

Copy link
Contributor

commented Aug 26, 2019

Maybe relevant, I found a prototype I wrote a while ago implementing this optimization as a functor:

https://gist.github.com/keleshev/47e10cf2ee1dba3828289ece6ac6b9c4

The code is unsafe, but the resulting abstraction (like the example Int_string_sum) is safe. However, you loose the ability to do pattern matching.

@recoules

This comment has been minimized.

Copy link
Author

commented Aug 26, 2019

Thank you, the post is very interesting but it made me sad:

  • I'm not the first to ask this feature -- unacceptable! ;-)
  • Four years after, I'm still here to ask it :-(

It sound like it is not as easy as I was thinking but let's hope

Anyway, thank you too for the code snippet. Yet, I knew how to make this optimisation with abstract type and C (or Obj, it is all the same) primitives but I am looking for a beautiful way to write code (with pattern-matching) while the compiler do the nasty optimizations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.