Fun with templates

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Fun with templates

Post by albinopapa » January 20th, 2022, 8:13 am

Haven't posted my usual random stuff in some time, but here's what I've been up to.

Code: Select all

template<typename...Ts>
struct list {
	using type = list<Ts...>;
	static constexpr auto size = sizeof...( Ts );

	using empty = std::conditional_t<size == 0, std::true_type, std::false_type>;
	static constexpr bool is_empty_v = empty::value;

	struct front {
		static_assert( size > 0, "Cannot get front(), list is empty." );
		template<typename U, typename...Us> struct helper {
			using type = U;
		};

		using type = helper<Ts...>::type;
	};

	template<typename T> struct push_back {
		using type = list<Ts..., T>;
	};
	template<typename T> struct push_front {
		using type = typename list<T, Ts...>;
	};

	struct pop_back {
		template<typename List, typename U, typename...Us> struct copy_pop_ {
			static constexpr auto count = sizeof...( Us );
			using next = typename List::template push_back<U>;

			using type = std::conditional_t<
				count == 0,
				List,
				typename copy_pop_<typename next::type, Us...>::type
			>;
		};

		using type = copy_pop_<list<>, Ts...>::type;
	};

	struct pop_front {
		static_assert( size > 0, "List is empty, cannot pop_back." );


		template<typename U, typename...Us> struct copy_after_front_ {
			using type = list<Us...>;
		};

		using type = copy_after_front_<Ts...>::type;
	};

	template<typename Other> struct cast {};
	template<template<typename...> typename Other> struct cast<Other<>> {
		using type = Other<Ts...>;
	};
	
	template<typename T>
	struct holds_type {
		static constexpr bool value = std::disjunction_v<std::is_same<T, Ts>...>;
	};

	template<std::size_t idx_>
	struct get_member {
		static_assert( idx_ < sizeof...( Ts ), "Index out of range." );

		template<std::size_t count, typename...Us> struct helper {};
		template<std::size_t count, typename U, typename...Us> struct helper<count,U,Us...> {
			using type = std::conditional_t<
				count == idx_,
				U,
				typename helper<count+1, Us...>::type
			>;
		};
		template<std::size_t count, typename U>
		struct helper<count, U> {
			using type = std::conditional_t<count == idx_, U, void>;
		};

		using type = helper<0, Ts...>::type;
	};
};
Here we have a list type. This list type has many features:
  • Check for empty
  • Get the size of the list
  • Get the front or first element in the parameter pack
  • Extend the list using push_front/push_back
  • Shrink the list using pop_front/pop_back
  • Cast list<T...> to another template type that allows multiple types ( std::variant for instance )
  • Check if a type is in the parameter pack using holds_type
  • Get the type of a parameter using an index
You might notice a couple things.
  1. There are no data objects
  2. All the functions are structs
This isn't a runtime list, it's a compile time list. I originally created this thing as a utility for a project I was working on way back in 2016 or 2017. It was around the time Chili was working on his software 3D Framework. He used templates to simulate DirectX shaders. One drawback to his method was with each new vertex you created, you'd have to write operator overloads for +=, -=, *= and /= at the very least. The reason for this is because he needed a way to interpolate between two vertices. Since each new vertex type might hold unknown data members ( one only requiring position and color, another requiring position and texture coordinates, etc...).

Well, I can't leave well enough alone and decided to learn how these templates worked and figure out if there is a way to 'cheat'. Here it is 2022 and I'm back at it.

With this list class, you can describe the vertex you intend to use.
using ColorVertexMembers = list<Vec3, Vec4>;
using TextureVertexMembers = list<Vec3, Vec2>;

The C++ standard library has something a little similar called std::tuple. One thing std::tuple does different is it actually creates storage space for each of the types in it's template parameter list. You even access it's 'members' using indices like my list<> class. What I've done different besides not creating storage is adding functionality to the class itself. Unfortunately, there is a drawback...and it's ugly. Say you wanted to get element 0 from an std::tuple:

