More UB questions

[ryani...@gmail.com]

I will preface this question by saying "Yes, I know this works on all compilers"; this is more of a question about the standard than the behavior of the program.

I was recently browsing the source code to Google V8 and noticed this curious pattern:

(abbreviated and rephrased here for conciseness)

class Value  // empty POD struct

{

public:

    bool IsBoolean();

private:

    Value(); // not constructible

// no data members

};

class InternalValue

{

public:

   bool IsBoolean() { return mIsBoolean; }

private:

   bool mIsBoolean;

};

// Applying these two functions is not UB

Value* FromHandle(InternalValue** handle)

{

    return reinterpret_cast<Value*>(handle);

}

InternalValue** ToHandle(Value* value)

{

    return reinterpret_cast<InternalValue**>(value);

}

// here is the magic:

bool Value::IsBoolean()

{

    InternalValue** handle = ToHandle(this);

    return (*handle)->IsBoolean();

    // same pointer has now been used both as InternalValue** and Value*

}

// Here is my question

InternalValue* internal_val = /* something that allocates an InternalValue */;

InternalValue** internal_val_handle = /* something that allocates an InternalValue* */

*internal_val_handle = internal_val;

// not UB, can certainly convert back to InternalValue** with ToHandle()

Value* value = FromHandle(internal_val_handle);

// Possibly UB?

bool is_this_ub = value->IsBoolean();

Is this UB?  N4296 9.3.1(2) states "If a non-static member function of a class X is called for an object that is not of type X, or of a type derived from X, the behavior is undefined".  It seems like a InternalValue*& is not a Value& so the access to Value::IsBoolean() on the reinterpet-casted pointer is UB, but I could be misreading the standard.

If this is UB, what could be done to make it not UB?

One thought I had was to re-write Value() like this:

class Value // single element POD struct

{

public:

    bool IsBoolean();

private:

    Value(); // not constructible

    InternalValue** mFirstMember;

};

At this point, since Value is a POD, it must have the same representation as its only member, so a reinterpret-cast between pointers to those types should be safe.  Is that true?

Alternatively, perhaps some magic with std::launder would also make this be defined behavior?

[Richard Smith]

The value here may be unspecified, depending on the alignment requirements of class Value and the actual alignment of internal_val_handle. But let's assume that we didn't hit that case.

 

// Possibly UB?

bool is_this_ub = value->IsBoolean();

Is this UB?

Yes.

 

N4296 9.3.1(2) states "If a non-static member function of a class X is called for an object that is not of type X, or of a type derived from X, the behavior is undefined".  It seems like a InternalValue*& is not a Value& so the access to Value::IsBoolean() on the reinterpet-casted pointer is UB, but I could be misreading the standard.

If this is UB, what could be done to make it not UB?

Redesign this library to not do this. For instance:

class Value {

public:

  static bool IsBoolean(Value *v) { return (*ToHandle(value))->IsBoolean(); }

// ...

};

One thought I had was to re-write Value() like this:

class Value // single element POD struct

{

public:

    bool IsBoolean();

private:

    Value(); // not constructible

    InternalValue** mFirstMember;

You mean InternalValue * here, I think. (You want InternalValue** and Value* to have the same representation, not InternalValue** and Value.)

 

};

At this point, since Value is a POD, it must have the same representation as its only member, so a reinterpret-cast between pointers to those types should be safe.  Is that true?

Not necessarily -- an object of type Value still doesn't exist, so it's still UB. If you want to know whether it's safe with any particular implementation, you'll need to ask the people providing that implementation. (If you originally created an object of type Value, rather than creating an object of type InternalValue*, then this *is* safe and correct if Value is a standard-layout class type.)

A hypothetical sufficiently-smart compiler could look at the whole program, determine that an object of type Value is never created, and then delete all the definitions of non-static member functions of that class. Or (in a sanitizing mode) it could build a side table listing which objects of what types exist at what addresses, and cause your program to crash with a diagnostic on the call to Value::IsBoolean. (And so on, these are just examples.)

Alternatively, perhaps some magic with std::launder would also make this be defined behavior?

No; std::launder does not create objects. Keep in mind [intro.object]/6:

"Two objects that are not bit-fields may have the same address if one is a subobject of the other, or if at least one is a base class subobject of zero size and they are of different types; otherwise, they shall have distinct addresses."

You can't have an object of type InternalValue* and an unrelated object of type Value at the same address.

[ryani...@gmail.com]

On Tuesday, June 7, 2016 at 4:27:16 PM UTC-7, Richard Smith wrote:

On Tue, Jun 7, 2016 at 11:40 AM, <ryani...@gmail.com> wrote:

// Possibly UB?

bool is_this_ub = value->IsBoolean();

Is this UB?

Yes.

 

If this is UB, what could be done to make it not UB?

Redesign this library to not do this. For instance:

class Value {

public:

  static bool IsBoolean(Value *v) { return (*ToHandle(value))->IsBoolean(); }

// ...

};

However you have to concede that the API user's experience here is significantly degraded.  "Value::IsBoolean(v)" is more verbose and non-idiomatic compared to "v->IsBoolean()".  And you lose automatic IDE autocompletion after "v->"

 

class Value // single element POD struct

{

public:

    bool IsBoolean();

private:

    Value(); // not constructible

    InternalValue** mFirstMember;

You mean InternalValue * here, I think. (You want InternalValue** and Value* to have the same representation, not InternalValue** and Value.)

 

Yes that's correct.

 

};

At this point, since Value is a POD, it must have the same representation as its only member, so a reinterpret-cast between pointers to those types should be safe.  Is that true?

Not necessarily -- an object of type Value still doesn't exist, so it's still UB. If you want to know whether it's safe with any particular implementation, you'll need to ask the people providing that implementation. (If you originally created an object of type Value, rather than creating an object of type InternalValue*, then this *is* safe and correct if Value is a standard-layout class type.)

Is that true?  Value is a standard layout type; at the very least copying the bytes of a InternalValue* into a new location certainly creates an object of type Value.  Otherwise creating standard-layout types by copying bytes (via char*) from an over-the-wire structure would be UB (since those objects were not necessarily created by new() or even the same program).

 

A hypothetical sufficiently-smart compiler could look at the whole program, determine that an object of type Value is never created, and then delete all the definitions of non-static member functions of that class. Or (in a sanitizig mode) it could build a side table listing which objects of what types exist at what addresses, and cause your program to crash with a diagnostic on the call to Value::IsBoolean. (And so on, these are just examples.)

Alternatively, perhaps some magic with std::launder would also make this be defined behavior?

No; std::launder does not create objects. Keep in mind [intro.object]/6:

So, if copying the bytes works, then shouldn't using the bytes in place also work, subject to the correct amount of aliasing-warning "I know what I'm doing" hints?  It's my understanding that giving the compiler hints that "strange aliasing may be going on here" is exactly what std::launder is supposed to do.

From http://en.cppreference.com/w/cpp/language/data_members#Standard_layout:

> A pointer to an object of standard-layout struct type can be reinterpret_cast to pointer to its first non-static data member (if it has non-static data members) or otherwise its first base class subobject (if it has any), and vice versa. (padding is not allowed before the first data member). Note that strict aliasing rules still apply to the result of such cast.

That said, I'm not confident in my logic here--if I was, I wouldn't be posting! :)

 

"Two objects that are not bit-fields may have the same address if one is a subobject of the other, or if at least one is a base class subobject of zero size and they are of different types; otherwise, they shall have distinct addresses." 

You can't have an object of type InternalValue* and an unrelated object of type Value at the same address.

Thanks for your time and insight!  I am sure I missed lots of things, so any standard references are appreciated.

[Nicol Bolas]

You're thinking of trivially copyable. Standard layout only governs byte-wise compatibility between two types. It does not mean that it is legal to create such an object by bytewise copying it. It is trivially copyable types that can be bytewise copied into new objects of that type.

[Jens Maurer]

On 06/08/2016 02:53 AM, Nicol Bolas wrote:
> You're thinking of trivially copyable. Standard layout only governs byte-wise compatibility between two types. It does not mean that it is legal to create such an object by bytewise copying it. It is trivially copyable types that can be bytewise copied into new objects of that type.

Even with trivially copyable, 3.9p2 and 3.9p3 seem to say that an
object must already exist before memcpy works.

Richard is working on clarifications what "object exists" actually
means; see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0137r0.html .

(With either the new or the existing wording around "object", it's not
clear that std::vector can actually be implemented in C++. This seems
a sub-optimal state of affairs.)

Jens

[Richard Smith]

On Wed, Jun 8, 2016 at 12:00 AM, Jens Maurer <Jens....@gmx.net> wrote:

On 06/08/2016 02:53 AM, Nicol Bolas wrote:
> You're thinking of trivially copyable. Standard layout only governs byte-wise compatibility between two types. It does not mean that it is legal to create such an object by bytewise copying it. It is trivially copyable types that can be bytewise copied into new objects of that type.

Even with trivially copyable, 3.9p2 and 3.9p3 seem to say that an
object must already exist before memcpy works.

Gabriel Dos Reis' http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3751.pdf made a start at specifying the behavior here, such that memcpy can be used to reinterpret the bits of one type as another, and can be used to start the lifetime of an object, but IIRC we've not seen any updates since Urbana-Champaign.

 

Richard is working on clarifications what "object exists" actually
means; see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0137r0.html .

(With either the new or the existing wording around "object", it's not
clear that std::vector can actually be implemented in C++.  This seems
a sub-optimal state of affairs.)

Dynamic array resizing remains a problem for our formal object model. :(

[Ryan Ingram]

> (With either the new or the existing wording around "object", it's not
clear that std::vector can actually be implemented in C++.  This seems
a sub-optimal state of affairs.)

Hmm, perhaps I don't understand the memory model then.  My usual understanding of how an implementation of vector<> would work in "strict" C++ is something along these lines (ignoring exception safety for the time being, and only showing a couple of the required methods):

template <typename T>

class vector {

    char* mBegin; // allocated with new char[]

    char* mEnd;   // pointer within mBegin array or one-off end

    char* mCapacity; // pointer one off end of mBegin array

public: // methods

};

T& vector<T>::operator[] (int index)

{

    return *reinterpret_cast<T*>(mBegin + index * sizeof(T));

}

void vector<T>::push_back(const T& elem)

{

    if(mEnd == mCapacity) Grow();

    new(mEnd) T(elem);

    mEnd += sizeof(T);

}

void vector<T>::Grow() // private

{

    int nElems = (mCapacity - mBegin) / sizeof(T);

    nElems *= 2;

    if( nElems < 1 ) nElems = 1;

    char* newBegin = new char[ nElems * sizeof(T) ];

    char* oldCur = mBegin;

    char* newCur = newBegin;

    for(; oldCur < mEnd; oldCur += sizeof(T), newCur += sizeof(T)) {

        new(newCur) T(*reinterpet_cast<T*>(oldCur));

        reinterpret_cast<T*>(oldCur)->~T();

    }

    int size = mEnd - mBegin;

    delete [] mBegin;

    mBegin = newBegin;

    mEnd = mBegin + size;

    mCapacity = mBegin + (nElems * sizeof(T));

}

Which part of this is undefined according to the standard?

--

---
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-discussion/p4BXNhTHY7U/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.

[Richard Smith]

You didn't specify how to implement the piece that's not implementable :-)

T *vector<T>::data() { return ??? }

vector<int> vi;

vi.push_back(1);

vi.push_back(2);

vi.push_back(3);

vi.data()[2] = 12; // ub, there is no array object on which to do array indexing

C++98's vector was fine, since it didn't pretend to expose an array to the user (there was no data(), iterators could be used to encapsulate the reinterpret_casts, and there was no contiguous iterator guarantee), but this has been unimplementable in the formal C++ object model since C++03 guaranteed that (&vi.begin())[2] should work.

Obviously it's actually fine in practice (and your implementation will certainly make sure it works), the question here is how to tweak the formal wording to give the guarantees we actually want. There are a number of different options with different tradeoffs (should we require explicit code in std::vector to create an array object? should we allow nontrivial pointer arithmetic / array indexing on pointers that don't point to arrays? should we magically conjure an array object into existence to make this work? should we allow an array object to be created without actually initializing all of its elements? how should the lifetime of an array object work anyway?). I'll probably write a paper on that once we're done with p0137.

