[cfe-dev] Comparison of 2 schemes to implement OpenMP 5.0 declare mapper codegen

[Alexey Bataev via cfe-dev]

Hi Neil, thanks for you suggestions.  Unfortunately,  we cannot use deques or some other container without continuous memory layout. Yes, it looks like vector of vectors, but actually should be represented as linearized, collapsed vector of vectors. The runtime functions are not aware about any complex structures, they accept continuous memory buffers as inputs, not vectors, deques etc.

Best regards,
Alexey Bataev

29 июня 2019 г., в 15:17, Neil Nelson via cfe-dev <cfe-dev at lists.llvm.org<mailto:cfe-dev at lists.llvm.org>> написал(а):


Lingda Li via cfe-dev wrote:

On Fri, Jun 28, 2019 at 9:49 AM Li, Lingda <lli at bnl.gov><mailto:lli at bnl.gov> wrote

I believe the key question here is whether it is true that (the
overhead of push_back() > the overhead of precalculating the total
number + the memory allocation overhead + directly memory write).

Not familiar with this area, nevertheless given

I believe the key question here is whether it is true that (the
overhead of push_back() > the overhead of precalculating the total
number + the memory allocation overhead + directly memory write).

What we appear to be looking at is something very close to vectors of vectors in using position pointers and indexes as against a separate key index as in the case of std::map.

Given that we have vectors of vectors (nested mappers), the nested vector, the vector under the parent vector would almost necessarily need to be reached via a pointer in the parent vector. The reductio ad absurdum would be if we have a nested dynamic vector or a resizable vector, it would be impossible to use pointer arithmetic on the parent if the parent object could change size in containing the dynamic nested vector.

The result is that the size of the parent object would be fixed in using a pointer to the nested dynamic vector. Hence the ability to allocate these vectors at compile time depends on knowing the lengths of the vectors in descending order, parent first. When the length of a child vector is not known, that vector and its children would need to be allocated at run time.

I believe the key question here is whether it is true that (the
overhead of push_back() > the overhead of precalculating the total
number + the memory allocation overhead + directly memory write).

There are two inefficiencies associated with dynamic vectors. That is, the question appears to be whether or not we know the vector lengths at compile time and hence if we do not have the lengths, use dynamic vectors.

Dynamic vectors require a reserve area that can receive push_back objects. Some of that empty memory area will be wasted as it will likely never be used and if you do not have some reasonable idea of how long the eventual vector will likely be, you can waste a large amount of memory.

And if the initial estimate of the vector length is too small, reallocating memory and copying to a larger vector when the first vector is used up takes time.

A deque may be a better choice than a dynamic vector. You can still use position indexes but not pointer arithmetic and the deque would automatically grow in chunks and not need to reallocate.

I suggest that the downsides of dynamic vectors prefers allocation in the compiler when the lengths can be known.

Neil Nelson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20190701/cbf3c96f/attachment.html>