JIT Compiler for URI Templates (C++/Xbyak)

URI Templates ( http://bitworking.org/projects/URI-Templates/ ) provides the methods to generate similar URIs.

For example, a template “/weather/{state}/{city}?forecast={day}” means that it has 3 parameters “state”, “city” and “day”, therefore it can generate URI when giving values for each parameter.

Is it interesting that URI Templates is implemented as JIT compiler…?

So, I tried JIT Compiler for URI Templates with Xbyak.

URI Templates for C++

http://coderepos.org/share/browser/lang/cplusplus/URITemplates

Xbyak is a header file library which can dynamically generate x86 binary programs while code is running.

As the previous template example “/weather/{state}/{city}?forecast={day}” is given to this JIT compiler class URITemplatesJIT, it generates the following x86 code dynamically.

003959D0 53               push        ebx
003959D1 56               push        esi
003959D2 8B 4C 24 0C      mov         ecx,dword ptr [esp+0Ch]
003959D6 8B 74 24 10      mov         esi,dword ptr [esp+10h]
003959DA B8 13 00 00 00   mov         eax,13h
003959DF C6 01 77         mov         byte ptr [ecx],77h ; 'w'
003959E2 C6 41 01 65      mov         byte ptr [ecx+1],65h ; 'e'
003959E6 C6 41 02 61      mov         byte ptr [ecx+2],61h ; 'a'
003959EA C6 41 03 74      mov         byte ptr [ecx+3],74h ; 't'
003959EE C6 41 04 68      mov         byte ptr [ecx+4],68h ; 'h'
003959F2 C6 41 05 65      mov         byte ptr [ecx+5],65h ; 'e'
003959F6 C6 41 06 72      mov         byte ptr [ecx+6],72h ; 'r'
003959FA C6 41 07 2F      mov         byte ptr [ecx+7],2Fh ; '/'
003959FE 8D 49 08         lea         ecx,[ecx+8]
00395A01 8B 16            mov         edx,dword ptr [esi]
00395A03 EB 05            jmp         00395A0A
00395A05 88 19            mov         byte ptr [ecx],bl
00395A07 40               inc         eax
00395A08 41               inc         ecx
00395A09 42               inc         edx
00395A0A 8A 1A            mov         bl,byte ptr [edx]
00395A0C 84 DB            test        bl,bl
00395A0E 75 F5            jne         00395A05
00395A10 C6 01 2F         mov         byte ptr [ecx],2Fh ; '/'
00395A13 41               inc         ecx
00395A14 8B 56 04         mov         edx,dword ptr [esi+4]
00395A17 EB 05            jmp         00395A1E
00395A19 88 19            mov         byte ptr [ecx],bl
00395A1B 40               inc         eax
00395A1C 41               inc         ecx
00395A1D 42               inc         edx
00395A1E 8A 1A            mov         bl,byte ptr [edx]
00395A20 84 DB            test        bl,bl
00395A22 75 F5            jne         00395A19
00395A24 C6 01 3F         mov         byte ptr [ecx],3Fh ; '?'
00395A27 C6 41 01 66      mov         byte ptr [ecx+1],66h ; 'f'
00395A2B C6 41 02 6F      mov         byte ptr [ecx+2],6Fh ; 'o'
00395A2F C6 41 03 72      mov         byte ptr [ecx+3],72h ; 'r'
00395A33 C6 41 04 65      mov         byte ptr [ecx+4],65h ; 'e'
00395A37 C6 41 05 63      mov         byte ptr [ecx+5],63h ; 'c'
00395A3B C6 41 06 61      mov         byte ptr [ecx+6],61h ; 'a'
00395A3F C6 41 07 73      mov         byte ptr [ecx+7],73h ; 's'
00395A43 C6 41 08 74      mov         byte ptr [ecx+8],74h ; 't'
00395A47 C6 41 09 3D      mov         byte ptr [ecx+9],3Dh ; '='
00395A4B 8D 49 0A         lea         ecx,[ecx+0Ah]
00395A4E 8B 56 08         mov         edx,dword ptr [esi+8]
00395A51 EB 05            jmp         00395A58
00395A53 88 19            mov         byte ptr [ecx],bl
00395A55 40               inc         eax
00395A56 41               inc         ecx
00395A57 42               inc         edx
00395A58 8A 1A            mov         bl,byte ptr [edx]
00395A5A 84 DB            test        bl,bl
00395A5C 75 F5            jne         00395A53
00395A5E C6 01 00         mov         byte ptr [ecx],0
00395A61 5E               pop         esi
00395A62 5B               pop         ebx
00395A63 C3               ret

How performance does this JIT compiler improve?
I measured performances of 3 type implementations including JIT compiler.

• URITemplatesNormal : an ordinary implementation with const_iterator
• URITemplatesRegex : an experimental implementation with boost::regex
• URITemplatesJIT : JIT compiler with Xbyak

The following is a result of 3 type programs.

==== URITemplatesRegex
city:Redmond
day:today
state:Washington
>> test1(extract) : 6.062usec
weather/Washington/Redmond?forecast=Today
>> test2(extend) : 12.094usec

==== URITemplatesNormal
city:Redmond
day:today
state:Washington
>> test1(extract) : 4.344usec
weather/Washington/Redmond?forecast=Today
>> test2(extend) : 1.842usec

==== URITemplatesJIT
city:Redmond
day:today
state:Washington
>> test1(extract) : 3.188usec
weather/Washington/Redmond?forecast=Today
>> test2(extend) : 0.72usec

JIT’s extend method (create a new URI from parameters) is 2.5 times faster than Normal’s.
But JIT’s extract method (extract parameters from URI) is only 1.3 times faster.
It is because substitution of std::map has considerable overhead. Indeed, It takes 70% of The execution time of JIT’S extract!

It is very simple implementation which only complies with URI Templates draft-01.
If more complicated logic such as draft-03, I expect that the difference will increase more…

Now, to tell the truth, this is my first study work of C++!