<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<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">
<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>
<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>
<style type="text/css">p { margin-bottom: 0.1in; line-height: 115%; background: transparent none repeat scroll 0% 0%; }</style>
</body>
</html>