DWARFUnit::m_die_array swap()->shrink_to_fit()

[jankratochvil]

Summary

rL145086 introduced m_die_array.shrink_to_fit() implemented by exact_size_die_array.swap, it was before LLVM became written in C++11.

That is fine to use shrink_to_fit() now, right? Although I see no real performance gain by a simple time test.

[labath]

shrink_to_fit should be fine. I wouldn't expect to see any difference as it is implemented (in libstdc++ at least) using the swap trick too.

[jankratochvil]

In D47492#1117350, @labath wrote:

it is implemented (in libstdc++ at least) using the swap trick too.

Thanks for the heads up, I expected it does realloc(): implementation absolutely cannot rely on realloc ... because realloc, if it cannot shrink in-place, will either leave the memory alone (no-op case) or make a bitwise copy (and miss the opportunity for readjusting pointers, etc. that the proper C++ copying/moving constructors would give)

[labath]

Well, if a type is trivially copyable (which DWARFDebugInfo should be, though I haven't checked), it should be able to do the copy via a single memcpy instead of a bunch of constructor calls. That should be more-or-less equivalent to realloc.

If this does not end up being implented as a memcpy here, we have an easy opportunity to improve things.

[jankratochvil]

If it is trivially copyable then IMO libstdc++ could use even that realloc() (that is for a shrink without any copy).

[jankratochvil]

FYI I have filed it for libstdc++ but I did not really understand their reaction: Bug 86013 - std::vector::shrink_to_fit() could sometimes use realloc()

[dblaikie]

In D47492#1120599, @jankratochvil wrote:

FYI I have filed it for libstdc++ but I did not really understand their reaction: Bug 86013 - std::vector::shrink_to_fit() could sometimes use realloc()

Happy to help explain it - which part(s) are you having a bit of trouble with?

It seems like the main one is that the implementation can't be sure that malloc was used to allocate the memory - since the global allocation function can be replaced & there's no convenient way to detect that.

[jankratochvil]

In D47492#1121543, @dblaikie wrote:

Happy to help explain it - which part(s) are you having a bit of trouble with?

What's wrong on this implementation?

It seems like the main one is that the implementation can't be sure that malloc was used to allocate the memory - since the global allocation function can be replaced & there's no convenient way to detect that.

The example above does verify whether the vector uses default libstdc++ std::allocator which uses libstdc++ ::operator new which uses malloc().

[labath]

In D47492#1122039, @jankratochvil wrote:

In D47492#1121543, @dblaikie wrote:

Happy to help explain it - which part(s) are you having a bit of trouble with?

What's wrong on this implementation?

It seems like the main one is that the implementation can't be sure that malloc was used to allocate the memory - since the global allocation function can be replaced & there's no convenient way to detect that.

The example above does verify whether the vector uses default libstdc++ std::allocator which uses libstdc++ ::operator new which uses malloc().

It doesn't look like your code verifies that the user hasn't replaced the global operator new by defining a custom version. http://en.cppreference.com/w/cpp/memory/new/operator_new:

The versions (1-4) are implicitly declared in each translation unit even if the <new> header is not included. Versions (1-8) are replaceable: a user-provided non-member function with the same signature defined anywhere in the program, in any source file, replaces the default version. Its declaration does not need to be visible.

The requirement that the declaration need not even be visible makes me believe this is not possible to detect at compile time. This kind of overriding is usually done via weak symbols, and the only way of detecting that I can think of is if libstdc++ exposed a non-weak alias to its operator new and then shrink_to_fit did a runtime check like if(&__standard_operator_new == &::operator new). That seems like a huge hack.

[jankratochvil]

In D47492#1122080, @labath wrote:

It doesn't look like your code verifies that the user hasn't replaced the global operator new by defining a custom version. http://en.cppreference.com/w/cpp/memory/new/operator_new:

I asked about it in the code, I see I could find it is permitted:

// Is permitted a symbol interposition of ::operator new to verify even that?

if libstdc++ exposed a non-weak alias to its operator new and then shrink_to_fit did a runtime check like if(&__standard_operator_new == &::operator new).

Yes, that is what I planned to write if the symbol interpoisiton is really permitted.

That seems like a huge hack.

Yes but possible.

[labath]

Well, with these kinds of safeguards I think this could work.
If I was the maintainer of std::vector in libstdc++ I am not sure if I would accept such a patch, but I am not, so feel free to try. :)

lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFUnit.cpp

while (offset < next_cu_offset &&
     }
   }
 
   if (!m_die_array.empty()) {
     lldbassert(!m_first_die || m_first_die == m_die_array.front());
     m_first_die = m_die_array.front();
   }
 
-  // Since std::vector objects will double their size, we really need to make a
-  // new array with the perfect size so we don't end up wasting space. So here
-  // we copy and swap to make sure we don't have any extra memory taken up.
-
-  if (m_die_array.size() < m_die_array.capacity()) {
-    DWARFDebugInfoEntry::collection exact_size_die_array(m_die_array.begin(),
-                                                         m_die_array.end());
-    exact_size_die_array.swap(m_die_array);
-  }
+  m_die_array.shrink_to_fit();
 
   ExtractDIEsEndCheck(offset);
 
   if (m_dwo_symbol_file) {
     DWARFUnit *dwo_cu = m_dwo_symbol_file->GetCompileUnit();
     dwo_cu->ExtractDIEsIfNeeded();
   }