On Wed, Jun 8, 2016 at 5:52 PM, Richard Smith <ric...@metafoo.co.uk> wrote:

On Wed, Jun 8, 2016 at 12:00 AM, Jens Maurer <Jens....@gmx.net> wrote:

On 06/08/2016 02:53 AM, Nicol Bolas wrote:
> You're thinking of trivially copyable. Standard layout only governs byte-wise compatibility between two types. It does not mean that it is legal to create such an object by bytewise copying it. It is trivially copyable types that can be bytewise copied into new objects of that type.

Even with trivially copyable, 3.9p2 and 3.9p3 seem to say that an
object must already exist before memcpy works.

Gabriel Dos Reis' http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3751.pdf made a start at specifying the behavior here, such that memcpy can be used to reinterpret the bits of one type as another, and can be used to start the lifetime of an object, but IIRC we've not seen any updates since Urbana-Champaign.

 

Richard is working on clarifications what "object exists" actually
means; see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0137r0.html .

(With either the new or the existing wording around "object", it's not
clear that std::vector can actually be implemented in C++.  This seems
a sub-optimal state of affairs.)

Dynamic array resizing remains a problem for our formal object model. :(

--

---
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-discussion/p4BXNhTHY7U/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.

[Jonathan Wakely]

On Thursday, 9 June 2016 21:05:43 UTC+1, Richard Smith wrote:

You didn't specify how to implement the piece that's not implementable :-)

T *vector<T>::data() { return ??? }

vector<int> vi;

vi.push_back(1);

vi.push_back(2);

vi.push_back(3);

vi.data()[2] = 12; // ub, there is no array object on which to do array indexing

C++98's vector was fine, since it didn't pretend to expose an array to the user (there was no data(), iterators could be used to encapsulate the reinterpret_casts, and there was no contiguous iterator guarantee), but this has been unimplementable in the formal C++ object model since C++03 guaranteed that (&vi.begin())[2] should work.

Obviously it's actually fine in practice (and your implementation will certainly make sure it works), the question here is how to tweak the formal wording to give the guarantees we actually want. There are a number of different options with different tradeoffs (should we require explicit code in std::vector to create an array object? should we allow nontrivial pointer arithmetic / array indexing on pointers that don't point to arrays? should we magically conjure an array object into existence to make this work? should we allow an array object to be created without actually initializing all of its elements? how should the lifetime of an array object work anyway?). I'll probably write a paper on that once we're done with p0137.

This is http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#2182 which I brought up (like an icky hairball) in Kona after LWG went pale and looked scared when I explained how std::vector is UB.

Someone (tkoeppe, I think) asserted it's OK because the array object doesn't have non-vacuous initialization (only its elements do) and so as soon as suitable storage is allocated you can say that an array object's lifetime has started at that location, and then the lifetimes of the array elements begin one-by-one as the vector creates them. I'm unconvinced.

[Richard Smith]

Right, the core wording here has historically been confusing: the wording in [basic.life]/1 is easy to (mis)read as saying that obtaining storage is enough to trigger an object to spontaneously come into existence, and the bogus claim in [intro.object]/1 that an object *is* (another name for) a region of storage adds to the confusion (I suffered from this confusion for a while before I was set straight, I think by GDR). It's the next sentence in [intro.object]/1 that gives the actual definition -- "An object is created by a definition (3.1), by a new-expression (5.3.4) or by the implementation (12.2) when needed." -- with the cross-reference to 12.2 clarifying that we're only talking about temporary objects in the third alternative.

So we only get an object from a definition, new-expression, or temporary, and [basic.life]/1 can't start the lifetime of an array object because there is no such object in the first place.

[Tony V E]

Does malloc start the lifetime of anything?

Sent from my BlackBerry portable Babbage Device

From: Richard Smith Sent: Friday, June 10, 2016 4:16 PM To: std-dis...@isocpp.org Reply To: std-dis...@isocpp.org Subject: Re: [std-discussion] More UB questions

--

[Ville Voutilainen]

On 10 June 2016 at 23:21, Tony V E <tvan...@gmail.com> wrote:

Does malloc start the lifetime of anything?

I would expect it will begin the lifetime of the void* it returns. Anything else than that, probably no.

[ryani...@gmail.com]

> So we only get an object from a definition, new-expression, or temporary, and [basic.life]/1 can't start the lifetime of an array object because there is no such object in the first place.

So I get why this is important to specify like this in the standard; it vastly simplifies talking about what behavior is defined and what isn't.  However, why is it important that this be true for actual code?

What I'm getting at is that there are a set of code transformations that we think of as 'valid', and the standard should recognize the transitive closure of those transformations when considering what objects are 'live',

For example, if C is trivially destructible and p is a pointer to a live object of type C, we should have

    p->~C();

is equivalent to

    /* nothing */ ;

Similarly if C is also zero-constructible we have

    p->~C();

    new(p) C;

is equivalent to

    p->~C();

    memset(p, 0, sizeof(C));

which by the above is equivalent to

    memset(p, 0, sizeof(C));

