Fix issue #2809 (broken test with clang)

[rhaschke]

The culprit of #2792 was essentially an optimization I proposed for #2698 to avoid copying strings to generate a map key.
Looks like this optimization leads to a stack-use-after-scope issue (found with asan), both in clang and gcc.
Reverting it, fixes the issue.

However, I'm not sure why this code doesn't work - the string references should exist:

#include <map>
#include <string>
#include <iostream>

int main(int argc, char const* argv[])
{
  using KeyT = std::pair<std::string, std::string>;
  std::map<KeyT, int> map;
  map.insert(std::make_pair(std::make_pair("foo", "bar"), 1));
  map.insert(std::make_pair(std::make_pair("bar", "foo"), 2));

  const std::string foo = "foo";
  const std::string bar = "bar";

  const std::pair<const std::string&, const std::string&> key =
      std::make_pair<const std::string&, const std::string&>(foo, bar);

  /*** at this point accessing elements of key results in stack-use-after-scope ***/
  std::cerr << key.first << ", " << key.second << std::endl;

  auto it = map.find(key);
  std::cerr << it->second << std::endl;
  return 0;
}

[rhaschke]

I found a trick to retain the original optimization using string references.

[tylerjw]

Approve because it gets rid of the building with -O0. Generally though isn't copying a short string going to be one of the most optimized features of any modern compiler and implementation of the STL? I as a rule generally avoid ever doing std::anything<Anything &>::anything because by using references with STL types you can create pessimizations by avoiding elision optimizations the compiler could otherwise do.

[tylerjw]

I copy-pasted the example code into godbolt and I'm not sure what doesn't work about it: https://godbolt.org/z/5azE4Exc5

[griswaldbrooks]

I likewise am confused. There is a single scope in the pasted example.

[rhaschke]

Generally though isn't copying a short string going to be one of the most optimized features of any modern compiler and implementation of the STL?

Here, it's not only copying the strings but also allocating new memory for them. That's one of the most costly operations one can do.

[griswaldbrooks]

@rhaschke I'm confused. Why would the pair heap allocate if the string was previously stack allocated, which I believe was @tylerjw 's conjecture?

[tylerjw]

Here, it's not only copying the strings but also allocating new memory for them. That's one of the most costly operations one can do.

It isn't always expensive to copy a string: https://tc-imba.github.io/posts/cpp-sso
Plus if it is a local variable only there is a good chance the compile optimizes the copy out: https://abseil.io/tips/117

[griswaldbrooks]

Probably a matter of style, but I believe you could have equivalently removed the references and preserved the ternary.

[rhaschke]

Keeping the (const) references ensure optimization.

[griswaldbrooks]

Yup yup. Was more of a comment before the std::cref became the choice thing to do.

[tylerjw]

Here is another blog post that explains SSO it in a helpful way: https://akrzemi1.wordpress.com/2014/04/14/common-optimizations/

[griswaldbrooks]

@rhaschke looking at the code/PR, my guess is asan isn't happy/able to peer through the multiple levels of pointer indirection. getId() had three possible sources for the reference, two of which are themselves references, all of which are pointers

https://github.com/ros-planning/moveit/blob/master/moveit_core/collision_detection_fcl/include/moveit/collision_detection_fcl/collision_common.h#L86-L98

and here, cd is also a pointer. pc only holding references then conceivably could have it's references go out of scope before being passed to distances.find. Or at least that's my working theory.

[codecov]

Codecov Report

Merging #2820 (8ac6637) into master (6e798bf) will increase coverage by 0.01%.
The diff coverage is 100.00%.

❗ Current head 8ac6637 differs from pull request most recent head bbd0552. Consider uploading reports for the commit bbd0552 to get more accurate results

@@            Coverage Diff             @@
##           master    #2820      +/-   ##
==========================================
+ Coverage   60.82%   60.82%   +0.01%     
==========================================
  Files         366      366              
  Lines       31713    31713              
==========================================
+ Hits        19285    19286       +1     
+ Misses      12428    12427       -1     

Impacted Files	Coverage Δ
...e/collision_detection_fcl/src/collision_common.cpp	76.36% <100.00%> (ø)
...nning_scene_monitor/src/planning_scene_monitor.cpp	68.27% <0.00%> (+0.14%)	⬆️

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 6e798bf...bbd0552. Read the comment docs.

[griswaldbrooks]

Or maybe some version of https://docs.microsoft.com/en-us/cpp/sanitizers/error-stack-use-after-scope?view=msvc-160#example-3---destructor-ordering-with-locals

[griswaldbrooks]

I also get SUMMARY: AddressSanitizer: stack-use-after-scope (/lib/x86_64-linux-gnu/libasan.so.5+0x6a1ac) when using g++ -fsanitize=address -std=c++17 main.cpp

[griswaldbrooks]

@rhaschke you know what's fun?

#include <string>
#include <iostream>

struct MyPair {
    const std::string& first;
    const std::string& second;
};

int main(int argc, char const* argv[])
{
  const std::string foo = "foo";
  const std::string bar = "bar";

  const MyPair key{foo, bar};

  /*** at this point accessing elements of key results in stack-use-after-scope ***/

  std::cout << key.first << ", " << key.second << std::endl;


  return 0;
}

https://godbolt.org/z/cE5PbvsfM

does not produce any error with address sanitizer.

