[LLVMdev] Deduplication of memory allocation

[David Blaikie]

On Fri, May 1, 2015 at 8:34 AM, François Fayard <fayard.francois at icloud.com>
wrote:

> Hi,
>
> Even though this question does not only concern LLVM, it seems that only
> compilers guru can answer it. So I am giving a try here, hoping for the
> best.
>
> In a recent talk by Chandler Carruth, “Performance with algorithms,
> efficiency with data structures” (
> https://www.youtube.com/watch?v=fHNmRkzxHWs ), Chandler says that one
> should never return by reference for efficiency. Although I totally agree
> with him in most cases because pointers make it difficult for a compiler to
> optimise, I still don’t always have an efficient solution with value
> semantics. Here is the case that I am thinking of :
>
> ====
> std::vector<double> f(std::size_t i);
>
> auto v = std::vector<double>( n );
> for (std::size_t i = 0; i < 1000; ++i) {
>     auto w = f(i);
>     for (std::size_t k = 0; k < v.size(); ++k) {
>         v[k] += w[k];
>     }
> }
> ====
>
> which would be way slower than
>
> ====
> void f(std::size_t i, std::vector<double>& w);
>
> auto v = std::vector<double>( n );
> auto w = std::vector<double>( n );
> for (std::size_t i = 0; i < 1000; ++i) {
>     f(i, w);
>     for (std::size_t k = 0; k < v.size(); ++k) {
>         v[k] += w[k];
>     }
> }
> ====
>
> because there is no memory allocation in the i-loop, inside the f-call. In
> the Q&A where a guy seems to give him such an example (at 1:06:46), he says
> that smart compilers such as LLVM can deduplicate memory allocation. It
> does not seem to me to be applicable to this kind of algorithm. Does anyone
> have a concrete example where a compiler deduplicates memory allocation?
>

Probably the easiest way to give the compiler an opportunity here would be
to have 'f's definition available for inlining - a compiler might be able
to inline that, then, depending on the particular allocation behavior of
'f', the allocation /may/ be reused (I don't think we do anything like
reusing yet - though we can, to some degree, inline a bunch of
std::vector's ops and then just remove the whole std::vector thing in favor
of a stack allocation, for example)

>
> Thanks,
> François
>
> _______________________________________________
> 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/20150501/95b7728a/attachment.html>