Deferred caller(or delegator.. whatever you name it) implementation with variadic template

Deferred caller, delegator implementation with variadic template

Recently I started playing with a small toy project – tiny web server with C++. The first requirement I wanted to implement was the ‘static type routing handler’ as shown from the crow project.

Which means, users should be able to register its routing handlers as the following manner:

In order to do that, two things come up to the list:

  1. constexpr string parser to determine the parameter type (e.g <int>, <string>…)
  2. being able to register lambda which can have variadic template arguments

Regarding #2 issue, people would agree it should have been called ‘delegator’ or ‘deferred caller’. Its concept is basically same. Accepts a functor, saves it and calls it later. Then, how can I save functor which can have variadic number and types without using variant?

I got a hint from the Codeproject article, and implemented as follows. The routing_delegator structure is a container owns a pointer to the routing_record interface pointer.

‘to(F&& f)’ is lambda subscribing function. If user tries to pass a lambda to the function, you can figure out the lambda’s parameters by specifying operator() functor signature to a specialized template below. (refer to this SO link)

The typed_routing_recored is the template class, and lambda signature will be deduced, and the typed figured out all will be saved to the std::function.

How about calling the saved functors? The routing_record is an interface and declares one abstract function – which is ‘handle(void*)’. As you might guess from its name, void* is the key point to enable accept variadic sized, typed arguments.

If user calls ‘handle’ with parameters, routing_delegator::handle(Args&&… args) wconverterts those parameters into tuple and passes it to the routing_record::handle(void*) with its address

And finally child class’s handle(void*) implementation will casts into tuple again and delivers it to the actual std::function functor.

You can check out the all code here, https://github.com/heejune/tinyweb-cppserver/blob/develop/router.h

Please be warned, it’s still in development and all experimental code. Thanks!

Heejune.

Sieve of Eratosthenes in C++

Updated June 8th, 2017. This post was introduced to the Reddit /r/cpp soon after I posted and immediately got a feedback saying “both semantically wrong as well as poorly optimized” which is quite true. 🙂  So I’d like to recommend visiting the Reddit link and consider the comments before preceding or even better, refer to the better example introduced here.

Let’s talk about prime numbers. As an application/system software developer, it’s not often to deal with prime numbers in daily working environments. For me, I came across it while solving the Project Euler’s questions.

There’re a lot of good reads on the net describing what prime numbers are, how to get the numbers. So instead of a basic introduction, I’d like to talk about few tricks which can improve the performance of getting prime numbers.

Let’s first talk about the very basic approach to get prime numbers to compare with optimized version later.

You can check whether it’s a prime number or not when a number is given by following:

You’ll also get the Nth prime number based on the isPrime() function above by incrementing the counter when it returns true.

It’s self-descriptive and easy.

Can we improve the performance? Sure! There’s a ‘Sieve of Eratosthenes‘ algorithm, and basically, it does pre-calculate all the non-prime numbers when it found a new prime number by removing all multiples.

Here’s the implementation of the algorithm and its example.

And Lastly, can we improve the Sieve of Eratosthenes algorithm better? Yeah, it’s possible. I first saw the optimized implementation from one of the answers here: http://qa.geeksforgeeks.org/3090/how-to-find-nth-prime-number It’s tricky to understand at first glance in fact. So that I rewrote a little bit and here’s the result:

Comments are still Koreans and will be translated into English soon. Few tricks used to improve the performance are like following:

#1. Check against odd numbers only from line 26 – if (j & 1

#2. Getting the odd number index when an odd number n is given: (n – 3) >> 1

If I changed the unit into ns…

D:\workspace\playground\SieveOfEratosthenes\Release>SieveOfEratosthenes.exe –benchmark_format=json

{

“context”: {

“date”: “06/05/17 01:06:32”,

“num_cpus”: 8,

“mhz_per_cpu”: 2592,

“cpu_scaling_enabled”: false,

“library_build_type”: “release”

},

“benchmarks”: [

{

“name”: “BM_get_nth_prime_without_sieve/10001”,

“iterations”: 160,

“real_time”: 4618235,

“cpu_time”: 4589844,

“time_unit”: “ns”

},

{

“name”: “BM_get_nth_prime_with_basic_sieve/10001”,

“iterations”: 373,

“real_time”: 1854873,

“cpu_time”: 1843164,

“time_unit”: “ns”

},

{

“name”: “BM_get_nth_prime_with_optimized_sieve/10001”,

“iterations”: 1120,

“real_time”: 642190,

“cpu_time”: 655692,

“time_unit”: “ns”

}

]

}

You can access the sample here: https://github.com/heejune/SieveOfEratosthenes

It’ll require the google benchmark and few modifications to correctly link and search headers and libraries to build.

Thanks,

Heejune