In particular, this would allow code like the above memset (which exists in every serious program I've seen) to be defined as starting *p's lifetime, as the transformation is valid in both directions!  And the program could have defined behavior both assuming that after this line p is a live, valid object, or assuming it is dead (destructed but not unallocated memory).  It's impossible for the compiler to know which the user intended here so it has to infer it from the code that follows.

This does put additional pressure on the aliasing rules to determine what objects are valid; since only byte* (the misnamed char*, that is) and C* are valid types for pointers to this memory, we can assume that p doesn't point to an object of some unrelated type D* without the programmer using shenanigans like std::launder() (which would probably have to be used to implement malloc() and free() in valid C++ at the low level)

[Nicol Bolas]

On Friday, June 10, 2016 at 8:39:41 PM UTC-4, ryani...@gmail.com wrote:

> So we only get an object from a definition, new-expression, or temporary, and [basic.life]/1 can't start the lifetime of an array object because there is no such object in the first place.

So I get why this is important to specify like this in the standard; it vastly simplifies talking about what behavior is defined and what isn't.  However, why is it important that this be true for actual code?

What I'm getting at is that there are a set of code transformations that we think of as 'valid', and the standard should recognize the transitive closure of those transformations when considering what objects are 'live',

I would say that it'd be better if "we" stopped thinking of those "code transformations" as "valid".

The point of lifetime rules, trivial copyability, and so forth, is not so that we legitimize C-style coding. It's so that we can set boundaries on where some of the useful gimmicks of C-style (copying objects via memcpy) can make sense.
 

For example, if C is trivially destructible and p is a pointer to a live object of type C, we should have

    p->~C();

is equivalent to

    /* nothing */ ;

How do you know when a lifetime has ended unless you have some actual syntax for that? If a non-statement can end the lifetime of an object, then every non-statement ends the lifetime of an object. The object's lifetime has ended right after it began. And it ended after every use.

By your reasoning, every use of `p` is illegal, because it is acting on an object who's lifetime has been ended by the non-statement right before it.

Similarly if C is also zero-constructible we have

    p->~C();

    new(p) C;

is equivalent to

    p->~C();

    memset(p, 0, sizeof(C));

which by the above is equivalent to

    memset(p, 0, sizeof(C));

In particular, this would allow code like the above memset (which exists in every serious program I've seen) to be defined as starting *p's lifetime, as the transformation is valid in both directions!

But it can't start C's lifetime. Because, by your rules, it starts the lifetime of `C` and every other type that can fit into that memory.

What good does it do to say that this memory has the lifetime of any number of objects in it? Just like with "nothing" being able to end an object's lifetime, having an object's lifetime start just because some memory was cleared says nothing about what's actually going on.

Just like non-statements being able to end object lifetimes, saying that poking at memory begins multiple objects' lifetimes leads to incoherent code. If `p` contains both `C` and `D`, then you could legally cast it to either. And now you have pointers to two objects living in the same space, where one is not a subobject of the other.

That's bad. Lifetime rules are supposed to make that impossible. So your rule kinda fails.
 

And the program could have defined behavior both assuming that after this line p is a live, valid object, or assuming it is dead (destructed but not unallocated memory).

Objects are either alive or dead. They cannot be both and neither. Even during construction and destruction, it is made abundantly clear which parts of objects are fully constructed and which parts are not.

It's impossible for the compiler to know which the user intended here so it has to infer it from the code that follows.

And how exactly does that work? What statements would cause you to "infer" that an object's lifetime has begun? What statements would cause you to "infer" than an object's lifetime has ended?

C++ doesn't need to make inferences for these things. We have explicit statements for doing both of these. Placement `new` doesn't "infer" anything; it starts an object's lifetime. That's what it is for. Manually calling the destructor doesn't "infer" anything; it ends the object's lifetime. That's what it is for.

I would much rather that code based on "infering" about the state of an object be declared undefined behavior. However often it is written, it's still bad code.

[Ryan Ingram]

Can you educate me as to what we gain from having the compiler know that this object is alive?

> By your reasoning, every use of `p` is illegal, because it is acting on an object who's lifetime has been ended by the non-statement right before it.

No, p's state is nondeterminate.  Each use of p that requires *p to be alive communicates information: *p must still be alive at this point."  Similarly, each use that requires *p to be dead communicates that it must be dead at that point.  If p must ever both be simultaneously alive and dead, *then* the behavior would be undefined.

It's just like if you get passed an integer parameter x; inside an if(x >= 0) branch you can infer that x is non-negative and use unsigned operations if they happen to be faster on your hardware, but before that statement x's state is indeterminate.

We already rely on the compiler to do these sorts of inferences.  If a function has a pointer argument 'p' and immediately calls p->Foo(), then the compiler can assume (1) p is non-null, and (2) p refers to a live object of its type.  But before that line the compiler doesn't and cannot know the programmers intention.

> But it can't start C's lifetime. Because, by your rules, it starts the lifetime of `C` and every other type that can fit into that memory.

Not exactly; in the absence of some sort of aliasing-laundering mechanism we know it only starts the lifetime of objects of type C (and whatever C's members are), since we have p : C*.

> And how exactly does that work? What statements would cause you to "infer" that an object's lifetime has begun? What statements would cause you to "infer" than an object's lifetime has ended?

The standard already makes those statements:

(paraphrased) "calling a non-static member function on a dead object is undefined".  In order to invoke UB on p->Foo(), the compiler must prove that p is dead.  If p is trivially constructible, then p can actually *never* be proved dead.  If p is zero-constructible, then after p->~C(), p is dead until a new-expression or a memclear of p's memory.  etc.

Honestly, we might fundamentally disagree on the purpose of C++ as a language.  I see it as a systems programming language which offers zero-cost abstractions and ways to make abstractions zero-cost whenever the hardware supports it.  The memory model is that objects are equivalent to arrays of bytes.  The standard should legitimize the memory model it describes by making it easy to treat them that way when it's appropriate to do so.

An example from my previous company, using pre-C++11 compiler:

AutoRefCount<T>: A smart pointer type that calls AddRef() / Release() as needed on the contained object.  ("intrusive" ref-counting).

https://github.com/xebecnan/EAWebkit/blob/master/EAWebKitSupportPackages/EATextEAWebKit/local/include/EAText/internal/EATextRefCount.h#L107

vector<T>: A stl-like vector class.

https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector.h

Our codebase contained a vector of ref-counted pointers.  We would see a performance degradation on frames where this vector was resized, caused by the equivalent of this loop:

    // exception-handling code omitted

    for( i=0; i<size; ++i )

    {

        // calls AddRef() on the target

        new( &newMemory[i] ) T( oldMemory[i] );

    }

    // if no exceptions, destruct the old stuff

    for( i=0; i<size; ++i )

    {

        // calls Release() on the target

        oldMemory[i]->~T();

    }

The addref/release pairs were thrashing our data cache for no real benefit.

We knew that semantically a copy-and-destruct operation for AutoRefCount was equivalent to memcpy, so we implemented this optimization to vector grow--it already had support for trivially copyable objects, but not for trivially copy+destructible.  (Note that this *isn't* the same as trivially movable as described in the standard, a concept which I think is mostly useless as specified as it doesn't handle this case and generally ends up being equivalent to trivial copy).

Now, you could argue that move semantics solves this problem, and you'd be somewhat correct, but it would be tricky for an optimizer to eliminate the second loop where it re-traverses the array and verifies that all the pointers are zero.  But I bet there are other concepts which don't yet have special support in the compiler, and there always will be.

So, how are you proposing that someone implement this sort of optimization in a world where we must explicitly declare to the compiler what objects are alive?  What benefit do we get in terms of other optimizations?

[Nicol Bolas]

On Saturday, June 11, 2016 at 1:35:56 PM UTC-4, Ryan Ingram wrote:

Can you educate me as to what we gain from having the compiler know that this object is alive?

I don't understand what you're saying here.

You're talking about the compiler. I'm talking about the standard. The compiler implements the standard, within the rules the standard lays down.

The standard says that accessing an object after its lifetime has ended is undefined behavior. Because undefined behavior does not require a diagnostic, compilers are not required to detect that an object's lifetime has ended. They will simply access it as if it were live; whatever will be, will be.

Lifetime rules aren't for "the compiler". They're for the standard. They define when undefined behavior is allowed to happen and when it is not.

Using specific syntax to begin and end object lifetimes makes it possible to write code that makes sense. Where you can see the clear intent of the programmer. If those particular instances are no-ops for the compiler, then I expect them to compile away to nothing.

So the benefit is not for the compiler. It's for a clear standard and clear programming by the user.

> And how exactly does that work? What statements would cause you to "infer" that an object's lifetime has begun? What statements would cause you to "infer" than an object's lifetime has ended?

The standard already makes those statements:

(paraphrased) "calling a non-static member function on a dead object is undefined".  In order to invoke UB on p->Foo(), the compiler must prove that p is dead.  If p is trivially constructible, then p can actually *never* be proved dead.

The closest thing to this that C++14 says is in [basic.life]:

> The lifetime of an object of type T ends when:
> - if T is a class type with a non-trivial destructor (12.4), the destructor call starts, or
> - the storage which the object occupies is reused or released.

Note that the exception is made for class types with a non-trivial destructor. The nature of their constructors is irrelevant.

Honestly, we might fundamentally disagree on the purpose of C++ as a language.  I see it as a systems programming language which offers zero-cost abstractions and ways to make abstractions zero-cost whenever the hardware supports it.

How did you get that impression of C++ as a language? C++ offers plenty of abstractions which aren't zero-cost.

The memory model is that objects are equivalent to arrays of bytes.

No. The memory model is that objects are defined by a region of storage. But at no time does the standard claim that all objects "are equivalent to arrays of bytes". The value representation for trivially copyable types are, but not for other types.

I think the language you're thinking of is C, not C++.
 

The standard should legitimize the memory model it describes by making it easy to treat them that way when it's appropriate to do so.

And it does that. You can have objects who are represented only by their bits and bytes. We call them trivially copyable. You're allowed to copy them by copying memory.

You can have objects which have trivial initialization. You can have objects which have trivial destruction. And so forth.

I don't see any reason why requiring specific syntax for starting and ending the lifetime of objects is a bad thing. Again: C++ is not C.

An example from my previous company, using pre-C++11 compiler: 

AutoRefCount<T>: A smart pointer type that calls AddRef() / Release() as needed on the contained object.  ("intrusive" ref-counting).

https://github.com/xebecnan/EAWebkit/blob/master/EAWebKitSupportPackages/EATextEAWebKit/local/include/EAText/internal/EATextRefCount.h#L107

vector<T>: A stl-like vector class.

https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector.h

Our codebase contained a vector of ref-counted pointers.  We would see a performance degradation on frames where this vector was resized, caused by the equivalent of this loop:

    // exception-handling code omitted

    for( i=0; i<size; ++i )

    {

        // calls AddRef() on the target

        new( &newMemory[i] ) T( oldMemory[i] );

    }

    // if no exceptions, destruct the old stuff

    for( i=0; i<size; ++i )

    {

        // calls Release() on the target

        oldMemory[i]->~T();

    }

The addref/release pairs were thrashing our data cache for no real benefit.

We knew that semantically a copy-and-destruct operation for AutoRefCount was equivalent to memcpy, so we implemented this optimization to vector grow--it already had support for trivially copyable objects, but not for trivially copy+destructible.

 

And thereby invoke undefined behavior. There is no such thing as "trivially copy+destructible".

`AutoRefCount` is not trivial in any way. It has no trivial constructors and it has no trivial destructors. Because it is not trivially copyable, you cause undefined behavior by copying it with mempcy ([basic.types]). Because it is not trivially destructible, you cause undefined behavior by deallocating the memory without calling the destructor ([basic.life]).

If you want to rely on undefined behavior, that's your choice. But we're talking about what the standard defines as valid behavior. And what you're doing isn't. And what you're doing shouldn't be.

It should also be noted that because `AutoRefCount` is not in any way trivial, it also doesn't qualify as an example of what you claim you want. Previously, you were talking about blocks of memory containing trivial types. `AutoRefCount` would not qualify.

(Note that this *isn't* the same as trivially movable as described in the standard, a concept which I think is mostly useless as specified as it doesn't handle this case and generally ends up being equivalent to trivial copy).

... The standard doesn't define "trivially moveable". A type which is trivially copyable must have a trivial copy&move constructors, as well as trivial copy/move assignments.
 

Now, you could argue that move semantics solves this problem, and you'd be somewhat correct, but it would be tricky for an optimizer to eliminate the second loop where it re-traverses the array and verifies that all the pointers are zero.  But I bet there are other concepts which don't yet have special support in the compiler, and there always will be.

So, how are you proposing that someone implement this sort of optimization in a world where we must explicitly declare to the compiler what objects are alive?

Implement a specific language feature for the concept. Like one of the destructive-move/relocation/etc proposals (why do you think there have been so many of those proposed?). The right way is not to violate the C++ standard. Nor is it to change the C++ memory model into one based on... well, quite frankly it's hard to tell, since your suggested design is rather incoherent.

That may be a functional way; it may work and it may be fast. But it's still contrary to the standard.

[Ryan Ingram]

>> Can you educate me as to what we gain from having the compiler know that this object is alive?

> I don't understand what you're saying here.

I am asking what benefit actual programs/programmers get from not having a simple memory model, and a simple model of object lifetime that matches what implementations actually do.  As it is, the standard is extremely divergent from actual practice (c.f. "can't actually implement vector in C++") and therefore not useful.

I want the standard to be useful and also match what real programs and real programmers do.  I don't want it to be tied down by notions of ideological purity as fundamentally programming languages exist to write programs, and C++ is foremost a pragmatic language.  There are plenty of research languages that are offer fascinating work if you want to see what you can do by focusing on purity of ideas over pragmatism.  I love those languages.  I write lots of Haskell in my free time.  But when I need to be pragmatic, I need a "pragmatic" tool in my belt, and C++ is the best one for it right now.

> The standard says that accessing an object after its lifetime has ended is undefined behavior. Because undefined behavior does not require a diagnostic, compilers are not required to detect that an object's lifetime has ended. They will simply access it as if it were live; whatever will be, will be.

That may be what they do now, but it is of vital importance what the standard declares as UB as compilers continue to take advantage of UB detection to treat code as unreachable.  As the theorem provers and whole-program optimization used by compilers get better, more and more UB will be found and (ab-)used, and suddenly my "working" code (because it relies on UB, as you say) causes demons to fly out of my nose.

> And thereby invoke undefined behavior. There is no such thing as "trivially copy+destructible".

Yes there is.  It may not be a defined term in the standard, but it is a simple concept to understand, and it enables optimizations that are not possible without it.  I consider it a defect that the standard does not allow me to define such concepts in terms of the lower-level definitions of memory layout, as it means the standard must either grow without bound to encompass all possible concepts for object usage, or else fail in its purpose of being a general-purpose language suitable for systems programming.

> `AutoRefCount` is not trivial in any way. It has no trivial constructors and it has no trivial destructors. Because it is not trivially copyable, you cause undefined behavior by copying it with mempcy ([basic.types]). Because it is not trivially destructible, you cause undefined behavior by deallocating the memory without calling the destructor ([basic.life]).

This is incorrect.  [Basic.life]:

> (4) For an object of a class type with a non-trivial destructor, the program is

> not required to call the destructor explicitly before the storage which the

> object occupies is reused or released; however, if there is no explicit call

> to the destructor or if a delete-expression (5.3.5) is not used to release

> the storage, the destructor shall not be implicitly called and any program

> that depends on the side effects produced by the destructor has undefined

> behavior.

Emphasis "any program that depends on the side effects produced by the destructor"; the whole point of this code transformation is that the resulting program does not rely on the side-effects of the destructor.

[basic.types] does not state that copying a non-trivially-copyable type with memcpy is UB, it simply states that the behavior is explicitly defined for trivially-copyable types.  AutoRefCount is a standard-layout class type, and therefore is represented by a contiguous array of bytes which contain its member variables: a single raw pointer, which *is* trivially copyable.  The only question is how to indicate that the lifetime of the new AutoRefCount has begun; an analogue to [Basic.life](4) for object construction that says that you can avoid calling the constructor if you don't rely on the side-effects of said constructor.

[Nicol Bolas]

On Saturday, June 11, 2016 at 4:35:28 PM UTC-4, Ryan Ingram wrote:

>> Can you educate me as to what we gain from having the compiler know that this object is alive?

> I don't understand what you're saying here.

I am asking what benefit actual programs/programmers get from not having a simple memory model, and a simple model of object lifetime that matches what implementations actually do.

You get to have classes that make sense. You get to have encapsulation of data structures and functional invariants. You get reasonable assurance that invariants established by the constructor or other functions cannot be broken by external code, unless the external code does something which provokes undefined behavior (like, say, memcpy-ing a non-trivially copyable class).

So what we get with these rules is the ability to live and function in a reasonably sane world. That's what the C++ memory model exists to create.

The world you seem to want to live in is C-with-classes.

As it is, the standard is extremely divergent from actual practice (c.f. "can't actually implement vector in C++") and therefore not useful.

The issue with `vector` has to do primarily with arrays, since they're kinda weird in C++. This is a defect because the standard is written contradictory: requiring something which cannot be implemented without provoking UB.

What you are talking about is essentially, "implementations will let you get away with X, so we should standardize that". That's not why the `vector` issue needs to be resolved. It is not the intent of the C++ standard to allow you to memcpy non-trivially copyable types. That's not a defect; that's a feature request.

I don't want it to be tied down by notions of ideological purity as fundamentally programming languages exist to write programs, and C++ is foremost a pragmatic language.  There are plenty of research languages that are offer fascinating work if you want to see what you can do by focusing on purity of ideas over pragmatism.  I love those languages.  I write lots of Haskell in my free time.  But when I need to be pragmatic, I need a "pragmatic" tool in my belt, and C++ is the best one for it right now.

So why do you care? If "don't want it to be tied down by notions of ideological purity" (notions like having a language that makes sense), if you're just going to ignore the rules and do what your compiler lets you get away with anyway... why does it matter to you what the standard says?

> The standard says that accessing an object after its lifetime has ended is undefined behavior. Because undefined behavior does not require a diagnostic, compilers are not required to detect that an object's lifetime has ended. They will simply access it as if it were live; whatever will be, will be.

That may be what they do now, but it is of vital importance what the standard declares as UB as compilers continue to take advantage of UB detection to treat code as unreachable.  As the theorem provers and whole-program optimization used by compilers get better, more and more UB will be found and (ab-)used, and suddenly my "working" code (because it relies on UB, as you say) causes demons to fly out of my nose.

That's what happens when you rely on undefined behavior.

Also, if truly every C++ programmer does this sort of thing, then surely no compiler writer would implement an optimization that would break every C++ program. If the kind of thing you're talking about is as widespread as you claim, you won't have anything to worry about.

> And thereby invoke undefined behavior. There is no such thing as "trivially copy+destructible".

Yes there is.  It may not be a defined term in the standard,

... you do realize that you're having a discussion on a mailing list about the standard, right?

However much you may want that concept, it is not one which C++ defines. Nor does it allow you to manufacture it. Nor is the intent of C++'s memory model that you can manufacture it.
 

but it is a simple concept to understand, and it enables optimizations that are not possible without it.  I consider it a defect that the standard does not allow me to define such concepts in terms of the lower-level definitions of memory layout, as it means the standard must either grow without bound to encompass all possible concepts for object usage, or else fail in its purpose of being a general-purpose language suitable for systems programming.

The term "defect" is not something to be thrown around just because the standard doesn't do what you think it ought to. I could easily call the fact that I can't reliably use uniform initialization on unknown types a "defect". That doesn't make it so.

> `AutoRefCount` is not trivial in any way. It has no trivial constructors and it has no trivial destructors. Because it is not trivially copyable, you cause undefined behavior by copying it with mempcy ([basic.types]). Because it is not trivially destructible, you cause undefined behavior by deallocating the memory without calling the destructor ([basic.life]).

This is incorrect.  [Basic.life]:

> (4) For an object of a class type with a non-trivial destructor, the program is

> not required to call the destructor explicitly before the storage which the

> object occupies is reused or released; however, if there is no explicit call

> to the destructor or if a delete-expression (5.3.5) is not used to release

> the storage, the destructor shall not be implicitly called and any program

> that depends on the side effects produced by the destructor has undefined

> behavior.

Emphasis "any program that depends on the side effects produced by the destructor"; the whole point of this code transformation is that the resulting program does not rely on the side-effects of the destructor.
 

[basic.types] does not state that copying a non-trivially-copyable type with memcpy is UB, it simply states that the behavior is explicitly defined for trivially-copyable types.

That's not how a standard works.

A standard specifies behavior. It specifies what will happen if you do a particular thing. If the standard does not explicitly say what the results of something are, then those results are undefined by default.

AutoRefCount is a standard-layout class type, and therefore is represented by a contiguous array of bytes which contain its member variables:

That's not what standard layout means. It merely means that it has a consistent layout of data members.
 

a single raw pointer, which *is* trivially copyable.

The fact that the contents of a class are trivially copyable does not mean that the class itself is trivially copyable. The trivial copyability of members is necessary but not sufficient. The standard makes that very clear.

The only question is how to indicate that the lifetime of the new AutoRefCount has begun; an analogue to [Basic.life](4) for object construction that says that you can avoid calling the constructor if you don't rely on the side-effects of said constructor.

Why should we want that? As far as I'm concerned, [basic.life](4) is a mistake and should be removed. If you give an object a non-trivial destructor, and it doesn't get called, then your program should be considered broken.

And as previously stated, the fact that you're memcpy-ing a non-trivially copyable class makes this process UB.

[Greg Marr]

On Saturday, June 11, 2016 at 7:29:46 PM UTC-4, Nicol Bolas wrote:

[Basic.life]:

> (4) For an object of a class type with a non-trivial destructor, the program is

> not required to call the destructor explicitly before the storage which the

> object occupies is reused or released; however, if there is no explicit call

> to the destructor or if a delete-expression (5.3.5) is not used to release

> the storage, the destructor shall not be implicitly called and any program

> that depends on the side effects produced by the destructor has undefined

> behavior.

As far as I'm concerned, [basic.life](4) is a mistake and should be removed. If you give an object a non-trivial destructor, and it doesn't get called, then your program should be considered broken.

Doesn't the standard mostly agree with you on it being broken?

"any program that depends on the side effects produced by the destructor has undefined behavior."

AIUI, this clause simply gives the compiler the freedom to not call the destructor of foo in the

following program, because the program doesn't depend on the side effects.

This class has a non-trivial destructor, but there are no observable side effects of not calling it.

class foo

{

public:

    foo() : m_val(10) {}

    ~foo() { m_val = 0; }

    int val() const { return m_val; }

private:

    int m_val;

}

int main()

{

    foo bar;

    printf("%d\n", foo.val());

    return 0;

}

[Ryan Ingram]

I'm not sure I can continue having a discussion with you if you continue to be intellectually dishonest.

For example, you ask

>  if you're just going to ignore the rules and do what your compiler lets you get

> away with anyway... why does it matter to you what the standard says?

which, guess what, I already answered -- in fact, you immediately quote my answer:

> That may be what they do now, but it is of vital importance what the standard

> declares as UB as compilers continue to take advantage of UB detection to

> treat code as unreachable.  As the theorem provers and whole-program

> optimization used by compilers get better, more and more UB will be found

> and (ab-)used, and suddenly my "working" code (because it relies on UB, as

> you say) causes demons to fly out of my nose.

and you follow with this claim

> That's what happens when you rely on undefined behavior.

You can't have it both ways; I care about what is in the standard because I care about my programs continuing to work, but I also care about being able to write programs that make the hardware do what I want.  The argument I am putting forward is that this behavior shouldn't be undefined; that the standard and common coding practice should be in agreement.  There are ways to have a language that semantically makes sense without hardcoding everything into explicit syntax about object construction, but you dismiss this idea out of hand.

You say I want "C with classes" and perhaps that is true, but I also want "C with generics" and "C with RAII" and really, all the things that C++ already provides and C is nowhere near providing.  The C++ standard is a living document written by people, not a bible from an all-knowing god, and I hope my voice is part of an effort to push the language closer to what it could be.

> Why should we want that? As far as I'm concerned, [basic.life](4) is a mistake and should be removed. If you give an object a non-trivial destructor, and it doesn't get called, then your program should be considered broken.

More dishonesty here.  You call me out when I propose that things are problems in the standard, but then you go ahead and do the same *in the same message*.

> That's not how a standard works.

>
> A standard specifies behavior. It specifies what will happen if you do a

> particular thing. If the standard does not explicitly say what the results

> of something are, then those results are undefined by default.

I agree with this statement.  I was simply pointing out that [basic.types] is not sufficient to call this behavior UB; I don't know the entire standard word-by-word (and neither do you, as evidenced by your misquote of [basic.life]), and I'm not 100% convinced that there is nothing elsewhere in the standard that defines what should happen in this case, although given that it's not defined at that point, I am willing to believe that it's more likely than not UB.  When something explicitly is declared UB it's easier to quote the relevant section!

So, lets go back to trying to find some common ground.  (Apologies to any of our readers who were hoping for a good old-fashioned flame war!)

Here's an example of some Haskell code using a GHC optimization extension:

    {-# RULES

        "map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs

    #-}

Here the programmer of "map" knows that semantically the code on both sides of the equals is the same, but that the right-hand one will generally be more efficient to evaluate.  Rewrite RULES inform the compiler of this knowledge and ask it to make a code transformation for us, adding additional optimization opportunities that can show up after inlining or other optimizations.

Now, you could trivially write a false rule

    {-# RULES

        "timesIsPlus"   forall x y. x*y = x+y

    #-}

The fact that the programmer could write a buggy program doesn't mean that the language makes no sense.  This feature is designed to be used by programmers who have proved that the code transformation being applied is valid.  In C++-standards-ese I would say "a program with a rewrite rule where the right hand side is observably different from the left hand side has undefined behavior"; the compiler is free to apply, or not apply the rewrite rule, and it's up to the author of the rule to guarantee that the difference between the LHS and RHS of the rule is not observable.

I am not suggesting a wild-west world where everyone just memcpy's objects everywhere.  I think you're right that this isn't a useful place to be.

I am suggesting a world where it is up to the programmer to define places where that makes sense and is legal; one where the memory model works in tandem with the object model to allow low-level optimizations to be done where needed.  [basic.life](4) is an example of this sort of world, it specifies that I can re-use the storage for an object without calling the destructor if I can prove that my program doesn't rely on the side-effects of that destructor.  It doesn't say I'm allowed to just not call destructors willy-nilly--it puts an obligation on me as a programmer to be more careful if I am writing crazy code.  It's this same sentiment that puts reinterpret_cast and const_cast in the language; tools of great power but that also carry great responsibility.

Similarly, objects on real hardware are made out of bytes, and sometimes it's useful to think of them as objects, sometimes as bytes, and sometimes as both simultaneously.  What are the best ways to enable this?  Are there ways that make sense or do you think it's fundamentally incompatible with the design of the language?

[Nicol Bolas]

On Sunday, June 12, 2016 at 6:38:31 AM UTC-4, Ryan Ingram wrote:

I'm not sure I can continue having a discussion with you if you continue to be intellectually dishonest.

For example, you ask

>  if you're just going to ignore the rules and do what your compiler lets you get

> away with anyway... why does it matter to you what the standard says?

which, guess what, I already answered -- in fact, you immediately quote my answer:

> That may be what they do now, but it is of vital importance what the standard

> declares as UB as compilers continue to take advantage of UB detection to

> treat code as unreachable.  As the theorem provers and whole-program

> optimization used by compilers get better, more and more UB will be found

> and (ab-)used, and suddenly my "working" code (because it relies on UB, as

> you say) causes demons to fly out of my nose.

and you follow with this claim

> That's what happens when you rely on undefined behavior.

You can't have it both ways; I care about what is in the standard because I care about my programs continuing to work,

As I said immediately after that:

> Also, if truly every C++ programmer does this sort of thing, then surely no compiler writer would implement an optimization that would break every C++ program. If the kind of thing you're talking about is as widespread as you claim, you won't have anything to worry about.

So what is the reason for your fear that your UB-dependent code will break? Or are you not as sure as you claim that your "common coding practice" is indeed "common"?

but I also care about being able to write programs that make the hardware do what I want.  The argument I am putting forward is that this behavior shouldn't be undefined; that the standard and common coding practice should be in agreement.  There are ways to have a language that semantically makes sense without hardcoding everything into explicit syntax about object construction, but you dismiss this idea out of hand.

The purpose of a constructor/destructor pair is to be able to establish and maintain invariants with respect to an object. The ability to create/destroy an object without calling one of these represents a violation of that, making such invariants a suggestion rather than a requirement.

You want the validity of this code to be dependent on the kind of invariant. That you can get away without doing what you normally ought to do based on the particular nature of the invariant that the class is designed to protect. I see nothing to be gained by that and a lot to be lost by it.

A static analyzer can detect when you attempt to `memcpy` a non-trivially-copyable class. A static analyzer cannot detect when you attempt to `memcpy` a non-trivially-copyable class and then drop the previous one on the floor, such that the invariant just so happens to be maintained.

The world you want to occupy makes that static analyzer impossible to write in a way that didn't get false positives or false negatives. The world I want makes that static analyzer correct, according to the standard, requiring you to write your code correctly in accord with the specification.

> Why should we want that? As far as I'm concerned, [basic.life](4) is a mistake and should be removed. If you give an object a non-trivial destructor, and it doesn't get called, then your program should be considered broken.

More dishonesty here.  You call me out when I propose that things are problems in the standard, but then you go ahead and do the same *in the same message*.

I'm not saying that the standard is perfect. I'm saying that the things you want to be legal are bad. Even if some of them already are legal.

> That's not how a standard works.

>
> A standard specifies behavior. It specifies what will happen if you do a

> particular thing. If the standard does not explicitly say what the results

> of something are, then those results are undefined by default.

I agree with this statement.  I was simply pointing out that [basic.types] is not sufficient to call this behavior UB; I don't know the entire standard word-by-word (and neither do you, as evidenced by your misquote of [basic.life]), and I'm not 100% convinced that there is nothing elsewhere in the standard that defines what should happen in this case, although given that it's not defined at that point, I am willing to believe that it's more likely than not UB.  When something explicitly is declared UB it's easier to quote the relevant section!

Generally speaking, something only needs to be called out explicitly as UB when it might otherwise have worked. Like the rules about integer overflow (though those are implementation-defined, not UB). Normally adding integers has well-defined results, but there are certain corner cases that have to be called out.

Nothing in the standard says that memcpy will generally work on objects, but there is a specific allowance made for trivially copyable types. Thus outside of that allowance, doing it is UB.

So, lets go back to trying to find some common ground.  (Apologies to any of our readers who were hoping for a good old-fashioned flame war!)

Here's an example of some Haskell code using a GHC optimization extension:

OK, I know nothing about Haskell (or functional programming of any kind), so I'll try to translate my understanding of what I think you're saying.

    {-# RULES

        "map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs

    #-}

Here the programmer of "map" knows that semantically the code on both sides of the equals is the same, but that the right-hand one will generally be more efficient to evaluate.  Rewrite RULES inform the compiler of this knowledge and ask it to make a code transformation for us, adding additional optimization opportunities that can show up after inlining or other optimizations.

 

Now, you could trivially write a false rule

    {-# RULES

        "timesIsPlus"   forall x y. x*y = x+y

    #-}

The fact that the programmer could write a buggy program doesn't mean that the language makes no sense.

From this, I gather that Haskell has some syntax for performing arbitrary transformations of its own code via patterns. And that you can write transformations that are actually legitimate as well as transformations that lead to broken code.

I have no idea why you brought up Haskell here. You may as well have used a macro or DSELs with C++ metaprogramming and operator overloading (say, Boost.Spirit). Any feature which could be abused would make your point.

This feature is designed to be used by programmers who have proved that the code transformation being applied is valid.  In C++-standards-ese I would say "a program with a rewrite rule where the right hand side is observably different from the left hand side has undefined behavior"; the compiler is free to apply, or not apply the rewrite rule, and it's up to the author of the rule to guarantee that the difference between the LHS and RHS of the rule is not observable.

I am not suggesting a wild-west world where everyone just memcpy's objects everywhere.  I think you're right that this isn't a useful place to be.

I am suggesting a world where it is up to the programmer to define places where that makes sense and is legal; one where the memory model works in tandem with the object model to allow low-level optimizations to be done where needed.  [basic.life](4) is an example of this sort of world, it specifies that I can re-use the storage for an object without calling the destructor if I can prove that my program doesn't rely on the side-effects of that destructor.  It doesn't say I'm allowed to just not call destructors willy-nilly--it puts an obligation on me as a programmer to be more careful if I am writing crazy code.

The fact that you could make use of something by itself does not justify permitting it.

The fact that something could be abused by itself does not justify forbidding it. It's a delicate balance. However, I feel that trivial copyability strikes a good balance between "blocks of bits" and "genuine objects". You get your low-level constructs and such, but it's cordoned off into cases that the language can verify actually works.

I consider an object model where important elements like constructors and destructors are made optional based on non-static implementation details to not be worth the risks. Your object either is an object or it is a block of bits.

It's this same sentiment that puts reinterpret_cast and const_cast in the language; tools of great power but that also carry great responsibility.

How useful is `reinterpret_cast` really, at the end of the day? You can't use it to violate strict aliasing, even if the type you're casting it to is layout-compatible with the source. The only thing I use it for with anything approaching regularity is converting integer values to pointers. And that's only because `glVertexAttribPointer` has a terrible API that pretends a pointer is really an integer offset.

And how useful is `const_cast`? The most useful thing its for is making it easier to write `const` and non-`const` overloads of the same function. Nice to have, yes. But hardly a "tool of great power".
 

Similarly, objects on real hardware are made out of bytes, and sometimes it's useful to think of them as objects, sometimes as bytes, and sometimes as both simultaneously.  What are the best ways to enable this?  Are there ways that make sense or do you think it's fundamentally incompatible with the design of the language?

OK, let's look at your exact example. You have some internal vector analog and you have your internal intrusive pointer. Now, let's assume that the standard actually permits you to `memcpy` non-trivially copyable types, and it allows you to end the lifetime of types with non-trivial destructors without actually calling those destructors.

So let's look at what you've done with that. In order to implement your optimization, you had to presumably add a specialization of `eastl::vector` specifically for the `AutoRefCount` type. That's a lot of work for just one type. You had to re-implement a lot of stuff. I'm sure that there were ways to reuse a lot of the standard code, but that's still a lot of work.

Let's compare this to the ability to optimize std::vector's reallocation routines for trivially copyable types. That works on every type that is trivially copyable. Why? Because these are the types that the language can prove will work. Suddenly, once those optimizations are made, everyone's code gets faster. `std::copy` gets faster when using trivially copyable types too. As do many other algorithms.

I don't have to specialize `vector` for each trivially copyable type I write. I don't have to specialize `std::copy` for each type. It all just works. I can take a type written by someone who can't even spell trivially copyable and it will work.

If you had a need to use a linked-list type in your `eastl::vector`, it would not automatically be able to use this optimization. You would likely need to write another specialization. With sufficient cleverness, you could write a traits type that could be used to detect such classes and employ those optimizations globally. But even that would only affect you and your own little world, not the rest of the C++ world.

Furthermore, I can now write my own `vector` analog that uses these optimizations. It can use template metaprogramming to detect when they would be allowed and employ them in those cases. I'm not writing some special one-time code for a specific thing. I'm making all kinds of stuff faster.

That is the power of having a firm definition in the language for behavior. That is the power of knowing a prior which objects are blocks of bits and objects which are not. That is the power of having real language mechanisms rather than inventing them on the fly based on the idea that any object should be able to be considered a block of bits whenever you feel you can get away with it.

C is about giving you a bunch of low-level tools and expecting you to implement whatever you like. C gives you function pointers and tells you that if you want virtual functions and inheritance, you'll have to implement it yourself.

C++ makes these first-class features. That way, everyone implements them the same way, and everyone's class hierarchies are inter-operable. If you write a class, I can derive from it and override those virtual functions using standard mechanisms. Oh sure, we still have function pointers. But nobody uses them to write vtables manually; that'd be stupid.

That's why adding destructive-move, relocation, or whatever else is far superior to your "let's pretend a type with invariants is a block of bits" approach. Because once it's in the language, everyone can use it. Everyone gets to use it, likely without asking for it. Every user of `unique_ptr`, `shared_ptr`, etc gets to have this performance boost.

If you improve the object model such that it actually supports the operations you want, you won't have to treat objects as blocks of bits to get things done. Just like with virtual functions, it's best to identify those repeated patterns and put them into the language.

Look, I've written code that treats genuine objects as blocks of bits. I wrote a serialization system that would write binary blobs to disk, which would later be loaded onto different platforms directly in memory. It supported virtual types through vtable pointer fixup. Oh, and the platform that wrote the data? It was completely different from the platform(s) that read it, so endian fixup was often needed (at writing time).

All that code worked just fine, but it relied on UB in probably 5 different ways. And it was good, useful code that shipped on at least 3 different projects.

But I would never want it to be standard.

[Ryan Ingram]

> If you had a need to use a linked-list type in your `eastl::vector`, it would not

> automatically be able to use this optimization. You would likely need to write

> another specialization. With sufficient cleverness, you could write a traits type

> that could be used to detect such classes and employ those optimizations

> globally. But even that would only affect you and your own little world, not the

> rest of the C++ world.

Which is exactly what we did.  When type traits can be a library feature instead of a language feature, they can be evolved more quickly than the language allows directly.  eastl type traits are override-able for particular classes, so while the default for "has_trivial_relocate" is "has_trivial_copy && has_trivial_destruct", programmers can specialize those traits for particular object types when they know the semantics of the underlying objects.

My general rule is "don't assume the language standard knows more about your program than the programmer".  The implementor of FooClass should be able to write "template <> has_trivial_copy<FooClass> : public true_type {};" in FooClass.h, even if they implemented a non-trivial copy constructor, because they hopefully knew what they were doing when they wrote that line of code, and this shouldn't suddenly cause vector<FooClass> resizes to become UB.  Maybe their copy constructor just logs when copies happen because they were curious how often FooClass was passed-by-value, and they don't care about users like vector<> who make trivial copies.  There's tons of reasons for this kind of code.

So it's not "vector knows about AutoRefCount", that would be a horrible layering problem.  It's "vector knows about has_trivial_relocate, a new type trait", and "AutoRefCount knows that it is trivially relocatable."  And vector is trivially relocatable too, so a vector of vectors can be resized with memcpy as well!  In fact, types that aren't trivially relocatable are the exception rather than the rule, even if they need non-trivial move constructors to handle the fact that they need to leave a live object behind to be destructed.  I am sure this is the reason for the plethora of relocation proposals, but this isn't a complicated concept.  It's just that the way the language defines the object/memory/lifetime model makes it complicated to iron out the details.

Type traits would get much simpler with a good compile-time reflection system so that there is a standard way to query "are all X's fields relocatable and X doesn't declare a special move constructor or destructor etc.?" allowing us to not have to manually specify has_trivial_relocate for every class, just the ones for which it's true, in the same way that the compiler automatically derives has_trivial_copy from the fields of the object via some un-exposed-to-the-user magic.

Making this sort of behavior defined allows iterating on these sorts of language features without the friction of a multi-year design and standardization process, and allows groups to come to the committee with (possibly portable!) implemented code that shows the feature for standardization -- moving it from the language standardization group which is intentionally high-friction, to the libraries standardization group which is a lower barrier for change, or allowing groups like boost to create portable extensions to the language before they become standard.

> C++ makes these first-class features. That way, everyone implements them

> the same way, and everyone's class hierarchies are inter-operable. If you write

> a class, I can derive from it and override those virtual functions using standard

> mechanisms. Oh sure, we still have function pointers. But nobody uses them

> to write vtables manually; that'd be stupid.

You'd be surprised.  I've seen some crazy code :)

> All that code worked just fine, but it relied on UB in probably 5 different ways.

> And it was good, useful code that shipped on at least 3 different projects.

>

> But I would never want it to be standard.

AHA, so I think this is where we have been talking past each other.

So the perspective I'm coming from is that when the standard writes "undefined behavior", what I read is "this will probably cause your program to crash or corrupt memory, and we can't guarantee that said memory corruption won't cause your program to erase your hard disk or do something else terrible.  Because of this, optimizers are free to pretend this case never happens and use that to help generate invariants about the code"

e.g.

   int* p = f();

   int& x = *p; // UB if p == nullptr

   if(p == nullptr) { /* optimizer can eliminate this as dead code */ }

When there's something that is useful but not possible to make portable due to representation or other issues, that is usually instead labeled as "implementation-defined behavior" rather than "undefined behavior".  Two examples:

First, from N4296:

> [expr.shift] (3)

>

> The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has

> an unsigned type or if E1 has a signed type and a non-negative value,

> the value of the result is the integral part of the quotient of E1/2E2. If

> E1 has a signed type and a negative value, the resulting value is

> implementation-defined.

Most implementations are twos-complement and treat signed-right-shift as "arithmetic right shift" which extends the sign bit to the new high bits.  But the standard supports other integer representations such as 1s complement, so it's not possible to define the actual value of the result.  But it's not UB--right shifting a negative number gives some implementation-defined result and it's not standards compliant for doing so to crash your program or erase your hard disk.

Second, from your message:

> How useful is `reinterpret_cast` really, at the end of the day? You can't use it to violate

> strict aliasing, even if the type you're casting it to is layout-compatible with the source.

> The only thing I use it for with anything approaching regularity is converting integer values

> to pointers. And that's only because `glVertexAttribPointer` has a terrible API that

> pretends a pointer is really an integer offset.

I used to use it commonly like this:

static_assert(sizeof(float) == sizeof(int32_t));

float x = ...;

int32_t x_representation = renterpret_cast<int32_t&>(x);

// do IEEE floating-point magic here e.g. https://en.wikipedia.org/wiki/Fast_inverse_square_root

// or use it for serialization.

The current standard has no way to do this sort of 'representation-cast'.  Implementations now generally outlaw using reinterpret_cast to violate strict aliasing, but allow representation casting to be done via unions.  But even that is an extension, and according to a strict reading of the standard it is UB.  I think that this is exactly the kind of thing that should have "implementation-defined" behavior rather than be UB.  The difference is that usually implementation-defined behavior has bounds to how wild implementations can go, for example: "the resulting value is implementation-defined" vs. "is UB".  It puts boundaries on how non-portable this code is.

> All that code worked just fine, but it relied on UB in probably 5 different ways. And it was good, useful code that shipped on at least 3 different projects.

> But I would never want it to be standard.

So when you say you don't want this behavior to be standard, I see where you are coming from, but I also don't think it should be UB.  UB means the next version of the compiler could decide to make your program erase your hard disk, and start world war 3.  The implementation of vtables is certainly implementation dependent but that doesn't mean the memory model shouldn't still allow you to treat an object as a bunch of implementation-defined bytes.  In the cases where it makes sense to do so, those bytes should even have defined values (e.g. standard layout object).

Tongue-in-cheek idea: 'frankenstein_new(p)' begins the lifetime of the object pointed to by p without calling any constructor.  ("IT'S ALIVE!")  Easy to audit for!  Implemented as a no-op but has semantic value to analysis tools.  UB if p is not standard-layout and the implementation-defined bytes aren't correctly initialized (with "correctly initialized" being implementation-defined).

(random segue here to more reinterpret_cast thoughts...)

Another use I've been doing more of lately is using reinterpret_cast to create strong opaque typedefs.  This is fortunately well-defined according to the standard:

foo.h

// define a uniquely-typed version of void*

// that isn't castable to other void*s

struct OpaqueFoo_t; // never defined

typedef OpaqueFoo_t* FooHandle;

class IFoo {

    (some functions that create and operate on FooHandles here)

};

foo_impl.cpp

struct ActualObject {

   ...

};

FooHandle ToFooHandle(ActualObject* p) { return reinterpret_cast<FooHandle>(p); }

ActualObject* FromFooHandle(FooHandle p) { return reinterpret_cast<ActualObject *>(p); }

class FooImpl : public IFoo { ... };

This allows multiple coexisting implementations of IFoo to exist within the same program as long as users only pass handles created by one IFoo to the same IFoo.  There are ways to make this more typesafe but the ones I've found all add a huge burden to users that so far hasn't been worth the small additional safety.

[Tony V E]

‎http://open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0023r0.pdf

Sent from my BlackBerry portable Babbage Device

From: Ryan Ingram Sent: Monday, June 13, 2016 2:55 AM To: Nicol Bolas Reply To: std-dis...@isocpp.org Cc: ISO C++ Standard - Discussion

Subject: Re: [std-discussion] More UB questions

[Edward Catmur]

On Monday, 13 June 2016 07:55:49 UTC+1, Ryan Ingram wrote:

I used to use it commonly like this:

static_assert(sizeof(float) == sizeof(int32_t));

float x = ...;

int32_t x_representation = renterpret_cast<int32_t&>(x);

// do IEEE floating-point magic here e.g. https://en.wikipedia.org/wiki/Fast_inverse_square_root

// or use it for serialization.

The current standard has no way to do this sort of 'representation-cast'.

What's wrong with using memcpy?

int32_t x_representation;

std::memcpy(&x_representation, &x, sizeof(x));

 

Implementations now generally outlaw using reinterpret_cast to violate strict aliasing, but allow representation casting to be done via unions.  But even that is an extension, and according to a strict reading of the standard it is UB.  I think that this is exactly the kind of thing that should have "implementation-defined" behavior rather than be UB.  The difference is that usually implementation-defined behavior has bounds to how wild implementations can go, for example: "the resulting value is implementation-defined" vs. "is UB".  It puts boundaries on how non-portable this code is.

Permitting aliasing via unions would wreck performance, as you would never know when two objects of completely different types might alias. The C union visibility rule is highly controversial even within the C community; see e.g. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65892

[Tony V E]

As for breaking code that is UB but common, compilers are already doing that, and some are complaining about it.

Sent from my BlackBerry portable Babbage Device

From: Nicol Bolas Sent: Monday, June 13, 2016 1:07 AM To: ISO C++ Standard - Discussion Reply To: std-dis...@isocpp.org Cc: jmck...@gmail.com; ryani...@gmail.com

Subject: Re: [std-discussion] More UB questions

[Ryan Ingram]

On Mon, Jun 13, 2016 at 6:41 AM, Edward Catmur <e...@catmur.co.uk> wrote:

> What's wrong with using memcpy?

> 

> int32_t x_representation;

> std::memcpy(&x_representation, &x, sizeof(x));

Honestly, I never thought of it.  I'd assumed that memcpy would copy 4 individual bytes instead of a single word, and that optimizers would have a harder time eliding the storage/read from memory into a register transfer.

As an old dog programmer, I'm used to thinking of memcpy as a library function, whereas it's more of a compiler intrinsic these days, so perhaps it is time to check those assumptions.

[FrankHB1989]

在 2016年6月12日星期日 UTC+8上午1:35:56，Ryan Ingram写道：

Can you educate me as to what we gain from having the compiler know that this object is alive?

> By your reasoning, every use of `p` is illegal, because it is acting on an object who's lifetime has been ended by the non-statement right before it.

No, p's state is nondeterminate.  Each use of p that requires *p to be alive communicates information: *p must still be alive at this point."  Similarly, each use that requires *p to be dead communicates that it must be dead at that point.  If p must ever both be simultaneously alive and dead, *then* the behavior would be undefined.

It's just like if you get passed an integer parameter x; inside an if(x >= 0) branch you can infer that x is non-negative and use unsigned operations if they happen to be faster on your hardware, but before that statement x's state is indeterminate.

We already rely on the compiler to do these sorts of inferences.  If a function has a pointer argument 'p' and immediately calls p->Foo(), then the compiler can assume (1) p is non-null, and (2) p refers to a live object of its type.  But before that line the compiler doesn't and cannot know the programmers intention.

> But it can't start C's lifetime. Because, by your rules, it starts the lifetime of `C` and every other type that can fit into that memory.

Not exactly; in the absence of some sort of aliasing-laundering mechanism we know it only starts the lifetime of objects of type C (and whatever C's members are), since we have p : C*.

> And how exactly does that work? What statements would cause you to "infer" that an object's lifetime has begun? What statements would cause you to "infer" than an object's lifetime has ended?

The standard already makes those statements:

(paraphrased) "calling a non-static member function on a dead object is undefined".  In order to invoke UB on p->Foo(), the compiler must prove that p is dead.  If p is trivially constructible, then p can actually *never* be proved dead.  If p is zero-constructible, then after p->~C(), p is dead until a new-expression or a memclear of p's memory.  etc.

"To invoke UB" is not mandated. That's an issue of QoI. If the compiler fails to prove that, it can still do anything it like.
 

Honestly, we might fundamentally disagree on the purpose of C++ as a language.

You were talking about dialects you want, not the language itself.
 

I see it as a systems programming language which offers zero-cost abstractions and ways to make abstractions zero-cost whenever the hardware supports it.  The memory model is that objects are equivalent to arrays of bytes.  The standard should legitimize the memory model it describes by making it easy to treat them that way when it's appropriate to do so.

"Whenever the hardware supports it" - That's plain wrong. If that's it, you should not have notion of C-style array/pointers, but pointers within typical ISA documents (i.e. some forms of address) directly in the language to reference the memory. It needs to provide explicit abstraction of alternative storage which is distinct to main memory in the system (e.g. architectural registers). It may or may not treat the cache transparently. It is also suspicious to have arrays of bytes but not of bits/words as the fundamental memory abstraction in this language.
Such a system programming language would rely on excessive assumptions for general applications and be essentially not portable between machines. It is not C++ aim to be.

[FrankHB1989]

在 2016年6月12日星期日 UTC+8上午4:35:28，Ryan Ingram写道：

>> Can you educate me as to what we gain from having the compiler know that this object is alive?

> I don't understand what you're saying here.

I am asking what benefit actual programs/programmers get from not having a simple memory model, and a simple model of object lifetime that matches what implementations actually do.  As it is, the standard is extremely divergent from actual practice (c.f. "can't actually implement vector in C++") and therefore not useful.

What implementations would actually do? It depends. Models of object lifetime are not required to "match" the implementations, because the check of violation of these rules are not mandated.
I don't know why the "actual practice" is concerned with "useful", just because the practice is not standardized? What is the benefit? More portable or more efficient code? Easier to implement?
And I doubt there are many users really need to implement a vector exactly as you said.

 

I want the standard to be useful and also match what real programs and real programmers do.  I don't want it to be tied down by notions of ideological purity as fundamentally programming languages exist to write programs, and C++ is foremost a pragmatic language.  There are plenty of research languages that are offer fascinating work if you want to see what you can do by focusing on purity of ideas over pragmatism.  I love those languages.  I write lots of Haskell in my free time.  But when I need to be pragmatic, I need a "pragmatic" tool in my belt, and C++ is the best one for it right now.

As a high level language, it is pragmatic to allow you express something does not need to be always preserved in low level implementation, including variety of guarantees provided by the author of the code. Without such features it would be less worth using. And as a general purposed language, it can't be that "pure" to ensure everything would be checked by the implementation.
 

> The standard says that accessing an object after its lifetime has ended is undefined behavior. Because undefined behavior does not require a diagnostic, compilers are not required to detect that an object's lifetime has ended. They will simply access it as if it were live; whatever will be, will be.

That may be what they do now, but it is of vital importance what the standard declares as UB as compilers continue to take advantage of UB detection to treat code as unreachable.  As the theorem provers and whole-program optimization used by compilers get better, more and more UB will be found and (ab-)used, and suddenly my "working" code (because it relies on UB, as you say) causes demons to fly out of my nose.

What's wrong here? If you are going to use a language with UB (or some "unsafe" features) you will always have such risks.
 

[FrankHB1989]

在 2016年6月12日星期日 UTC+8上午7:29:46，Nicol Bolas写道：

On Saturday, June 11, 2016 at 4:35:28 PM UTC-4, Ryan Ingram wrote:

>> Can you educate me as to what we gain from having the compiler know that this object is alive?

> I don't understand what you're saying here.

I am asking what benefit actual programs/programmers get from not having a simple memory model, and a simple model of object lifetime that matches what implementations actually do.

You get to have classes that make sense. You get to have encapsulation of data structures and functional invariants. You get reasonable assurance that invariants established by the constructor or other functions cannot be broken by external code, unless the external code does something which provokes undefined behavior (like, say, memcpy-ing a non-trivially copyable class).

So what we get with these rules is the ability to live and function in a reasonably sane world. That's what the C++ memory model exists to create.

The world you seem to want to live in is C-with-classes.

As it is, the standard is extremely divergent from actual practice (c.f. "can't actually implement vector in C++") and therefore not useful.

The issue with `vector` has to do primarily with arrays, since they're kinda weird in C++. This is a defect because the standard is written contradictory: requiring something which cannot be implemented without provoking UB.

This is not enough to make it a defect. The standard library is not required to be implemented in C++. Language support libraries should have rights to rely on extra assumptions. Other components of the standard library may be implement solely based on the existed language rules, but this is also not mandated. In fact, it allows language extensions to be used, which may has "provoking UB". The problem is, it surprises you a lot to take care of the fact; it might be over-complicated and needs too much extra work on the standard itself. I don't think it is the case of something like vector.
 

[FrankHB1989]

在 2016年6月12日星期日 UTC+8上午7:29:46，Nicol Bolas写道：

A standard specifies behavior. It specifies what will happen if you do a particular thing. If the standard does not explicitly say what the results of something are, then those results are undefined by default.

 I doubt this is true in ISO C++.

A language standard, in general, gives you rules about compliance or conformance on implementations. Requirements on behavior of programs or program executions are not essential, but they make the rules easier to understand.

If something is not specified, that is underspecified. This is not necessary implying "undefined", since the meaning of "undefined" is also specified by some normative text elsewhere with clear definition. Sometimes rules may be missing, make the standard defective or even inconsistent. In such cases, they are also underspecified, but not undefined.

Your "by default" statement can be achieved by a rule in normative text, e.g. in ISO C:

4/2 If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears outside of a constraint or runtime constraint
is violated, the behavior is undefined. Undefined behavior is otherwise
indicated in this International Standard by the words ‘‘undefined behavior’’ or by the
omission of any explicit definition of behavior. There is no difference in emphasis among
these three; they all describe ‘‘behavior that is undefined’’.

(Emphasized mine.)

But I find no similar rules for the entire language in ISO C++.

[Jens Maurer]

On 06/14/2016 09:16 AM, FrankHB1989 wrote:
>
>
> 在 2016年6月12日星期日 UTC+8上午7:29:46，Nicol Bolas写道：
>
>
>

> A standard specifies behavior. It specifies what will happen if you do a particular thing. If the standard does not explicitly say what the results of something are, then those results are undefined /by default/.

>
> I doubt this is true in ISO C++.
>

> A language standard, in general, gives you rules about /compliance /or /conformance/ on implementations. Requirements on behavior of programs or program executions are not essential, but they make the rules easier to understand.
>
> If something is not specified, that is /underspecified/. This is not necessary implying "undefined", since the meaning of "undefined" is also specified by some normative text elsewhere with clear definition. Sometimes rules may be missing, make the standard defective or even inconsistent. In such cases, they are also underspecified, but not undefined.

>
> Your "by default" statement can be achieved by a rule in normative text, e.g. in ISO C:
>
> 4/2 If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears outside of a constraint or runtime constraint
> is violated, the behavior is undefined. Undefined behavior is otherwise

> indicated in this International Standard by the words ‘‘undefined behavior’’ or *by the
> omission of any explicit definition of behavior*. *There is no difference in emphasis among
> these three; they all describe ‘‘behavior that is undefined’’.*

>
> (Emphasized mine.)
>
> But I find no similar rules for the entire language in ISO C++.

See 1.3.25 with similar phrasing (although in a note) and 1.4 otherwise.

As an aside, I think it's a great advantage that C and C++ explicitly
specify "undefined behavior" in the standard, as opposed to relying on
the absence of specification. That avoids doubt whether the omission
of specification was intentional or not.

I believe CWG is, in general, amenable to extending the standard to say
"undefined behavior" in cases where an explicit specification is currently
missing; please point out the specific cases.

Jens

[FrankHB1989]

在 2016年6月14日星期二 UTC+8下午5:39:35，Jens Maurer写道：

On 06/14/2016 09:16 AM, FrankHB1989 wrote:
>
>
> 在 2016年6月12日星期日 UTC+8上午7:29:46，Nicol Bolas写道：
>
>
>
>     A standard specifies behavior. It specifies what will happen if you do a particular thing. If the standard does not explicitly say what the results of something are, then those results are undefined /by default/.
>
>  I doubt this is true in ISO C++.
>
> A language standard, in general, gives you rules about /compliance /or /conformance/ on implementations. Requirements on behavior of programs or program executions are not essential, but they make the rules easier to understand.
>
> If something is not specified, that is /underspecified/. This is not necessary implying "undefined", since the meaning of "undefined" is also specified by some normative text elsewhere with clear definition. Sometimes rules may be missing, make the standard defective or even inconsistent. In such cases, they are also underspecified, but not undefined.
>
> Your "by default" statement can be achieved by a rule in normative text, e.g. in ISO C:
>
> 4/2 If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears outside of a constraint or runtime constraint
> is violated, the behavior is undefined. Undefined behavior is otherwise
> indicated in this International Standard by the words ‘‘undefined behavior’’ or *by the
> omission of any explicit definition of behavior*. *There is no difference in emphasis among
> these three; they all describe ‘‘behavior that is undefined’’.*
>
> (Emphasized mine.)
>
> But I find no similar rules for the entire language in ISO C++.

See 1.3.25 with similar phrasing (although in a note) and 1.4 otherwise.

A note is informative. Though it provides one more way to figure out the extension of set of undefined behavior and it sounds intended, it has no force on conformance. Even interpreted normatively (which should not be the case of a note), with ISO terminology, "may" means "is allowed", but not "is"/"is required". This effectively allows readers to ignore it and to treat the omission of rules as a defect.

That's why I mention "in normative text".
 

As an aside, I think it's a great advantage that C and C++ explicitly
specify "undefined behavior" in the standard, as opposed to relying on
the absence of specification.  That avoids doubt whether the omission
of specification was intentional or not.

I agree. Practically, the ISO C rule make the standard harder to use.

Nevertheless, ISO C also has an informal annex listing undefined behavior overall to make life easier a little. As of ISO C++... well, perhaps the greatest problem is... lengthy, so the list of undefined behavior would be not so useful, also difficult to maintain.
 

[Mikhail Maltsev]

Actually the compiler converts memcpy into a function call or bytewise copy
fairly late, so most optimization passes have a chance to see it as an intrinsic
and convert into something better. Consider:

$ cat test.cc
#include <string.h>

int test(float x)
{
int dest;
memcpy(&dest, &x, 4);
return dest;
}

$ g++ -O -S -fdump-tree-ssa -fdump-tree-optimized test.cc

Here memcpy is actually treated as two operations (a load from memory into a
scalar variable and then a store):

;; Function int test(float) (_Z4testf, funcdef_no=14, decl_uid=2574,
cgraph_uid=14, symbol_order=14)

int test(float) (float x)
{
int dest;
unsigned int _2;
int _4;

<bb 2>:
_2 = MEM[(char * {ref-all})&x];
MEM[(char * {ref-all})&dest] = _2;
_4 = dest;
dest ={v} {CLOBBER};
return _4;

}

This pair is optimized into a cast:

;; Function int test(float) (_Z4testf, funcdef_no=14, decl_uid=2574,
cgraph_uid=14, symbol_order=14)

int test(float) (float x)
{
int dest;
unsigned int _2;

<bb 2>:
_2 = VIEW_CONVERT_EXPR<unsigned int>(x_3(D));
dest_4 = (int) _2;
return dest_4;

}

And compiled into a single instruction:

_Z4testf:
movd %xmm0, %eax
ret

--
Mikhail Maltsev

[Thiago Macieira]

On sexta-feira, 17 de junho de 2016 00:30:07 PDT Mikhail Maltsev wrote:
> Actually the compiler converts memcpy into a function call or bytewise copy
> fairly late, so most optimization passes have a chance to see it as an
> intrinsic and convert into something better

It's better than that. If you couple a memcpy with a __builtin_bswap32, the
compiler combines the multiple intrinsics into single instructions too.

In other words: don't be afraid of memcpy and do use it instead of abusing
type punning.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Language Lawyer]

четверг, 9 июня 2016 г., 23:05:43 UTC+3 пользователь Richard Smith написал:

You didn't specify how to implement the piece that's not implementable :-)

T *vector<T>::data() { return ??? }

vector<int> vi;

vi.push_back(1);

vi.push_back(2);

vi.push_back(3);

vi.data()[2] = 12; // ub, there is no array object on which to do array indexing

C++98's vector was fine, since it didn't pretend to expose an array to the user (there was no data(), iterators could be used to encapsulate the reinterpret_casts, and there was no contiguous iterator guarantee), but this has been unimplementable in the formal C++ object model since C++03 guaranteed that (&vi.begin())[2] should work.

Obviously it's actually fine in practice (and your implementation will certainly make sure it works), the question here is how to tweak the formal wording to give the guarantees we actually want. There are a number of different options with different tradeoffs (should we require explicit code in std::vector to create an array object? should we allow nontrivial pointer arithmetic / array indexing on pointers that don't point to arrays? should we magically conjure an array object into existence to make this work? should we allow an array object to be created without actually initializing all of its elements? how should the lifetime of an array object work anyway?). I'll probably write a paper on that once we're done with p0137.

std::less specialization for pointers guarantee a strict total order even if the built-in operator< does not.
Does it mean that using std::less for unrelated pointers causes UB because there is no mechanism in the core language which makes it possible to implement std::less?
Or implementation can use some implementation-defined magic mechanism to implement it?
If the later, why can't there be a magic mechanism to conjure an array object of size N from N sequentially stored objects?

[Bo Persson]

On most current systems std::less just uses operator< to compare the
pointers. No magic involved.

However, on systems with a segmented memory model std::less might have
to do a lot more work to normalize an address. For example in real mode
8086 the segment:offset pair used 16+16 bits but the physical address is
only 20 bits. And segments can overlap.

One way to make operator< work for array elements or struct members is
to limit their size to a single segment. Then you can just compare the
offsets. And so operator< would work.

> Or implementation can use some implementation-defined magic mechanism to
> implement it?

Of course, if needed.

> If the later, why can't there be a magic mechanism to conjure an array
> object of size N from N sequentially stored objects?
>

How did we get here?

One problem could be that N objects really are not sequential. For
example if an array is limited to a single segment and you have two
other variables in different segments, how would you combine those?


Bo Persson

[Language Lawyer]

Look. It is simple. We either:
1. Say that using the pointer we got from the std::vector<T>::data() to do the pointer arithmetic is UB, because there is no array object (because we know, that in all implementations elements are constructed one-by-one) and we has to fix the core language to allow this pointer arithmetic. But then it must be said that using std::less for unrelated pointers do not give strict total ordering, because it is not implementable in C++.
2. We give some guarantees in the standard library and event though it is not implementable in the core language, we imply that there are magic mechanisms in the implementations that make everything working as guaranteed without UB. And then there is no need to fix wording about pointer arithmetic to make std::vector implementable.

Either the core language should be fixed to make the whole standard library implementable in it (which means, among other things, it should be defined how to get a strict total order on all pointers) or we imply that there may be magic mechanisms in the implementations.
 

[Edward Catmur]

There is no problem with the standard library using magic. However, it would be preferable if the magic were exposed at a level that enables user components. 

So less<T*> being magic is not a problem, because it can just be a thin wrapper around any magic, and third party components are not disadvantaged by having to invoke that magic via std::less. But vector::data being magic is a problem, because then there is no way to write user contiguous containers without platform-specific code. 

One problem could be that N objects really are not sequential. For
example if an array is limited to a single segment and you have two
other variables in different segments, how would you combine those?


     Bo Persson

--

---
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-discussion/p4BXNhTHY7U/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-discussion+unsubscribe@isocpp.org.

[Bo Persson]

> Either the core language should be fixed to make *the whole* standard

> library implementable in it (which means, among other things, it should
> be defined how to get a strict total order on all pointers) or we imply
> that there may be magic mechanisms in the implementations.
>

There has always been magic in the standard library, ever since offsetof
was added to the C library. Not to talk about <type_traits>, which is
full of it.

I see no problem with std::less et al being similar (for implementations
that do seemingly odd things anyway).


Bo Persson

[Thiago Macieira]

On Friday, 23 February 2018 08:13:40 PST Bo Persson wrote:
> I see no problem with std::less et al being similar (for implementations
> that do seemingly odd things anyway).

Like Edward said, I don't see a problem for std::less to have magic. I do see
a problem for std::vector to do so, especially for handling the allocated
memory block as an array. There's just too much code out there that depends on
this functionality, so we need a solution in the core language.

[Language Lawyer]

Thank you for clarifying!
From Richard's and Jonathan's conversation I (mis?)understood that the committee was shocked by the fact that all code which uses a pointer from std::vector<T>::data() as a pointer to an array has UB. But actually this is not the case, because one may always use "it is magically working" as a last-resort argument.
Now I see that the real problem is that a user can't efficiently implement *her own* contiguous container.

[Todd Fleming]

Like http://wg21.link/p0593r2 ?

Todd

[Thiago Macieira]

On Friday, 23 February 2018 09:03:42 PST Todd Fleming wrote:
> On Friday, February 23, 2018 at 11:20:34 AM UTC-5, Thiago Macieira wrote:
> > On Friday, 23 February 2018 08:13:40 PST Bo Persson wrote:
> > > I see no problem with std::less et al being similar (for implementations
> > > that do seemingly odd things anyway).
> >
> > Like Edward said, I don't see a problem for std::less to have magic. I do
> > see
> > a problem for std::vector to do so, especially for handling the allocated
> > memory block as an array. There's just too much code out there that
> > depends on
> > this functionality, so we need a solution in the core language.
>

> Like http://wg21.link/p0593r2 ?

Yes. Primitives like std::bless and std::launder, even though the story is
getting really complex here, are acceptable magic.

[Ville Voutilainen]

On 23 February 2018 at 19:57, Thiago Macieira <thi...@macieira.org> wrote:
>> Like http://wg21.link/p0593r2 ?
>
> Yes. Primitives like std::bless and std::launder, even though the story is
> getting really complex here, are acceptable magic.

There's no non-magical way to implement those things; they are
communicating library intent to the compiler.

[Todd Fleming]

On Friday, February 23, 2018 at 12:58:04 PM UTC-5, Thiago Macieira wrote:

On Friday, 23 February 2018 09:03:42 PST Todd Fleming wrote:
> On Friday, February 23, 2018 at 11:20:34 AM UTC-5, Thiago Macieira wrote:
> > On Friday, 23 February 2018 08:13:40 PST Bo Persson wrote:
> > > I see no problem with std::less et al being similar (for implementations
> > > that do seemingly odd things anyway).
> >
> > Like Edward said, I don't see a problem for std::less to have magic. I do
> > see
> > a problem for std::vector to do so, especially for handling the allocated
> > memory block as an array. There's just too much code out there that
> > depends on
> > this functionality, so we need a solution in the core language.
>
> Like http://wg21.link/p0593r2 ?

Yes. Primitives like std::bless and std::launder, even though the story is
getting really complex here, are acceptable magic.

I hope std::bless doesn't become the training nightmare that std::launder is. I've seen too many postings where people either thought launder solved issues outside the one case it handles, or tried to use the original pointer instead of the one launder returns.

Todd

[Hyman Rosen]

On Fri, Feb 23, 2018 at 1:01 PM, Ville Voutilainen <ville.vo...@gmail.com> wrote:

There's no non-magical way to implement those things; they are
communicating library intent to the compiler.

Type-based alias analysis has led C and C++ down the garden path.

Pointer arithmetic within the bounds of an allocated memory segment
is only a problem because the language standards are distorted and
wrong due to optimisationist influence.

[Richard Hodges]

On Fri, 2018-02-23 at 13:07 -0500, Hyman Rosen wrote:

On Fri, Feb 23, 2018 at 1:01 PM, Ville Voutilainen <ville.vo...@gmail.com> wrote:

There's no non-magical way to implement those things; they are
communicating library intent to the compiler.

Type-based alias analysis has led C and C++ down the garden path.

I have some sympathy with this position. I am teaching c++ right now. The conversation often goes this way:

Q: "Is it true that [logically obvious thing is true because it's true on all current CPUs]

A: "Conceptually, according to the abstract c++ memory model, no. But in reality, yes. However, don't rely on it because the compiler is allowed to do a non-obvious thing in response."

Which seems to me to break the "make easy things easy" paradigm.

The inability to compare two addresses of two discrete objects is down to only one thing: The anachronistic and now utterly irrelevant segmented memory architecture of the 8086.

The 8086 was a special case, a candidate for an implementation-defined extension (e.g. FAR), not a sensible cornerstone around which to build a standard. 

The c++ standard should no longer take the 8086 into account. Doing so simply makes c++ harder to learn and easier to get wrong for absolutely zero benefit.

Once upon a time, address lines were expensive. Now they're basically free. It's time to move on.

Pointer arithmetic within the bounds of an allocated memory segment
is only a problem because the language standards are distorted and
wrong due to optimisationist influence.

--

---

You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.

[Language Lawyer]

On Thursday, June 9, 2016 at 11:05:43 PM UTC+3, Richard Smith wrote:

On Wed, Jun 8, 2016 at 11:08 PM, Ryan Ingram <ryani...@gmail.com> wrote:

> (With either the new or the existing wording around "object", it's not
clear that std::vector can actually be implemented in C++.  This seems
a sub-optimal state of affairs.)

Hmm, perhaps I don't understand the memory model then.  My usual understanding of how an implementation of vector<> would work in "strict" C++ is something along these lines (ignoring exception safety for the time being, and only showing a couple of the required methods):

template <typename T>

class vector {

    char* mBegin; // allocated with new char[]

    char* mEnd;   // pointer within mBegin array or one-off end

    char* mCapacity; // pointer one off end of mBegin array

public: // methods

};

T& vector<T>::operator[] (int index)

{

    return *reinterpret_cast<T*>(mBegin + index * sizeof(T));

}

void vector<T>::push_back(const T& elem)

{

    if(mEnd == mCapacity) Grow();

    new(mEnd) T(elem);

    mEnd += sizeof(T);

}

void vector<T>::Grow() // private

{

    int nElems = (mCapacity - mBegin) / sizeof(T);

    nElems *= 2;

    if( nElems < 1 ) nElems = 1;

    char* newBegin = new char[ nElems * sizeof(T) ];

    char* oldCur = mBegin;

    char* newCur = newBegin;

    for(; oldCur < mEnd; oldCur += sizeof(T), newCur += sizeof(T)) {

        new(newCur) T(*reinterpet_cast<T*>(oldCur));

        reinterpret_cast<T*>(oldCur)->~T();

    }

    int size = mEnd - mBegin;

    delete [] mBegin;

    mBegin = newBegin;

    mEnd = mBegin + size;

    mCapacity = mBegin + (nElems * sizeof(T));

}

Which part of this is undefined according to the standard?

You didn't specify how to implement the piece that's not implementable :-)

T *vector<T>::data() { return ??? } 

BTW, is operator[] implementable?
I'll ask more specifically: what allows one to reinterpret_cast a pointer to storage into pointer to object stored there (reinterpret_cast<T*>(mBegin + index * sizeof(T)))?
I've thought it is related to whether the pointers are pointer-interconvertible (http://eel.is/c++draft/basic.compound#def:pointer-interconvertible ), but the rules there don't seem to allow such a cast.

[Myriachan]

The reinterpret_cast is not the problem.  It's legal because you're reinterpret_casting to a pointer type matching the dynamic type of the object--namely T.  What makes std::vector unimplementable is the pointer arithmetic, most obviously with std::vector<T>::data().

alignas(int) std::byte storage[sizeof(int) * 3];
int *p = new(&storage[sizeof(int) * 0]) int{ 1 };
new(&storage[sizeof(int) * 1]) int{ 2 };
new(&storage[sizeof(int) * 2]) int{ 3 };
assert(*(p + 2) == 3); // undefined behavior

What's undefined behavior is the addition of 2 to p.  A singular object is considered an array of size 1 for pointer arithmetic purposes.  Pointer arithmetic is only defined if the value that you're adding is such that the pointer remains within the array.  It is completely irrelevant to the current text of the Standard that the object immediately after is of the same dynamic type.

Because std::vector is required to support emplace_back/push_back in such a way that iterators and pointers are not invalidated unless the backing store needs to be grown, std::vector by necessity must construct individual objects into storage much like the example I gave.  So the following is equivalent to my example:

std::vector<int> v;
v.reserve(3);
v.emplace_back(1);
int *p = v.data();
v.emplace_back(2);
v.emplace_back(3);
assert(*(p + 2) == 3); // undefined behavior???

It is impossible to implement std::vector in such a way that the above is well-defined and while still meeting the other requirements of std::vector.  Therefore, std::vector is necessarily a magic class, like, say, std::initializer_list.

This state of affairs is clearly broken, and there has been at least one proposal to fix the Standard in this regard, one by Richard Smith.

Melissa

[Edward Catmur]

On Mon, Mar 5, 2018 at 8:37 PM, Myriachan <myri...@gmail.com> wrote:

On Saturday, March 3, 2018 at 6:34:54 AM UTC-8, Language Lawyer wrote:

On Thursday, June 9, 2016 at 11:05:43 PM UTC+3, Richard Smith wrote:

You didn't specify how to implement the piece that's not implementable :-)

T *vector<T>::data() { return ??? } 

BTW, is operator[] implementable?
I'll ask more specifically: what allows one to reinterpret_cast a pointer to storage into pointer to object stored there (reinterpret_cast<T*>(mBegin + index * sizeof(T)))?
I've thought it is related to whether the pointers are pointer-interconvertible (http://eel.is/c++draft/basic.compound#def:pointer-interconvertible ), but the rules there don't seem to allow such a cast.

The reinterpret_cast is not the problem.  It's legal because you're reinterpret_casting to a pointer type matching the dynamic type of the object--namely T.  What makes std::vector unimplementable is the pointer arithmetic, most obviously with std::vector<T>::data().

Unfortunately this isn't quite correct; the reinterpret_cast is insufficient. It is necessary to use launder [ptr.launder] to convert a T* pointer representing the address of a memory location to a pointer to a T object located at that address and pointer-interconvertible (as Language Lawyer mentions) with the T* pointer. launder is suitable for use by (e.g.) optional (an alternative is to use a union with a unit type), but as you correctly note below it is insufficient for the purposes of vector::data() returning a pointer that can be the operand of a non-trivial arithmetic expression.

alignas(int) std::byte storage[sizeof(int) * 3];
int *p = new(&storage[sizeof(int) * 0]) int{ 1 };
new(&storage[sizeof(int) * 1]) int{ 2 };
new(&storage[sizeof(int) * 2]) int{ 3 };
assert(*(p + 2) == 3); // undefined behavior

What's undefined behavior is the addition of 2 to p.  A singular object is considered an array of size 1 for pointer arithmetic purposes.  Pointer arithmetic is only defined if the value that you're adding is such that the pointer remains within the array.  It is completely irrelevant to the current text of the Standard that the object immediately after is of the same dynamic type.

Because std::vector is required to support emplace_back/push_back in such a way that iterators and pointers are not invalidated unless the backing store needs to be grown, std::vector by necessity must construct individual objects into storage much like the example I gave.  So the following is equivalent to my example:

std::vector<int> v;
v.reserve(3);
v.emplace_back(1);
int *p = v.data();
v.emplace_back(2);
v.emplace_back(3);
assert(*(p + 2) == 3); // undefined behavior???

It is impossible to implement std::vector in such a way that the above is well-defined and while still meeting the other requirements of std::vector.  Therefore, std::vector is necessarily a magic class, like, say, std::initializer_list.

This state of affairs is clearly broken, and there has been at least one proposal to fix the Standard in this regard, one by Richard Smith.

Melissa

--

---

You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-discussion/p4BXNhTHY7U/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-discussion+unsubscribe@isocpp.org.

[Myriachan]

On Monday, March 5, 2018 at 3:34:31 PM UTC-8, Edward Catmur wrote:

On Mon, Mar 5, 2018 at 8:37 PM, Myriachan <myri...@gmail.com> wrote:

On Saturday, March 3, 2018 at 6:34:54 AM UTC-8, Language Lawyer wrote:

On Thursday, June 9, 2016 at 11:05:43 PM UTC+3, Richard Smith wrote:

You didn't specify how to implement the piece that's not implementable :-)

T *vector<T>::data() { return ??? } 

BTW, is operator[] implementable?
I'll ask more specifically: what allows one to reinterpret_cast a pointer to storage into pointer to object stored there (reinterpret_cast<T*>(mBegin + index * sizeof(T)))?
I've thought it is related to whether the pointers are pointer-interconvertible (http://eel.is/c++draft/basic.compound#def:pointer-interconvertible ), but the rules there don't seem to allow such a cast.

The reinterpret_cast is not the problem.  It's legal because you're reinterpret_casting to a pointer type matching the dynamic type of the object--namely T.  What makes std::vector unimplementable is the pointer arithmetic, most obviously with std::vector<T>::data().

Unfortunately this isn't quite correct; the reinterpret_cast is insufficient. It is necessary to use launder [ptr.launder] to convert a T* pointer representing the address of a memory location to a pointer to a T object located at that address and pointer-interconvertible (as Language Lawyer mentions) with the T* pointer. launder is suitable for use by (e.g.) optional (an alternative is to use a union with a unit type), but as you correctly note below it is insufficient for the purposes of vector::data() returning a pointer that can be the operand of a non-trivial arithmetic expression.

Then the Standard is even more broken than I imagined.

This lifetime stuff needs to be cleaned up, because the percentage of large C++ programs that do this properly approaches zero.  Instead, all the proposals I've seen about this are about making the problems worse.

Melissa

[Thiago Macieira]

On Tuesday, 6 March 2018 12:43:24 PST Myriachan wrote:
> This lifetime stuff needs to be cleaned up, because the percentage of large
> C++ programs that do this properly approaches zero. Instead, all the
> proposals I've seen about this are about making the problems worse.

It might be a strict zero because there's no way to do it properly.