Re-implementation of `std::tuple` for MCUs

Question

Background

I'm writing code for an 8-bit MCU with very limited RAM (1KiB) and program flash space (64KiB). I have a C++14 capable compiler with no standard library implementation available. This is a good enough excuse for me to do some recreational template programming. :)

In the project where I intend to use this I need to be able to create a densely packed, complex, configurable tuple of varying types and values. And I need this data structure to be stored in program space, so I need it to be usable as constexpr.

About the code

In the code below I have used uint8_t for the size type because the MCU has 8-bit words and an int (which has to be 16 bits to be standard compliant) thus is "extended precision" for my MCU and incurs speed and program size overhead. And frankly, with 1K of ram I'm not expecting to make tuples with more than 255 elements.

The code is put into a single file for your reviewing pleasure and uses std::forward which is technically not available on my target, but I intend to re-implement it as the next step. This code is written for PC first to be able to debug and test it.

I'm happy for any comments on suggestions on the code, but please bear in mind the target architecture.

tuple_test.cpp

#include <iostream>
#include <type_traits>
//#define PACKED_TUPLES
#ifdef PACKED_TUPLES
#define ATTRIBUTE_PACKED __attribute__((__packed__))
#else
#define ATTRIBUTE_PACKED
#endif
namespace xtd {
 namespace detail {
 template <typename...>
 struct ATTRIBUTE_PACKED pack;
 // Helper class to get a value from a pack. 
 // This is required as template functions cannot be
 // partially specialised.
 template <int, typename...>
 struct pack_get;
 template <typename... types>
 struct pack_get<0, types...> {
 static auto get(const pack<types...>& pack) { return pack.value; }
 };
 template <int i, typename first_type, typename second_type, typename... types>
 struct pack_get<i, first_type, second_type, types...> {
 static auto get(const pack<first_type, second_type, types...>& pack) {
 return pack_get<i - 1, second_type, types...>::get(pack.next);
 }
 };
 template <typename type>
 struct ATTRIBUTE_PACKED pack<type> {
 constexpr static int size() { return 1; }
 constexpr pack() = default;
 constexpr pack(type arg) : value(arg) {}
 private:
 const type value;
 template <int, typename...>
 friend struct pack_get;
 };
 template <typename type, typename... types>
 struct ATTRIBUTE_PACKED pack<type, types...> {
 using next_pack = pack<types...>;
 constexpr pack() = default;
 constexpr pack(const type& arg, types&&... args)
 : value(arg), next(std::forward<types>(args)...) {}
 constexpr static int size() { return 1 + next_pack::size(); }
 private:
 const type value;
 const next_pack next;
 template <int, typename...>
 friend struct pack_get;
 };
 } // namespace detail
 template <typename... types>
 using tuple = detail::pack<types...>;
 template <int i, typename... types>
 auto get(const tuple<types...>& tuple) {
 return detail::pack_get<i, types...>().get(tuple);
 }
 template <typename... types>
 constexpr auto make_tuple(types&&... args) {
 return tuple<types...>(std::forward<types>(args)...);
 }
} // namespace xtd
extern constexpr auto p = xtd::make_tuple(3, 3.14, "fooo");
int main(int, char**) {
 std::cout << sizeof(p) << std::endl;
 std::cout << p.size() << std::endl;
 auto x = xtd::get<2>(p);
 std::cout << x << std::endl;
}

• πάντα ῥεῖ: Some warnings for the packed version.
• Emily L.: Thanks, but that's unfortunately unavoidable on PC AFAIK (I'd love to be proven wrong). On the target architecture the fundamental alignment is 1 byte so it won't be an issue there.
• πάντα ῥεῖ: @Emily L. That would be enough and acceptable explanation in a professional code review for me. Just a minor point to mention (hence the comment).
• yuri: By PC you mean x86_64?
• Emily L.: @yuri by PC i mean any machine which has a C++14 compliant compiler with a C++14 compliant standard library.

Answer 1

Good stuff!

improvements:

Your constructors should move the value.

constexpr pack(type arg) : value(arg) {}

vs

constexpr pack(type arg) : value(std::move(arg)) {}

Inconsistent constructor parameter:

Your pack<...> template's constructor's first argument is by reference, whereas your root template takes it by value. Be consistent, pick one. (the one by value with a move is the correct choice here)

This is not actually forwarding:

constexpr pack(const type& arg, types&&... args)
 : value(arg), next(std::forward<types>(args)...) {}

Forwarding is needed when the template deduction can deduce the type of a parameter to be a reference. I.E. the arguments themselves need to be templated. That's not the case here.

You can simply use:

constexpr pack(type arg, types... args)
 : value(std::move(arg)), next(std::move(args)...) {}

