llvm dev - May 2015 - [LLVMdev] Memory Allocation Optimized away with new by not with ::operator new

Hi,

I’ve made my own version of std::vector which is called il::Vector. Due to
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html>, LLVM
can optimise away memory allocation. Therefore, the following code optimise away
all memory allocation for w resulting in a single allocation during the whole
program (for v).

When using my own vector implementation, I realised that the allocation were not
optimized away because I was using ::operator new. When I’ve switched back to
new, the optimisation came back.

Is it expected or a bug from LLVM?

François

====
#include <iostream>
#include <vector>


std::vector<double> f_val(std::size_t i, std::size_t n) {
    auto v = std::vector<double>(n);
    for (std::size_t k = 0; k < v.size(); ++k) {
        v[k] = static_cast<double>(i);
    }
    return v;
}

int main (int argc, char const *argv[])
{
    const auto n = std::size_t{10};
    const auto nb_loops = std::size_t{300000000};

    auto v = std::vector<double>( n, 0.0 );
    for (std::size_t i = 0; i < nb_loops; ++i) {
        auto w = f_val(i, n);
        for (std::size_t k = 0; k < v.size(); ++k) {
            v[k] += w[k];
        }
    }
    std::cout << v[0] << " " << v[n - 1] <<
std::endl;

    return 0;
}

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150504/0056bfa2/attachment.html>

On Mon, May 4, 2015 at 12:37 PM, François Fayard
<fayard.francois at icloud.com> wrote:
> Hi,
>
> I’ve made my own version of std::vector which is called il::Vector. Due to
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html, LLVM
can
> optimise away memory allocation. Therefore, the following code optimise
away
> all memory allocation for w resulting in a single allocation during the
> whole program (for v).
>
> When using my own vector implementation, I realised that the allocation
were
> not optimized away because I was using ::operator new. When I’ve switched
> back to new, the optimisation came back.
>
> Is it expected or a bug from LLVM?
Sadly this is a feature. The C++ standard has been unclear
historically about whether removing pairs of new/delete. The problem
is that the user may override them so this is an observable change,
but some compilers (LLVM) removed them anyways. As you said C++14
changed the wording so removing new/delete expression pairs is now
explicitly legal. Calls to ::operator new and delete aren't new/delete
expressions though, so it should behave as expected when overridden.

It looks like a glitch in the standard, but if I remember correctly it
was done intentionally.

- Ben
>
> François
>
> ====>
> #include <iostream>
> #include <vector>
>
>
> std::vector<double> f_val(std::size_t i, std::size_t n) {
>     auto v = std::vector<double>(n);
>     for (std::size_t k = 0; k < v.size(); ++k) {
>         v[k] = static_cast<double>(i);
>     }
>     return v;
> }
>
> int main (int argc, char const *argv[])
> {
>     const auto n = std::size_t{10};
>     const auto nb_loops = std::size_t{300000000};
>
>     auto v = std::vector<double>( n, 0.0 );
>     for (std::size_t i = 0; i < nb_loops; ++i) {
>         auto w = f_val(i, n);
>         for (std::size_t k = 0; k < v.size(); ++k) {
>             v[k] += w[k];
>         }
>     }
>     std::cout << v[0] << " " << v[n - 1]
<< std::endl;
>
>     return 0;
> }
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

If the compiler can't say for sure that your operator new is identical (has
no side-effects beyond allocating memory), it would be correct for the
compiler to NOT optimise it out - as it can't determine that it has no
other effect that your program rely on in some way.

--
Mats

On 4 May 2015 at 11:37, François Fayard <fayard.francois at icloud.com>
wrote:
> Hi,
>
> I’ve made my own version of std::vector which is called il::Vector. Due to
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html, LLVM
> can optimise away memory allocation. Therefore, the following code optimise
> away all memory allocation for w resulting in a single allocation during
> the whole program (for v).
>
> When using my own vector implementation, I realised that the allocation
> were not optimized away because I was using ::operator new. When I’ve
> switched back to new, the optimisation came back.
>
> Is it expected or a bug from LLVM?
>
> François
>
> ====>
> #include <iostream>
> #include <vector>
>
>
> std::vector<double> f_val(std::size_t i, std::size_t n) {
>     auto v = std::vector<double>(n);
>     for (std::size_t k = 0; k < v.size(); ++k) {
>         v[k] = static_cast<double>(i);
>     }
>     return v;
> }
>
> int main (int argc, char const *argv[])
> {
>     const auto n = std::size_t{10};
>     const auto nb_loops = std::size_t{300000000};
>
>     auto v = std::vector<double>( n, 0.0 );
>     for (std::size_t i = 0; i < nb_loops; ++i) {
>         auto w = f_val(i, n);
>         for (std::size_t k = 0; k < v.size(); ++k) {
>             v[k] += w[k];
>         }
>     }
>     std::cout << v[0] << " " << v[n - 1]
<< std::endl;
>
>     return 0;
> }
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150504/2355e1a9/attachment.html>