[griswaldbrooks]

Also, this code is fine

#include <string>
#include <iostream>
#include <utility>

int main(int argc, char const* argv[])
{
    const std::string foo = "foo";
    const std::string bar = "bar";

    const std::pair<const std::string&, const std::string&> key{foo, bar};

    std::cout << key.first << ", " << key.second << std::endl;
    return 0;
}

ie, removing the make_pair

[griswaldbrooks]

Forgot to mention this still generates the error

#include <string>
#include <iostream>
#include <utility>

int main(int argc, char const* argv[])
{
    const std::string foo = "foo";
    const std::string bar = "bar";

    const std::pair<const std::string&, const std::string&> key = std::make_pair(foo, bar);

    std::cout << key.first << ", " << key.second << std::endl;
    return 0;
}

[griswaldbrooks]

Also

#include <string>
#include <iostream>
#include <utility>

int main(int argc, char const* argv[])
{
    const std::string foo = "foo";
    const std::string bar = "bar";

    const std::pair<const std::string&, const std::string&> key = std::pair<const std::string&, const std::string&>(foo, bar);

    std::cout << key.first << ", " << key.second << std::endl;
    return 0;
}

is fine. Seems to be something with std::make_pair

[griswaldbrooks]

const std::pair<const std::string&, const std::string&> key = std::make_pair(std::ref(foo), std::ref(bar));

is good too

[JafarAbdi]

@griswaldbrooks If I understand it correctly, it's because of std::make_pair always returning the decayed type see, which call the copy-constructor for pc causing its members first & second to reference temporaries (the copies of foo & bar)

[JafarAbdi]

I think we should go with using std::cref since the behavior is well documented in the standard see

const auto pc = cd1->getID() < cd2->getID() ? std::make_pair(std::cref(cd1->getID()), std::cref(cd2->getID())) :
                                              std::make_pair(std::cref(cd2->getID()), std::cref(cd1->getID()));

[v4hn]

@tylerjw wrote

It isn't always expensive to copy a string: https://tc-imba.github.io/posts/cpp-sso

Very true, but I don't want to rely on implicit optimizations and end up in situations where there's a significant runtime difference depending on whether my collision object is called armature_handle or armature_hex_cap at runtime. The latter is not "short" in libstdc++.

[rhaschke]

@JafarAbdi, thanks for pointing out std::cref. Indeed that resolves the issue. I also profiled the code.
@tylerjw, even with SSO, there is significant overhead explicitly copying the strings (note that most of the time is actually spent in std::map::find)

ref !find: 84
with cref: 1399715
with copy: 2036093

I will push an update to this PR using std::cref later.

#include <map>
#include <string>
#include <iostream>
#include <functional>
#include <chrono>

int main(int argc, char const* argv[])
{
  using KeyT = std::pair<std::string, std::string>;
  std::map<KeyT, int> map;
  map.insert(std::make_pair(std::make_pair("foo", "bar"), 1));
  map.insert(std::make_pair(std::make_pair("bar", "foo"), 2));

  const std::string foo = "foo";
  const std::string bar = "bar";

  auto start = std::chrono::steady_clock::now();
  for (int i = 0; i < 10000; ++i)
  {
    const std::pair<const std::string&, const std::string&> key1(foo, bar);
    const std::pair<const std::string&, const std::string&> key2(bar, foo);
    const std::pair<const std::string&, const std::string&>& key = foo < bar ? key1 : key2;
  }
  auto elapsed = std::chrono::steady_clock::now() - start;
  std::cerr << "ref !find: " << elapsed.count() << std::endl;

  start = std::chrono::steady_clock::now();
  for (int i = 0; i < 10000; ++i)
  {
    const std::pair<const std::string&, const std::string&> key1(foo, bar);
    const std::pair<const std::string&, const std::string&> key2(bar, foo);
    const std::pair<const std::string&, const std::string&>& key =
        foo < bar ? std::make_pair(std::cref(foo), std::cref(bar)) : std::make_pair(std::cref(bar), std::cref(foo));

    auto it = map.find(key);
  }
  elapsed = std::chrono::steady_clock::now() - start;
  std::cerr << "with cref: " << elapsed.count() << std::endl;

  start = std::chrono::steady_clock::now();
  for (int i = 0; i < 10000; ++i)
  {
    const std::pair<const std::string, const std::string> key1(foo, bar);
    const std::pair<const std::string, const std::string> key2(bar, foo);
    const std::pair<const std::string, const std::string>& key = foo < bar ? key1 : key2;

    auto it = map.find(key);
  }
  elapsed = std::chrono::steady_clock::now() - start;
  std::cerr << "with copy: " << elapsed.count() << std::endl;
  return 0;
}

[griswaldbrooks]

@rhaschke very cool. Throwing it into quickbench shows a 2.5x speedup https://quick-bench.com/q/CtWmHGp4nHOglaietXVNfi8r7cY

@JafarAbdi do you have another reference about std::decay and the temporaries from make_pair? It wasn't obvious to me from the std::make_pair documentation.

[griswaldbrooks]

@JafarAbdi nvm, I got it
https://stackoverflow.com/questions/57860088/do-i-need-to-use-ref-with-make-pair-to-return-a-reference
https://stackoverflow.com/questions/25732386/what-is-stddecay-and-when-it-should-be-used