Note that your make_tuple() function DOES perform forwarding, so that one is fine.

Get by reference, please.

Your get function returns by value, when a reference would make more sense:

auto get(const tuple<types...>& tuple) {}

vs

const auto& get(const tuple<types...>& tuple) {}
auto& get(tuple<types...>& tuple) {}

make_tuple() should decay the type of its arguments.

Specifically, you should apply std::decay on a per-arg basis so that make_tuple(int&, const float&) returns a tuple<int, float>.

No EBO

Since you seem to care about packing, you should really be performing empty base class optimisation to get the maximum oomph out of your tuple class. This does make the code a lot more complicated though, so if you know for a fact that you'll never pack 0-sized types in a tuple, then I wouldn't bother.

A note on PACKED_TUPLES:

Making this a compile-time switch like this is pretty dicey, as you can eventually run into some nasty binary incompatibilities in the future. I would rather make a complete separate class called packed_tuple<>, and use the compile-time switch in higher-level code so that symbols related to tuple<> and packed_tuple<> remain consistent between binaries. It also allows you to mix packed and unpacked tuples in the same binary which is potentially convenient, since __attribute__((__packed__)) can have a substantial hit on performance.

• Emily L.: Good catch with the return types, I forgot that I have to coerce auto to return a reference. I do not see how EBO applies here. There is no use of inheritance and all of the members of tuple/pack are non-zero sized. With the packed attribute the data structure is dense. Also please keep in mind that this is for an 8-bit MCU, where the word size is 1 byte thus unaligned access doesn't exist, so performance penalty is null.
• user128454: @EmilyL. The idea of EBO here is that if you want to do something like tuple<int, some_trait_type> (which can be useful in some TMP stuff), you can have the tuple be sizeof(int) by stuffing the 0-sized type in EBO'd storage.
• user128454: @EmilyL. With regards to padding: My understanding (and I might be wrong on that...) is that If that's the case, then alignof(T) would always be 1 on that platform, and explicit packing would be pointless. The fact that __attribute__((__packed__)) is not a no-op sort of tells me that it's not quite as simple as you make it out to be.
• Emily L.: On my platform, static_assert(1 == alignof(long), "Align of long is not one!"); holds and the attribute packed is indeed a no-op. I just like to be explicit when I actually require it to be packed as opposed to when it doesn't matter.
• user128454: @EmilyL. In that case, then I'd argue that having a compile-time switch for what amounts to a no-op is just adding fragility for no value. And if you wan to be able to pick and choose what has the attribute attached to it, then it's back to having two types being preferable to a program-wide toggle.

Answer 2

I subscribe to what Frank wrote in his review, I just want to expand a bit on the Empty base optimization and, more generally, on the matter of the lay out.

EBO

As you said, EBO won't bring anything to the table unless your implementation is hierarchy-based, and yours isn't. But I don't believe you should leave it at that, because it's a weakness of your code: you should use a hierarchy-based implementation to benefit from the EBO. In the near future (C++20), you'll have the possibility to do without it, with the new [[no_unique_address]] attribute, but that's not the case yet.

Recursive lay-out

You use a recursive lay-out without inheritance, and I fear it's the worst of both world. Without inheritance, as I said, you don't benefit from EBO, and with a recursive lay-out, you make it really hard, or even impossible, to optimize the padding of your tuple. I don't say you should make it your mission, but if you want to minimize padding, you must be able to uncorrelate the elements' index and position.

What you could do

I've read about an implementation of tuple based on multiple inheritance. I don't remember the details, but the general idea was:

template <typename... Ts, std::size_t... Ns>
class tuple_impl : tuple_element<Ns, Ts>, ... { ... };

You can then find your element back by casting it out:

auto* elem = static_cast<tuple_element<N, Type>*>(this);
...

It also means you can do hairy computations to choose the best lay-out, since the index is part of the types and you don't have to store them in the same order they're declared.

I've looked it up and the implementation I'm talking about is libc++ : https://github.com/llvm-mirror/libcxx/blob/master/include/__tuple

• Incomputable: Lol, that looks like CRTP (about multiple inheritance).
• papagaga: @Incomputable: you're right. It's indexed CRTP!
• user128454: Am I right in thinking that tuple_element here refers to some implementation-detail type, and not std::tuple_element? Otherwise, I'm a little confused.
• papagaga: @Frank: you're totally right. It's just a wrapper that ties an index to the type.
• Emily L.: I didn't mention it but the order of the elements must be the order in which they are defined for my intended use case. Using inheritance the easy way would have inverted the order. This is why I opted not to. And my target architecture is an 8-bit MCU where aligning(T)==1 for all basic types, so padding isn't a thing. As Frank correctly pointed out, the attribute packed is a noop on my target.