«

»

Oct 03

Heterogeneous vector in c++ – overview of common approaches

So, you are wondering about heterogeneous vector in c++?
Maybe even dare to dream about any suitable substitution of such non-existent container?
In another word, you need a generic-like container that can store different datatypes.

If you just need a quick answer – stick with std::vector < boost::any> approach or read this,
If you need more technical-rich overview of purely templated solution – scroll down to links part,
If you are wondering about other options and don’t mind to dive in a world of bad English grammar and details about one of my recent task – read on.

heterogeneous container in c++

So, you want a heterogeneous container in c++…

First ask yourself – do you really need a heterogeneous vector?
If your answer is – yes, I have a bad news for you – in 99.9 percent it’s just consequences of messy design.
However, I am sure you are here for the sake of that one exceptional case: for example – your task is providing intermediate peace of software for interaction with some 3rd party old-fashion engine.

In my case – I was trying to implement convenient way of operating variable length list of parameters for OpenCL kernel wrapper.

If you are not familiar with mechanism of interaction of OpenCL code with C++, there are only one problem (sarcasm!) – it is too verbose. Off course there are numerous third party wrappers – http://streamcomputing.eu/knowledge/for-developers/opencl-wrappers/ but in situation where even NVidia drivers sometimes do not support all features from those-before-the-last standard,
I am afraid to think about cases when you have to deal with additional layer of external api.
Yeah, lets think about your own implementation because development of your own bugs is very entertaining and educational. It’s time consuming as well as terrible error-prone but you can narrow desired functional for your needs and be sure that all issues are made by you.

OpenCL kernels are compiled independently of host code, so you do not have any standard approaches for checking whether arguments provided to kernel have appropriate types and whether their amount corresponds to definition of kernel. It means that:
1) In case you are too lazy to somehow analyze every OpenCL kernels you can’t check how many arguments is necessary for particular kernel
2) You can’t check whether provided arguments have proper data type without any external parser

As a consequence, in general, my wrapper should be able to deal with variable length array of arbitrary any-type parameters.

(NOTE: Yeah, I’m familiar with undocumented c++ wrappers based on variadic templates, but it force you to follow their low-level nature by falling down from level of domain-specific objects to operating in terms of POD types.)

From that brief idea, I conclude that my goal was:

vector < gpu_arg > kernel_args;

where gpu_arg is a class that can encapsulate any data types – built-in as well as a user-defined.
Who have mentioned templates? How to create vector that can hold any templated parameter? (we discuss it a bit latter)

I approach – return to the ancient times
The most straightforward way – forget about C++ and rely on encapsulation of data into void* pointers with numerous C-way casting:

struct gpu_arg
{
  void* data;
  size_t size;
  // numerous helper methods here
  // NOTE: you have to add some kind of type_id to deal with data in proper way
};

I.e. kernel parser report that there should be following parameter set:

float, int, custom_class *

and when you start adding parameters it treat them as predefined types (with or without your own additional datatypes checks).

As an advantage of such idea – we can easily use it in run-time.
In addition, this solution is error-prone and can lead to cruel punishment during any code review.

II approach – std::tuple and variadic templates
On the other hand – in many cases when you are not keen to find a perfect silver bullet you may find helpful to simplify task. In order to check argument’s types you have to preprocess kernel, so you can form an expected parameter list. If you perform this operation during compilation of host-side code, you may use acquired parameter list to simplify code-generation task.
I started investigation of possible approaches and find out that the most obvious solution would be based on std::tuple:

// this C++11 container allows creation custom container like this:
std::tuple < int, int, bool, float *, unsigned short * > parameters_set;

or encapsulate it in a class with some syntax sugar for convenience:

template < typename ...T >
class arguments_set
{

    std::tuple<T...> data;
    template< size_t I >
    using data_type = typename std::tuple_element<I, decltype(data)>::type;

    /*
     *      variadic-based routine for initialize every element of tuple
     * */
   	template < std::size_t I = 0, typename TT >
	void
	init ( TT & arg )
	{
        std::get<I>( data ) = arg;
	};

	template < std::size_t I = 0, typename TT, typename ...Args>
	void
	init ( TT & arg, Args ... args )
	{
		init <I,TT> ( arg );
		init <I+1,Args...>( args ... );
	};

public:

    template<typename... Ts>
    arguments_set(Ts... args) {
       init <0,Ts...> ( args... );
    };

    template < std::size_t I = 0>
    constexpr
    auto get ( ) -> data_type<I>
    {
        return std::get<I>(data);
    }

};

Argh templates, well, who care about compiler’s effort to parse all this fluff?
Despite of convenience of variadic templates constructor, template metaprogramming is not easy to deal with during maintenance phase (as well as during developing).
On the other hand, it provides a desired result – strong type-checking combined with ability to generate variable length list of parameters.

So, solution was:
1) run pre-processor for OpenCL kernels in order to generate proper tuple for method invocation
2) compile the whole module

It is can be a solution in situation where you are not intend to run this mechanism in run-time.
(because it mean you have to dynamically extend templated class tuple objects)
Not my case.
Idea of pre-compiled kernels (PTX) sound great, but reality is sad – mess of drivers, hardware and vendor’s ambitions lead to incompatibility of generated binaries in general case. Not usable for me :(.
(But hope springs eternal – if you are lucky enough you can play with CL_CONTEXT_OFFLINE_DEVICES_AMD, http://clusterchimps.org/ocltools.php, http://www.browndeertechnology.com/coprthr.htm )

III approach – type erasure

Ok, let’s return to my preconditions once again:
1) I need type checking – template?
2) I need it in run-time – maybe some virtual stuff?!

What if I declare interface of argument as an abstract class and inherit it as a templated child with proper data fields

i.e.:

// pure abstract class
// in case of necessity can be further divided on pure interface\data-fields parts

class gpu_arg_base {
  /*
   *  interface part that depend on child's template parameter = a lot of virtual functions
   */
  /*
   *  common data fields with ordinary setters\getters methods
   */
}

template < typename T>
class gpu_arg : gpu_arg_base {
  /*
   * explicit override of interface with possible overloading
   */
  gpu_arg ( T* init_data);
  private:
    T *data; // NOTE: just a reference to data, no allocation\de-allocation!
};

It allow me to use them in following way:

class kernel_wrapper {
    vector <gpu_array_base*> kernel_params;
     /* some stuff here */
    public:
        // variadic template functions to deal with any number of parameters
        template < typename T>
	void
	add_kernel_args ( T * arg )
	{
		add_kernel_arg ( arg );
	};

	template <typename T, typename ...Args>
	void
	add_kernel_args( T * arg, Args ... args )
	{
		add_kernel_arg ( arg );
		add_kernel_args ( args ... );
	};

        // generating of proper function for particular type
        template<class T>
        void add_kernel_arg( T * host_data )
        {
	        gpu_arg_base* new_arg = new gpu_arg<T> ( host_data );
		kernel_params.push_back( new_arg );
        };

     /* interface part */
}

But be careful with this easy-looking approach – there are two main issues which can affect your mood and calmness.
First, read about differences between overriding and hiding of methods in inheritance hierarchy here or here. It is a great source of confusion, especially during investigation of fresh bug-reports.
Second, do not forget about “covariant return type” rules – http://aycchen.wordpress.com/2009/08/17/covariant-return-type-in-cpp/.
Great article about possible caveats and workaround can be found there:
http://nerdland.net/2009/06/covariant-templatized-virtual-copy-constructors/

After reviewing all solutions described above, you may find that you accept additional dependency in exchange for absence of disastrous side-effects of your implementation.
boost::any or boost::variant can be a proper choice.

PS. Actually, I suspect that using tuples and dark magic of template metaprogramming, you can save few ticks of processor’s time by abandoning inheritance and virtual table, but as usual during development we have to balance between concept of the perfect code and requirements of too fussy world.

LINKS:

Example of heterogeneous container ( deeply nested approach)
www.codeproject.com/Articles/23304/High-Performance-Heterogeneous-Container

Interesting practical example of tuple usage for ORM-like engine:
http://javol.wordpress.com/2009/08/06/type-safe-table-container-using-variadic-templates/
Some practical aspects of using tuples:
http://stackoverflow.com/questions/1198260/iterate-over-tuple
http://stackoverflow.com/questions/15411022/how-do-i-replace-a-tuple-element-at-compile-time
http://stackoverflow.com/questions/7858817/unpacking-a-tuple-to-call-a-matching-function-pointer

Using variadic templates to initialize tuples or other way round:
http://stackoverflow.com/questions/10014713/build-tuple-using-variadic-templates
http://stackoverflow.com/questions/21413045/variadic-variable-initialization-for-variadic-template
http://stackoverflow.com/questions/687490/how-do-i-expand-a-tuple-into-variadic-template-functions-arguments

Any class in c++:
http://codereview.stackexchange.com/questions/20058/a-c11-any-class
www.codeproject.com/Articles/11250/High-Performance-Dynamic-Typing-in-C-using-a-Repla

Illustration of variadic templates usages for generating C++11 variant class:
http://thenewcpp.wordpress.com/2012/02/15/variadic-templates-part-3-or-how-i-wrote-a-variant-class/

Hands-on experience with tuples:
http://yapb-soc.blogspot.ru/2012/12/fun-with-tuples.html
http://yapb-soc.blogspot.ru/2012/12/zipping-and-mapping-tuples.html

1 comment

  1. Ghanshyam

    Nice article !! clear concise coverage of literature.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>