Page MenuHomePhabricator

[1/2] Add a benchmark for map operations.
ClosedPublic

Authored by Mordante on Jun 1 2019, 9:29 AM.

Details

Summary

Before tackling bug 38722 make sure there is a baseline benchmark.

Diff Detail

Event Timeline

Mordante created this revision.Jun 1 2019, 9:29 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 1 2019, 9:29 AM
Herald added a subscriber: christof. · View Herald Transcript

There are several cases for "insert with hint". This tests one of them - the case where the hint is a dreferenceable iterator that points to the correct place in the map.

There are (at least) two other cases:

  • The hint is a dreferenceable iterator that points to the wrong place in the map.
  • The hint is not a dereferenceable iterator at all (think end())
Mordante updated this revision to Diff 207205.Jun 29 2019, 11:40 AM

I added 3 extra iterator positions for all hint cases:

  • end() as you suggested.
  • begin() this is most of the time the wrong iterator.
  • the third element this is most of the time the wrong iterator. Just to avoid the code will use special optimizations on begin() and end().
mclow.lists added inline comments.Sep 10 2019, 4:48 PM
libcxx/benchmarks/map.bench.cpp
58

The fact that the keys you use to test are ordered is troubling to me. See comment on erase

684

Isn't this just "Erase the first element" over and over until the map is empty?

713

Same with this one - isn't this just erasing the first element over and over?

Mordante updated this revision to Diff 224746.Oct 12 2019, 8:31 AM
Mordante marked 2 inline comments as done.

Adds additional tests to makes sure the order doesn't result in always removing the first element as observed by @mclow.lists .

ldionne requested changes to this revision.Mar 3 2020, 12:54 PM
ldionne added a reviewer: mvels.
ldionne added a subscriber: mvels.

@Mordante Can this be rebased on master? Also, I'd be curious to have @mvels look at this since he's been doing performance work for libc++ (albeit in unrelated areas).

This revision now requires changes to proceed.Mar 3 2020, 12:54 PM
Mordante updated this revision to Diff 249014.Mar 8 2020, 11:19 AM

Rebased against master.

ldionne requested changes to this revision.Mar 9 2020, 6:49 AM

How did you compile that? ninja -C build cxx-benchmarks fail after applying your patch:

In file included from <llvm>/libcxx/benchmarks/map.bench.cpp:15:
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:65:71: warning: pack fold expression is a C++17 extension [-Wc++17-extensions]
  (internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...);
                                                                      ^
<llvm>/libcxx/benchmarks/map.bench.cpp:77:9: error: cannot form a reference to 'void'
    auto& map = R.Maps.emplace_back();
        ^
<llvm>/libcxx/benchmarks/map.bench.cpp:78:9: error: cannot form a reference to 'void'
    auto& hints = R.Hints.emplace_back();
        ^
<llvm>/libcxx/benchmarks/map.bench.cpp:367:40: error: no member named 'insert_or_assign' in 'std::__1::map<unsigned long long, long long, std::__1::less<unsigned long long>, std::__1::allocator<std::__1::pair<const unsigned long long, long long> > >'
          benchmark::DoNotOptimize(Map.insert_or_assign(K, 1));
                                   ~~~ ^
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:46:69: note: in instantiation of member function '(anonymous namespace)::InsertAssign<internal::EnumValue<(anonymous namespace)::AllModes, (anonymous namespace)::Mode, 1>, internal::EnumValue<(anonymous namespace)::AllOrders, (anonymous namespace)::Order, 1> >::run' requested here
                                   [=](benchmark::State& S) { Bench.run(S); });
                                                                    ^
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:53:3: note: in instantiation of function template specialization 'internal::makeBenchmarkFromValuesImpl<(anonymous namespace)::InsertAssign<internal::EnumValue<(anonymous namespace)::AllModes, (anonymous namespace)::Mode, 1>, internal::EnumValue<(anonymous namespace)::AllOrders, (anonymous namespace)::Order, 1> >, std::__1::vector<std::__1::tuple<unsigned long>, std::__1::allocator<std::__1::tuple<unsigned long> > >, 0>' requested here
  makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>());
  ^
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:58:3: note: in instantiation of function template specialization 'internal::makeBenchmarkFromValues<(anonymous namespace)::InsertAssign<internal::EnumValue<(anonymous namespace)::AllModes, (anonymous namespace)::Mode, 1>, internal::EnumValue<(anonymous namespace)::AllOrders, (anonymous namespace)::Order, 1> >, unsigned long>' requested here
  makeBenchmarkFromValues<B<U...> >(A);
  ^
This revision now requires changes to proceed.Mar 9 2020, 6:49 AM
Mordante requested review of this revision.Mar 10 2020, 12:58 PM

It builds for me, but I had CMAKE_CXX_STANDARD set to 17 for this build. It seems the method used to use C++17 for the benchmarks didn't work. I feel fixing this issue should not be part of this commit. So I created D75955 to fix the issue. With that patch applied it also works for me when CMAKE_CXX_STANDARD set to 14. This is the default value.

ldionne accepted this revision.Mar 11 2020, 12:05 PM

LGTM assuming it build on top of your other patch.

This revision is now accepted and ready to land.Mar 11 2020, 12:05 PM
EricWF requested changes to this revision.Mar 11 2020, 2:36 PM
EricWF added inline comments.
libcxx/benchmarks/CartesianBenchmarks.h
22 ↗(On Diff #249014)

Uh, EnumValue::value should already work, since it's inherited from integral constant, no?

This revision now requires changes to proceed.Mar 11 2020, 2:36 PM

Good catch, I'll update the patch.

Mordante updated this revision to Diff 250045.Mar 12 2020, 1:51 PM

Addresses @EricWF's comment.

ldionne accepted this revision.May 14 2020, 10:16 AM

I'll ship this now. Thanks.

This revision was not accepted when it landed; it landed in state Needs Review.Sep 15 2020, 9:10 AM
This revision was automatically updated to reflect the committed changes.
Herald added a reviewer: Restricted Project. · View Herald TranscriptSep 15 2020, 9:10 AM

Thanks for accepting and committing the patch.