Implementations of URI Templates in various languages

Before the URI Templates implementation in C++/Xbyak, I researched implementations of URI Templates.

Python (Joe Gregorio himself’s experimental implementation)

http://code.google.com/p/uri-templates/

Ruby – Addressable

http://addressable.rubyforge.org/

Ruby – uri-templates

http://github.com/juretta/uri-templates/tree/master

Javascript – url_template

http://www.mnot.net/javascript/url_template/

Javascript – Template

http://www.snellspace.com/wp/?p=831

Perl – URI::Template

http://search.cpan.org/~bricas/URI-Template/

.NET – UriTemplate

http://msdn.microsoft.com/en-us/library/system.uritemplate.aspx

PHP – URI_Template

http://pear.php.net/package/URI_Template/download/

Java – Apache Abdera

http://cwiki.apache.org/ABDERA/uri-templates.html

Java – Metanotion URLMapper

http://www.metanotion.net/software/urlmapper/

Erlang – uri-template

http://tfletcher.com/dev/erlang-uri-template

C++ – URITemplates

http://shuyo.wordpress.com/2008/07/17/jit-compiler-for-uri-templates-cxbyak/

Some of them implement “extract” method which isn’t mentioned by URI Templates specifications. Now “extract” means extraction of parameters from URI.
To me, URI Templates is valuable if it implements extend and extract both. Because we often need to generate and parse the same format URIs when our application meets connectivity(connectedness). Of course, we can generate URI by string join and parse by regular expressions, but are prone to mistake in changing format.
So I hope that URI Templates include “extract” specifications. It’ll bring about restriction of templates, however…(e.g. Extraction by template “http://example.com/{foo}{bar}” isn’t well defined.)

Original Japanese article: Implementations of URI Templates in various languages

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++!