Skip to content

Latest commit

 

History

History
274 lines (201 loc) · 12.1 KB

DIP1014.md

File metadata and controls

274 lines (201 loc) · 12.1 KB
Raw

Hooking D's struct move semantics

Field Value
DIP: 1014
Review Count: 1
Author: Shachar Shemesh
Implementation:
Status: Final Review

Abstract

The current language definitions prohibits a struct type from maintaining external/internal references to its instance, as D might choose to move a struct instance around by a simple bit-copy operation.

The purpose of this DIP is to maintain this ability, while also allowing internal and external references to the instance. This is achieved by allowing the struct to define a postblit-like callback, called opPostMove, that will be called after the move, allowing the struct to update any references invalidated by the move.

Reference

Contents

Rationale

D compilers are allowed to move (instead of destroying) stack allocated struct objects that have reached the end of their scope. While this may be a very useful feature, it does mean certain programming patterns become more difficult.

The limitation is usually phrased as "D structs may not contain pointers to themselves". While that limitation is correct, it is not the only one. For example, D structs also may not use the constructor/destructor to register themselves with a global registry that keeps track of all instances in the system, e.g. via a linked list. This also severely limits the ability to store delegates that reference the struct instance from outside the struct.

While not all of these scenarios will be easily solved by this DIP, without it the programmer is left with zero tools to tackle the problem, even if she is lucky enough to spot it before it causes memory corruption.

Terminology

Whenever an upper case vowel is used (MAY, SHOULD, MUST NOT), its meaning should be taken as defined in RFC 2119.

Description

Outline

The DIP suggests the following changes:

  1. A new function, called __move_post_blt, will be added to DRuntime.
  2. The user MAY define a member function, called opPostMove, in structs. If defined, the function MUST follow a well-defined interface.
  3. When deciding to move a struct instance, the compiler MUST emit a call to the struct's __move_post_blt after blitting the instance and before releasing the memory containing the old instance. __move_post_blt MUST receive references to both the pre- and post-move instances.

__move_post_blt's implementation

__move_post_blt SHOULD be defined in a manner that is compatible with the following code:

void __move_post_blt(S)(ref S newLocation, ref S oldLocation) nothrow if( is(S==struct) ) {
    foreach(memberName; __traits(allMembers, S)) {
        static if( is( typeof(__traits(getMember, S, memberName))==struct ) ) {
            mixin("__move_post_blt( newLocation." ~ memberName ~ ", oldLocation." ~ memberName ~ " );");
        }
    }

    static if( __traits(hasMember, S, "opPostMove") ) {
        newLocation.opPostMove(oldLocation);
    }
}

Please note that S might also be shared, immutable or const.

opPostMove

opPostMove, if defined, MUST be a nothrow function that updates the external/internal references after they have already been copied. Implementors SHOULD also make it @nogc and either @safe or @trusted.

Implementors MAY define opPostMove for const and/or immutable instances. If they do, the implementation code MAY safely modify the data in the destination location for the object, as that has no pointers referencing it. Such modifications will require a cast.

Whether it is safe to modify external data referenced to by pointers stored in the struct (as in the case of an intrusive linked list), or the data in the source address of the move, heavily depends on the specifics of the precise semantics of those pointers. The user documentation for opPostMove MUST explain what is guaranteed to be safe and what is not.

Implementors may also choose not to define const/immutable versions of opPostMove. This will result in a compile-time error should the compiler try to move an instance of such a struct.

The documentation for an opPostMove implementation MUST also emphasize that while manipulating the memory at the opPostMove source location is allowed, the memory will be released with no destruction immediately after the function's return. Implementors SHOULD be encouraged to define the source argument to opPostMove as const ref, to gain some compiler protection against accidental manipulation. This does not harm the implementor's access to the data, as she already has a copy at the destination location.

Code emitted by the compiler on move

When moving a struct's instance, the compiler MUST call __move_post_blt giving it both new and old instances' addresses.

opPostMove Decoration Considerations

opPostMove SHOULD be @nogc, and either @safe or @trusted. If these attributes are not present, trying to compile code that moves a struct instance from within a context that is @nogc or @safe MUST result in a compilation error. opPostMove, if implemented, MUST be nothrow.

