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

Inefficient record duplication #5931

Closed
vicuna opened this issue Feb 24, 2013 · 8 comments
Closed

Inefficient record duplication #5931

vicuna opened this issue Feb 24, 2013 · 8 comments

Comments

@vicuna
Copy link

vicuna commented Feb 24, 2013

Original bug ID: 5931
Reporter: @mmottl
Status: closed (set by @gasche on 2013-02-25T14:29:04Z)
Resolution: not a bug
Priority: normal
Severity: tweak
Platform: Mac OS X
Version: 4.00.1
Category: back end (clambda to assembly)
Related to: #5098
Monitored by: @mmottl

Bug description

The following code demonstrates that duplicating a non-mutable record is surprisingly less efficient than duplicating a first-class module:


type t = { foo : int }
let copy_rec { foo } = { foo }

module type T = sig val foo : int end
let copy_mod (module T : T) = (module T : T)

The generated assembly shows that the record duplication will actually involve an allocation and copying of fields whereas the compiler is smart enough to recognize that the module duplication is really equivalent to the identity function.

I think this suggests a general optimization: if any non-mutable block is copied to another non-mutable one (maybe even of different type!), then the generated code should just be the identity function.

@vicuna
Copy link
Author

vicuna commented Feb 24, 2013

Comment author: @alainfrisch

There isn't any clever logic for the module case: it is just that the first-class module is represented exactly as the underlying module, so:

let copy_mod (module T : T) = (module T : T)

is morally compiled as:

let copy_mode t = t

The optimization you suggest would require some easy but heavy logic to keep track of which identifier come from which record, and try to re-use an existing record value if an exact copy is created. How often does this happen in practice? I'm not sure it is worth adding logic for such a case, especially because doing the optimization manually is trivial without degrading code readability.

@vicuna
Copy link
Author

vicuna commented Feb 24, 2013

Comment author: @gasche

Indeed, this seems to be an issue of writing

let copy (t : t) = t

vs the explicit destructuring then reconstruction

let copy { foo } = { foo }

Do you have a real-world example where turning the second into the first is important for an application?

@vicuna
Copy link
Author

vicuna commented Feb 24, 2013

Comment author: @mmottl

I actually found a solution that doesn't force me to duplicate the record. The problem was that a functor argument required a record declaration (or module type in the alternative solution). The argument implementation, however, did not declare this record (or module type) by itself, it had to use a type alias to some other place. The solution was to add a manifest type to that alias so that the compiler would know that the record declarations will match. No such manifest type was necessary with the module type solution to avoid copying.

I wonder how often it actually happens in practice that two non-mutable values would have the exact same physical representation. E.g. as in:

function [x] -> Some x

Or:

function (Tag0 (a, b, c)) -> { a; b; c}

Though there are many possible ways in which such optimization opportunities could arise in practice, it's probably still not a frequent enough occurrence to warrant an extra optimization step.

@vicuna
Copy link
Author

vicuna commented Feb 24, 2013

Comment author: @gasche

Correct me if I'm wrong, but here is my rephrasing of what you say: because of a complex situation with functors, signatures and module system wizardry, you had two records types (or first-class module types) that had the same fields of the same type, but without an explicit equality.

Because module types are compared structurally (field-by-field) by the type checker, you could write (fun t -> t); but with record types that have a nominal flavor (two records with the same name and fields are not necessarily equal), you had to write an explicit coercion term that deconstructed and reconstructed the record, leading to an inefficiency.

Adding an explicit equality between the source and destination type solved the problem by allowing to write (fun t -> t) in both cases.

(Marking the issue resolved.)

@vicuna
Copy link
Author

vicuna commented Feb 25, 2013

Comment author: @mmottl

That's basically correct. However, I've just found out that there is clearly something different if not to say fishy going on. I'll file a separate bug report (#5932) about a memory leak concerning first-class modules, which is somewhat orthogonal to this optimization discussion.

Anyway, in my test case concerning records the source and target type for the record were the same, not just structurally but also nominally. Yet, the generated assembly code was still inferior to the module case. That's what surprised me, because I always thought that modules were really just fancy records and would be either treated the same or worse, certainly not better.

I also thought that writing "(module T : T)" wasn't just some sort of declaration, but that the runtime would actually do something, i.e. copy an underlying record, because the type constraint on the destination might not be the same as for the source. There does seem to be some special treatment here that records apparently do not receive and which does not seem to be sound in terms of memory management.

@vicuna
Copy link
Author

vicuna commented Feb 25, 2013

Comment author: @alainfrisch

An expression "(module M : T)" is compiled as the coercion between T0, the module type inferred for M, and T. If the coercion is the identity, no code is needed. As an optimization, if the coercion is a "prefix projection" (i.e. value components of T0 form a prefix of value components of T), the compiler also uses the identity. This can indeed leads to memory leaks, since other values in M are still part of the block but might become dead otherwise. But note that this is not strictly related to first-class module per se; the same already happens with normal modules (which can be generated on the fly with local modules and hidden inside abstractions).

@vicuna
Copy link
Author

vicuna commented Feb 25, 2013

Comment author: @mmottl

Thanks for the explanation, Alain, I've just read your comments for the duplicate bug report, too. It's good to know that there is at least a workaround using "include". In case anybody needs to know the details, the following alternative copy function will do the right thing when dealing with different source and target module signatures:

let copy (module M : T) = (module struct include (M : S) end : S)

I think I'd still be happier if the current behavior could be changed. It's quite surely not what most people would intuitively expect. Even if the programmer knows about this issue, it's just too easy to make this mistake, especially with first-class modules.

@vicuna
Copy link
Author

vicuna commented Feb 25, 2013

Comment author: @alainfrisch

I don't have a strong opinion on this subject. In some cases, when using first-class modules as extensible records, it could be a nice property that a "prefix" extraction does not induce any allocation, but I tend to agree that being safer w.r.t. memory leaks is more important.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant