Kategori: c++

With the new c++11 a wonderful feature called variadic templates was introduced. This basically means that we can have an arbitrary amount of template argument to our functions or structs in a type-safe way, and have all the argument handling logic resolved in at compile-time.

1: template<typename... Args>
2: void do_something(Args... args)
3: {
4:   //Do something useful
5: }

This means we can any number arguments with any number of types to the function do_something. This is exactly what we want! We want to specify how many AU’s we want to use. But we don’t want to change the LM everytime we want to change something. So lets define it this way.

1: 
2: template< typename... Stations>
3: struct Line
4: {
5: 

The argument Stations is variadic since it doesnt specify how many it is. On the other hand, it needs to be specified at compile time. Meaning we cannot change it with for example, program arguments. But in this design we know how many AU’s we will be using for our production, so its not an issue. But we need to store all the AU’s someway. There are of course several ways of doing this. But since we are looking for an versatile design the Stations can be of many different types. Lets imagine we find a better way of doing the work for some special AU. We could of course created a interface, and implemented inheritance, then we wouldn’t have needed the variadic templates but on the other hand , that would have caused alot of runtime overhead. The interface on the other hand could have been used if we want to change the amount of AU’s during runtime. But thats not what we want, so we are stuck with the variadic templats.

The first thing that comes to ones mind when talking about different types is of course std::variants , but to be honest, i find std::variants to be a pain in the ass. It sure has its benefits and it sure has many useful places it can be used. But for this design, I’m not convinced. How about std::vector or any other container? Well, then we need an interface, and pointers and container aso….. Nop, not my choice. Tuples, on the other hand! A tuple is like a list of types, its perfect, it only has one little caveats, it needs to be defined at compile time..Well, thats not a problem for us. We just said we know how many AU’s we will use at compile time.

Class template std::tuple is a fixed-size collection of heterogeneous values.

Well, thats it! cppreference on tuples. So we take all the Stations and add them to a tuple

 1: 
 2: template< typename... Stations>
 3: struct Line
 4: {
 5: 
 6: 
 7:   Line( Stations... sts):
 8:     assembly_line_(std::make_tuple(sts...))
 9:   {
10: 
11:   }
12: 
13: .
14: .
15: .
16:   /*!< Assembly line with different assembly units */
17:   std::tuple<Stations...> assembly_line_;
18: };

This is the constructor creating a tuple of AU’s see Line 7 and adds them to the struct variable assembly_line_ Line 16 to notice here is that we can actually use the variadic template argument Stations to be the type to the tuple. So we manage to create a list of Assembly unit even if there not the same type. So we need to add some job to the Line manager.

So lets define a method that does that. I will keep this simple to start with, all the AU’s will do the same job. So we need a method that adds a job.

In this implementation all the AU’s will perform the same job, this to keep it simple and understandable. Lets define the method as.

 1: template< typename... Stations>
 2: struct Line
 3: {
 4: .
 5: .
 6: .
 7: 
 8:   template<typename JobT>
 9:   void start_production(JobT const& job)
10:   {
11:     constexpr auto nrAu = std::tuple_size<decltype(assembly_line_)>::value;
12:     start_production_impl<JobT,nrAu-1>(job);
13:     ++job_nr_;
14:   }
15: .
16: .
17: int job_nr_;
18: };

To keep track on what job has been in what AU we add a job_nr Line 17. Its a simple int, and after we start a production on a job, we just increase that number. We also need to know the tuple size, that is how many AU’s is contained in the tuple. Fortunatly the std::tuple_size is part of the standard for more information see tuple_size on cppreference. To quote cppreference:

Provides access to the number of elements in a tuple as a compile-time constant expression.

That means we can obtain the number of elements in the tuple at compile time Line 11. This number can then be used to iterate through the AU’s in the tuple, when one is done we can move on to the next, until the job is finally finished and the coolest thing is that we let the compiler do the iteration since the iteration is on compile time. Though as mentioned before all template arguments needs to be there at compile time. But thats not a problem since thats exactly what tuple_size does. One little problem is that tuple_size needs to know the type of the tuple, so we need to use decltype to get the actual type for the assembly_line_ to be able to get to the size. The next thing to do is to actual call the production implementation, which takes two template arguments, one for the job and one which AU’s to use. Since the size shows the number of elements in the assembly line, we actually want the index of the first AU, thats why we decrease the size by 1 when calling implementation see Line 12, we also need to provide the job which the AU needs to be doing.

As mentioned before the implementation is a template function, which iterates through the job. It will be compile-time recursive, that means the recursion will be done during compile time. Well actually as I understood it the functions with the specific template arguments will be inserted into the code as functions. Lets consider this really simple program.

 1: #include <functional>
 2: 
 3: template< std::size_t N>
 4: void do_something()
 5: {
 6:   int x=1;
 7:   if constexpr( N == 0 )
 8:     return;
 9:   else
10:     do_something<N-1>();
11: }
12: 
13: int main()
14: {
15:   constexpr int i = 3;          
16:   do_something<i>();
17: 
18:   return 0;
19: 
20: }

If we use cppinsight.io and paste that code, and compile it. We get:

 1: #include <functional>
 2: 
 3: 
 4: template< std::size_t N>
 5: void do_something()
 6: {
 7:   int x=1;
 8:   if constexpr( N == 0 )
 9:     return;
10:   else
11:     do_something<N-1>();
12: }
13: 
14: /* First instantiated from: insights.cpp:19 */
15: #ifdef INSIGHTS_USE_TEMPLATE
16: template<>
17: void do_something<3>()
18: {
19:   int x = 1;
20:   if constexpr(3ul == 0) ;
21:   else /* constexpr */ do_something<3ul - 1>();
22: 
23: 
24: }
25: #endif
26: 
27: 
28: /* First instantiated from: insights.cpp:11 */
29: #ifdef INSIGHTS_USE_TEMPLATE
30: template<>
31: void do_something<2>()
32: {
33:   int x = 1;
34:   if constexpr(2ul == 0) ;
35:   else /* constexpr */ do_something<2ul - 1>();
36: 
37: 
38: }
39: #endif
40: 
41: 
42: /* First instantiated from: insights.cpp:11 */
43: #ifdef INSIGHTS_USE_TEMPLATE
44: template<>
45: void do_something<1>()
46: {
47:   int x = 1;
48:   if constexpr(1ul == 0) ;
49:   else /* constexpr */ do_something<1ul - 1>();
50: 
51: 
52: }
53: #endif
54: 
55: 
56: /* First instantiated from: insights.cpp:11 */
57: #ifdef INSIGHTS_USE_TEMPLATE
58: template<>
59: void do_something<0>()
60: {
61:   int x = 1;
62:   if constexpr(0ul == 0) return;
63: 
64: 
65: }
66: #endif
67: 
68: 
69: 
70: 
71: int main()
72: {
73:   constexpr const int i = 3;
74:   do_something<i>();
75:   return 0;
76: }

Here we can see that the do_something function will actually be part of the code 4 times, as template specialization since the compiler knows that we will use it four times. This is the only time I will be using assembler, but to see the assembler might shed even more light on what I mean.

 1: main:
 2:         push    rbp
 3:         mov     rbp, rsp
 4:         sub     rsp, 16
 5:         mov     DWORD PTR [rbp-4], 3
 6:         call    void do_something<3ul>()
 7:         mov     eax, 0
 8:         leave
 9:         ret
10: void do_something<3ul>():
11:         push    rbp
12:         mov     rbp, rsp
13:         sub     rsp, 16
14:         mov     DWORD PTR [rbp-4], 1
15:         call    void do_something<2ul>()
16:         nop
17:         leave
18:         ret
19: void do_something<2ul>():
20:         push    rbp
21:         mov     rbp, rsp
22:         sub     rsp, 16
23:         mov     DWORD PTR [rbp-4], 1
24:         call    void do_something<1ul>()
25:         nop
26:         leave
27:         ret
28: void do_something<1ul>():
29:         push    rbp
30:         mov     rbp, rsp
31:         sub     rsp, 16
32:         mov     DWORD PTR [rbp-4], 1
33:         call    void do_something<0ul>()
34:         nop
35:         leave
36:         ret
37: void do_something<0ul>():
38:         push    rbp
39:         mov     rbp, rsp
40:         mov     DWORD PTR [rbp-4], 1
41:         nop
42:         pop     rbp
43:         ret

Here we see the assembler output and can straight away see that do_something is actually four functions, one for each of the template argument. If we for example forget the if constexpr(N == 0) expression, then the compiler would need to do std::size number of functions, which will make the compilation to crash.

Line 6

The first initial call to do_something<3>()

Line 10

do_something When N == 3

Line 19

do_something When N == 2

Line 28

do_something When N == 1

Line 37

do_something When N == 0

This is exactly the same thing we will do with the start_production_impl, but with some extra salt on it. So lets smack it right in there and try to disect it.

 1: template< typename... Stations>
 2: struct Line
 3: {
 4: .
 5: .
 6: .
 7: .
 8: .
 9: 
10:   template<typename JobT,std::size_t N>
11:   void start_production_impl(JobT const& job, int jobNr)
12:   {
13:     constexpr auto next = N-1;
14:     auto cb = [=]()
15:     {
16: 
17:       if constexpr  (N > 0 )
18:       {
19:         log_->debug("Next AU <{}>",next); 
20:         start_production_impl<decltype(job),next>(job,jobNr);
21:       }
22:     };
23: 
24:     auto F = details::Lamda_wrapper<N>::lambda_wrap(log_);
25:     auto P =F(job,job_nr_,cb);
26: 
27:     details::Process_job< decltype(assembly_line_), decltype(P), N>::
28:       process(assembly_line_,P,jobNr,log_);
29: 
30:   }
31: 
32: .
33: .
34: .
35: .
36: };

Lets start at the top, the template argument JobT is the type of the job that the AU’s are to do. The N is the current AU number, for this implementation the first AU has the highest number, not really intuitive but we just want to keep the code as simple as possible. A job is considered to be a functor.

Functors are objects that can be treated as though they are a function or function pointer.

For this example lets consider the job to be a lambda expression of some sort, no need to dwelve into to much details. The next variable which is defined on Line 13, is the next AU in line, meaning when we done with the current AU, we should use the next which is

$latex next = current-1$

The line manager must know when to pass the current job from the current AU to the next AU. Lets say current AU is 2, then the next AU will be one, but the line manager is not allowed to send the job before the AU[2] is completely done. So somehow he needs to be notified that the work is done from an AU, what better way to do that then let the worker tell him that the job is done by a callback, Line 14. This is a lamda expression using capture by copy. We also see that this callback checks if the next AU is N == 0 in that case it should not do anything. But in any other case it should call recursivly start_production_impl with the next AU number and the job. So we have the callback covered. What next.

Well, to be able to use the callback, we need somehow to wrap the job lambda and the callback lambda into a new lambda. See next section for this.

The problem with the wrapper is that we need to provide the lamda function with values that are current. Consider the fact that we need to provide the right callback functor with the right AU number, I also want the line manager log together with some output for readability. So lets dive into the code.

 1: template< std::size_t N>
 2: struct Lamda_wrapper
 3: {
 4:   static auto lambda_wrap(Logger log)
 5:   {
 6: 
 7:     return [=](auto const fun_org,int job_nr,auto cb)
 8:            {
 9: 
10: 
11:              return [=]() 
12:                     {
13:                       log->debug("AU<{}> working on Job [{}]", N, job_nr );
14:                       fun_org();
15:                       cb();
16:                       log->info("AU<{}> done! [{}]",N,job_nr);
17:                     };
18:            };
19:   };
20: };
21: 

No need to be intimidated, its not as bad as it looks. So whats the deal? Well, the job function needs to be a functor, but the problem is that we want to provide some additional information. In this case its log and a callback function together with the original job functor and not the least the current AU number which can be found Line 1. To be able to do that I’ve created a template function, which returns a lamda function, but this one needs argument Line 7 lets call this the outer. When those arguments are provided, the function will return a new lambda , which has captured all the necessary information that was provided by the outer lambda. In this case we get a new function which is a functor and can be called without any arguments. This is exactly what the following two lines does.

1: auto F = details::Lamda_wrapper<N>::lambda_wrap(log_);
2: auto P =F(job,job_nr_,cb);

The first calls lambda_wrap with log arguments will return the outer lambda functor. But this functor needs arguments, so we provide it with the necessary information, by doing that we will recive a functor which can be called ecplicitly with no arguments. Exactly as we want it. We have now modified the original lambda job and provided logs and a callback. We are now ready to proceed by calling the actual AU and give it our new job. Ok one might wonder why in earth do we need 2 lambdas? Good question and the reason is that auto is not allowed in function prototype, though it is allowed in lambdas. Though one could have passsed it as template arguments. I.e

 1: template< std::size_t N, typename JobT, typename CbT>
 2: struct Lamda_wrapper
 3: {
 4:   static auto lambda_wrap(Logger log, JobT fun_org, CbT cb, int job_nr)
 5:   {
 6: 
 7:     return [=]() 
 8:            {
 9:              log->debug("AU<{}> working on Job [{}]", N, job_nr );
10:              fun_org();
11:              cb();
12:              log->info("AU<{}> done! [{}]",N,job_nr);
13: 
14:            };
15:   };
16: };

Maybe easier to read but the call to the lambda wrap would be.

1: auto P = details::Lamda_wrapper<N,JobT,decltype(cb)>::lambda_wrap(log_,job,cb,job_nr_);

I don’t know , its up to the reader what you prefer, I don’t see any difference in the two ways. Lets move on, the next part is to actually call the workers with our ned lambda. There is one other thing that I hanven’t mentioned that needs to be considered. But I leave this to later in a broader discussion.

to actually retrieve a value/object from a tuple we must use std::get<N>(tuple) the problem with get is that N needs to be known at compile time. I.e

1: auto tupp = std::make_tuple("hello",1,2,3.14);
2: constexpr auto index = 3;
3: std::cout << "Hi: " << std::get<0>(tupp) << " What pi: " << std::get<index>(tupp) << '\n'; //Works fine!
4: int x = 2;
5: std::cout << std::get<x>(tupp) << '\n'; //ERROR!! x is not compile time defined.

As long as index is compile time defined it works fine. So this means we need to pass the N along to the process function.

So how does the process job look like. its fairly simple:

 1: /////////////////////////////////////////////////////////////////////////////
 2: // Process_job - get the right tuple from the assembly and executes the jobid
 3: /////////////////////////////////////////////////////////////////////////////
 4: template<typename Tuple,typename JobT,std::size_t N>
 5: struct Process_job
 6: {
 7: static void process(const Tuple& tp, const JobT& job , int jobId, Logger log)
 8:   {
 9:     auto current_assembly = std::get<N>(tp);
10:     log->debug("Process job {} current AU <{}>",jobId,N);
11:     current_assembly->log_->debug("Im Worker");
12:     current_assembly->addWork(job);
13:   }
14: };

The process_job needs of course the assmembly line. Fair and square, it retrieves the current AU from the assembly unit Line 9. And then adds the modified job (see Production implementation) . The assembly unit will add the job to its queue Line 12 and Voila! When the AU is done a callback will be executed through our modified function if the there is still AU’s to be done then a new call pro process , and a new callback until N=0..

Is there any issues with this implementation? Yes, the callback! The start_production_impl is called from the callback, and every time it is called from a different thread. So is it thread safe? Maybe, im not really sure anymore. But when im not sure lets make it safe instead. By letting the callback post a job from one thread to the manager io context we make sure that whenever the linemanager has time to process the job, it will do it. The job is still done by the Assembly unit though through the Process_job. We also need to add an post from start_production call, to make sure that this is also included in the thread safty procedure. Here is the new thread safe version of program.

 1: template<typename JobT>
 2: void start_production(JobT const& job)
 3: {
 4:   //constexpr auto nrAu = get_nr_AUs();
 5:   constexpr auto nrAu = std::tuple_size<decltype(assembly_line_)>::value;
 6:   io_.post([=]() 
 7:           {
 8:             start_production_impl<JobT,nrAu-1>(job,job_nr_);
 9:             ++job_nr_;
10:             log_->debug("Main is using {}", details::thread_str());
11:           });
12: 
13: 
14: 
15: 
16: 
17: }
18: 
19: 
20: 
21: 
22: template<typename JobT,std::size_t N>
23: void start_production_impl(JobT const& job, int jobNr)
24: {
25:   //auto jobId = job_nr_;
26:   constexpr auto next = N-1;
27:   auto cb = [=]() 
28:   {
29: 
30:     log_->debug( "Callback is called from thread {}",details::thread_str());
31: 
32:     io_.post([=]()  
33:             {
34:               if constexpr  (N > 0 )
35:               {
36:                 log_->debug("Next AU <{}> Current Thread {}",next,details::thread_str());
37:                 start_production_impl<decltype(job),next>(job,jobNr);
38:               }else
39:               {
40:                 log_->info("Production Done for job[{}] Current thread: {}",jobNr,details::thread_str());
41:               }
42: 
43:             });
44: 
45:   };
46: 
47:   auto P = details::Lamda_wrapper<N,JobT,decltype(cb)>::lambda_wrap(log_,job,cb,jobNr);
48:   // auto F = details::Lamda_wrapper<N>::lambda_wrap(log_);
49:   // auto P =F(job,job_nr_,cb);
50: 
51:   details::Process_job< decltype(assembly_line_), decltype(P), N>::
52:     process(assembly_line_,P,jobNr,log_);
53: 
54: }