Uzytkownik "Seungbeom Kim" <musiphil@bawi.org> napisal w wiadomosci
news:ejeohj$8b4$1@news.Stanford.EDU...
> You can think of a new analogy where you're driving, your secretary
> robot is the passenger crossing the road, and you're doomed if you hit
> your robot you depend on. It can serve you better by doing more useful
> things without worrying about being hit by cars. Hence a contract (or a
> specification) which says: "I promise I'll never hit you, so don't worry
> and do more useful things." If it keeps being distracted to avoid being
> hit and gets less productive even if you told it so, then you won't like
> it, will you? :)
>

It depends on its purpose and its computing power.
If my secretary robot gets smashed by a car in the street, I can get a new
one;
I can even have a spare one just in case.
But if I send it to the orbit and it gets smashed by orbital junk, I am out
of luck.
And the other situation is more typical for an optimized release build.
I would like it to do useful things and avoid doing harmful things or
getting hurt at the same time.
Those things happen: my car beeps when it approaches an object while driving
backwards
or if I leave the lights on
- and your car is probably much better then mine.  It is called progress in
technology.
And this particular requirement does not seem particularly expensive to
respect.
Today's news in Poland is that we may run out of electricity in 15 years;
I could perhaps change my mind then :-)
Chris


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
news:1162993773.264975.307170@e3g2000cwe.googlegroups.com...
> "Kristof Zelechovski" wrote:
>> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
>> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
>> > 2. A different issue is far more relevant to the ordinary programmer.
>> > Because the behavior of dereferencing an out-of-bounds pointer is
>> > undefined, an implementation is allowed to make optimizations based
>> > upon the assumption that no such dereferences will occur. For instance,
>> > taking the example code you've given, an implementation isn't required
>> > to consider the possibility that arr[0][3] might refer to the same
>> > object as arr[1][0]. Therefore, if you write something like the
>> > following:
>
>> > arr[0][3] = 3;
>> > arr[1][0] = 2;
>> > arr[0][3]++;
>
>> > It's allowed to translate that C code into machine code which places 3
>> > in a register, stores a 2 in the location referred to by arr[1][0],
>> > increments the register, giving it a value of 4, and then places the
>> > value of that register in the location referred to by arr[0][3].
>
>> I think the optimizer should operate on object code;
>
> That doesn't necessarily make sense.  It depends on the type of
> optimization.  And what is "object code", anyway; none of the
> really good optimizers use what would classically have been
> considered "object code".
>
>> it might take the source code as a hint about the programmer's intention
>> but all assumptions based on source code analysis should be validated
>> against object code.
>
> I'm not sure what your point is.  The object code depends on the
> source code AND the aleas of how the unoptimized translator
> works.  You certainly don't want the optimizer to be restricted
> by such aleas.
>

Yes and no.
While it would be difficult for the low-level optimizer e.g. to eliminate
copy constructors as required,
it is not entirely impossible.
My optimizer replaces strlen(s) with an immediate value
where extern char const s[] is defined in another object file.
If I implemented an algorithm
to output the 10,000th digit of the decimal expansion of the perimeter of a
circle,
I can imagine the object code would contain that particular digit as an
immediate constant.
It works as if by simulating the execution of the programme that does not
depend on external data.
It can reason about object code and create various shortcuts based on the
code it sees.

>> An optimizer that fails to do this is dumb and would do more
>> harm than good.
>
> Then I guess all effective optimizers are dumb, and do more harm
> than good.  But I fail to see the problem; the object code is
> one particular translators interpretation of the source,
> generally with much information lost, but also with much added.
> It doesn't make sense for the optimizer to be forced to ignore
> information provided by the original program, but to take into
> account information added by the original translator.
>


If you think reasoning about object code only is infeasible or impossible,
which may indeed be the case when eliminating copy constructors with side
effects,
which is an insane practice by itself introduced to make up for a weakness
in the language,
the compiler can leave hints in object code in form "consider this
optimization here".
The optimizer sees the ultimate machine code
and it is in position to validate whether implementing this hint breaks
anything or not.

>> In this particular case, arr[0][3] and arr[1][0] denote the
>> same physical location and would be replaced with the same
>> memory reference in object code and thus the optimizer will
>> know that both assignments can be eliminated and the
>> incrementation can be replaced with an assignment.
>
> In this particular case, the compiler will know that arr[0][3]
> is an illegal access, and won't necessarily generate any code
> for it.  It will certainly know that arr[0][3] and arr[1][0] are
> not the same cell.  Whether this information propagates down to
> the object level or not depends on the original translator and
> the object format; I've seen examples of both.

Oh my goodness.  But it was probably Mr Kuyper's mistake, or there is indeed
no reason to worry about.
The OP would have used arr[0][3] and arr[1][1] of course.

Chris


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

James Kanze wrote:
> "Kristof Zelechovski" wrote:
> > Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
> > news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> > > 2. A different issue is far more relevant to the ordinary programmer.
> > > Because the behavior of dereferencing an out-of-bounds pointer is
> > > undefined, an implementation is allowed to make optimizations based
> > > upon the assumption that no such dereferences will occur. For instance,
> > > taking the example code you've given, an implementation isn't required
> > > to consider the possibility that arr[0][3] might refer to the same
> > > object as arr[1][0]. Therefore, if you write something like the
> > > following:
>
> > > arr[0][3] = 3;
> > > arr[1][0] = 2;
> > > arr[0][3]++;
>
> > > It's allowed to translate that C code into machine code which places 3
> > > in a register, stores a 2 in the location referred to by arr[1][0],
> > > increments the register, giving it a value of 4, and then places the
> > > value of that register in the location referred to by arr[0][3].
.
> > In this particular case, arr[0][3] and arr[1][0] denote the
> > same physical location and would be replaced with the same
> > memory reference in object code and thus the optimizer will
> > know that both assignments can be eliminated and the
> > incrementation can be replaced with an assignment.
>
> In this particular case, the compiler will know that arr[0][3]
> is an illegal access, and won't necessarily generate any code
> for it.  ...

While it is perfectly feasible for the compiler to determine that
arr[0][3] is an illegal access, the fact that the access has undefined
behavior means that the implementation isn't required to make that
determination. It's just a matter of QoI whether or not it bothers to
do so.


> ... It will certainly know that arr[0][3] and arr[1][0] are
> not the same cell.

As Kristof has pointed out, that was a mistake on my part. arr[1][0]
should have been arr[1][1]. It was my intention to provide an example
where they do in fact refer to same cell. Of course, as far as the
standard is concerned, it isn't meaningful to talk about what arr[0][3]
refers to, since any use of that reference has undefined behavior.
However, I'm talking about what it refers to in terms of conventional
expectations about the form of that undefined behavior.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Kristof Zelechovski" wrote:
> Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
> news:1162993773.264975.307170@e3g2000cwe.googlegroups.com...
> > "Kristof Zelechovski" wrote:
> >> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
> >> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> >> > 2. A different issue is far more relevant to the ordinary programmer.
> >> > Because the behavior of dereferencing an out-of-bounds pointer is
> >> > undefined, an implementation is allowed to make optimizations based
> >> > upon the assumption that no such dereferences will occur. For instance,
> >> > taking the example code you've given, an implementation isn't required
> >> > to consider the possibility that arr[0][3] might refer to the same
> >> > object as arr[1][0]. Therefore, if you write something like the
> >> > following:
> >
> >> > arr[0][3] = 3;
> >> > arr[1][0] = 2;
> >> > arr[0][3]++;
> >
> >> > It's allowed to translate that C code into machine code which places 3
> >> > in a register, stores a 2 in the location referred to by arr[1][0],
> >> > increments the register, giving it a value of 4, and then places the
> >> > value of that register in the location referred to by arr[0][3].
.
> >> In this particular case, arr[0][3] and arr[1][0] denote the
> >> same physical location and would be replaced with the same
> >> memory reference in object code and thus the optimizer will
> >> know that both assignments can be eliminated and the
> >> incrementation can be replaced with an assignment.
> >
> > In this particular case, the compiler will know that arr[0][3]
> > is an illegal access, and won't necessarily generate any code
> > for it.  It will certainly know that arr[0][3] and arr[1][0] are
> > not the same cell.  Whether this information propagates down to
> > the object level or not depends on the original translator and
> > the object format; I've seen examples of both.
>
> Oh my goodness.  But it was probably Mr Kuyper's mistake, or there is indeed
> no reason to worry about.
> The OP would have used arr[0][3] and arr[1][1] of course.

You're correct - apparantly I was thinking of a 3x3 array rather than
the 2x2 array that was declared in Frederick Gotham's original code.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kuyper@wizard.net wrote:
> James Kanze wrote:
> > "Kristof Zelechovski" wrote:
> > > In this particular case, arr[0][3] and arr[1][0] denote the
> > > same physical location and would be replaced with the same
> > > memory reference in object code and thus the optimizer will
> > > know that both assignments can be eliminated and the
> > > incrementation can be replaced with an assignment.

> > In this particular case, the compiler will know that arr[0][3]
> > is an illegal access, and won't necessarily generate any code
> > for it.  ...

> While it is perfectly feasible for the compiler to determine that
> arr[0][3] is an illegal access, the fact that the access has undefined
> behavior means that the implementation isn't required to make that
> determination.

No.  On the other hand, it is free to assume that arr[0][i] and
arr[1][j] never refer to the same memory location, and optimize
in consequence.  For example, if I write:

    arr[0][i] = 0 ;
    arr[1][j] = 1 ;
    if ( arr[0][i] != 0 ) ...

a good compiler will suppress the test, and delete the block of
code in the if on the grounds that it is unreachable.

Note that this is far from a theoretical concern.  I've used
compilers which regularly reordered indepentant writes.  And
which definitly considered writes to arr[0][i] and arr[1][j] as
independant, without trying to deduce anything about i or j.
Thus, if I wrote:

    arr[0][i] = 0 ;
    arr[1][j] = 1 ;

the compiler might actually generate code in which the 1 was
written before the 0.

(Microsoft C, version 1.0, did this, for example.)

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Kristof Zelechovski" wrote:
> Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
> news:1162993773.264975.307170@e3g2000cwe.googlegroups.com...
> > "Kristof Zelechovski" wrote:
> >> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
> >> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> >> > 2. A different issue is far more relevant to the ordinary programmer.
> >> > Because the behavior of dereferencing an out-of-bounds pointer is
> >> > undefined, an implementation is allowed to make optimizations based
> >> > upon the assumption that no such dereferences will occur. For instance,
> >> > taking the example code you've given, an implementation isn't required
> >> > to consider the possibility that arr[0][3] might refer to the same
> >> > object as arr[1][0]. Therefore, if you write something like the
> >> > following:

> >> > arr[0][3] = 3;
> >> > arr[1][0] = 2;
> >> > arr[0][3]++;

> >> > It's allowed to translate that C code into machine code which places 3
> >> > in a register, stores a 2 in the location referred to by arr[1][0],
> >> > increments the register, giving it a value of 4, and then places the
> >> > value of that register in the location referred to by arr[0][3].

> >> I think the optimizer should operate on object code;

> > That doesn't necessarily make sense.  It depends on the type of
> > optimization.  And what is "object code", anyway; none of the
> > really good optimizers use what would classically have been
> > considered "object code".

> >> it might take the source code as a hint about the programmer's intention
> >> but all assumptions based on source code analysis should be validated
> >> against object code.

> > I'm not sure what your point is.  The object code depends on the
> > source code AND the aleas of how the unoptimized translator
> > works.  You certainly don't want the optimizer to be restricted
> > by such aleas.

> Yes and no.  While it would be difficult for the low-level
> optimizer e.g. to eliminate copy constructors as required, it
> is not entirely impossible.  My optimizer replaces strlen(s)
> with an immediate value where extern char const s[] is defined
> in another object file.

And it likely does so because it knows the semantics of strlen,
rather than deducing them from object code.  (I don't know which
optimizer you are talking about, but the ones I've seen often
had built-in knowledge of the standard functions.  If a compiler
supports multi-threading, this is almost a requirement, since it
has to know which functions impose memory synchronization, and
which don't.)

> If I implemented an algorithm to output the 10,000th digit of
> the decimal expansion of the perimeter of a circle, I can
> imagine the object code would contain that particular digit as
> an immediate constant.  It works as if by simulating the
> execution of the programme that does not depend on external
> data.  It can reason about object code and create various
> shortcuts based on the code it sees.

But I'd be surprised if it did.  It's a lot of work to throw out
important information, and then reconstruct it from the object
code.  In some cases, it's impossible.

And of course, there are cases where the object code adds
information.  Once you've got object code, for example, the
order of evaluation is fixed.

> >> An optimizer that fails to do this is dumb and would do more
> >> harm than good.

> > Then I guess all effective optimizers are dumb, and do more harm
> > than good.  But I fail to see the problem; the object code is
> > one particular translators interpretation of the source,
> > generally with much information lost, but also with much added.
> > It doesn't make sense for the optimizer to be forced to ignore
> > information provided by the original program, but to take into
> > account information added by the original translator.

> If you think reasoning about object code only is infeasible or
> impossible, which may indeed be the case when eliminating copy
> constructors with side effects, which is an insane practice by
> itself introduced to make up for a weakness in the language,
> the compiler can leave hints in object code in form "consider
> this optimization here".

That's often exactly what occurs.  Except that the code doesn't
look much like what you'd traditionally consider object code.

> The optimizer sees the ultimate machine code and it is in
> position to validate whether implementing this hint breaks
> anything or not.

Most modern optimizers work on an intermediate representation,
still quite far from the final machine code.  In particular, I
think there are definite advantages in doing register
allocation AFTER optimization.

> >> In this particular case, arr[0][3] and arr[1][0] denote the
> >> same physical location and would be replaced with the same
> >> memory reference in object code and thus the optimizer will
> >> know that both assignments can be eliminated and the
> >> incrementation can be replaced with an assignment.

> > In this particular case, the compiler will know that arr[0][3]
> > is an illegal access, and won't necessarily generate any code
> > for it.  It will certainly know that arr[0][3] and arr[1][0] are
> > not the same cell.  Whether this information propagates down to
> > the object level or not depends on the original translator and
> > the object format; I've seen examples of both.

> Oh my goodness.  But it was probably Mr Kuyper's mistake, or
> there is indeed no reason to worry about.  The OP would have
> used arr[0][3] and arr[1][1] of course.

which doesn't change much.  The point is that the compiler knows
that these two expressions cannot legally refer to the same
cell, and can optimize in consequence.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
news:1163499235.928717.308990@b28g2000cwb.googlegroups.com...
> "Kristof Zelechovski" wrote:
>> Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
>> news:1162993773.264975.307170@e3g2000cwe.googlegroups.com...
>> > "Kristof Zelechovski" wrote:
>> >> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
>> >> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
>> >> > 2. A different issue is far more relevant to the ordinary
>> >> > programmer.
>> >> > Because the behavior of dereferencing an out-of-bounds pointer is
>> >> > undefined, an implementation is allowed to make optimizations based
>> >> > upon the assumption that no such dereferences will occur. For
>> >> > instance,
>> >> > taking the example code you've given, an implementation isn't
>> >> > required
>> >> > to consider the possibility that arr[0][3] might refer to the same
>> >> > object as arr[1][0]. Therefore, if you write something like the
>> >> > following:
>
>> >> > arr[0][3] = 3;
>> >> > arr[1][0] = 2;
>> >> > arr[0][3]++;
>
>> >> > It's allowed to translate that C code into machine code which places
>> >> > 3
>> >> > in a register, stores a 2 in the location referred to by arr[1][0],
>> >> > increments the register, giving it a value of 4, and then places the
>> >> > value of that register in the location referred to by arr[0][3].
>
>> Oh my goodness.  But it was probably Mr Kuyper's mistake, or
>> there is indeed no reason to worry about.  The OP would have
>> used arr[0][3] and arr[1][1] of course.
>
> which doesn't change much.  The point is that the compiler knows
> that these two expressions cannot legally refer to the same
> cell, and can optimize in consequence.

These two expressions refer to the same cell and the optimizer knows that.
Imagine you see a car that is going to hit you while you cross the road
while the passage is open.
What do you do?
You think "Well, that car cannot legally approach me now."
And you go on as if the car were waiting as it should be  :-)
Chris


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Kristof Zelechovski wrote:
> Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
> news:1163499235.928717.308990@b28g2000cwb.googlegroups.com...
> > "Kristof Zelechovski" wrote:
> >> Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
> >> news:1162993773.264975.307170@e3g2000cwe.googlegroups.com...
> >> > "Kristof Zelechovski" wrote:
> >> >> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
> >> >> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> >> >> > 2. A different issue is far more relevant to the ordinary
> >> >> > programmer.
> >> >> > Because the behavior of dereferencing an out-of-bounds pointer is
> >> >> > undefined, an implementation is allowed to make optimizations based
> >> >> > upon the assumption that no such dereferences will occur. For
> >> >> > instance,
> >> >> > taking the example code you've given, an implementation isn't
> >> >> > required
> >> >> > to consider the possibility that arr[0][3] might refer to the same
> >> >> > object as arr[1][0]. Therefore, if you write something like the
> >> >> > following:

> >> >> > arr[0][3] = 3;
> >> >> > arr[1][0] = 2;
> >> >> > arr[0][3]++;

> >> >> > It's allowed to translate that C code into machine
> >> >> > code which places 3 in a register, stores a 2 in the
> >> >> > location referred to by arr[1][0], increments the
> >> >> > register, giving it a value of 4, and then places the
> >> >> > value of that register in the location referred to by
> >> >> > arr[0][3].

> >> Oh my goodness.  But it was probably Mr Kuyper's mistake, or
> >> there is indeed no reason to worry about.  The OP would have
> >> used arr[0][3] and arr[1][1] of course.

> > which doesn't change much.  The point is that the compiler knows
> > that these two expressions cannot legally refer to the same
> > cell, and can optimize in consequence.

> These two expressions refer to the same cell and the optimizer
> knows that.

Except that the standard says that they cannot refer to the same
cell, which is what the optimizer knows to begin with.

> Imagine you see a car that is going to hit you while you cross the road
> while the passage is open.
> What do you do?
> You think "Well, that car cannot legally approach me now."
> And you go on as if the car were waiting as it should be  :-)

The situation isn't the same.  Generating wrong code for an
incorrect program doesn't do any harm to the optimizer.  The
optimizer is more in the situation of a driver who sees you
about to cross the road illegally---if he hits you, it's not his
fault, so who cares.  (You do, of course, but that's your tough
luck.)  The moral is, of course, not to cross the road
illegally (and to be careful even when you can do it legally).

In practice, of course, the authors of the optimizer would
prefer not hitting you, even if you are technically doing
something illegal.  However, they are also under great presure
to generate the fastest code possible, in the least time.  And
the C++ rules introduce a lot of undefined behavior (too much,
IMHO) just to make it easier for them to do so.  Given this, it
is common practice for compilers to exploit such rules to the
maximum.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

John Nagle wrote:
> James Kanze wrote:

> >>Only for POD types. (Alas!) What for non-POD types?
>
>     Use a loop and let the compiler optimize.
>
>     I previously submitted a long reply on this subject, detailing
> how modern optimizing compilers do better than "memcpy" on this,

some modern compilers understand memcpy, and know how to optimize it
(gcc -O3)

#include <cstring>
void  foo(unsigned char* a, unsigned char* b)
{
  std::memcpy(b, a, 8);
}

void  bar(unsigned char* a, unsigned char* b)
{
  for(unsigned int i=0; i < 8; i++)
    *a++ = *b++;
}

The resulting assembly is:

_Z3fooPhS_:
.LFB7:
 pushl %ebp
.LCFI2:
 movl %esp, %ebp
.LCFI3:
 movl 8(%ebp), %edx
 movl 12(%ebp), %ecx
 movl (%edx), %eax
 movl %eax, (%ecx)
 movl 4(%edx), %eax
 movl %eax, 4(%ecx)
 popl %ebp
 ret

_Z3barPhS_:
.LFB8:
 pushl %ebp
.LCFI0:
 movl %esp, %ebp
.LCFI1:
 movl 12(%ebp), %edx
 movl 8(%ebp), %ecx
 movzbl (%edx), %eax
 movb %al, (%ecx)
 movzbl 1(%edx), %eax
 movb %al, 1(%ecx)
 movzbl 2(%edx), %eax
 movb %al, 2(%ecx)
 movzbl 3(%edx), %eax
 movb %al, 3(%ecx)
 movzbl 4(%edx), %eax
 movb %al, 4(%ecx)
 movzbl 5(%edx), %eax
 movb %al, 5(%ecx)
 movzbl 6(%edx), %eax
 movb %al, 6(%ecx)
 movzbl 7(%edx), %eax
 movb %al, 7(%ecx)
 popl %ebp
 ret

The memcpy version is 4x shorter. The compiler understands memcpy as
well as it can understand anything else, except that using memcpy tells
the compiler what you want, not how to do it. That makes it easier to
optimize (it can choose how to do what you want).

-Ed

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Kristof Zelechovski wrote:
> Uzytkownik "James Kanze" <james.kanze@gmail.com> napisal w wiadomosci
> news:1163499235.928717.308990@b28g2000cwb.googlegroups.com...
>> "Kristof Zelechovski" wrote:
>>> Oh my goodness.  But it was probably Mr Kuyper's mistake, or
>>> there is indeed no reason to worry about.  The OP would have
>>> used arr[0][3] and arr[1][1] of course.
>> which doesn't change much.  The point is that the compiler knows
>> that these two expressions cannot legally refer to the same
>> cell, and can optimize in consequence.
>
> These two expressions refer to the same cell and the optimizer knows that.

They're not supposed to, which is the whole point here.
Therefore the optimizer can assume they don't.

> Imagine you see a car that is going to hit you while you cross the road
> while the passage is open.
> What do you do?
> You think "Well, that car cannot legally approach me now."
> And you go on as if the car were waiting as it should be  :-)

And by doing so, you don't have to worry about being hit by the car and
can concentrate more on other things while you're crossing the road.

The standard is a contract between implementations and source codes.
Your analogy is broken because: an implementation doesn't have to
"defend itself" from possible misbehaviours of a source code, whereas
it's the source code that depends on the implementation to achieve its
purpose and that fails if it breaks the contract.

You can think of a new analogy where you're driving, your secretary
robot is the passenger crossing the road, and you're doomed if you hit
your robot you depend on. It can serve you better by doing more useful
things without worrying about being hit by cars. Hence a contract (or a
specification) which says: "I promise I'll never hit you, so don't worry
and do more useful things." If it keeps being distracted to avoid being
hit and gets less productive even if you told it so, then you won't like
it, will you? :)

--
Seungbeom Kim

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

James Kanze wrote:
> Seungbeom Kim wrote:
>> kuyper@wizard.net wrote:
>>> Kristof Zelechovski wrote:
>
>>>> Now this is too bad.  How do you copy a multidimensional array?

And it came to my mind later that we also need a simple method to fill a
multi-dimensional array with a value, as we do

    std::fill(array.begin(), array.end(), init_value);

for a single-dimensional array.
Even memset() is not an option even for POD types, because we don't know
the internal representation of the types.

>>> For POD types, memcpy() will do the job pretty efficiently, and just
>>> about as simply as std::copy().
>
>> Only for POD types. (Alas!) What for non-POD types?
>
>> I don't agree with Frederick that the current rules are nonsense,
>> but I do want to see that we have a simple and efficient way to
>> copy a multi-dimensional array of any type.
>
>> Or.. should we advised to just wrap the array in a struct?
>
> That's probably the best solution.
>
> The real problem, of course, is that C style arrays are
> irremedially broken; as a type, they are discriminated against,
> and don't have the full rights that other types do.

Oh, I see. That's too bad.

>> Or to just stay away from built-in arrays? (But often, using
>> std::vector for a multi-dimensional array is too cumbersome.)
>
> Agreed.  In practice, I'd almost always write some sort of class
> to handle the issue.  (Or maybe valarray is already a sufficient
> solution---I'm not familiar enough with it to judge.)
>
> When you say that std::vector is too cumbersome, do you mean the
> declaration syntax, or the machinery it puts into work each
> time.

I once had to write a declaration like this:

    std::vector< std::vector< std::vector<constr_info_t> > >
        constr_info(
            table_.height(),
            std::vector< std::vector<constr_info_t> >(
                table_.width(),
                std::vector<constr_info_t>(2)
            )
        );

Isn't this ugly?
The length of the declaration is roughly quadratic in the dimension.
And constr_info_t could just have been a local type or even an anonymous
struct, but I had to name it so and place it outside the only function
that needed it so that the name could have external linkage.
I can almost never suggest this as an answer to a FAQ item "How do I
declare a multi-dimensional array?" for novices. (And there seems to be
none yet. Oh.)

If I were to use the variable-length array in C99, I could just write:

    constr_info_t constr_info[table_.height()][table_.width()][2];

which is so simple and elegant.

> For the first, I haven't a solution, but for the second,
> boost::array should do the trick well in a lot of cases:
>     boost::array< boost::array< double, 20 >, 10 >
>                         array2d ;
> should result in almost the same code as:
>     double              array2d[ 10 ][ 20 ] ;
> (But the declaration syntax is still a pain.)

The policy didn't allow me to use a third-party library, and even if it
had, I guess boost::array wouldn't have helped me much because the
dimensions were not compile-time constants. Maybe boost::multi_array
could have helped me (with even more weird syntax that I have to figure
out each time I try to use it).


I like the general idea of providing the necessary infrastructure
(classes, templates, etc.) to build the library that solves a problem,
as opposed to providing the direct solution in the language level (e.g.
std::vector in C++ vs VLA in C99, std::complex in C++ vs _Complex in
C99, and so on). However, I sometimes wonder: wouldn't it have been nice
if C++ just provided some basic constructs such as arrays (single- or
multi-dimensional) in a more usable form in the language level, if the
library solution couldn't be good enough?

--
Seungbeom Kim

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

James Kanze wrote:
> I'm not sure what your point is.  The object code depends on the
> source code AND the aleas of how the unoptimized translator
> works.  You certainly don't want the optimizer to be restricted
> by such aleas.

I'm not familiar with the word "aleas." I'm probably not the only one.

It seems to be French for "risks"? But that doesn't make sense in
context.

The word "alea" (singular?) could mean games of chance, a German game
publisher, a musical organization, a community in Greece, a 1984 movie
starring Janet Reno, or a software package for conducting randomization
in
clinical trials... but none of these make sense in context either.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"AllanW" <allan_w@my-dejanews.com> writes:
> James Kanze wrote:
>> I'm not sure what your point is.  The object code depends on the
>> source code AND the aleas of how the unoptimized translator
>> works.  You certainly don't want the optimizer to be restricted
>> by such aleas.
>
> I'm not familiar with the word "aleas." I'm probably not the only one.
>
> It seems to be French for "risks"? But that doesn't make sense in
> context.

Vagaries?

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Na comp.std.c++ Keith Thompson skrobie:
> "AllanW" <allan_w@my-dejanews.com> writes:
> > James Kanze wrote:
> >> I'm not sure what your point is.  The object code depends on the
> >> source code AND the aleas of how the unoptimized translator
> >> works.  You certainly don't want the optimizer to be restricted
> >> by such aleas.
> >
> > I'm not familiar with the word "aleas." I'm probably not the only one.
> >
> > It seems to be French for "risks"? But that doesn't make sense in
> > context.

> Vagaries?

Guys, please... is that a group for English language dungeons?

The only explanation of "alea" I found on www.answers.com mostly comes from a
name or surname, it is also a name of software package.

The word "vagaries" also seems not well matching in this case, or else we
think about "what crazy and bizarre things the compiler does to produce the
object code".

This is unfortunate because of a "bizarre word", but it is also not precise.
Please use more precise nomenclature. :)


--
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"Java is answer for a question that has never been stated"

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

AllanW wrote:
> James Kanze wrote:
> > I'm not sure what your point is.  The object code depends on the
> > source code AND the aleas of how the unoptimized translator
> > works.  You certainly don't want the optimizer to be restricted
> > by such aleas.

> I'm not familiar with the word "aleas." I'm probably not the only one.

Oops.

> It seems to be French for "risks"? But that doesn't make sense in
> context.

Not necessarily risks---just any more or less random or
non-deterministic effects.  (I don't even know a good English
word for it.)

> The word "alea" (singular?) could mean games of chance, a
> German game publisher, a musical organization, a community in
> Greece, a 1984 movie starring Janet Reno, or a software
> package for conducting randomization in clinical trials... but
> none of these make sense in context either.

The word alea is actually Latin for die, as in "alea jacta est"
("the die is thrown", supposedly said by Ceasar before some
important battle).  It's moved into French with the more
generalized meaning of anything due to chance.

In this case, of course, what I was saying is that the object
code isn't totally dependant on the source code, and depends
greatly on choices made in the implementation strategy.  In
terms of information theory, the translation from source to
object entails a loss of information, much of which could be
useful for optimization, but the resulting object code also
contains a lot of additional, irrelevant information, which
depends on the way the compiler happened to be implemented.  And
that you certainly don't want to take this information into
account when optimizing, but if you only have access to the
object representation, you have no real way of distinguishing it
from the essential information.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Sektor van Skijlen wrote:
> Na comp.std.c++ Keith Thompson skrobie:
> > "AllanW" <allan_w@my-dejanews.com> writes:
> > > James Kanze wrote:
> > >> I'm not sure what your point is.  The object code depends on the
> > >> source code AND the aleas of how the unoptimized translator
> > >> works.  You certainly don't want the optimizer to be restricted
> > >> by such aleas.

> > > I'm not familiar with the word "aleas." I'm probably not the only one.

> > > It seems to be French for "risks"? But that doesn't make sense in
> > > context.

> > Vagaries?

> Guys, please... is that a group for English language dungeons?

It's a group where we're supposed to write in English.  Some of
us do slip up occasionally, however.

> The only explanation of "alea" I found on www.answers.com
> mostly comes from a name or surname, it is also a name of
> software package.

> The word "vagaries" also seems not well matching in this case,
> or else we think about "what crazy and bizarre things the
> compiler does to produce the object code".

Actually, it's a pretty good translation of the French word.  Or
maybe not: the American Heritage Dictionary says "an extravagant
or erratic notion or action", and there's no implication of
extravagant (nor, really, of erratic) in the French word.  More
indeterminate, or randomly chosen, or something along those
lines.  In this case, the results of a decision made for other
reasons.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> If you're going to post the exact same message to both newsgroups, and
> even comment on the fact that it refers equally to C and C++, it would
> have been better to cross-post it to both groups. I'm posting a copy of
> my response to your comp.std.c posting, since my response, like your
> question, covers both languages. I've redirected follow-ups to
> cross-post both groups.
>
> Frederick Gotham wrote:
>> > [ This post deals with both C and C++, but does not alienate either
>> > language because the language feature being discussed is common to both
>> > languages. ]
>> >
>> > Over on comp.lang.c, we've been discussing the accessing of array
>> > elements
>> > via subscript indices which may appear to be out of range. In
>> > particular,
>> > accesses similar to the following:
>> >
>> >     int arr[2][2];
>> >
>> >     arr[0][3] = 7;
>> >
>> > Both the C Standard and the C++ Standard necessitate that the four
>> > int's be
>> > lain out in memory in ascending order with no padding in between, i.e.:
>> >
>> > (best viewed with a monowidth font)
>> >
>> >     --------------------------------
>> >     | Memory Address |    Object   |
>> >     --------------------------------
>> >     |       0        |   arr[0][0] |
>> >     |       1        |   arr[0][1] |
>> >     |       2        |   arr[1][0] |
>> >     |       3        |   arr[1][1] |
>> >     --------------------------------
>> >
>> > One can see plainly that there should be no problem with the little
>> > snippet
>> > above because arr[0][3] should be the same as arr[1][1], but I've had
>> > people over on comp.lang.c telling me that the behaviour of the snippet
>> > is
>> > undefined because of an "out of bounds" array access. ...
>
> Good - they've been telling you the truth.
>
> It's very simple. What you've proven that it's perfectly possible, and
> in fact, trivial, for a C or C++ implementation to implement pointer
> arithmetic in such a fashion that this works in the manner you expect.
> However, this isn't about what's possible, it's about what's permitted.
> Because both standards say that this behavior is undefined,
> implementors are allowed to implement pointer arithmetic in other ways.
> Why would an implementation want to do something else? Well,
> ordinarily, they don't. However, there's two main reasons why something
> could go wrong.
>
> 1. Debugging implementations: the simplest way to do this is to use a
> heavy pointer, which contains more than just the address of the
> location in memory that it points at: it also contains information
> about the limits of how far it can be moved without crossing an array
> boundary. The calculation of p+n, where p is a pointer and n is an
> integer, results in a check of the new pointer value against those
> limits; if it's outside those limits, an appropriate signal is raised.
> This is a pretty expensive way to implement pointer arithmetic, so it
> would ordinarily be used only in a debugging mode. However, because the
> behavior is undefined, the compiler would continue to be a conforming
> implementation, even when that mode is turned on.
>
> 2. A different issue is far more relevant to the ordinary programmer.
> Because the behavior of dereferencing an out-of-bounds pointer is
> undefined, an implementation is allowed to make optimizations based
> upon the assumption that no such dereferences will occur. For instance,
> taking the example code you've given, an implementation isn't required
> to consider the possibility that arr[0][3] might refer to the same
> object as arr[1][0]. Therefore, if you write something like the
> following:
>
> arr[0][3] = 3;
> arr[1][0] = 2;
> arr[0][3]++;
>
> It's allowed to translate that C code into machine code which places 3
> in a register, stores a 2 in the location referred to by arr[1][0],
> increments the register, giving it a value of 4, and then places the
> value of that register in the location referred to by arr[0][3].
>

Now this is too bad.  How do you copy a multidimensional array?  The
simplest thing to do, also for efficiency reasons, is

void do_copy(int a[2][2], int const b[2][2]) { std::copy(*a, *b, 2*2); }

My first idea was to call std::copy(a, b, 2) but it is not supported.  Now
it seems you have to replace this simple construct with nested loops.  I do
not like it.

Chris


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Kristof Zelechovski wrote:
.
> Now this is too bad.  How do you copy a multidimensional array?  The
> simplest thing to do, also for efficiency reasons, is
>
> void do_copy(int a[2][2], int const b[2][2]) { std::copy(*a, *b, 2*2); }

There are many implementations where that will work, and it precisely
because of the popularity of this approach that I wouldn't object very
strenuously to a change to the standard that made the behavior of such
code well-defined. My point is that it would require a change to the
standard.

> My first idea was to call std::copy(a, b, 2) but it is not supported.  Now
> it seems you have to replace this simple construct with nested loops.  I do
> not like it.

For POD types, memcpy() will do the job pretty efficiently, and just
about as simply as std::copy().

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Hi

Kristof Zelechovski wrote:

> Now this is too bad.  How do you copy a multidimensional array?  The
> simplest thing to do, also for efficiency reasons, is
>
> void do_copy(int a[2][2], int const b[2][2]) { std::copy(*a, *b, 2*2); }

Yes, that seems to be wrong.
But if 8.3.4 (3) can be read the way I read it, your arrays are POD-types
and therefore you can memcpy them:

void do_copy(int (&a)[2][2], int const (&b)[2][2])
{
        std::memcpy(a, b, sizeof b);
}

This is both simple and efficient.

Markus

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

U=BFytkownik "Kristof Zelechovski" <giecrilj@stegny.2a.pl> napisa=B3 w=20
wiadomo=B6ci news:eijncl$jv8$1@news2.ipartners.pl...
>
>
> Now this is too bad.  How do you copy a multidimensional array?  The=20
> simplest thing to do, also for efficiency reasons, is
>
> void do_copy(int a[2][2], int const b[2][2]) { std::copy(*a, *b, 2*2); =
}
>

Oops, my mistake, should be std::copy(*a, *b, *(b + 2)) of course.

> My first idea was to call std::copy(a, b, 2) but it is not supported.  =
Now

rather std::copy(a, b, b + 2)

> it seems you have to replace this simple construct with nested loops.  =
I=20
> do not like it.
>
> Chris
>


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kuyper@wizard.net wrote:
> Kristof Zelechovski wrote:
> .
>> Now this is too bad.  How do you copy a multidimensional array?
>
> For POD types, memcpy() will do the job pretty efficiently, and just
> about as simply as std::copy().

Only for POD types. (Alas!) What for non-POD types?

I don't agree with Frederick that the current rules are nonsense,
but I do want to see that we have a simple and efficient way to
copy a multi-dimensional array of any type.

Or.. should we advised to just wrap the array in a struct?
Or to just stay away from built-in arrays? (But often, using
std::vector for a multi-dimensional array is too cumbersome.)

--
Seungbeom Kim

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Hi

Seungbeom Kim wrote:

> kuyper@wizard.net wrote:
>> Kristof Zelechovski wrote:
>> .
>>> Now this is too bad.  How do you copy a multidimensional array?
>>
>> For POD types, memcpy() will do the job pretty efficiently, and just
>> about as simply as std::copy().
>
> Only for POD types. (Alas!) What for non-POD types?

If you're only looking for convenience, how about some template magic?

-- snip --

