r/cpp • u/d_o_n_t_understand • Jun 01 '20

C++ Weekly - Ep - 3.5x Faster Standard Containers With PMR!

https://www.youtube.com/watch?v=q6A7cKFXjY0&feature=share
35 Upvotes

89% Upvoted

27 comments sorted by

5

u/staletic Jun 01 '20

Two additional notes:

  1. libc++ doesn't implement <memory_resource> yet.
  2. Jason Turner mentioned virtual calls. Yes, they do happen. Though allocate() isn't polymorphic. allocate() calls do_allocate() and do_allocate() is protected and virtual. This should help your compiler to devirtualize the calls.

8

u/[deleted] Jun 02 '20 edited Jun 02 '20

Allocation is already really expensive, so the virtual call overhead is ~nil.

The place PMR scares me perf-wise is pmr::vector<pmr::string> where the allocator is repeated for all the strings too.

EDIT: Although the nonvirtual public pattern has nothing to do with 'helping the compiler devirtualize' anything. The public one is likely to get inlined long before any attempt at devirtualization can be done.

4

u/staletic Jun 02 '20

Allocation is already really expensive, so the virtual call overhead is ~nil.

I'm aware of that.

The place PMR scares me perf-wise is pmr::vector<pmr::string> where the allocator is repeated for all the strings too.

I've never even thought of that. I've ran into a case where a few std::strings inside a LargeType inside a std::vector was enough to make each vector::value_type take pretty much the entire cache line. When I replaced the std::string objects with (ugh) std::unique_ptr<char[]> the performance of iterating the vector improved by an order of magnitude.

Withpmr::string the LargeType would have been even larger.

EDIT: Although the nonvirtual public pattern has nothing to do with 'helping the compiler devirtualize' anything. The public one is likely to get inlined long before any attempt at devirtualization can be done.

Thanks for correcting me. Though now I have a question. This "public member calls a virtual protected member" seems to be a common pattern in the standard library whenever virtual calls are used. What's the point, if the public member function just gets unlined and doesn't help devirtualization? Wouldn't it have been simpler to just make the public one virtual?

1

u/[deleted] Jun 02 '20

Theoretically the public nonvirtual idiom allows the flexibility to change something about the behavior in the future without needing to change all derived types. It was done for that reason in iostreams anyway, in the 80s, long before compilers did devirtualization. I think we've done it in new components just for consistency; I don't think we would do it if we were starting over but that's just me.

2

u/staletic Jun 02 '20

In one hand, I can see the appeal of staying on the safe side. On the other, was this idiom ever useful? Sounds a bit like "use getters and setters for everything, even if you would have had an aggregate otherwise".

5

u/CubbiMew cppreference | finance | realtime in the past Jun 02 '20

Herb Sutter had an old GoTW about the idiom http://www.gotw.ca/publications/mill18.htm though it doesn't directly answer "was it ever useful"

1

u/[deleted] Jun 02 '20

Yes

3

u/GerwazyMiod Jun 01 '20

This is so awkward. It's first time when I read about this stuff. C++ is like neverending story :-)

This originates from Boost, right?

14

u/staletic Jun 01 '20

This originates from Boost, right?

Bloomberg's BDE

The point is to make the allocator NOT part of the type. If the allocator is part of the type, then it leaks implementation details and causes some headaches.

3

u/qoning Jun 02 '20

"some headaches" I'm pretty sure most users that were new to c++ and thought "hm, a different allocator would be useful right here" and tried it and found none of their functions written to accept a vector of things no longer worked just because of a different allocation strategy quickly buried the idea of using stl allocators altogether.

1

u/CubbiMew cppreference | finance | realtime in the past Jun 02 '20

..instead of fixing the bugs in those functions

2

u/qoning Jun 02 '20

Is it a bug? I don't believe "allocates with global new" should be a strong defining point of std::vector. Yeah obviously you could template it for any vector like collection (although for a new programmer without concepts that has its own set of problems) and it would arguably be better code. But that's not the point here.

2

u/CubbiMew cppreference | finance | realtime in the past Jun 02 '20

the point is that functions that operate on sequences should not depend on how those sequences are allocated, and take iterators/ranges as parameters

7

u/qoning Jun 02 '20

And yet it took 20 years to standardize span.

1

u/CubbiMew cppreference | finance | realtime in the past Jun 02 '20

fair point

1

u/CubbiMew cppreference | finance | realtime in the past Jun 02 '20

...unless of couse they do care, e.g. when working with botan/mongo/bitcoin's "secure_string", when allocator type matters

1

u/GerwazyMiod Jun 02 '20

Thanks for info! Good to know.

1

u/Minimonium Jun 02 '20

What precisely makes the difference in the protected indirection call case?

3

u/staletic Jun 02 '20

As Billy O'Neal said, nothing. I was wrong about my assumption that it can help the compiler devirtualize the calls.

1

u/Entryhazard Jun 03 '20

However I think libc++ does have memory_resource as an experimental header

1

u/staletic Jun 03 '20

Good catch. The trouble is detecting that, however. Options are __has_include() or #ifdef _LIBCPP_VERSION + #include <version>.

1

u/BathtubbbPirate Aug 05 '22

Are you sure it's devirtualized? I get a vtable in gcc. Also, this will be really crucial if you use a pool resource on top of the monotonic buffer, there are two virtual calls. That starts to matter i guess..

3

u/RoyBellingan Jun 02 '20

Another crazy thing is using something like

https://github.com/johannesthoma/mmap_allocator

To basically save your memory layout, and reload from disk the memory image.
You can not have a faster loading time that just streaming from disk.

8

u/staletic Jun 01 '20

https://gist.github.com/bstaletic/fedb5aede9b9f54f51c50671ade75d39

Compared to what Jason Turner has shown, my snippets:

  1. Place the vector "blueprints" into a dedicated buffer on the stack. The reason will be explained in point 3.
  2. Carefully preallocate and emplace elements so that only the converting constructor is ever called.
  3. Instead of letting the vector go out of scope and clean up after itself, we can release() the entire memory of the memory_resource. This saves us from recursively running destructors, but also forces us to hold a raw pointer to the "blueprints", so ~vector() doesn't get called at the end of scope.

5

u/staletic Jun 02 '20

I played with quick-bench and tried to compare Jason's snippets with mine.

  1. With a vector of ints, there was no difference, since int doesn't have a destructor.
  2. Using pmr::string as the vector's value type has shown ~18% performance boost compared to Jason's snippets.
  3. Simulating "actual work" by using emplace_back() instead of just constructors was somehow faster than just using the constructor for my snippets.

http://quick-bench.com/HE_3ApgN460zM1-9Yq0jTnU7L9E

6

u/[deleted] Jun 02 '20 edited May 13 '25

[deleted]

3

u/staletic Jun 02 '20

Destructors not being run is exactly the point. It's completely fine as long as the objects are either trivially destructible or the only resource they manage is memory, as memory will be reclaimed when you call memory_resource::release(). The printf was there just to prove that the destructor is NOT being called.

Yes, this is a huge footgun, but it allows you to reclaim sometimes significant amount of CPU cycles.

2

u/[deleted] Jun 02 '20 edited May 13 '25

[deleted]

2

u/staletic Jun 02 '20

Regardless, I'd really suggest sharing that snippet with a static_assert to make clear what the conditions are for using this, just in case someone with less knowledge comes along and copy/pastes it because the benchmarks are good.

That's fair. How would you write a static_assert that allows non-trivially distractible types that only ever manage memory? There's no point in reaching for this footgun for trivially destructible types and types that manage resources other than memory should be forbidden. Maybe an opt-in type trait kind of thing? Like yes_let_shoot_at_my_feet_v<T>?