These attributes could be forced by decorating __move_post_blt itself as nothrow @nogc @safe, thus preventing opPostMove from being defined any other way. Doing so is not recommended, as the user might opt not to use, e.g., @safe anywhere in her program. It would not make sense to force her to use it in opPostMove. Due to attribute inference on template functions, if the opPostMove implementation of all of an instance's members are, e.g., @nogc, D will automatically define __move_post_blt as @nogc for that struct.

This proposal does require that nothrow be defined on opPostMove, because throwing would mean a change in the program flow from a place that appears to execute no code. There is a danger that this will be too confusing for the programmer to properly take into account.

Examples

In order to facilitate discussion, following are a couple of concrete examples where opPostMove is needed in order to maintain correctness.

Internal Reference

Consider a struct that keeps track of a number. This may be either a local (per struct) number or a global one. One possible implementation would be:

struct Tracker {
    static uint globalCounter;
    uint localCounter;
    bool isLocal;

    @disable this(this);

    this(bool local) {
        isLocal = local;
        localCounter = 0;
    }

    void increment() {
        if( isLocal )
            localCounter++;
        else
            globalCounter++;
    }
}

The use of an if clause to determine who to update has potentially grave performance implications. Unless branch prediction is successful, a branch is an expensive operation on modern CPUs. If the instances of the struct are evenly distributed between global and local updates, branch prediction is expected to fail in 50% of the cases, and the performance of this implementation is going to be quite bad.

Making isLocal a template argument will solve the branch prediction problem, but is only possible if the determination of local vs. global is known at compile time, which it might not be.

A more performant solution is to use a pointer:

struct Tracker {
    static uint globalCounter;
    uint localCounter;
    uint* counter;

    @disable this(this);

    this(bool local) {
        localCounter = 0;
        if( local )
            counter = &localCounter;
        else
            counter = &globalCounter;
    }

    void increment() {
        (*counter)++;
    }

    void opPostMove(const ref Tracker oldLocation) {
        if( counter is &oldLocation.localCounter )
            counter = &localCounter;
    }
}

Performance Considerations

The __move_post_blt expansion for structs that do not define opPostMove, and for which none of the members opPostMove is defined, will result in an implementation that which recursively calls empty functions for its member instances. The compiler should be able to elide this series of calls via inlining. As such, the run-time cost for this feature for structs that do not use it will be zero.

If compiler implementers fear that inlining will not elide these calls where applicable, they MAY manually eliminate no-op sub-trees. This may be done by adding, at the beginning of __move_post_blt:

static if( !hasElaborateMove!S )
    return;

Such an addition incurs some compile-time cost in the case that an inner member does have opPostMove defined, as it performs multiple scans of the subtrees during the recursive descent. It does, however, guarantee zero run time cost, regardless of compiler optimization capabilities.

Structs that do define opPostMove manage their own costs.

Effect on Phobos

This proposal has minimal impact on Phobos. Even if opPostMove is defined for a struct, the compiler's handling, detailed above, should make sure Phobos is, largely, not affected.

The exceptions are:

  • The move family of functions defined in std.algorithm MUST be updated to add a call to __move_post_blt.
  • The swap functions SHOULD, depending on precise implementation, need to be similarly updated.
  • A new template, hasElaborateMove, SHOULD be added to std.traits. This MUST return true iff a struct or any of its members have an opPostMove defined.

Breaking Changes and Deprecations

There are no breaking changes introduced by the proposal itself, as struct types have to explicitly opt-in to this change to see any change in behavior at all.

This proposal does add two functions with special meaning. One of them is in the reserved space, so should not break anything. If an existing struct has a function called opPostMove, however, switching to an implementation that supports this DIP will break the old code.

Since it is generally understood by D programmers that op* functions are for operator overloads, this problem should not be common. We can further reduce this problem by calling the function opPostMove.

Copyright & License

Copyright (c) 2018 by Weka.IO ltd.

Licensed under This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Reviews

Community Review Round 1

Reviewed Version

Discussion

The point was made that the proposal may require a change in the D ABI, due to the approach D takes in passing by-value non-POD structs as function arguments. The DIP author agreed.

One criticism was that the proposed feature breaks @safety. The DIP author pointed out that the only non-safe aspect is the moving of const/immutable structs, and that the DIP already addresses this by advocating casting the constness away. In that case, @system or @trusted is required.