InplaceVector project discussions

Beman Libraries
21

I feel similarly about gtest and was going to try using doctest instead. We’ll see what we end up with.

2 Likes
22

I am writing more tests based on GTest as previous doctest is not materialized.

I am also writing static_assert based tests to check constexpr compatibility, and it turns out current implementation is not constexpr friendly at all, the root cause is the need to reinterpret_cast to access first element due to the underlying storage being T aligned byte array.

I am reading up on constexpr support for inplace_vector, and seems like there’s talk about implementing constexpr inplace_vector to be almost impossible due to requirement for constexpr uninitialized storage.

See: https://www.youtube.com/watch?v=I8QJLGI0GOE and it’s vaguely mentioned in Episode 384 : CppCast

I presume this quote in the paper is meant to help with this:

constexpr support
The API of inplace_vector<T, Capacity> can be used in constexpr-contexts if is_trivially_copyable_v<T> , is_default_constructible_v<T> , and is_trivially_destructible<T> are true. This proposal only supports using the constexpr methods in constant expressions if is_trivial_t<T> is true.
The implementation cost of this is small. The prototype implementation specializes the storage to use a C array with value-initialized elements.
This negatively impacts the algorithmic complexity of inplace_vector constructors for these types from O(size) to O(capacity). When value-initialization takes place at run-time, this difference is significant.
Vectors with large capacity requirements are better served by vector instead.

I don’t think the referenced implementation mentioned here is publicly available, there’s no link to the implementation besides saying its “based on Howard Hinnant std::vector implementation in libc++”, and I am not good at digging LWG’s email chain.

I am just interpreting this constexpr support section as a nod to “for trivial type, do value initialization for the interest of constexpr, we know its painful”, to be more blunt, they are saying “use std::array or T[] for constexpr”.

I would be happy to try to implement a storage abstraction that use std::array as underlying storage type for trivial type and use the current type-erased T aligned unsigned char array for non-trivial type.

But before I do that, is my understanding here correct? I need someone knowledgeable here to give me more context.

23

Hi there,

I learned about Beman from David Sankel’s talk at Meeting C++ and I would be happy to contribute. InplaceVector is kind of a pet peeve for me, I have seen many (mostly bad/wrong) implementations of something similar throughout my career (+25 years of C++). And implementing all the bells and whistles from the paper is certainly a challenge.

I have just studied the implementation at Compiler Explorer, which is quoted in `inplace_vector` - HackMD.
This has a storage abstraction which uses std::array for trivial types, constexpr is added to all member functions. It also comes with a test suite, which I haven’t yet studied.

Please let me know how I can contribute. There might be more going on in local branches/forks of the repo than can be seen from the issues and open PRs, I want to avoid doing duplicate work.

1 Like
24

Hi jbab welcome!

The repository is located here: GitHub - beman-project/inplace_vector: Beman.InplaceVector: A dynamically-resizable vector with fixed capacity and embedded storage

The progress of inplace_vector has just been some-what restarted as we have been busy with other project.

Currently we have an initial implementation of inplace_vector, I am actively working making inplace_vector constexpr and writing a test suite for it.

We need more tests and examples as current test suite is bit bare-bone.

25

Hi River,

Any particular reason to use GTest over doctest? Sorry I dropped the ball on this one, haven’t had much time to work on it. If you would prefer to look at other things I can have a go at porting over the tests.

26

I would not use doctest again.
see Considering Lit for the Beman Project - #13 by ClausKlein

27

Welcome @jbab!

Here are some notes on the inplace vector paper:

  1. The best specification to use for beman.inplace_vector is Working Draft, Programming Languages – C++ (N4993), the latest working draft of the C++ standard which can always be found on open-std.org.
  2. The paper initially restricted constexpr support to Ts that are trivial. This was relaxed in a later version of the paper, but was reverted by the time it got merged into the working draft. See [inplace.vector.overview] paragraph 4.
  3. There’s another paper, trivial unions (P3074R4), that proposes to strike paragraph 4 because it introduces language machinery that would enable constexpr support for non-trivial types. The proposed language feature is only available in a particular branch of clang, however.
  4. There are two inplace_vector implementations available and they both have Apache-2.0 WITH LLVM-exception licenses. They’re linked to from here.
1 Like