<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body dir="auto">
<span style="background-color: rgba(255, 255, 255, 0);">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.</span><br>
<br>
<div id="AppleMailSignature" dir="ltr">Best regards,
<div>Alexey Bataev</div>
</div>
<div dir="ltr"><br>
29 июня 2019 г., в 15:17, Neil Nelson via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>> написал(а):<br>
<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">Lingda Li via cfe-dev wrote:</font></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">On Fri, Jun 28, 2019 at 9:49 AM Li, Lingda
<a class="moz-txt-link-rfc2396E" href="mailto:lli@bnl.gov"><lli@bnl.gov></a> wrote</font></p>
<font size="-1">
<blockquote type="cite">I believe the key question here is whether it is true that (the
<br>
overhead of push_back() > the overhead of precalculating the total <br>
number + the memory allocation overhead + directly memory write).</blockquote>
</font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">Not familiar with this area, nevertheless given</font></p>
<font size="-1"></font><font size="-1">
<blockquote type="cite">I believe the key question here is whether it is true that (the
<br>
overhead of push_back() > the overhead of precalculating the total <br>
number + the memory allocation overhead + directly memory write).</blockquote>
</font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font></p>
<font size="-1"></font><font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font></p>
<font size="-1"></font><font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1"></font></p>
<blockquote type="cite"><font size="-1">I believe the key question here is whether it is true that (the
<br>
overhead of push_back() > the overhead of precalculating the total <br>
number + the memory allocation overhead + directly memory write).</font></blockquote>
<font size="-1"></font>
<p></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font><font size="-1">
</font></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">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.</font><font size="-1">
</font></p>
<font size="-1"></font>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">I suggest that the downsides of dynamic vectors prefers allocation in the compiler when the lengths can be known.</font></p>
<p style="margin-bottom: 0in; line-height: 100%"><font size="-1">Neil Nelson<br>
</font></p>
</div>
</blockquote>
</body>
</html>