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
28

Hey folks! If anyone have extra time please come help out at inplace vector : |

Project’s getting attention but we might an extra pair of eyes to go through some of the existing code, I have been busy and I haven’t been able to make everything all neat-and-tidy.

29

@river do you have any particular parts of the code you’d like feedback on?

30

Mainly review work for the new PRs, new folks are coming in the project and contributing, check: Pull requests · bemanproject/inplace_vector · GitHub

@Jeff-Garland @JeffGarland (why is there two jeffs) is being very proactive on helping already.

1 Like
31

We had a license question in this review: Update license by wusatosi · Pull Request #76 · bemanproject/inplace_vector · GitHub

Before we remove the MIT marking…