look at the "newly" added __builtin_operator_new/delete (by Richard
Smith)

discussed missing heap optimization for vector and std::string
http://clang-developers.42468.n3.nabble.com/missing-optimization-opportunity-for-const-std-vector-compared-to-std-array-td4034587.html#none

resulting patches to clang/libc++ to use the optimization
http://reviews.llvm.org/rL210137
http://reviews.llvm.org/rL210211

or is it now in c++14 explicitly allowed?



Am 04.05.2015 um 12:37 schrieb François Fayard:
> Hi,
>
> I’ve made my own version of std::vector which is called il::Vector. Due
to http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html>, LLVM
can optimise away memory allocation. Therefore, the following code optimise away
all memory allocation for w resulting in a single allocation during the whole
program (for v).
>
> When using my own vector implementation, I realised that the allocation
were not optimized away because I was using ::operator new. When I’ve switched
back to new, the optimisation came back.
>
> Is it expected or a bug from LLVM?
>
> François
>
> ====>
> #include <iostream>
> #include <vector>
>
>
> std::vector<double> f_val(std::size_t i, std::size_t n) {
>      auto v = std::vector<double>(n);
>      for (std::size_t k = 0; k < v.size(); ++k) {
>          v[k] = static_cast<double>(i);
>      }
>      return v;
> }
>
> int main (int argc, char const *argv[])
> {
>      const auto n = std::size_t{10};
>      const auto nb_loops = std::size_t{300000000};
>
>      auto v = std::vector<double>( n, 0.0 );
>      for (std::size_t i = 0; i < nb_loops; ++i) {
>          auto w = f_val(i, n);
>          for (std::size_t k = 0; k < v.size(); ++k) {
>              v[k] += w[k];
>          }
>      }
>      std::cout << v[0] << " " << v[n - 1]
<< std::endl;
>
>      return 0;
> }
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi,

I have checked and N3664 only talks about new/delete but not about operator
new/delete. Do you know the rationale behind this choice?
> On 04 May 2015, at 13:45, Benjamin Kramer <benny.kra at gmail.com>
wrote:
> 
> Sadly this is a feature. The C++ standard has been unclear
> historically about whether removing pairs of new/delete. The problem
> is that the user may override them so this is an observable change,
> but some compilers (LLVM) removed them anyways. As you said C++14
> changed the wording so removing new/delete expression pairs is now
> explicitly legal. Calls to ::operator new and delete aren't new/delete
> expressions though, so it should behave as expected when overridden.
> 
> It looks like a glitch in the standard, but if I remember correctly it
> was done intentionally.
> 
> - Ben
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150504/53079bd4/attachment.html>

On Mon, May 4, 2015 at 6:27 AM, François Fayard <fayard.francois at
icloud.com>
wrote:
> Hi,
>
>
> I have checked and N3664 only talks about new/delete but not about operator
> new/delete. Do you know the rationale behind this choice?
>
I believe the notion was to provide a syntax for /actually/ calling those
functions that the compiler couldn't optimize away, in case you wanted them
for their side effects, etc.

>
> On 04 May 2015, at 13:45, Benjamin Kramer <benny.kra at gmail.com>
wrote:
>
>
> Sadly this is a feature. The C++ standard has been unclear
>
> historically about whether removing pairs of new/delete. The problem
>
> is that the user may override them so this is an observable change,
>
> but some compilers (LLVM) removed them anyways. As you said C++14
>
> changed the wording so removing new/delete expression pairs is now
>
> explicitly legal. Calls to ::operator new and delete aren't new/delete
>
> expressions though, so it should behave as expected when overridden.
>
>
> It looks like a glitch in the standard, but if I remember correctly it
>
> was done intentionally.
>
>
> - Ben
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150504/d9565f4e/attachment.html>