You are viewing a plain text version of this content. The canonical link for it is here.
Posted to c-dev@axis.apache.org by Dimuthu Gamage <di...@gmail.com> on 2008/11/20 05:31:45 UTC
REST URL Mapping - The changes done in pattern matching Algorithm
Hi devs,
As you may have already noticed, I changed the REST URL pattern matching
algorithm while fixing the https://issues.apache.org/jira/browse/AXIS2C-1290
issue and the WSF/PHP issue, https://wso2.org/jira/browse/WSFPHP-347. Since
Apache's principle is to 'Commit first' I committed the code first (after
making sure everything works), decided to start a discussion on that :)
Basically What I have done is changing the code
1. Initializing the REST Mapping per operation -
axis2_svc_get_rest_op_list_with_method_and_location ( in
src/core/description/svc.c)
2. REST dispaching algorithm to find the operation and the matching
patterns - axis2_rest_disp_find_op (in src/core/engine/rest_disp.c )
At the initializing face It store the url pattern in a internal recursive
structure call 'axutil_core_utils_map_internal_t' whcih is only used inside
the core_utils.c function. And it store this structure for each operation in
the svc->op_rest_map hash. Here is the structure of the struct.
/* internal structure to keep the rest map in a multi level hash */
typedef struct {
/* the structure will keep as many as following fields */
/* if the mapped value is directly the operation */
axis2_op_t *op_desc;
/* if the mapped value is a constant, this keeps a hash map of
possible constants => corrosponding map_internal structure */
axutil_hash_t *consts_map;
/* if the mapped value is a param, this keeps a hash map of
possible param_values => corrosponding_map_internal structre */
axutil_hash_t *params_map;
} axutil_core_utils_map_internal_t;
For an example think you have operations with following REST mapping (Using
the example attached in the
https://issues.apache.org/jira/browse/AXIS2C-1290 and
http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ )
GET students
GET students/{stduent_id}
GET students/{student_id}/marks/{subject_id}
Then thes svc->op_rest_map will be like
<pre>
svc->op_rest_map (hash)
|
"GET:students" --------- axutil_core_utils_map_internal_t
(instance)
|
op_desc (axis2_op_t*
for "GET students" op)
|
consts_map (empty
hash)
|
params_map (hash)
|
"{student_id}" ------------- axutil_core_utils_map_internal_t (instance)
|
op_desc (axis2_op_t* for "GET students/{student_id}" op)
|
parms_map (empty hash)
|
const_map (hash)
|
"marks" -------------------
axutil_core_utils_map_internal_t (instance)
|
op_desc (NULL)
|
consts_map (empty
hash)
|
params_map (hash)
|
"{subject_id}"
----------- axutil_core_utils_map_internal_t (instance)
|
op_desc (axis2_op_t*
for "GET students/{student_id}/marks/{subject_id}" op)
|
consts_map / params_map (Both NULL)
</pre>
So at the Dispatching URL we can clearly sort out the operation and the
parameter values.
For matching patterns like {student_id}, {subject_id} and more complex
matching like xx{p}yy{q}zz{r} the logic uses the function
axis2_core_utils_match_url_component_with_pattern ( in
src/core/util/core_utils.c)
This is O(n^2) order (in worse case) algorithm.
And what I want to discuss is the point whether the above described logic is
better than the early logic which sequentilly checks all the mapping.
Calculating the approximate time complexity takng n =numbe of operations, p
= average URL mapping length
The early logic = n/2 (<--go through all the operation in average) *
O(p^2) (<--the complexity of
axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2)
For the second logic it is really complex to do a methematical analysis of
the tiime complexity. Assuming (being optimistic:) average length of the url
component is d (d <= p) and the average parameters in a url is k (k <=p/d)
and taking hash search is O(1)
The new logic = log(n) (<-- long n number of hash search) *(k*O(d^2)) (<--
assuming k parameters have to execute the function
axis2_core_utils_match_url_component_with_pattern) => O(logn * k* d^2)
Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p and k
<=p/d)
Anyway the new logic contain some recursive functions and hash functions
heavily which may slow down things at little n (number of operations),
littld k (little number of url components) and little d (small length urls).
So my question is do we need to favor on the smal number of operation so go
back to old logic(after correcting bugs) or do we stay with the current
logic?. Your opinions?
--
Thanks,
Dimuthu Gamage
http://www.dimuthu.org
http://www.wso2.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Thiago Rafael Becker <th...@gmail.com>.
I guess that the list, hash and tree manipulation functions are more
interesting in this case.
A bit more of information: for the inlining to be successful, the
inlined function and the function that calls it must be in the same
file scope. What is usually done is to declare and define the function
in a header, so every file that includes it has a copy of the
function. Since the function is declared static as well, it will not
be exported outside this scope, so no conflicting simbols will be
found when the linker comes into action. The gcc option to assure that
a function will be inlined is -finline-functions, and there should be
an equivalent option for Microsoft compiler as well.
As can be seen in the gcc manual
(http://developer.apple.com/documentation/developertools/gcc-3.3/gcc/Optimize-Options.html),
the compiler still has the final word on which function will be
inlined (look for the -finline-functions switch), so simple functions
have high probability to be inlined. From my experience, recursive
functions wont be inlined.
On Mon, Nov 24, 2008 at 3:18 PM, Supun Kamburugamuva <su...@gmail.com> wrote:
> I also tried to find the C99 compatibility of Microsoft compilers. But the
> details are not that clear. Yes, inline functions can increase the
> performance. But we should consider the overhead work and complexity vs
> performance. If we are going to introduce inline functions, one ideal place
> will be for getter/setter functions.
>
> Thanks,
> Supun.
>
> On Mon, Nov 24, 2008 at 8:31 PM, Thiago Rafael Becker
> <th...@gmail.com> wrote:
>>
>> I'm a unix guy, and in this platform, the portability is good for c99
>> (but gcc doesn't implement it completely, as you can see in [1]).
>> Looks like Microsoft compilers are compatible with this startdard, if
>> they implement full compatibility with C++/TR1 specification - and
>> looks like the /TP implements this compatibility. But I can't find
>> anything clear on this issue, and I could find some pointers to some
>> failures on microsoft compilers[2]. Extra pointers in [3].
>>
>> [1] http://gcc.gnu.org/c99status.html
>> [2]
>> http://coding.derkeiler.com/Archive/C_CPP/comp.lang.c/2007-03/msg05350.html
>> [3] http://www.dinkumware.com/tr1.aspx,
>>
>> http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/913a2001-d2a6-450a-a15e-ff97ab6da0f1/
>>
>> Responding to Supun, static inline functions can increase the size of
>> binaries a bit, but there's no hit in performance. And some functions,
>> if inlined, can improve the overall performance. It works more or less
>> like macros, but with type verification at compile time and correct
>> debugging pointers. Both type verification and correct debugging
>> pointers can be cited as advantages of c99 over ansi c.
>>
>>
>> Thanks.
>>
>> On Sat, Nov 22, 2008 at 3:26 AM, Damitha Kumarage <da...@gmail.com>
>> wrote:
>> > Thiago Rafael Becker wrote:
>> >>
>> >> Hi, all
>> >>
>> >> I was looking at the recursive functions and below are my findings.
>> >>
>> >> In the case of axis2_core_utils_internal_build_rest_map_recursively,
>> >> which is a tail-recursive function, seems easy to convert it to a
>> >> iterative function.
>> >>
>> >> In the case of
>> >> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
>> >> which is not a tail-recursive function, seems harder to do. Also, it
>> >> spans for about 250 lines, it's complicated to find how to convert it.
>> >> Did you ever thought about switching from ansi c to iso99 c? You can
>> >> do some things to reduce the line span of functions (static inline
>> >> functions) that you can't do with ansi c. What do you think about it?
>> >>
>> >
>> > How about portability if we adopt C99?
>> > thanks
>> > Damitha
>> >
>> > --
>> > __________________________________________________________________
>> >
>> > Damitha Kumarage
>> > http://people.apache.org/
>> > __________________________________________________________________
>> >
>> > ---------------------------------------------------------------------
>> > To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
>> > For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>> >
>> >
>>
>>
>>
>> --
>> Thiago Rafael Becker
>> http://www.monstros.org/trbecker
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
>> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>>
>
>
>
> --
> Software Engineer, WSO2 Inc
> http://wso2.org
> Web Services with Axis2/C http://wsaxc.blospot.com
>
>
--
Thiago Rafael Becker
http://www.monstros.org/trbecker
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Supun Kamburugamuva <su...@gmail.com>.
I also tried to find the C99 compatibility of Microsoft compilers. But the
details are not that clear. Yes, inline functions can increase the
performance. But we should consider the overhead work and complexity vs
performance. If we are going to introduce inline functions, one ideal place
will be for getter/setter functions.
Thanks,
Supun.
On Mon, Nov 24, 2008 at 8:31 PM, Thiago Rafael Becker <
thiago.becker@gmail.com> wrote:
> I'm a unix guy, and in this platform, the portability is good for c99
> (but gcc doesn't implement it completely, as you can see in [1]).
> Looks like Microsoft compilers are compatible with this startdard, if
> they implement full compatibility with C++/TR1 specification - and
> looks like the /TP implements this compatibility. But I can't find
> anything clear on this issue, and I could find some pointers to some
> failures on microsoft compilers[2]. Extra pointers in [3].
>
> [1] http://gcc.gnu.org/c99status.html
> [2]
> http://coding.derkeiler.com/Archive/C_CPP/comp.lang.c/2007-03/msg05350.html
> [3] http://www.dinkumware.com/tr1.aspx,
>
> http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/913a2001-d2a6-450a-a15e-ff97ab6da0f1/
>
> Responding to Supun, static inline functions can increase the size of
> binaries a bit, but there's no hit in performance. And some functions,
> if inlined, can improve the overall performance. It works more or less
> like macros, but with type verification at compile time and correct
> debugging pointers. Both type verification and correct debugging
> pointers can be cited as advantages of c99 over ansi c.
>
>
> Thanks.
>
> On Sat, Nov 22, 2008 at 3:26 AM, Damitha Kumarage <da...@gmail.com>
> wrote:
> > Thiago Rafael Becker wrote:
> >>
> >> Hi, all
> >>
> >> I was looking at the recursive functions and below are my findings.
> >>
> >> In the case of axis2_core_utils_internal_build_rest_map_recursively,
> >> which is a tail-recursive function, seems easy to convert it to a
> >> iterative function.
> >>
> >> In the case of
> >> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
> >> which is not a tail-recursive function, seems harder to do. Also, it
> >> spans for about 250 lines, it's complicated to find how to convert it.
> >> Did you ever thought about switching from ansi c to iso99 c? You can
> >> do some things to reduce the line span of functions (static inline
> >> functions) that you can't do with ansi c. What do you think about it?
> >>
> >
> > How about portability if we adopt C99?
> > thanks
> > Damitha
> >
> > --
> > __________________________________________________________________
> >
> > Damitha Kumarage
> > http://people.apache.org/
> > __________________________________________________________________
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> > For additional commands, e-mail: axis-c-dev-help@ws.apache.org
> >
> >
>
>
>
> --
> Thiago Rafael Becker
> http://www.monstros.org/trbecker
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>
>
--
Software Engineer, WSO2 Inc
http://wso2.org
Web Services with Axis2/C http://wsaxc.blospot.com
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Thiago Rafael Becker <th...@gmail.com>.
I'm a unix guy, and in this platform, the portability is good for c99
(but gcc doesn't implement it completely, as you can see in [1]).
Looks like Microsoft compilers are compatible with this startdard, if
they implement full compatibility with C++/TR1 specification - and
looks like the /TP implements this compatibility. But I can't find
anything clear on this issue, and I could find some pointers to some
failures on microsoft compilers[2]. Extra pointers in [3].
[1] http://gcc.gnu.org/c99status.html
[2] http://coding.derkeiler.com/Archive/C_CPP/comp.lang.c/2007-03/msg05350.html
[3] http://www.dinkumware.com/tr1.aspx,
http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/913a2001-d2a6-450a-a15e-ff97ab6da0f1/
Responding to Supun, static inline functions can increase the size of
binaries a bit, but there's no hit in performance. And some functions,
if inlined, can improve the overall performance. It works more or less
like macros, but with type verification at compile time and correct
debugging pointers. Both type verification and correct debugging
pointers can be cited as advantages of c99 over ansi c.
Thanks.
On Sat, Nov 22, 2008 at 3:26 AM, Damitha Kumarage <da...@gmail.com> wrote:
> Thiago Rafael Becker wrote:
>>
>> Hi, all
>>
>> I was looking at the recursive functions and below are my findings.
>>
>> In the case of axis2_core_utils_internal_build_rest_map_recursively,
>> which is a tail-recursive function, seems easy to convert it to a
>> iterative function.
>>
>> In the case of
>> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
>> which is not a tail-recursive function, seems harder to do. Also, it
>> spans for about 250 lines, it's complicated to find how to convert it.
>> Did you ever thought about switching from ansi c to iso99 c? You can
>> do some things to reduce the line span of functions (static inline
>> functions) that you can't do with ansi c. What do you think about it?
>>
>
> How about portability if we adopt C99?
> thanks
> Damitha
>
> --
> __________________________________________________________________
>
> Damitha Kumarage
> http://people.apache.org/
> __________________________________________________________________
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>
>
--
Thiago Rafael Becker
http://www.monstros.org/trbecker
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Damitha Kumarage <da...@gmail.com>.
Thiago Rafael Becker wrote:
> Hi, all
>
> I was looking at the recursive functions and below are my findings.
>
> In the case of axis2_core_utils_internal_build_rest_map_recursively,
> which is a tail-recursive function, seems easy to convert it to a
> iterative function.
>
> In the case of axis2_core_utils_internal_infer_op_from_rest_map_recursively,
> which is not a tail-recursive function, seems harder to do. Also, it
> spans for about 250 lines, it's complicated to find how to convert it.
> Did you ever thought about switching from ansi c to iso99 c? You can
> do some things to reduce the line span of functions (static inline
> functions) that you can't do with ansi c. What do you think about it?
>
How about portability if we adopt C99?
thanks
Damitha
--
__________________________________________________________________
Damitha Kumarage
http://people.apache.org/
__________________________________________________________________
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Dimuthu Gamage <di...@gmail.com>.
On Sat, Nov 22, 2008 at 1:20 AM, Thiago Rafael Becker <
thiago.becker@gmail.com> wrote:
> Hi, all
>
> I was looking at the recursive functions and below are my findings.
>
> In the case of axis2_core_utils_internal_build_rest_map_recursively,
> which is a tail-recursive function, seems easy to convert it to a
> iterative function.
Agreed.
>
>
> In the case of
> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
> which is not a tail-recursive function, seems harder to do. Also, it
> spans for about 250 lines, it's complicated to find how to convert it.
> Did you ever thought about switching from ansi c to iso99 c? You can
> do some things to reduce the line span of functions (static inline
> functions) that you can't do with ansi c. What do you think about it?
Well I'm not sure about that. Axis2/C has lot of codes developed with ansi c
constraints. And it is not logical to move it to c99 just because of this.
:).
Thanks
Dimuthu
>
>
> Thanks :)
>
> On Thu, Nov 20, 2008 at 4:04 PM, Thiago Rafael Becker
> <th...@gmail.com> wrote:
> > Hi,
> >
> > On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <di...@gmail.com>
> wrote:
> <... Large clip ...>
> --
> Thiago Rafael Becker
> http://www.monstros.org/trbecker
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>
>
--
Thanks,
Dimuthu Gamage
http://www.dimuthu.org
http://www.wso2.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Supun Kamburugamuva <su...@gmail.com>.
Hi Thiago,
Do you think we will be able to observe significant differences if we make
some functions inline?
Supun.
On Sat, Nov 22, 2008 at 12:50 AM, Thiago Rafael Becker <
thiago.becker@gmail.com> wrote:
> Hi, all
>
> I was looking at the recursive functions and below are my findings.
>
> In the case of axis2_core_utils_internal_build_rest_map_recursively,
> which is a tail-recursive function, seems easy to convert it to a
> iterative function.
>
> In the case of
> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
> which is not a tail-recursive function, seems harder to do. Also, it
> spans for about 250 lines, it's complicated to find how to convert it.
> Did you ever thought about switching from ansi c to iso99 c? You can
> do some things to reduce the line span of functions (static inline
> functions) that you can't do with ansi c. What do you think about it?
>
> Thanks :)
>
> On Thu, Nov 20, 2008 at 4:04 PM, Thiago Rafael Becker
> <th...@gmail.com> wrote:
> > Hi,
> >
> > On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <di...@gmail.com>
> wrote:
> <... Large clip ...>
> --
> Thiago Rafael Becker
> http://www.monstros.org/trbecker
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>
>
--
Software Engineer, WSO2 Inc
http://wso2.org
Web Services with Axis2/C http://wsaxc.blospot.com
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Dimuthu Gamage <di...@gmail.com>.
On Sat, Nov 22, 2008 at 5:01 PM, Dumindu Pallewela <pa...@gmail.com>wrote:
> Hi All,
> While I doubt the need for removing recursion here (given the fact that
> using more than a few url components will plainly be an overkill), it seems
> to me that removing recursion from both the functions is quite straight
> forward.
>
> As it was mentioned earlier the function axis2_core_utils_internal_build_rest_map_recursively()
> is tail recursion, all you need is a loop.
>
> Since axis2_core_utils_internal_infer_op_from_rest_map_recursively() is
> basically a Depth First Search (DFS) over the op_rest_map structure which
> essentially is a tree, it is just a matter of implementing the DFS
> iteratively, for which again there is a well known technique (e.g. [1]),
> which can be achieved using a stack to hold the current list of
> param/const_maps to visit.
>
Thanks for remembering that:). Only variables we need to keep in the stack
is the mapping structure and the pointer to the component of the URL. So as
you said it should be straight forward.
Thanks
Dimuthu
>
> HTH.
> Thanks,
> Dumindu.
>
> [1]
> http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L20-Depth.htm
>
> On Sat, Nov 22, 2008 at 1:20 AM, Thiago Rafael Becker <
> thiago.becker@gmail.com> wrote:
>
>> Hi, all
>>
>> I was looking at the recursive functions and below are my findings.
>>
>> In the case of axis2_core_utils_internal_build_rest_map_recursively,
>> which is a tail-recursive function, seems easy to convert it to a
>> iterative function.
>>
>> In the case of
>> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
>> which is not a tail-recursive function, seems harder to do. Also, it
>> spans for about 250 lines, it's complicated to find how to convert it.
>> Did you ever thought about switching from ansi c to iso99 c? You can
>> do some things to reduce the line span of functions (static inline
>> functions) that you can't do with ansi c. What do you think about it?
>>
>> Thanks :)
>>
>> On Thu, Nov 20, 2008 at 4:04 PM, Thiago Rafael Becker
>> <th...@gmail.com> wrote:
>> > Hi,
>> >
>> > On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <di...@gmail.com>
>> wrote:
>> <... Large clip ...>
>> --
>> Thiago Rafael Becker
>> http://www.monstros.org/trbecker
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
>> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>>
>>
>
--
Thanks,
Dimuthu Gamage
http://www.dimuthu.org
http://www.wso2.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Dumindu Pallewela <pa...@gmail.com>.
Hi All,
While I doubt the need for removing recursion here (given the fact that
using more than a few url components will plainly be an overkill), it seems
to me that removing recursion from both the functions is quite straight
forward.
As it was mentioned earlier the function
axis2_core_utils_internal_build_rest_map_recursively()
is tail recursion, all you need is a loop.
Since axis2_core_utils_internal_infer_op_from_rest_map_recursively() is
basically a Depth First Search (DFS) over the op_rest_map structure which
essentially is a tree, it is just a matter of implementing the DFS
iteratively, for which again there is a well known technique (e.g. [1]),
which can be achieved using a stack to hold the current list of
param/const_maps to visit.
HTH.
Thanks,
Dumindu.
[1]
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L20-Depth.htm
On Sat, Nov 22, 2008 at 1:20 AM, Thiago Rafael Becker <
thiago.becker@gmail.com> wrote:
> Hi, all
>
> I was looking at the recursive functions and below are my findings.
>
> In the case of axis2_core_utils_internal_build_rest_map_recursively,
> which is a tail-recursive function, seems easy to convert it to a
> iterative function.
>
> In the case of
> axis2_core_utils_internal_infer_op_from_rest_map_recursively,
> which is not a tail-recursive function, seems harder to do. Also, it
> spans for about 250 lines, it's complicated to find how to convert it.
> Did you ever thought about switching from ansi c to iso99 c? You can
> do some things to reduce the line span of functions (static inline
> functions) that you can't do with ansi c. What do you think about it?
>
> Thanks :)
>
> On Thu, Nov 20, 2008 at 4:04 PM, Thiago Rafael Becker
> <th...@gmail.com> wrote:
> > Hi,
> >
> > On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <di...@gmail.com>
> wrote:
> <... Large clip ...>
> --
> Thiago Rafael Becker
> http://www.monstros.org/trbecker
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>
>
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Thiago Rafael Becker <th...@gmail.com>.
Hi, all
I was looking at the recursive functions and below are my findings.
In the case of axis2_core_utils_internal_build_rest_map_recursively,
which is a tail-recursive function, seems easy to convert it to a
iterative function.
In the case of axis2_core_utils_internal_infer_op_from_rest_map_recursively,
which is not a tail-recursive function, seems harder to do. Also, it
spans for about 250 lines, it's complicated to find how to convert it.
Did you ever thought about switching from ansi c to iso99 c? You can
do some things to reduce the line span of functions (static inline
functions) that you can't do with ansi c. What do you think about it?
Thanks :)
On Thu, Nov 20, 2008 at 4:04 PM, Thiago Rafael Becker
<th...@gmail.com> wrote:
> Hi,
>
> On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <di...@gmail.com> wrote:
<... Large clip ...>
--
Thiago Rafael Becker
http://www.monstros.org/trbecker
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Thiago Rafael Becker <th...@gmail.com>.
Hi,
On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <di...@gmail.com> wrote:
> Hi Thiago,
>
> Yes, recursive should anyway cause problems with small stacks. But I think
> we can safely assume the number of url component will not exceed 4/5 times.
> If the call stack is still smaller than that number, the code will fail.
Ok. I'll take a look at my work here to see if I'll hit some limit
where I can have this problem. If so, I'll have to fix it ;) Thanks.
> We can iteratively implement that with a manual hash which simulate the
> recursive call stack. So we can traverse a branch of the tree and return to
> the root and traverse the other branches if the first branch is not
> successful. I will check the possibility of such an algorithm.
I'll take a closer look at the code to maybe suggest something.
> The hash we uses is already a dynamic one. Anyway we have to go out from the
> hash and do linear searches, if the url contains params (since we have to do
> simple pattern matching). Where do you think, you can place dynamic hash?
Looking at it too.
> Thanks
> Dimuthu
>>
>>
>> On Thu, Nov 20, 2008 at 2:31 AM, Dimuthu Gamage <di...@gmail.com>
>> wrote:
>> > Hi devs,
>> >
>> > As you may have already noticed, I changed the REST URL pattern
>> > matching
>> > algorithm while fixing the
>> > https://issues.apache.org/jira/browse/AXIS2C-1290 issue and the WSF/PHP
>> > issue, https://wso2.org/jira/browse/WSFPHP-347. Since Apache's principle
>> > is
>> > to 'Commit first' I committed the code first (after making sure
>> > everything
>> > works), decided to start a discussion on that :)
>> >
>> > Basically What I have done is changing the code
>> > 1. Initializing the REST Mapping per operation -
>> > axis2_svc_get_rest_op_list_with_method_and_location ( in
>> > src/core/description/svc.c)
>> > 2. REST dispaching algorithm to find the operation and the matching
>> > patterns - axis2_rest_disp_find_op (in src/core/engine/rest_disp.c )
>> >
>> > At the initializing face It store the url pattern in a internal
>> > recursive
>> > structure call 'axutil_core_utils_map_internal_t' whcih is only used
>> > inside
>> > the core_utils.c function. And it store this structure for each
>> > operation in
>> > the svc->op_rest_map hash. Here is the structure of the struct.
>> >
>> > /* internal structure to keep the rest map in a multi level hash */
>> > typedef struct {
>> > /* the structure will keep as many as following fields */
>> >
>> > /* if the mapped value is directly the operation */
>> > axis2_op_t *op_desc;
>> >
>> > /* if the mapped value is a constant, this keeps a hash map of
>> > possible constants => corrosponding map_internal structure */
>> > axutil_hash_t *consts_map;
>> >
>> > /* if the mapped value is a param, this keeps a hash map of
>> > possible param_values => corrosponding_map_internal structre */
>> > axutil_hash_t *params_map;
>> >
>> > } axutil_core_utils_map_internal_t;
>> >
>> > For an example think you have operations with following REST mapping
>> > (Using
>> > the example attached in the
>> > https://issues.apache.org/jira/browse/AXIS2C-1290 and
>> > http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ )
>> >
>> > GET students
>> > GET students/{stduent_id}
>> > GET students/{student_id}/marks/{subject_id}
>> >
>> > Then thes svc->op_rest_map will be like
>> >
>> > <pre>
>> > svc->op_rest_map (hash)
>> > |
>> > "GET:students" --------- axutil_core_utils_map_internal_t
>> > (instance)
>> > |
>> > op_desc
>> > (axis2_op_t*
>> > for "GET students" op)
>> > |
>> > consts_map
>> > (empty
>> > hash)
>> > |
>> > params_map
>> > (hash)
>> >
>> > |
>> >
>> > "{student_id}" ------------- axutil_core_utils_map_internal_t (instance)
>> >
>> > |
>> >
>> > op_desc (axis2_op_t* for "GET students/{student_id}"
>> > op)
>> >
>> > |
>> >
>> > parms_map (empty hash)
>> >
>> > |
>> >
>> > const_map (hash)
>> >
>> > |
>> >
>> > "marks" -------------------
>> > axutil_core_utils_map_internal_t (instance)
>> >
>> > |
>> >
>> > op_desc (NULL)
>> >
>> > |
>> >
>> > consts_map (empty
>> > hash)
>> >
>> > |
>> >
>> > params_map (hash)
>> >
>> >
>> > |
>> >
>> >
>> > "{subject_id}"
>> > ----------- axutil_core_utils_map_internal_t (instance)
>> >
>> >
>> > |
>> >
>> > op_desc
>> > (axis2_op_t*
>> > for "GET students/{student_id}/marks/{subject_id}" op)
>> >
>> > |
>> >
>> > consts_map / params_map (Both NULL)
>> >
>> > </pre>
>> >
>> > So at the Dispatching URL we can clearly sort out the operation and the
>> > parameter values.
>> >
>> > For matching patterns like {student_id}, {subject_id} and more complex
>> > matching like xx{p}yy{q}zz{r} the logic uses the function
>> > axis2_core_utils_match_url_component_with_pattern ( in
>> > src/core/util/core_utils.c)
>> > This is O(n^2) order (in worse case) algorithm.
>> >
>> > And what I want to discuss is the point whether the above described
>> > logic is
>> > better than the early logic which sequentilly checks all the mapping.
>> >
>> > Calculating the approximate time complexity takng n =numbe of
>> > operations, p
>> > = average URL mapping length
>> > The early logic = n/2 (<--go through all the operation in average) *
>> > O(p^2) (<--the complexity of
>> > axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2)
>> >
>> > For the second logic it is really complex to do a methematical analysis
>> > of
>> > the tiime complexity. Assuming (being optimistic:) average length of the
>> > url
>> > component is d (d <= p) and the average parameters in a url is k (k
>> > <=p/d)
>> > and taking hash search is O(1)
>> >
>> > The new logic = log(n) (<-- long n number of hash search) *(k*O(d^2))
>> > (<--
>> > assuming k parameters have to execute the function
>> > axis2_core_utils_match_url_component_with_pattern) => O(logn * k* d^2)
>> >
>> > Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p and k
>> > <=p/d)
>> >
>> > Anyway the new logic contain some recursive functions and hash functions
>> > heavily which may slow down things at little n (number of operations),
>> > littld k (little number of url components) and little d (small length
>> > urls).
>> >
>> > So my question is do we need to favor on the smal number of operation so
>> > go
>> > back to old logic(after correcting bugs) or do we stay with the current
>> > logic?. Your opinions?
>> >
>> >
>> >
>> > --
>> > Thanks,
>> > Dimuthu Gamage
>> >
>> > http://www.dimuthu.org
>> > http://www.wso2.org
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
>> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>>
>
>
>
> --
> Thanks,
> Dimuthu Gamage
>
> http://www.dimuthu.org
> http://www.wso2.org
>
--
Thiago Rafael Becker
http://www.monstros.org/trbecker
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Dimuthu Gamage <di...@gmail.com>.
Hi Thiago,
Yes, recursive should anyway cause problems with small stacks. But I think
we can safely assume the number of url component will not exceed 4/5 times.
If the call stack is still smaller than that number, the code will fail.
On Thu, Nov 20, 2008 at 3:40 PM, Thiago Rafael Becker <
thiago.becker@gmail.com> wrote:
> The only thing that worries me is the recursion. Suppose that I have a
> small stack (which is common on embedded systems), and a long chain of
> possibilities to a single pattern or even several patterns (which may
> be common). Can this overflow the application stack? Can these
> functions be implemented with iterative functions instead?
We can iteratively implement that with a manual hash which simulate the
recursive call stack. So we can traverse a branch of the tree and return to
the root and traverse the other branches if the first branch is not
successful. I will check the possibility of such an algorithm.
>
>
> I was thinking about using dynamic hash tables for this. Do you think
> this can lead to more improvement in the performance?
The hash we uses is already a dynamic one. Anyway we have to go out from the
hash and do linear searches, if the url contains params (since we have to do
simple pattern matching). Where do you think, you can place dynamic hash?
Thanks
Dimuthu
>
>
> On Thu, Nov 20, 2008 at 2:31 AM, Dimuthu Gamage <di...@gmail.com>
> wrote:
> > Hi devs,
> >
> > As you may have already noticed, I changed the REST URL pattern matching
> > algorithm while fixing the
> > https://issues.apache.org/jira/browse/AXIS2C-1290 issue and the WSF/PHP
> > issue, https://wso2.org/jira/browse/WSFPHP-347. Since Apache's principle
> is
> > to 'Commit first' I committed the code first (after making sure
> everything
> > works), decided to start a discussion on that :)
> >
> > Basically What I have done is changing the code
> > 1. Initializing the REST Mapping per operation -
> > axis2_svc_get_rest_op_list_with_method_and_location ( in
> > src/core/description/svc.c)
> > 2. REST dispaching algorithm to find the operation and the matching
> > patterns - axis2_rest_disp_find_op (in src/core/engine/rest_disp.c )
> >
> > At the initializing face It store the url pattern in a internal recursive
> > structure call 'axutil_core_utils_map_internal_t' whcih is only used
> inside
> > the core_utils.c function. And it store this structure for each operation
> in
> > the svc->op_rest_map hash. Here is the structure of the struct.
> >
> > /* internal structure to keep the rest map in a multi level hash */
> > typedef struct {
> > /* the structure will keep as many as following fields */
> >
> > /* if the mapped value is directly the operation */
> > axis2_op_t *op_desc;
> >
> > /* if the mapped value is a constant, this keeps a hash map of
> > possible constants => corrosponding map_internal structure */
> > axutil_hash_t *consts_map;
> >
> > /* if the mapped value is a param, this keeps a hash map of
> > possible param_values => corrosponding_map_internal structre */
> > axutil_hash_t *params_map;
> >
> > } axutil_core_utils_map_internal_t;
> >
> > For an example think you have operations with following REST mapping
> (Using
> > the example attached in the
> > https://issues.apache.org/jira/browse/AXIS2C-1290 and
> > http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ )
> >
> > GET students
> > GET students/{stduent_id}
> > GET students/{student_id}/marks/{subject_id}
> >
> > Then thes svc->op_rest_map will be like
> >
> > <pre>
> > svc->op_rest_map (hash)
> > |
> > "GET:students" --------- axutil_core_utils_map_internal_t
> > (instance)
> > |
> > op_desc
> (axis2_op_t*
> > for "GET students" op)
> > |
> > consts_map (empty
> > hash)
> > |
> > params_map (hash)
> >
> |
> >
> > "{student_id}" ------------- axutil_core_utils_map_internal_t (instance)
> >
> > |
> >
> > op_desc (axis2_op_t* for "GET students/{student_id}"
> op)
> >
> > |
> >
> > parms_map (empty hash)
> >
> > |
> >
> > const_map (hash)
> >
> > |
> >
> > "marks" -------------------
> > axutil_core_utils_map_internal_t (instance)
> >
> > |
> >
> > op_desc (NULL)
> >
> > |
> >
> > consts_map (empty
> > hash)
> >
> > |
> >
> > params_map (hash)
> >
> >
> |
> >
> >
> "{subject_id}"
> > ----------- axutil_core_utils_map_internal_t (instance)
> >
> >
> > |
> >
> > op_desc
> (axis2_op_t*
> > for "GET students/{student_id}/marks/{subject_id}" op)
> >
> > |
> >
> > consts_map / params_map (Both NULL)
> >
> > </pre>
> >
> > So at the Dispatching URL we can clearly sort out the operation and the
> > parameter values.
> >
> > For matching patterns like {student_id}, {subject_id} and more complex
> > matching like xx{p}yy{q}zz{r} the logic uses the function
> > axis2_core_utils_match_url_component_with_pattern ( in
> > src/core/util/core_utils.c)
> > This is O(n^2) order (in worse case) algorithm.
> >
> > And what I want to discuss is the point whether the above described logic
> is
> > better than the early logic which sequentilly checks all the mapping.
> >
> > Calculating the approximate time complexity takng n =numbe of operations,
> p
> > = average URL mapping length
> > The early logic = n/2 (<--go through all the operation in average) *
> > O(p^2) (<--the complexity of
> > axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2)
> >
> > For the second logic it is really complex to do a methematical analysis
> of
> > the tiime complexity. Assuming (being optimistic:) average length of the
> url
> > component is d (d <= p) and the average parameters in a url is k (k
> <=p/d)
> > and taking hash search is O(1)
> >
> > The new logic = log(n) (<-- long n number of hash search) *(k*O(d^2))
> (<--
> > assuming k parameters have to execute the function
> > axis2_core_utils_match_url_component_with_pattern) => O(logn * k* d^2)
> >
> > Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p and k
> > <=p/d)
> >
> > Anyway the new logic contain some recursive functions and hash functions
> > heavily which may slow down things at little n (number of operations),
> > littld k (little number of url components) and little d (small length
> urls).
> >
> > So my question is do we need to favor on the smal number of operation so
> go
> > back to old logic(after correcting bugs) or do we stay with the current
> > logic?. Your opinions?
> >
> >
> >
> > --
> > Thanks,
> > Dimuthu Gamage
> >
> > http://www.dimuthu.org
> > http://www.wso2.org
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
> For additional commands, e-mail: axis-c-dev-help@ws.apache.org
>
>
--
Thanks,
Dimuthu Gamage
http://www.dimuthu.org
http://www.wso2.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Thiago Rafael Becker <th...@gmail.com>.
The only thing that worries me is the recursion. Suppose that I have a
small stack (which is common on embedded systems), and a long chain of
possibilities to a single pattern or even several patterns (which may
be common). Can this overflow the application stack? Can these
functions be implemented with iterative functions instead?
I was thinking about using dynamic hash tables for this. Do you think
this can lead to more improvement in the performance?
On Thu, Nov 20, 2008 at 2:31 AM, Dimuthu Gamage <di...@gmail.com> wrote:
> Hi devs,
>
> As you may have already noticed, I changed the REST URL pattern matching
> algorithm while fixing the
> https://issues.apache.org/jira/browse/AXIS2C-1290 issue and the WSF/PHP
> issue, https://wso2.org/jira/browse/WSFPHP-347. Since Apache's principle is
> to 'Commit first' I committed the code first (after making sure everything
> works), decided to start a discussion on that :)
>
> Basically What I have done is changing the code
> 1. Initializing the REST Mapping per operation -
> axis2_svc_get_rest_op_list_with_method_and_location ( in
> src/core/description/svc.c)
> 2. REST dispaching algorithm to find the operation and the matching
> patterns - axis2_rest_disp_find_op (in src/core/engine/rest_disp.c )
>
> At the initializing face It store the url pattern in a internal recursive
> structure call 'axutil_core_utils_map_internal_t' whcih is only used inside
> the core_utils.c function. And it store this structure for each operation in
> the svc->op_rest_map hash. Here is the structure of the struct.
>
> /* internal structure to keep the rest map in a multi level hash */
> typedef struct {
> /* the structure will keep as many as following fields */
>
> /* if the mapped value is directly the operation */
> axis2_op_t *op_desc;
>
> /* if the mapped value is a constant, this keeps a hash map of
> possible constants => corrosponding map_internal structure */
> axutil_hash_t *consts_map;
>
> /* if the mapped value is a param, this keeps a hash map of
> possible param_values => corrosponding_map_internal structre */
> axutil_hash_t *params_map;
>
> } axutil_core_utils_map_internal_t;
>
> For an example think you have operations with following REST mapping (Using
> the example attached in the
> https://issues.apache.org/jira/browse/AXIS2C-1290 and
> http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ )
>
> GET students
> GET students/{stduent_id}
> GET students/{student_id}/marks/{subject_id}
>
> Then thes svc->op_rest_map will be like
>
> <pre>
> svc->op_rest_map (hash)
> |
> "GET:students" --------- axutil_core_utils_map_internal_t
> (instance)
> |
> op_desc (axis2_op_t*
> for "GET students" op)
> |
> consts_map (empty
> hash)
> |
> params_map (hash)
> |
>
> "{student_id}" ------------- axutil_core_utils_map_internal_t (instance)
>
> |
>
> op_desc (axis2_op_t* for "GET students/{student_id}" op)
>
> |
>
> parms_map (empty hash)
>
> |
>
> const_map (hash)
>
> |
>
> "marks" -------------------
> axutil_core_utils_map_internal_t (instance)
>
> |
>
> op_desc (NULL)
>
> |
>
> consts_map (empty
> hash)
>
> |
>
> params_map (hash)
>
> |
>
> "{subject_id}"
> ----------- axutil_core_utils_map_internal_t (instance)
>
>
> |
>
> op_desc (axis2_op_t*
> for "GET students/{student_id}/marks/{subject_id}" op)
>
> |
>
> consts_map / params_map (Both NULL)
>
> </pre>
>
> So at the Dispatching URL we can clearly sort out the operation and the
> parameter values.
>
> For matching patterns like {student_id}, {subject_id} and more complex
> matching like xx{p}yy{q}zz{r} the logic uses the function
> axis2_core_utils_match_url_component_with_pattern ( in
> src/core/util/core_utils.c)
> This is O(n^2) order (in worse case) algorithm.
>
> And what I want to discuss is the point whether the above described logic is
> better than the early logic which sequentilly checks all the mapping.
>
> Calculating the approximate time complexity takng n =numbe of operations, p
> = average URL mapping length
> The early logic = n/2 (<--go through all the operation in average) *
> O(p^2) (<--the complexity of
> axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2)
>
> For the second logic it is really complex to do a methematical analysis of
> the tiime complexity. Assuming (being optimistic:) average length of the url
> component is d (d <= p) and the average parameters in a url is k (k <=p/d)
> and taking hash search is O(1)
>
> The new logic = log(n) (<-- long n number of hash search) *(k*O(d^2)) (<--
> assuming k parameters have to execute the function
> axis2_core_utils_match_url_component_with_pattern) => O(logn * k* d^2)
>
> Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p and k
> <=p/d)
>
> Anyway the new logic contain some recursive functions and hash functions
> heavily which may slow down things at little n (number of operations),
> littld k (little number of url components) and little d (small length urls).
>
> So my question is do we need to favor on the smal number of operation so go
> back to old logic(after correcting bugs) or do we stay with the current
> logic?. Your opinions?
>
>
>
> --
> Thanks,
> Dimuthu Gamage
>
> http://www.dimuthu.org
> http://www.wso2.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Damitha Kumarage <da...@gmail.com>.
Hi Dimuthu,
Yes the blog post explain it very well. I could not understand it by
looking at your previous mail or by looking at the code.
Is there a way we can avoid recursion?
thanks
Damitha
Dimuthu Gamage wrote:
> Did a blog post explaining the $subject,
> http://www.dimuthu.org/blog/2008/11/21/apache-axis2c-restful-url-mapping-algorithm/
>
> Thanks
> Dimuthu
>
> On Thu, Nov 20, 2008 at 10:01 AM, Dimuthu Gamage <dimuthuc@gmail.com
> <ma...@gmail.com>> wrote:
>
> Hi devs,
>
> As you may have already noticed, I changed the REST URL pattern
> matching algorithm while fixing the
> https://issues.apache.org/jira/browse/AXIS2C-1290 issue and the
> WSF/PHP issue, https://wso2.org/jira/browse/WSFPHP-347. Since
> Apache's principle is to 'Commit first' I committed the code first
> (after making sure everything works), decided to start a
> discussion on that :)
>
> Basically What I have done is changing the code
> 1. Initializing the REST Mapping per operation -
> axis2_svc_get_rest_op_list_with_method_and_location ( in
> src/core/description/svc.c)
> 2. REST dispaching algorithm to find the operation and the
> matching patterns - axis2_rest_disp_find_op (in
> src/core/engine/rest_disp.c )
>
> At the initializing face It store the url pattern in a internal
> recursive structure call 'axutil_core_utils_map_internal_t' whcih
> is only used inside the core_utils.c function. And it store this
> structure for each operation in the svc->op_rest_map hash. Here is
> the structure of the struct.
>
> /* internal structure to keep the rest map in a multi level hash */
> typedef struct {
> /* the structure will keep as many as following fields */
>
> /* if the mapped value is directly the operation */
> axis2_op_t *op_desc;
>
> /* if the mapped value is a constant, this keeps a hash map of
> possible constants => corrosponding map_internal structure */
> axutil_hash_t *consts_map;
>
> /* if the mapped value is a param, this keeps a hash map of
> possible param_values => corrosponding_map_internal structre */
> axutil_hash_t *params_map;
>
> } axutil_core_utils_map_internal_t;
>
> For an example think you have operations with following REST
> mapping (Using the example attached in the
> https://issues.apache.org/jira/browse/AXIS2C-1290 and
> http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ )
>
> GET students
> GET students/{stduent_id}
> GET students/{student_id}/marks/{subject_id}
>
> Then thes svc->op_rest_map will be like
>
> <pre>
> svc->op_rest_map (hash)
> |
> "GET:students" ---------
> axutil_core_utils_map_internal_t (instance)
> |
> op_desc
> (axis2_op_t* for "GET students" op)
> |
> consts_map
> (empty hash)
> |
> params_map
> (hash)
>
> |
>
> "{student_id}" ------------- axutil_core_utils_map_internal_t
> (instance)
>
> |
>
> op_desc (axis2_op_t* for "GET
> students/{student_id}" op)
>
> |
>
> parms_map (empty hash)
>
> |
>
> const_map (hash)
>
> |
>
> "marks"
> ------------------- axutil_core_utils_map_internal_t (instance)
>
>
> |
>
>
> op_desc (NULL)
>
>
> |
>
>
> consts_map (empty hash)
>
>
> |
>
>
> params_map (hash)
>
>
> |
>
>
> "{subject_id}" ----------- axutil_core_utils_map_internal_t
> (instance)
>
>
> |
>
>
> op_desc (axis2_op_t* for "GET
> students/{student_id}/marks/{subject_id}" op)
>
> |
>
> consts_map / params_map (Both NULL)
>
>
> </pre>
>
> So at the Dispatching URL we can clearly sort out the operation
> and the parameter values.
>
> For matching patterns like {student_id}, {subject_id} and more
> complex matching like xx{p}yy{q}zz{r} the logic uses the function
> axis2_core_utils_match_url_component_with_pattern ( in
> src/core/util/core_utils.c)
> This is O(n^2) order (in worse case) algorithm.
>
> And what I want to discuss is the point whether the above
> described logic is better than the early logic which sequentilly
> checks all the mapping.
>
> Calculating the approximate time complexity takng n =numbe of
> operations, p = average URL mapping length
> The early logic = n/2 (<--go through all the operation in
> average) * O(p^2) (<--the complexity of
> axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2)
>
> For the second logic it is really complex to do a methematical
> analysis of the tiime complexity. Assuming (being optimistic:)
> average length of the url component is d (d <= p) and the average
> parameters in a url is k (k <=p/d) and taking hash search is O(1)
>
> The new logic = log(n) (<-- long n number of hash search)
> *(k*O(d^2)) (<-- assuming k parameters have to execute the
> function axis2_core_utils_match_url_component_with_pattern) =>
> O(logn * k* d^2)
>
> Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p
> and k <=p/d)
>
> Anyway the new logic contain some recursive functions and hash
> functions heavily which may slow down things at little n (number
> of operations), littld k (little number of url components) and
> little d (small length urls).
>
> So my question is do we need to favor on the smal number of
> operation so go back to old logic(after correcting bugs) or do we
> stay with the current logic?. Your opinions?
>
>
>
> --
> Thanks,
> Dimuthu Gamage
>
> http://www.dimuthu.org
> http://www.wso2.org
>
>
>
>
> --
> Thanks,
> Dimuthu Gamage
>
> http://www.dimuthu.org
> http://www.wso2.org
--
__________________________________________________________________
Damitha Kumarage
http://people.apache.org/
__________________________________________________________________
---------------------------------------------------------------------
To unsubscribe, e-mail: axis-c-dev-unsubscribe@ws.apache.org
For additional commands, e-mail: axis-c-dev-help@ws.apache.org
Re: REST URL Mapping - The changes done in pattern matching Algorithm
Posted by Dimuthu Gamage <di...@gmail.com>.
Did a blog post explaining the $subject,
http://www.dimuthu.org/blog/2008/11/21/apache-axis2c-restful-url-mapping-algorithm/
Thanks
Dimuthu
On Thu, Nov 20, 2008 at 10:01 AM, Dimuthu Gamage <di...@gmail.com> wrote:
> Hi devs,
>
> As you may have already noticed, I changed the REST URL pattern matching
> algorithm while fixing the
> https://issues.apache.org/jira/browse/AXIS2C-1290 issue and the WSF/PHP
> issue, https://wso2.org/jira/browse/WSFPHP-347. Since Apache's principle
> is to 'Commit first' I committed the code first (after making sure
> everything works), decided to start a discussion on that :)
>
> Basically What I have done is changing the code
> 1. Initializing the REST Mapping per operation -
> axis2_svc_get_rest_op_list_with_method_and_location ( in
> src/core/description/svc.c)
> 2. REST dispaching algorithm to find the operation and the matching
> patterns - axis2_rest_disp_find_op (in src/core/engine/rest_disp.c )
>
> At the initializing face It store the url pattern in a internal recursive
> structure call 'axutil_core_utils_map_internal_t' whcih is only used inside
> the core_utils.c function. And it store this structure for each operation in
> the svc->op_rest_map hash. Here is the structure of the struct.
>
> /* internal structure to keep the rest map in a multi level hash */
> typedef struct {
> /* the structure will keep as many as following fields */
>
> /* if the mapped value is directly the operation */
> axis2_op_t *op_desc;
>
> /* if the mapped value is a constant, this keeps a hash map of
> possible constants => corrosponding map_internal structure */
> axutil_hash_t *consts_map;
>
> /* if the mapped value is a param, this keeps a hash map of
> possible param_values => corrosponding_map_internal structre */
> axutil_hash_t *params_map;
>
> } axutil_core_utils_map_internal_t;
>
> For an example think you have operations with following REST mapping
> (Using the example attached in the
> https://issues.apache.org/jira/browse/AXIS2C-1290 and
> http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ )
>
> GET students
> GET students/{stduent_id}
> GET students/{student_id}/marks/{subject_id}
>
> Then thes svc->op_rest_map will be like
>
> <pre>
> svc->op_rest_map (hash)
> |
> "GET:students" --------- axutil_core_utils_map_internal_t
> (instance)
> |
> op_desc
> (axis2_op_t* for "GET students" op)
> |
> consts_map (empty
> hash)
> |
> params_map (hash)
> |
>
> "{student_id}" ------------- axutil_core_utils_map_internal_t (instance)
>
> |
>
> op_desc (axis2_op_t* for "GET students/{student_id}" op)
>
> |
>
> parms_map (empty hash)
>
> |
>
> const_map (hash)
>
> |
>
> "marks" -------------------
> axutil_core_utils_map_internal_t (instance)
>
> |
>
> op_desc (NULL)
>
> |
>
> consts_map (empty
> hash)
>
> |
>
> params_map (hash)
>
>
> |
>
>
> "{subject_id}" ----------- axutil_core_utils_map_internal_t (instance)
>
>
> |
>
> op_desc (axis2_op_t*
> for "GET students/{student_id}/marks/{subject_id}" op)
>
> |
>
> consts_map / params_map (Both NULL)
>
>
> </pre>
>
> So at the Dispatching URL we can clearly sort out the operation and the
> parameter values.
>
> For matching patterns like {student_id}, {subject_id} and more complex
> matching like xx{p}yy{q}zz{r} the logic uses the function
> axis2_core_utils_match_url_component_with_pattern ( in
> src/core/util/core_utils.c)
> This is O(n^2) order (in worse case) algorithm.
>
> And what I want to discuss is the point whether the above described logic
> is better than the early logic which sequentilly checks all the mapping.
>
> Calculating the approximate time complexity takng n =numbe of operations, p
> = average URL mapping length
> The early logic = n/2 (<--go through all the operation in average) *
> O(p^2) (<--the complexity of
> axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2)
>
> For the second logic it is really complex to do a methematical analysis of
> the tiime complexity. Assuming (being optimistic:) average length of the url
> component is d (d <= p) and the average parameters in a url is k (k <=p/d)
> and taking hash search is O(1)
>
> The new logic = log(n) (<-- long n number of hash search) *(k*O(d^2)) (<--
> assuming k parameters have to execute the function
> axis2_core_utils_match_url_component_with_pattern) => O(logn * k* d^2)
>
> Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p and k
> <=p/d)
>
> Anyway the new logic contain some recursive functions and hash functions
> heavily which may slow down things at little n (number of operations),
> littld k (little number of url components) and little d (small length urls).
>
>
> So my question is do we need to favor on the smal number of operation so go
> back to old logic(after correcting bugs) or do we stay with the current
> logic?. Your opinions?
>
>
>
> --
> Thanks,
> Dimuthu Gamage
>
> http://www.dimuthu.org
> http://www.wso2.org
>
--
Thanks,
Dimuthu Gamage
http://www.dimuthu.org
http://www.wso2.org