#include <iostream>
#include <boost/type_traits/is_array.hpp>
#include <boost/static_assert.hpp>

using namespace std;
using namespace boost;

template<bool isarray> struct do_copy_array;
template<> struct do_copy_array<true>
{
        template<typename T1, typename T2, unsigned N>
        void copy(T1 (&dst)[N], T2 (&src)[N])
        {
                BOOST_STATIC_ASSERT(!is_array<T1>::value ||
is_array<T2>::value)
;
                do_copy_array<is_array<T1>::value> copier;
                for(unsigned i=0; i!=N; ++i)
                        copier.copy(dst[i], src[i]);
        }
};

template<> struct do_copy_array<false>
{
        template<typename T1, typename T2>
        void copy(T1& dst, T2& src)
        {
                dst = src;
        }
};

template<typename T1, typename T2, unsigned N>
void copy_array(T1 (&dst)[N], T2 (&src)[N])
{
        do_copy_array<true> copier;
        copier.copy(dst, src);
}

int main()
{
        // Have three arrays
        int a[3][3] = { { 1, 2, 3}, { 6, 5, 4}, { 7, 8, 9 } };
        int b[3][3] = {};
        int* c[3];

        copy_array(b,a); // copy all elements from a to b

        copy_array(c,b); // c[i] <- b[i] (with conversion int[3] -> int*)

        for(int i=0; i<3; ++i)
        {
                for(int j=0; j<3; ++j)
                        cout << c[i][j] << " ";
                cout << "\n";
        }
}

-- snip --

Probably there are some problems with it, but I'm quite confident they can
be solved. It might even be improved to use memcpy in case the types are
PODs, at least on those platforms where boost::is_pod is not trivial.
Also, possibly it's way too complicated, but I don't want to think about it
any more...

cheers
Markus

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Uzytkownik "Markus Moll" <moll@rbg.informatik.tu-darmstadt.de> napisal w
wiadomosci news:454fca5c$0$5724$9b4e6d93@newsspool3.arcor-online.net...
> Hi
>
> Seungbeom Kim wrote:
>
>> kuyper@wizard.net wrote:
>>> Kristof Zelechovski wrote:
>>> .
>>>> Now this is too bad.  How do you copy a multidimensional array?
>>>
>>> For POD types, memcpy() will do the job pretty efficiently, and just
>>> about as simply as std::copy().
>>
>> Only for POD types. (Alas!) What for non-POD types?
>
> If you're only looking for convenience, how about some template magic?
>
> -- snip --

Your solution uses runtime recursion and nested loops.  I do not think such
complications are really necessary in this case, except that the standard
declares flattening multidimensional arrays as undefined behaviour.
Chris


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Seungbeom Kim wrote:
> kuyper@wizard.net wrote:
> > Kristof Zelechovski wrote:

> >> Now this is too bad.  How do you copy a multidimensional array?

> > For POD types, memcpy() will do the job pretty efficiently, and just
> > about as simply as std::copy().

> Only for POD types. (Alas!) What for non-POD types?

> I don't agree with Frederick that the current rules are nonsense,
> but I do want to see that we have a simple and efficient way to
> copy a multi-dimensional array of any type.

> Or.. should we advised to just wrap the array in a struct?

That's probably the best solution.

The real problem, of course, is that C style arrays are
irremedially broken; as a type, they are discriminated against,
and don't have the full rights that other types do.

> Or to just stay away from built-in arrays? (But often, using
> std::vector for a multi-dimensional array is too cumbersome.)

