Asp Forum - Fast implementation of XML escape

Bob Hutchison

8/3/2007 12:41:00 PM

Hi,

Does anyone know of a fast implementation of the XML escape method
(the one that converts '"<>& to " etc.)?

I did some benchmarking on one of my applications and the
implementation I have, which I thought was okay -- simple minded for
sure, but okay -- turns out to be a bottle neck in certain operations.

I used ruby-prof with a simple test, running over a 400 character
string 50,000 times or so. Running the profiler on version0 (below)
took 1.39 seconds.

def version0(input)
# all kinds of other processing of input simulated by the input.dup
result = input.dup

return result
end

The original simple minded way was, under ruby-prof ran in 8.74 seconds:

def version1(input)
# all kinds of other processing of input simulated by the input.dup
result = input.dup

result.gsub!("&", "&")
result.gsub!("<", "<")
result.gsub!(">", ">")
result.gsub!("'", "'")
result.gsub!("\"", """)

return result
end

The best I've come up with so far is, under ruby-prof ran in 3.33:

def version2(input)
# all kinds of other processing of input simulated by the input.dup
result = input.dup

result.gsub!(/[&<>'"]/) do | match |
case match
when '&' then return '&'
when '<' then return '<'
when '>' then return '>'
when "'" then return '''
when '"' then return '&quote;'
end
end

return result
end

After accounting for overhead, 3.8 times faster is good, I'd like it
faster still. BTW, gsub is only marginally slower that gsub! I've
tried using simple iteration, gsub with a hash to avoid the case, and
variations, all slower to a lot slower than version 1, nothing really
near version2 (which really was the first variation I tried).

Any ideas?

Cheers,
Bob

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.rec...
hutch
http://www.rec... -- works on http://www.racon...
cms-for-static-content/home/

4 Answers

Robert Klemme

8/3/2007 12:47:00 PM

2007/8/3, Bob Hutchison <hutch@recursive.ca>:
> Hi,
>
> Does anyone know of a fast implementation of the XML escape method
> (the one that converts '"<>& to " etc.)?
>
> I did some benchmarking on one of my applications and the
> implementation I have, which I thought was okay -- simple minded for
> sure, but okay -- turns out to be a bottle neck in certain operations.
>
> I used ruby-prof with a simple test, running over a 400 character
> string 50,000 times or so. Running the profiler on version0 (below)
> took 1.39 seconds.
>
> def version0(input)
> # all kinds of other processing of input simulated by the input.dup
> result = input.dup
>
> return result
> end
>
> The original simple minded way was, under ruby-prof ran in 8.74 seconds:
>
> def version1(input)
> # all kinds of other processing of input simulated by the input.dup
> result = input.dup
>
> result.gsub!("&", "&")
> result.gsub!("<", "<")
> result.gsub!(">", ">")
> result.gsub!("'", "'")
> result.gsub!("\"", """)
>
> return result
> end
>
> The best I've come up with so far is, under ruby-prof ran in 3.33:
>
> def version2(input)
> # all kinds of other processing of input simulated by the input.dup
> result = input.dup
>
> result.gsub!(/[&<>'"]/) do | match |
> case match
> when '&' then return '&'
> when '<' then return '<'
> when '>' then return '>'
> when "'" then return '''
> when '"' then return '&quote;'
> end
> end
>
> return result
> end
>
> After accounting for overhead, 3.8 times faster is good, I'd like it
> faster still. BTW, gsub is only marginally slower that gsub! I've
> tried using simple iteration, gsub with a hash to avoid the case, and
> variations, all slower to a lot slower than version 1, nothing really
> near version2 (which really was the first variation I tried).
>
> Any ideas?

You are on the right track. There is just one thing to improve: get
rid of "case":

class Converter
MAP = {
"&" => "&",
# ...
}

def self.convert(s)
s.gsub(/[&<>'"]/) do |m|
MAP[m] || "ERROR"
end
end
end

Also, I believe x.dup.gsub! is less efficient than doing just a single x.gsub.

Kind regards

robert

Bob Hutchison

8/3/2007 12:56:00 PM

Sorry, There are some corrections to this post. I made two STUPID
errors, one a cut and paste error into the message, and another in
recording my test results.

I apologise again.

Here is the real situation:

------

Does anyone know of a fast implementation of the XML escape method
(the one that converts '"<>& to " etc.)?

I did some benchmarking on one of my applications and the
implementation I have, which I thought was okay -- simple minded for
sure, but okay -- turns out to be a bottle neck in certain operations.

I used ruby-prof with a simple test, running over a 400 character
string 50,000 times or so. Running the profiler on version0 (below)
took 1.39 seconds.

def version0(input)
# all kinds of other processing of input simulated by the input.dup
result = input.dup

return result
end

The original simple minded way was, under ruby-prof ran in 8.74 seconds:

def version1(input)
# all kinds of other processing of input simulated by the input.dup
result = input.dup

result.gsub!("&", "&")
result.gsub!("<", "<")
result.gsub!(">", ">")
result.gsub!("'", "'")
result.gsub!("\"", """)

return result
end

[ the version2 that I originally posted was a cut and paste error
from an old file (too many windows open), there should not have been
those returns in the gsub. Then to compound things, I had made a typo
in the test case and the loop was not run as often, so rather than
taking 3.33 seconds it in fact took 105 seconds ]

The simple-minded approach is the fastest I've come up with.

Any any better ideas?

Cheers,
Bob

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.rec...
hutch
http://www.rec... -- works on http://www.racon...
cms-for-static-content/home/

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.rec...
hutch
http://www.rec... -- works on http://www.racon...
cms-for-static-content/home/

Bob Hutchison

8/3/2007 1:00:00 PM

Hi Robert,

Thanks for the response.

On 3-Aug-07, at 8:47 AM, Robert Klemme wrote:
>
> You are on the right track. There is just one thing to improve: get
> rid of "case":
>
> class Converter
> MAP = {
> "&" => "&",
> # ...
> }
>
> def self.convert(s)
> s.gsub(/[&<>'"]/) do |m|
> MAP[m] || "ERROR"
> end
> end
> end

My version3 was:

@@convert = {
'&' => '&',
'<' => '<',
'>' => '>',
"'" => ''',
'"' => '"'
}

def version3(input)
# all kinds of other processing of input simulated by the input.dup
result = input.dup

result.gsub!(/[&<>'"]/) do | match |
@@convert[match]
end

return result
end

which is pretty much what you suggested, but it takes 29.71 seconds
(rather than 8.74 seconds).

>
> Also, I believe x.dup.gsub! is less efficient than doing just a
> single x.gsub.

That dup is just so I could 1) simulate some extra work that I had to
do; and 2) make sure I didn't permanently change the test string with
the gsub!.

Thanks!

Cheers,
Bob

>
> Kind regards
>
> robert
>

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.rec...
hutch
http://www.rec... -- works on http://www.racon...
cms-for-static-content/home/

Robert Klemme

8/3/2007 1:07:00 PM

2007/8/3, Bob Hutchison <hutch@recursive.ca>:
> Hi Robert,
>
> Thanks for the response.
>
>
> On 3-Aug-07, at 8:47 AM, Robert Klemme wrote:
> >
> > You are on the right track. There is just one thing to improve: get
> > rid of "case":
> >
> > class Converter
> > MAP = {
> > "&" => "&",
> > # ...
> > }
> >
> > def self.convert(s)
> > s.gsub(/[&<>'"]/) do |m|
> > MAP[m] || "ERROR"
> > end
> > end
> > end
>
>
> My version3 was:
>
> @@convert = {
> '&' => '&',
> '<' => '<',
> '>' => '>',
> "'" => ''',
> '"' => '"'
> }
>
> def version3(input)
> # all kinds of other processing of input simulated by the input.dup
> result = input.dup
>
> result.gsub!(/[&<>'"]/) do | match |
> @@convert[match]
> end
>
> return result
> end
>
> which is pretty much what you suggested, but it takes 29.71 seconds
> (rather than 8.74 seconds).

The overhead of the block form is significant. It probably pays off
when you have longer strings. That depends.

Kind regards

robert

comp.lang.ruby

Fast implementation of XML escape

Bob Hutchison

Robert Klemme

Bob Hutchison

Bob Hutchison

Robert Klemme

x Login to ForumsZone