Code: Select all

using my_tuple_struct = std::tuple<Vec3, Vec4>;
auto& first_member = std::get<0>( my_tuple_struct );
With my class with nested types acting as functions:

Code: Select all

using my_list_struct = list<Vec3, Vec4>;
using first_member_type = typename my_list_struct:: template get_member<0>::type;
Not very pleasant, I know, but that's how you access a nested templated type. Well, I don't think typing all that each time you wanted to access a member, so I made an alias:

Code: Select all

template<std::size_t idx_, typename List>
using list_get_member_t = typename List::template get_member<idx_>::type;
So now it's:

Code: Select all

using first_member_type = list_get_member_t<0, my_list_struct>;
Yes, I made aliases for each of the pseudo functions.

So what's the point? This just tells me the type of each member in some hypothetical struct. Well, I made a companion class that utilizes this list class.

Out of fear something goes wrong, I'm going to break up posts.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Fun with templates

Post by albinopapa » January 20th, 2022, 8:50 am

Here's the companion class and a specialization.

Code: Select all

template<std::size_t alignment_, typename...Ts>
class tuple_like {
public:
	using member_list = list<Ts...>;
	using element_type = list_to_variant<list<Ts...>>::type;
	using storage = std::array<element_type, m_member_count>;

public:
	constexpr tuple_like()noexcept = default;
	constexpr tuple_like( Ts... values_ )noexcept
		:
		m_members{ std::forward<Ts>( values_ )... }
	{}

	static constexpr std::size_t count()noexcept { return m_member_count; }
	static constexpr std::size_t size()noexcept { return m_size; }
	static constexpr std::size_t alignment()noexcept { return m_alignment; }

	template<std::size_t element_id> constexpr auto member()const
		->list_get_member_t<element_id, member_list> const&
	{
		static_assert( element_id < m_member_count, "Invalid element_id." );
		using type = list_get_member_t<element_id, member_list>;

		return std::get<type>( m_members[ element_id ] );
	}
	template<std::size_t element_id, typename T> constexpr void member( T const& val ) {
		std::get<T>( m_members[ element_id ] ) = val;
	}

private:
	static constexpr auto m_member_count = sizeof...( Ts );
	static constexpr auto m_alignment = alignment_;
	static constexpr auto m_size = get_aligned_size_of_v<m_alignment, Ts...>;
	alignas( alignment_ ) storage m_members;
};

Code: Select all

template<typename...Ts>
class tuple_like<0, Ts...> {
public:
	static constexpr auto m_member_count = sizeof...( Ts );
	using member_list = list<Ts...>;
	using element_type = list_to_variant<member_list>::type;
	using storage = std::array<element_type, m_member_count>;

public:
	constexpr tuple_like()noexcept = default;
	constexpr tuple_like( Ts... values_ )noexcept
		:
		m_members{ std::forward<Ts>( values_ )... }
	{}
	constexpr tuple_like( const tuple_like& ) = default;
	constexpr tuple_like( tuple_like&& ) = default;


	static constexpr std::size_t count()noexcept { return m_member_count; }
	static constexpr std::size_t size()noexcept { return m_size; }
	static constexpr std::size_t alignment()noexcept { return m_alignment; }
	static constexpr auto make_index_sequence() {
		return std::make_index_sequence<count()>{};
	}
	template<std::size_t element_id> constexpr auto member()const
		->list_get_member_t<element_id, member_list> const&
	{
		static_assert( element_id < m_member_count, "Invalid element_id." );
		using type = list_get_member_t<element_id, member_list>;

		return std::get<type>( m_members[ element_id ] );
	}
	template<std::size_t element_id, typename T> constexpr void member( T const& val ) {
		std::get<T>( m_members[ element_id ] ) = val;
	}

private:
	static constexpr auto m_alignment = get_natural_alignment_v<Ts...>;
	static constexpr auto m_size = get_aligned_size_of_v<m_alignment, Ts...>;
	std::array<element_type, m_member_count> m_members;
};
They are very similar, actually they're pretty much the same with the exception of the template parameters. In the first version, you pass in the alignment you want for each member. In the second one, I was hoping to pass in a default value and not have to pass in alignment and have the compiler figure it out using some helper classes I made. For now, to get the compiler to use the helper classes, you have to pass in 0 for alignment.