Beginning the coroutine with Visual Studio 2015 Update 3 Part 2

As we discussed through Part I, co_wait keyword requires sort of “resumable thing”. So what if we want to use co_await with time delta?

For example, you can see the code which the co_await takes std::chrono::duration in order to suspend for the specified time from here: https://github.com/Microsoft/cppwinrt/blob/master/10.0.14393.0/Samples/JustCoroutines/Main.cpp#L31

The answer is the fact that vc++ compiler allows co_await to be overloaded. So, we can overload the co_await keyword and returns the “resumable thing” within the overloading implementation.

See the code here. https://github.com/Microsoft/cppwinrt/blob/master/10.0.14393.0/winrt/base.h#L8897

If you follow the resume_after(), then you’ll clearly see it actually returns the instance of resumable thing struct which contain implementations of await_ready, await_suspend, and await_resume.

https://github.com/Microsoft/cppwinrt/blob/master/10.0.14393.0/winrt/base.h#L8643

Let’s test with another test sample here. https://github.com/heejune/wrl-cppwinrt-sample/blob/async-support/SampleLib.Shared/DemoCore.cpp#L81

In this sample, I called the winrt’s co_await as the above sample illustrated.

And if I step into the co_await… we hit the overloaded co_await.

part_ii_1

Step in again, then finally it creates resume_after struct instance and calls the await_suspend.

part_ii_2

part_ii_3

It spawns timer thread with specified time, and finally resume_after::callback static callback is being called.

part_ii_3-4png

The callback will finally call resume().

part_ii_4

And the resume() transfers its context into where the co_await being called.

part_ii_5

And lastly, the coroutine function hits the co_return keyword after looping 5 times,

part_ii_6

And reached the end.

Next time, I’d like to talk about another co_await adapter ‘await_adapter’ which makes winrt IAsync.. types possible to be awaitable. Thanks.

Heejune

Building WinRT component with WRL(non C++/CX) and cppwinrt

The cppwinrt project focused to consume Microsoft provided OS winrt components and it doesn’t support building a winrt component(yet) although they mentioned it will be supported later.

Even though it’s not technically supported yet, we still can create a winrt component with WRL(pure C++ and non C++/CX) and still can get some benefits from using cppwinrt within WRL component.

For example, I created a WinRT sample component with WRL and exports IAsyncAction async methods from it. Inside the method, I utilized the cppwinrt provided coroutine method which easily can produce IAsync operations. See the following:

https://github.com/heejune/wrl-cppwinrt-sample/blob/async-support/SampleLib.Shared/DemoCore.cpp

There’s a DemoCore::GetCppwinrtDataasync method defined as this:

It just (detached and) returns the object which also returned from GetAsyncOp private method. GetAsyncOp is a coroutine function which also creates an instance of winrt::Windows::Foundation::IAsyncOperation. And that’s the winrt implementation of IAsyncOperation.

You can download the source project and test it from https://github.com/heejune/wrl-cppwinrt-sample/tree/async-support

Thanks,

Heejune

Beginning the coroutine with Visual Studio 2015 Update 3 Part 1

I recently started using the cppwinrt library which brought chances dealing with the new C++ standard(yet) coroutine. The cppwinrt recommends using C++ coroutines instead of PPL while handling async operations. Refer to the following github issues for more information:

https://github.com/Microsoft/cppwinrt/issues/54

https://github.com/Microsoft/cppwinrt/issues/46

Although the coroutine concept itself might feel coming familiar because we’re already exposed async programming concept much from python asyncio, C# async/await experiences, however the C++ coroutine requires few prerequisite concepts, predefined structures and functions just in order to begin with. I had absolute no idea those, so I decided to start digging in to understand how things orchestrate and work under the hood.

Fortunately, James McNellis from the Microsoft VC++ team had an introductory talk “Introduction to C++ Coroutines” from the cppcon 2016. The talk is great. You really should watch it first if you want to learn the C++ coroutine. However, it feels like a little ambiguous. So that I decided to write actual codes what he had shown from his slides and test it.

So at the very beginning, I created the simplest C++ console project from the Visual Studio 2015 Update 3.

First, changed the warning level,

Typed the simple awaitable function shown from the slide and tried build it.

 

And of course the compiler failed to build and showed the following error:

 

1>—— Build started: Project: resumable-concept, Configuration: Debug x64 ——

1> Skipping… (no relevant changes detected)

1> stdafx.cpp

1> resumable-concept.cpp

1>d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(10): error C3773: please use /await compiler switch to enable coroutines

1>d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(13): error C3774: cannot find ‘std::experimental’: Please include <experimental/resumable> header

1>d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(15): error C3773: please use /await compiler switch to enable coroutines

1>d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(20): error C2228: left of ‘.get’ must have class/struct/union