Agreed.  In practice, I'd almost always write some sort of class
to handle the issue.  (Or maybe valarray is already a sufficient
solution---I'm not familiar enough with it to judge.)

When you say that std::vector is too cumbersome, do you mean the
declaration syntax, or the machinery it puts into work each
time.  For the first, I haven't a solution, but for the second,
boost::array should do the trick well in a lot of cases:
    boost::array< boost::array< double, 20 >, 10 >
                        array2d ;
should result in almost the same code as:
    double              array2d[ 10 ][ 20 ] ;
(But the declaration syntax is still a pain.)

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

James Kanze wrote:
> Seungbeom Kim wrote:
>
>>kuyper@wizard.net wrote:
>>
>>>Kristof Zelechovski wrote:
>
>
>>>>Now this is too bad.  How do you copy a multidimensional array?
>
>
>>>For POD types, memcpy() will do the job pretty efficiently, and just
>>>about as simply as std::copy().
>
>
>>Only for POD types. (Alas!) What for non-POD types?

    Use a loop and let the compiler optimize.

    I previously submitted a long reply on this subject, detailing
how modern optimizing compilers do better than "memcpy" on this,
with an assembly code excerpt from a Microsoft compiler as
a demonstration.  That's stuck in the moderation queue somewhere.

    Don't try to do low-level optimization at the source level.

    John Nagle
    Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> 2. A different issue is far more relevant to the ordinary programmer.
> Because the behavior of dereferencing an out-of-bounds pointer is
> undefined, an implementation is allowed to make optimizations based
> upon the assumption that no such dereferences will occur. For instance,
> taking the example code you've given, an implementation isn't required
> to consider the possibility that arr[0][3] might refer to the same
> object as arr[1][0]. Therefore, if you write something like the
> following:
>
> arr[0][3] = 3;
> arr[1][0] = 2;
> arr[0][3]++;
>
> It's allowed to translate that C code into machine code which places 3
> in a register, stores a 2 in the location referred to by arr[1][0],
> increments the register, giving it a value of 4, and then places the
> value of that register in the location referred to by arr[0][3].

I think the optimizer should operate on object code;
it might take the source code as a hint about the programmer's intention
but all assumptions based on source code analysis should be validated
against object code.
An optimizer that fails to do this is dumb and would do more harm than good.
In this particular case, arr[0][3] and arr[1][0] denote the same physical
location
and would be replaced with the same memory reference in object code
and thus the optimizer will know
that both assignments can be eliminated and the incrementation can be
replaced with an assignment.

Chris


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Kristof Zelechovski" wrote:
> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> > 2. A different issue is far more relevant to the ordinary programmer.
> > Because the behavior of dereferencing an out-of-bounds pointer is
> > undefined, an implementation is allowed to make optimizations based
> > upon the assumption that no such dereferences will occur. For instance,
> > taking the example code you've given, an implementation isn't required
> > to consider the possibility that arr[0][3] might refer to the same
> > object as arr[1][0]. Therefore, if you write something like the
> > following:
> >
> > arr[0][3] = 3;
> > arr[1][0] = 2;
> > arr[0][3]++;
> >
> > It's allowed to translate that C code into machine code which places 3
> > in a register, stores a 2 in the location referred to by arr[1][0],
> > increments the register, giving it a value of 4, and then places the
> > value of that register in the location referred to by arr[0][3].
>
> I think the optimizer should operate on object code;

Some optimizations are permitted only because of some feature of the
original source code which cannot be identified as such by examining
the generated object code. If I understand you correctly, you'd like to
prohibit any optimization that relies on such information.

> it might take the source code as a hint about the programmer's intention
> but all assumptions based on source code analysis should be validated
> against object code.

If an implementor wants to do something like that, it can; I'm just
pointing out that it's not required to do so.

> An optimizer that fails to do this is dumb and would do more harm than good.

If it breaks code that is doing things it shouldn't be doing, I think
it's actually an improvement.


> In this particular case, arr[0][3] and arr[1][0] denote the same physical
> location
> and would be replaced with the same memory reference in object code
> and thus the optimizer will know
> that both assignments can be eliminated and the incrementation can be
> replaced with an assignment.

I used constant subscripts only to keep things simple, and because the
optimization is just as legal when the subscripts are constants.
However, such an optimization would be much more likely to be done when
the references are to a[0][i] and a[1][j]. An implementation can check
whether the values of i and j are such that they refer to the same
physical location in memory. Identifying this in the object code is
feasible, but more complicated than it would be with constant
subscripts. My point was that an implementation is not required to make
such a check, since the behavior is undefined.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Kristof Zelechovski" wrote:
> Uzytkownik <kuyper@wizard.net> napisal w wiadomosci
> news:1162382690.261763.306600@e64g2000cwd.googlegroups.com...
> > 2. A different issue is far more relevant to the ordinary programmer.
> > Because the behavior of dereferencing an out-of-bounds pointer is
> > undefined, an implementation is allowed to make optimizations based
> > upon the assumption that no such dereferences will occur. For instance,
> > taking the example code you've given, an implementation isn't required
> > to consider the possibility that arr[0][3] might refer to the same
> > object as arr[1][0]. Therefore, if you write something like the
> > following:

> > arr[0][3] = 3;
> > arr[1][0] = 2;
> > arr[0][3]++;

> > It's allowed to translate that C code into machine code which places 3
> > in a register, stores a 2 in the location referred to by arr[1][0],
> > increments the register, giving it a value of 4, and then places the
> > value of that register in the location referred to by arr[0][3].

> I think the optimizer should operate on object code;

That doesn't necessarily make sense.  It depends on the type of
optimization.  And what is "object code", anyway; none of the
really good optimizers use what would classically have been
considered "object code".

> it might take the source code as a hint about the programmer's intention
> but all assumptions based on source code analysis should be validated
> against object code.

I'm not sure what your point is.  The object code depends on the
source code AND the aleas of how the unoptimized translator
works.  You certainly don't want the optimizer to be restricted
by such aleas.

> An optimizer that fails to do this is dumb and would do more
> harm than good.

Then I guess all effective optimizers are dumb, and do more harm
than good.  But I fail to see the problem; the object code is
one particular translators interpretation of the source,
generally with much information lost, but also with much added.
It doesn't make sense for the optimizer to be forced to ignore
information provided by the original program, but to take into
account information added by the original translator.

> In this particular case, arr[0][3] and arr[1][0] denote the
> same physical location and would be replaced with the same
> memory reference in object code and thus the optimizer will
> know that both assignments can be eliminated and the
> incrementation can be replaced with an assignment.

In this particular case, the compiler will know that arr[0][3]
is an illegal access, and won't necessarily generate any code
for it.  It will certainly know that arr[0][3] and arr[1][0] are
not the same cell.  Whether this information propagates down to
the object level or not depends on the original translator and
the object format; I've seen examples of both.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

[ This post deals with both C and C++, but does not alienate either
language because the language feature being discussed is common to both
languages. ]

Over on comp.lang.c, we've been discussing the accessing of array elements
via subscript indices which may appear to be out of range. In particular,
accesses similar to the following:

    int arr[2][2];

    arr[0][3] = 7;

Both the C Standard and the C++ Standard necessitate that the four int's be
lain out in memory in ascending order with no padding in between, i.e.:

(best viewed with a monowidth font)

    --------------------------------
    | Memory Address |    Object   |
    --------------------------------
    |       0        |   arr[0][0] |
    |       1        |   arr[0][1] |
    |       2        |   arr[1][0] |
    |       3        |   arr[1][1] |
    --------------------------------

One can see plainly that there should be no problem with the little snippet
above because arr[0][3] should be the same as arr[1][1], but I've had
people over on comp.lang.c telling me that the behaviour of the snippet is
undefined because of an "out of bounds" array access. They've even backed
this up with a quote from the C Standard:

J.2 Undefined behavior:
The behavior is undefined in the following circumstances:
[...]
- An array subscript is out of range, even if an object is apparently
accessible with the given subscript (as in the lvalue expression
a[1][7] given the declaration int a[4][5]) (6.5.6).

Are the same claims of undefined behaviour existing in C++ made by anyone?

If it is claimed that the snippet's behaviour is undefined because the
second subscript index is out of range of the dimension, then this
rationale can be brought into doubt by the following breakdown. First let's
look at the expression statement:

    arr[0][3] = 9;

The compiler, both in C and in C++, must interpret this as:

    *( *(arr+0) + 3 ) = 9;

In the inner-most set of parentheses, "arr" decays to a pointer to its
first element, i.e. an R-value of the type int(*)[2]. The value 0 is then
added to this address, which has no effect. The address is then
dereferenced, yielding an L-value of the type int[2]. This expression then
decays to a pointer to its first element, yielding an R-value of the type
int*. The value 3 is then added to this address. (In terms of bytes, it's p
+= 3 * sizeof(int)). This address is then dereferenced, yielding an L-value
of the type int. The L-value int is then assigned to.

The only thing that sounds a little dodgy in the above paragraph is that an
L-value of the type int[2] is used as a stepping stone to access an element
whose index is greater than 1 -- but this shouldn't be a problem, because
the L-value decays to a simple R-value int pointer prior to the accessing
of the int object, so any dimension info should be lost by then.

To the C++ programmers: Is the snippet viewed as invoking undefined
behaviour? If so, why?

To the C programmers: How can you rationalise the assertion that it
actually does invoke undefined behaviour?

I'd like to remind both camps that, in other places, we're free to use our
memory however we please (given that it's suitably aligned, of course). For
instance, look at the following. The code is an absolute dog's dinner, but
it should work perfectly on all implementations:

/* Assume the inclusion of all necessary headers */

void Output(int);  /* Defined elsewhere */

int main(void)
{
    assert( sizeof(double) > sizeof(int) );

    { /* Start */

    double *p;
    int *q;
    char unsigned const *pover;
    char unsigned const *ptr;

    p = malloc(5 * sizeof*p);
    q = (int*)p++;
    pover = (char unsigned*)(p+4);
    ptr = (char unsigned*)p;
    p[3] = 2423.234;
    *q++ = -9;


    do Output(*ptr++);
    while (pover != ptr);

    return 0;

    } /* End */
}

Another thing I would remind both camps of, is that we can access any
memory as if it were simply an array of unsigned char's. That means we can
access an "int[2][2]" as if it were simply an object of the type "char
unsigned[sizeof(int[2][2])]".

The reason I'm writing this is that, at the moment, it sounds like absolute
nonsense to me that the original snippet's behaviour is undefined, and so I
challenge those who support its alleged undefinedness.

I leave you with this:

    int arr[2][2];

    void *const pv = &arr;

    int *const pi = (int*)pv;  /* Cast used for C++ programmers! */

    pi[3] = 8;

--

Frederick Gotham

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Frederick Gotham wrote:
> [ This post deals with both C and C++, but does not alienate either
> language because the language feature being discussed is common to both
> languages. ]
>
> Over on comp.lang.c, we've been discussing the accessing of array elements
> via subscript indices which may appear to be out of range. In particular,
> accesses similar to the following:
>
>     int arr[2][2];
>
>     arr[0][3] = 7;
>


     Yes.

     "Subscript #2, value of 3, out of range for array 'arr[2][2]'"

C++ implementations are allowed to check subscripts.  A few of them
actually do.

    John Nagle
    Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <GqT1h.15442$j7.332992@news.indigo.ie>, Frederick Gotham
<fgothamNO@SPAM.com> writes
>
>[ This post deals with both C and C++, but does not alienate either
>language because the language feature being discussed is common to both
>languages. ]
The explanation you had in comp.std.c is just as true in C++. Had you
just posted to one group you would have had your explanation and been
able to consider if that covered both languages. A saving on everyone's
time.


--
Francis Glassborow      ACCU
Author of 'You Can Do It!' and "You Can Program in C++"
see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

By the way, I'm arguing that the Standard should say that both of the
following are well-defined:

    Snippet 1:

        int arr[2][2];

        arr[0][3] = 8;

    Snippet 2:

        int arr[2][2];

        int (&b)[4] = reinterpret_cast<int(&)[4]>(arr);

        b[0] = 1; b[1] = 2; b[2] = 3; b[3] = 4;

--

Frederick Gotham

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

If you're going to post the exact same message to both newsgroups, and
even comment on the fact that it refers equally to C and C++, it would
have been better to cross-post it to both groups. I'm posting a copy of
my response to your comp.std.c posting, since my response, like your
question, covers both languages. I've redirected follow-ups to
cross-post both groups.

Frederick Gotham wrote:
> > [ This post deals with both C and C++, but does not alienate either
> > language because the language feature being discussed is common to both
> > languages. ]
> >
> > Over on comp.lang.c, we've been discussing the accessing of array elements
> > via subscript indices which may appear to be out of range. In particular,
> > accesses similar to the following:
> >
> >     int arr[2][2];
> >
> >     arr[0][3] = 7;
> >
> > Both the C Standard and the C++ Standard necessitate that the four int's be
> > lain out in memory in ascending order with no padding in between, i.e.:
> >
> > (best viewed with a monowidth font)
> >
> >     --------------------------------
> >     | Memory Address |    Object   |
> >     --------------------------------
> >     |       0        |   arr[0][0] |
> >     |       1        |   arr[0][1] |
> >     |       2        |   arr[1][0] |
> >     |       3        |   arr[1][1] |
> >     --------------------------------
> >
> > One can see plainly that there should be no problem with the little snippet
> > above because arr[0][3] should be the same as arr[1][1], but I've had
> > people over on comp.lang.c telling me that the behaviour of the snippet is
> > undefined because of an "out of bounds" array access. ...

Good - they've been telling you the truth.

> > ... They've even backed
> > this up with a quote from the C Standard:
> >
> > J.2 Undefined behavior:
> > The behavior is undefined in the following circumstances:
> > [...]
> > - An array subscript is out of range, even if an object is apparently
> > accessible with the given subscript (as in the lvalue expression
> > a[1][7] given the declaration int a[4][5]) (6.5.6).
> >
> > Are the same claims of undefined behaviour existing in C++ made by anyone?

Yes.  Appendix J.2 isn't normative, it merely explains some of the
consequences of what 6.5.6 itself says. Section 5.7p5 of the C++
standard says the same thing about C++ pointer arithmetic that section
6.5.6p8 of the C standard says about C pointer arithmetic. They both
talk about the pointer pointing at an element of an array, and they
define what adding an integer to such a pointer means, in terms of
moving through that array. Most importantly, they both say that such
an expression has undefined behavior if the result doesn't continue
pointing into that array.

The wording used in both standards makes sense only if the relevent
array has elements of the same type that are pointed at by the pointer.
The array 'a' has elements of type 'array of 5 ints'. When it decays to
a pointer, a[1] points at an int, and the only array whose element type
is 'int' that contains the object it points at is the sub-array a[1].
Therefore, it's the sub-array a[1] whose length (5) determines the
maximum amount that can be added to a[1]. The array 'a' can't be used
for that purpose, because it's element type is incorrect; and if it
were used, it would set a limit of 4, not 20, because it only contains
4 elements of it's element type.

> > If it is claimed that the snippet's behaviour is undefined because the
> > second subscript index is out of range of the dimension, then this
> > rationale can be brought into doubt by the following breakdown. First let's
> > look at the expression statement:
> >
> >     arr[0][3] = 9;
> >
> > The compiler, both in C and in C++, must interpret this as:
> >
> >     *( *(arr+0) + 3 ) = 9;
> >
> > In the inner-most set of parentheses, "arr" decays to a pointer to its
> > first element, i.e. an R-value of the type int(*)[2]. The value 0 is then
> > added to this address, which has no effect. The address is then
> > dereferenced, yielding an L-value of the type int[2]. This expression then
> > decays to a pointer to its first element, yielding an R-value of the type
> > int*. The value 3 is then added to this address. (In terms of bytes, it's p
> > += 3 * sizeof(int)). This address is then dereferenced, yielding an L-value
> > of the type int. The L-value int is then assigned to.
> >
> > The only thing that sounds a little dodgy in the above paragraph is that an
> > L-value of the type int[2] is used as a stepping stone to access an element
> > whose index is greater than 1 -- but this shouldn't be a problem, because
> > the L-value decays to a simple R-value int pointer prior to the accessing
> > of the int object, so any dimension info should be lost by then.
> >
> > To the C++ programmers: Is the snippet viewed as invoking undefined
> > behaviour? If so, why?
> >
> > To the C programmers: How can you rationalise the assertion that it
> > actually does invoke undefined behaviour?

It's very simple. What you've proven that it's perfectly possible, and
in fact, trivial, for a C or C++ implementation to implement pointer
arithmetic in such a fashion that this works in the manner you expect.
However, this isn't about what's possible, it's about what's permitted.
Because both standards say that this behavior is undefined,
implementors are allowed to implement pointer arithmetic in other ways.
Why would an implementation want to do something else? Well,
ordinarily, they don't. However, there's two main reasons why something
could go wrong.

1. Debugging implementations: the simplest way to do this is to use a
heavy pointer, which contains more than just the address of the
location in memory that it points at: it also contains information
about the limits of how far it can be moved without crossing an array
boundary. The calculation of p+n, where p is a pointer and n is an
integer, results in a check of the new pointer value against those
limits; if it's outside those limits, an appropriate signal is raised.
This is a pretty expensive way to implement pointer arithmetic, so it
would ordinarily be used only in a debugging mode. However, because the
behavior is undefined, the compiler would continue to be a conforming
implementation, even when that mode is turned on.

2. A different issue is far more relevant to the ordinary programmer.
Because the behavior of dereferencing an out-of-bounds pointer is
undefined, an implementation is allowed to make optimizations based
upon the assumption that no such dereferences will occur. For instance,
taking the example code you've given, an implementation isn't required
to consider the possibility that arr[0][3] might refer to the same
object as arr[1][0]. Therefore, if you write something like the
following:

arr[0][3] = 3;
arr[1][0] = 2;
arr[0][3]++;

It's allowed to translate that C code into machine code which places 3
in a register, stores a 2 in the location referred to by arr[1][0],
increments the register, giving it a value of 4, and then places the
value of that register in the location referred to by arr[0][3].

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Frederick Gotham wrote:
> By the way, I'm arguing that the Standard should say that both of the
> following are well-defined:
>
>     Snippet 1:
>
>         int arr[2][2];
>
>         arr[0][3] = 8;
>
>     Snippet 2:
>
>         int arr[2][2];
>
>         int (&b)[4] = reinterpret_cast<int(&)[4]>(arr);
>
>         b[0] = 1; b[1] = 2; b[2] = 3; b[3] = 4;

I'd gotten the impression from your previoius comments here, and on
comp.lang.c, that you were arguing that the behavior  IS well defined,
not that it SHOULD BE well defined. That's a very different issue.

Code like that is a popular error, precisely because it works as you
expect it to for many compilers, and can be very convenient. The
reinterpret_cast<> is, IMO, a sufficiently clear indication that you're
doing something tricky. Re-wording section 5.7p5 to be consistent with
this concept would be complicated, but I'm sure it can be done. I'd be
comfortable with making such a change to the standard, though I would
not argue in favor of it.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]