I had two options here, use std::tuple as the storage data type or do what I did here and combine std::array and std::variant, I don't think I could have used std::any for this since I think std::any only holds one type at a time. Std::array also only holds one type at a time, and std::variant works out to allow multiple types as long as each type is unique to that variant. In other words, <float,int,double> will work, but <float,float,int> would not.

To rectify the requirement of std::variant I created a helper class:

Code: Select all

template<typename List> struct list_to_variant {
	using unique_list_ = list_make_unique_t<List>;
	using type = typename make_variant<unique_list_>::type;
};
And of course, more helper classes:

Code: Select all

template<typename List1> struct list_make_unique_ {	
	template<typename out_list, typename in_list> struct helper {};
	template<typename out_list, typename U, typename...Us> 
	struct helper<out_list, list<U,Us...>> {
		static constexpr bool holds_type_ = list_holds_type_v<out_list, U>;
		static constexpr auto is_last = sizeof...(Us) == 0;
		
		using in_list = list<U, Us...>;
		using next_out_ = std::conditional_t<holds_type_, out_list, list_push_back_t<out_list, U>>;
		using next_in_ = std::conditional_t<is_last, in_list, list_pop_front_t<in_list>>;

		using type = std::conditional_t<is_last, out_list, typename helper<next_out_, next_in_>::type>;
	};
	template<typename out_list, typename U>
	struct helper<out_list, list<U>> {
		using type = std::conditional_t<
			list_holds_type_v<out_list, U>,
			out_list,
			list_push_back_t<out_list, U>
		>;
	};

	using type = helper<list<>, List1>::type;
};

template<typename List>
using list_make_unique_t = list_make_unique_<List>::type;

#include <variant>
template<typename List> struct make_variant {
	using type = typename List:: template cast<std::variant<>>::type;
};
That list_make_unique struct was a pain in the arse. Took me like 20 hours to get it working.

As the names imply, one takes a list<> class and only copies over elements that aren't in the resulting list and make_variant takes a list<> class that has already been stripped of duplicate types and presents an std::variant<...>;

Using the tuple_like class, I can get the number of 'members' by calling object.count(). Tuple_like::count() is a static constexpr function, so you don't have to create an object to access it either.

Code: Select all

using my_tuple_struct = tuple_like<float, int, double, float, float, char>;
constexpr mts_count = my_tuple_struct::count();
Accessing members:

Code: Select all

auto mts_object = my_tuple_struct{};
auto const& member0 = mts_object.member<0>();
To modify a member, you must call mts_object.member<N>( value ). The 'N' represents the nth element in the template parameter list and the value is deduced by the compiler which allows me to use std::get<T>( m_members[N] ). Since std::variant requires it's template parameters to be unique, you can use std::get<T> instead of std::get<N>. The T means any type like 'x' in algebra. The 'N' in this case is an index into the array holding the members.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Fun with templates

Post by albinopapa » January 20th, 2022, 9:24 am

One of the things I find myself doing is making small simple utility functions or in this case, classes and pseudo functions that I can use to build something more complex. While a lot of those utilities probably aren't useful outside of this domain, it helps making the complex things simpler and easier to understand...assuming you understand template meta programming and fold expressions.

Now, putting it all together to do what I originally intended to use it for...shaders. Not just the Chili 3D Framework or similar, but also something that's been on my mind for about the same amount of time. One of the other draw backs to chili's 3D framework is the nontrivial amount of work it would take to implement SIMD instructions, especially if you wanted to support multiple versions: SSE through SSE4.2 or AVX/AVX2/AVX512 or even ARM Neon. You'd have to write several versions of each vertex type.
  • x86_64
  • SSE
  • SSE2
  • SSE3
  • SSSE3
  • SSE4.1
  • SSE4.2
  • AVX
  • AVX2
  • AVX512
  • ARM Neon
I'm thinking "Hell nah". On top of that, there are alignment requirements for each. The SSE version types are all 128 bit, AVX and AVX2 are 256 bit, AVX512 is 512 bit ( 16, 32 and 64 byte alignment requirements ).

So what other shaders might I be talking about? That would be compute. A compute shader is more general than say a vertex shader or pixel shader you'd find in Direct3D. My goal is to create a template based compute shader that automatically chooses which set of SIMD instructions to use based on CPU capabilities of the hardware it's run on. The user would need to setup the templated shader, using the tuple_like class for the input and output buffers. This will give the user and the library a common interface.

The shader library will accept an std::vector<tuple_like<...>> as it's buffer type ( haven't actually planned that far ahead so may change ).

The user will need to pass in by template parameters a list of instructions that are then forwarded to one of the math operations associated with the capabilities of the architecture.

Once the buffers and shader description have been passed, the library will load the input buffer data into a memory pool, the instructions will be executed then the data will be stored into the output buffer and returned.

Depending on how this is implemented, I think it could be pretty useful to get some extra speed out of your processor and not have to write several different versions of the same code.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

FirepathAgain
Posts: 30
Joined: March 20th, 2021, 3:01 am

Re: Fun with templates

Post by FirepathAgain » February 5th, 2022, 1:52 am

I did a crazy thing with conditional templates to make some random ranges of different types without duplicating the code for them.

So I have random ranges for floats and ints, in uniform, normal, and log normal distribution types all boxed up in a single template. It was a fun exercise but I don't think I'd like to do it again lol. If the need came where it would be really useful or wasn't sooo complicated (maybe two or three single options) it would be worth it.
Attachments
conditional_templates.PNG
(63.56 KiB) Not downloaded yet

FirepathAgain
Posts: 30
Joined: March 20th, 2021, 3:01 am

Re: Fun with templates

Post by FirepathAgain » February 5th, 2022, 1:55 am

Man I'll have to look into your template stuff more. I thought the conditional thing was complicated but there is more going on in your stuff than I have done or know about and I've only seen it a couple of times.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Fun with templates

Post by albinopapa » February 8th, 2022, 9:54 am

For some reason the forum doesn't like me quoting or posting images, so I just respond like this:

Conditional templates
I keep forgetting you can use enums as non-type template parameters the same way you can use integers. Chaining conditional statements sucks for readability. I usually have to use indentation like I would with normal code.

Code: Select all

template<RangeDistributionType D, class T>
using type = 
std::conditional_t<
    D == RangeDistributionType::Normal, 
    std::conditional_t<std::is_floating_point_v<T>, std::normal_distribution<T>, void>,
    std::conditional_t<
        D == RangeDistributionType::Uniform,
        std::conditional_t<
            std::is_floating_point_v<T>,
            std::uniform_real_distribution<T>,
            std::conditional_t<std::is_integral_v<T>, std::uniform_int_distribution<T>, void>
        >,
        std::conditional_t<
            D == RangeDistributionType::LogNormal,
            std::conditional_t<std::is_floating_point_v<T>, std::log_normal_distribution<T>, void>,
            void
        >
    >
>;
Of course, I'd probably not go that route to begin with. I'd probably create some utility structs to clean it up.

Code: Select all

#include <concepts>
template<class T>
concept uniform_type = std::disjunction_v<
    std::is_floating_point<T>,
    std::is_integral<T>
>;