========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

 

So I added the /await option as the error indicated:

Also included required header files at stdafx.h:

 

And tried build again…….

Succeeded!

 

1>—— Rebuild All started: Project: resumable-concept, Configuration: Debug x64 ——

1> stdafx.cpp

1> resumable-concept.cpp

1> resumable-idea.vcxproj -> D:\workspace\playground\async_research\resumable-idea\x64\Debug\resumable-concept.exe

1> resumable-idea.vcxproj -> D:\workspace\playground\async_research\resumable-idea\x64\Debug\resumable-concept.pdb (Full PDB)

========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========

Let’s see what the co_await actually does in detail:

From the cppcon talk,

He explains that if we use the co_await keyword, the compiler will generate the code shown on the right. Which means in order to work with the co_await keyword, someone should provide the required functions such as await_ready, await_suspend, await_resume, so from the next page it introduces the ‘awaitable_concept’ structure which has the all functions mentioned.

For example, we used the std::future from the first sample, and you’ll see the following snippets if you open the future std header file and search ‘await_ready’ string.

 

If so, how can you make your own type to awaitable to work with co_await instead of using std::future?

From the cppcon talk, James explains it type named ‘resumable_thing’.

Let’s type exactly same code he’d shown us and try build it. I added the ‘resume()’ class method which is not listed from the slide but to work. This is to see what functions exactly required to be implemented to work with co_await keyword.

 

You’ll get following errors when you build the example:

 

1>—— Build started: Project: resumable-concept, Configuration: Debug x64 ——

1> resumable-concept.cpp

1>d:\devtools\vs14\vc\include\experimental\resumable(44): error C2039: ‘promise_type’: is not a member of ‘resumable_thing’

1> d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(9): note: see declaration of ‘resumable_thing’

1> d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(17): note: see reference to class template instantiation ‘std::experimental::coroutine_traits<resumable_thing>’ being compiled

1>d:\devtools\vs14\vc\include\experimental\resumable(44): error C2061: syntax error: identifier ‘promise_type’

1>d:\devtools\vs14\vc\include\experimental\resumable(44): error C2238: unexpected token(s) preceding ‘;’

1>d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(25): error C2440: ‘initializing’: cannot convert from ‘resumable_thing (__cdecl *)(void)’ to ‘resumable_thing’

1> d:\workspace\playground\async_research\resumable-idea\resumable-idea\resumable-concept.cpp(25): note: No constructor could take the source type, or constructor overload resolution was ambiguous

========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Double clicked the first error line to move to exact error location,

1>d:\devtools\vs14\vc\include\experimental\resumable(44): error C2039: ‘promise_type’: is not a member of ‘resumable_thing’

namespace experimental {

    // TEMPLATE CLASS coroutine_traits

    template <typename
_Ret, typename_Ts>

    struct
coroutine_traits

    {

        using
promise_type = typename
_Ret::promise_type;

    };

As you see, the compiler failed to template instantiate coroutine_traits<resumable_thing> because the promise_type is not declared from resumable_thing.

If so, let’s fill up the remaining method implementations as the slide shows:

 

Finally works as expected:

If so, what exactly happening from the ‘counter’ coroutine function returns resumable_thing? From the talk, the slide shows the following pseudo code:

If you’re stepping into the assembly code while debugging, you’ll see similar functions are actually implemented:

First of all, it starts its async operation by calling the ‘InitCoro$1’. If you stepped into the inside ‘InitCoro$1’ function, you’ll see the function implements prologue what the next image suggests as the first three lines:

00B12A41 call std::experimental::_Resumable_helper_traits<resumable_thing>::_ConstructPromise (0B1132Ah)

00B12A46 add esp,0Ch

00B12A49 mov byte ptr [ebp-4],1

00B12A4D lea eax,[ebp-0D1h]

00B12A53 push eax

00B12A54 mov ecx,dword ptr [<coro_frame_ptr>]

00B12A57 push ecx

00B12A58 call std::experimental::_Resumable_helper_traits<resumable_thing>::_Promise_from_frame (0B11217h)

00B12A5D add esp,4

00B12A60 mov ecx,eax

00B12A62 call resumable_thing::promise_type::initial_suspend (0B111EFh)

00B12A67 mov dl,byte ptr [eax]

00B12A69 movzx eax,dl

00B12A6C push eax

00B12A6D mov ecx,80h

00B12A72 add ecx,dword ptr [<coro_frame_ptr>]

00B12A75 call `counter’::`5′::<parameters>::<parameters> (0B11FC0h)

00B12A7A mov eax,dword ptr [__$ReturnUdt]

00B12A7D push eax

00B12A7E mov ecx,dword ptr [<coro_frame_ptr>]

00B12A81 push ecx

00B12A82 call std::experimental::_Resumable_helper_traits<resumable_thing>::_Promise_from_frame (0B11217h)

00B12A87 add esp,4

00B12A8A mov ecx,eax

00B12A8C call resumable_thing::promise_type::get_return_object (0B11479h)

00B12A91 mov dword ptr [ebp-4],2

00B12A98 mov ecx,80h

00B12A9D add ecx,dword ptr [<coro_frame_ptr>]

00B12AA0 call std::experimental::suspend_never::await_ready (0B11348h)

00B12AA5 movzx eax,al

00B12AA8 test eax,eax

00B12AAA je counter$_InitCoro$1+0CAh (0B12ABAh)

00B12AAC mov ecx,dword ptr [<coro_frame_ptr>]

00B12AAF push ecx

00B12AB0 call counter$_ResumeCoro$2 (0B12B70h)

00B12AB5 add esp,4

00B12AB8 jmp counter$_InitCoro$1+103h (0B12AF3h)

}

It first creates the Promise instance:

00B12A41 call std::experimental::_Resumable_helper_traits<resumable_thing>::_ConstructPromise (0B1132Ah)

The function creates it by calling the std::experimental::_Resumable_helper_traits<resumable_thing>::_ConstructPromise(void *, void *, int) function which is implemented at “\VC\include\experimental\resumable”

If you open the file and see the code,

        static
void _ConstructPromise(void *_Addr, void *_Resume_addr, int
_HeapElision)

        {

            *reinterpret_cast<void **>(_Addr) = _Resume_addr;

            *reinterpret_cast<uint32_t *>(reinterpret_cast<uintptr_t>(_Addr) +

                                         sizeof(void *)) = 2 + (_HeapElision ? 0 : 0x10000);

            auto _Prom = _Promise_from_frame(_Addr);

            ::new (static_cast<void *>(_Prom)) _PromiseT();

        }

It instantiates the promise_type which is defined within resumable_thing from our example. After instantiated, initial_suspend() will be executed as the deck explained.

As a next step, resumable_thing::promise_type::get_return_object() will be called. The resumable_thing instance is getting created from this get_return_object().

The prologue pseudo code explained that _promise.initial_suspend() will be called as a next step, and from the our example, the resumable_thing::promise_type::initial_suspend() returns suspend_never{}. So suspend_never::await_ready is getting called as next.

Finally, if we step into the function counter$_ResumeCoro$2(void) which is below:

There exists actual counter() function implementation if we stepped into resumeCoro. Later when the the_counter.resume() ran, Instruction Pointer is transferred same as if the resumeCoro ran.

Next time, let’s see how the cppwinrt overloads co_await operator and utilize it.

Part II

[C++/Cx] How can I get the AsyncOperationWithProgress progress?

Windows Runtime provides the HttpClient class along with async APIs. For example, you can send a GET request through the GetAsync(Uri) method.

GetAsync() method is an awaitable API so that it returns IAsyncOperationWithProgress<HttpResponseMessage, HttpProgress>^. You will get the HttpResponseMessage by specifying the IAsyncOperationWithProgress to Concurrency::create_task(). However, how can I get the progress?

There’s no direct answer from MSDN but gives a hint here:

You just supply the delegate for the object’s Progress property

Here’s the snippet:

Generating assembly output from msvc and CMake

Sometimes it’s needed or you may require to see the assembly output listing of a C++ snippet code just for the testing purpose. Testing yourself with Jason Turner’s session might be the example.

If you’re using a msvc with Windows environment, then it’s quite easy by running the simple command line argument:

Let’s say we have an optimizaing.cpp as following:

#include <string>

int main()

{

    std::string s(“a”);

    return s.size();

}

Launch the build environment and run the cl.exe with a ‘/FA’ parameter.


cl /EHsc /nologo /W4  optimizing.cpp /FAs /GL /O2


CMake also automatically adds the target generating assembly output and it’ll be also a good choice when you’re not using msvc.

Let’s say if we have the following CMakeLists.txt,

project(demo)

cmake_minimum_required(VERSION 3.1)

#—————————————————-

# Flags

#—————————————————-

set(CMAKE_CXX_STANDARD 14)

add_definitions(-DCMAKE_EXPORT_COMPILE_COMMANDS=1)

#—————————————————-

# Executable

#—————————————————-

add_executable(optimizing “optimizing.cpp”)


You can generate the build files. I use theMinGWw g++ toolchain here.

cmake -G “MinGW Makefiles” -DCMAKE_BUILD_TYPE=RELEASE ..


Then you’ll see the target.s for the assembly output. For example, the generated Makefile contains ‘optimizing.s’ here.


You’ll finally get the assembly output listing by running make target.s as below:


 

Thanks,

Heejune