namespace WFUtility{
enum class RangeDistributionType{
    Normal, Uniform, LogNormal
};

template<RangeDistributionType, class T> struct DistributionHelper;
template<std::floating_point T> struct DistributionHelper<RangeDistributionType::Normal, T>{
    using type = std::normal_distribution<T>;
};

template<uniform_type T> struct DistributionHelper<RangeDistributionType::Uniform, T>{
    using type = std::conditional_t<
        std::is_floating_point_v<T>,
        std::uniform_real_distribution<T>,
        std::uniform_int_distribution<T>
    >;
};

template<std::floating_point T> struct DistributionHelper<RangeDistributionType::LogNormal, T>{
    using type = std::lognormal_distribution<T>;
};

template<RangeDistributionType D, class T>
using Distribution = DistributionHelper<D,T>::type;
}
I cheated a little using 'concepts' from C++20. The std::floating_point is a standard library concept only allowing floating points and the one I made uniform_type restricts the helper to floating point and integral types. In this way, you don't have to assign void to the type.

I prefer using helpers, they add a lot of code, but removes a lot of complexity to the final product.

Also, I'd like to point out, you don't have to use typename when the expression ends in ::value since value isn't a type. As you can see, starting in C++17 a lot of the library has added convenience types and constexpr values either ending in _t for types and _v for values.
std::is_integral<T>::value -> std::is_integral_v<T>.

Regarding my template post
I have been practicing off and on with templates for a few years now. When I first saw someone post a butt load of template metaprogramming here, I said "wow...nope F that". Then I started getting to the point where I saw how useful it was when chili made his software 3D Framework and I was hooked. As I mentioned, I like using helpers. Sometimes there necessary, sometimes their just there for ease. For instance, when you want to expand a parameter pack, you HAVE to use helpers. A parameter pack is when you see:
template<typename...Ts>
The 'Ts' is the pack. If you are wanting to expand that to evaluate all the parameters that were pass, you'd have to use a helper since you can't index into it as is.

The list<> template was probably the most fun for me because it was pretty challenging. Not creating a list of types, but adding the push and pop helpers. I wanted to remove duplicates from a list<> so I could convert a list<> to an std::variant<> which has the requirement that all the types in the parameter pack have to be unique. So that is when the push/pop pseudo functions came into being. The microsoft STL implementation has this type as well, but it's not for general use. It's there for the library maintainers to use and could change or be removed entirely, so I wanted to make my own.

There are some down sides to my 'tuple_like' struct there. The biggest is you have to access everything by index according to the list order. Also, there is some waste in memory footprint. Each std::variant<> object has storage space for the largest type ( uses a union as storage ) and another byte or larger to store the index of the active type in the variant. If the variant has less than 255 types in the parameter pack, then it's only a byte. More types requires a larger type so more wasted space. So even for four floats in my tuple_like struct, it requires ( ( 4 + 1 ) * 4 ) 20 bytes for the tuple_like object instead of 16 for a struct holding 4 floats. I thought about doing some manual memory manipulation, but that means no constexpr support. Not that it's needed, and I don't know the performance details of using this as is or manual memory manipulation yet.

Anyway, it's always fun having a chat.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

FirepathAgain
Posts: 30
Joined: March 20th, 2021, 3:01 am

Re: Fun with templates

Post by FirepathAgain » February 8th, 2022, 9:18 pm

I tried indenting the conditional things but VS just wrecks it all at some point afterwards anyway reformatting it how it likes so I leave it how you see it lol.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Fun with templates

Post by albinopapa » February 8th, 2022, 10:59 pm

Yeah, there is a setting that formats when you press TAB or when you type '}' or ';'.
The TAB thing is pretty annoying since it's a pretty common button to press and it formats the entire document. The '}' formats the current scope/block and the ';' formats the current line/statement. I disabled the TAB formatting, but left the other two on as more often than not it does what I want it to do. There are a few exceptions like template parameter indentation and braced initialization. For those instances, I usually either put the end brace, angle bracket or semi-colon first and manually format, or let VS format it as is and manually change it afterward.

You can find those settings in Tools/Options, but beyond that I don't remember exactly where.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply