You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@spamassassin.apache.org by Sidney Markowitz <si...@sidney.com> on 2004/06/25 07:30:28 UTC
Hash function performance
I started a thread off of this list that turned out to be something that
should be discussed here where it is public and archived.
I'll catch it up now from the beginning and then we can continue here.
Starting from where I wandered from one topic into the sa-dev related
one and proceeding in chronological order, email between me and Michael
Parker:
=========================
Speaking of hash functions, we settled on SHA-1 as being overkill but
already available and fast enough. Someone had suggested Jenkin's hash,
but that was not suitable being limited to 32 bits. Recently I have been
doing some digging into hash functions and I think that FMV-1 would be
better suited for what we are doing and quite a bit faster. What I would
want to do is submit a perl xs Digest::FMV-1 to CPAN modeled after the
Digest::SHA-1 that we use. The code is very simple and on any modern
computer that has a fast 32 bit integer multiply it is even faster than
Jenkin's hash while being extensible to many different bit sizes.
Before I do that, is anyone set up to easily run some test with Bayes
MySQL and some profiling that would give a general idea how much time is
spent in the SHA-1 function? I would like to know if the potential time
savings is enough to be worth bothering with this.
-- sidney
========================
Michael Parker wrote:
> I can do some profiling.
>
> I'm not certain there is a easy path to switch from
> one hash to the next since it's a oneway hash.
If you could just determine what percent of the overall time is spent
computing SHA-1 that would answer the question if it is even worth
worrying about. If it is a clear win, then before 3.0 goes out is the
best time to make a change that requires rebuilding the database. And if
the total SHA-1 time is an insignificant percentage of the total then
there's nothing to worry about.
-- sidney
========================
I think this might be a good thing to switch over to the dev list if
it's something we would like to pursue.
Here are the results for a sa-learn on 2000 msgs under MySQL:
%Time ExclSec CumulS #Calls sec/call Csec/c Name
26.1 56.75 56.753 571263 0.0001 0.0001 DBI::st::execute
16.1 35.12 35.126 656147 0.0001 0.0001 DBI::db::do
11.3 24.55 167.32 482158 0.0001 0.0003
Mail::SpamAssassin::BayesStore::SQ
5 L::_put_token
6.57 14.28 98.080 482158 0.0000 0.0002
Mail::SpamAssassin::BayesStore::SQ
L::tok_get
5.40 11.72 11.726 114252 0.0000 0.0000 DBI::common::FETCH
4.82 10.48 10.787 75201 0.0001 0.0001
Mail::SpamAssassin::Bayes::tokeniz
e_line
4.06 8.814 31.217 2000 0.0044 0.0156
Mail::SpamAssassin::Bayes::tokeniz
e
3.87 8.419 20.145 571263 0.0000 0.0000 DBD::_::db::prepare_cached
3.09 6.711 6.711 486162 0.0000 0.0000 DBI::st::fetchrow_array
3.02 6.557 216.37 2000 0.0033 0.1082
Mail::SpamAssassin::Bayes::learn_t
1 rapped
2.86 6.223 173.54 482158 0.0000 0.0004
Mail::SpamAssassin::BayesStore::SQ
8 L::tok_count_change
2.63 5.713 5.713 571263 0.0000 0.0000 DBI::st::finish
2.30 4.996 25.141 571263 0.0000 0.0000 DBI::db::prepare_cached
1.71 3.711 5.531 139666 0.0000 0.0000
Mail::SpamAssassin::Message::Node:
:get_header
1.68 3.661 4.175 215202 0.0000 0.0000
Mail::SpamAssassin::Message::Node:
:header
1.29 2.800 5.230 839953 0.0000 0.0000 Mail::SpamAssassin::SHA1::sha1
1.15 2.497 4.757 2005 0.0012 0.0024
Mail::SpamAssassin::Message::new
1.12 2.430 2.430 839953 0.0000 0.0000 Digest::SHA1::sha1
1.01 2.201 6.417 2000 0.0011 0.0032
Mail::SpamAssassin::Bayes::tokeniz
e_headers
0.96 2.093 2.209 12667 0.0002 0.0002
Mail::SpamAssassin::Message::Metad
ata::parse_received_line
0.84 1.815 1.815 9933 0.0002 0.0002
Mail::SpamAssassin::Util::Registra
rBoundaries::split_domain
0.78 1.698 4.337 39929 0.0000 0.0001
Mail::SpamAssassin::HTML::html_tag
0.66 1.426 4.540 2000 0.0007 0.0023
Mail::SpamAssassin::PerMsgStatus::
get_uri_list
0.62 1.351 240.88 2000 0.0007 0.1204
Mail::SpamAssassin::ArchiveIterato
5 r::run_mailbox
0.61 1.325 6.130 4000 0.0003 0.0015
Mail::SpamAssassin::Message::Node:
:get_all_headers
0.24 0.526 0.526 2459 0.0002 0.0002
Mail::SpamAssassin::Message::Node:
:finish
0.24 0.514 0.514 4000 0.0001 0.0001
Mail::SpamAssassin::Message::Node:
:delete_header
0.24 0.514 0.514 63987 0.0000 0.0000
Mail::SpamAssassin::Message::Node:
:_decode_header
0.23 0.493 0.739 21980 0.0000 0.0000
Mail::SpamAssassin::HTML::html_tex
t
0.22 0.484 0.483 23471 0.0000 0.0000
Mail::SpamAssassin::HTML::html_tes
ts
0.22 0.474 0.474 10733 0.0000 0.0000
Mail::SpamAssassin::HTML::display_
text
0.21 0.447 0.819 16037 0.0000 0.0001
Mail::SpamAssassin::HTML::text_sty
le
0.21 0.447 0.454 1 0.4470 0.4540
Mail::SpamAssassin::ArchiveIterato
r::scan_mailbox
0.20 0.441 0.441 6000 0.0001 0.0001
Mail::SpamAssassin::Message::split
Here are the results from an sa-learn on 2000 msgs under DBM:
%Time ExclSec CumulS #Calls sec/call Csec/c Name
24.6 33.94 33.943 203774 0.0000 0.0000 DB_File::FETCH
18.6 25.66 58.852 482158 0.0001 0.0001
Mail::SpamAssassin::BayesStore::DB
M::tok_put
9.16 12.64 27.500 482158 0.0000 0.0001
Mail::SpamAssassin::BayesStore::DB
M::tok_unpack
7.95 10.97 10.970 573480 0.0000 0.0000 DB_File::STORE
7.77 10.72 11.337 75201 0.0001 0.0002
Mail::SpamAssassin::Bayes::tokeniz
e_line
6.51 8.984 32.067 2000 0.0045 0.0160
Mail::SpamAssassin::Bayes::tokeniz
e
3.75 5.180 93.745 482158 0.0000 0.0002
Mail::SpamAssassin::BayesStore::DB
M::tok_sync_counters
2.96 4.087 4.087 482158 0.0000 0.0000
Mail::SpamAssassin::BayesStore::DB
M::tok_pack
2.83 3.911 5.881 139666 0.0000 0.0000
Mail::SpamAssassin::Message::Node:
:get_header
2.55 3.521 4.145 215202 0.0000 0.0000
Mail::SpamAssassin::Message::Node:
:header
2.24 3.097 137.13 2000 0.0015 0.0686
Mail::SpamAssassin::Bayes::learn_t
7 rapped
1.93 2.657 4.807 2005 0.0013 0.0024
Mail::SpamAssassin::Message::new
1.91 2.640 5.090 839953 0.0000 0.0000 Mail::SpamAssassin::SHA1::sha1
1.81 2.503 96.249 482158 0.0000 0.0002
Mail::SpamAssassin::BayesStore::DB
M::tok_count_change
1.78 2.450 2.450 839953 0.0000 0.0000 Digest::SHA1::sha1
1.72 2.371 6.727 2000 0.0012 0.0034
Mail::SpamAssassin::Bayes::tokeniz
e_headers
1.60 2.213 29.713 482158 0.0000 0.0001
Mail::SpamAssassin::BayesStore::DB
M::tok_get
1.55 2.133 2.339 12667 0.0002 0.0002
Mail::SpamAssassin::Message::Metad
ata::parse_received_line
1.33 1.831 162.08 2000 0.0009 0.0810
Mail::SpamAssassin::ArchiveIterato
4 r::run_mailbox
1.26 1.735 1.735 9933 0.0002 0.0002
Mail::SpamAssassin::Util::Registra
rBoundaries::split_domain
1.22 1.686 4.570 2000 0.0008 0.0023
Mail::SpamAssassin::PerMsgStatus::
get_uri_list
1.01 1.398 4.077 39929 0.0000 0.0001
Mail::SpamAssassin::HTML::html_tag
0.87 1.195 6.560 4000 0.0003 0.0016
Mail::SpamAssassin::Message::Node:
:get_all_headers
0.45 0.624 0.624 63987 0.0000 0.0000
Mail::SpamAssassin::Message::Node:
:_decode_header
0.45 0.614 0.614 4000 0.0002 0.0002
Mail::SpamAssassin::Message::Node:
:delete_header
0.44 0.603 0.849 21980 0.0000 0.0000
Mail::SpamAssassin::HTML::html_tex
t
0.41 0.567 5.716 94 0.0060 0.0608 HTML::Parser::parse
0.37 0.505 3.877 2000 0.0003 0.0019
Mail::SpamAssassin::Message::Metad
ata::parse_received_headers
0.35 0.477 0.969 16037 0.0000 0.0001
Mail::SpamAssassin::HTML::text_sty
le
0.35 0.476 0.476 2459 0.0002 0.0002
Mail::SpamAssassin::Message::Node:
:finish
0.34 0.475 0.475 16384 0.0000 0.0000
Mail::SpamAssassin::Bayes::tokeniz
e_mail_addrs
0.34 0.474 0.473 23471 0.0000 0.0000
Mail::SpamAssassin::HTML::html_tes
Michael
Re: Hash function performance
Posted by Michael Parker <pa...@pobox.com>.
On Fri, Jun 25, 2004 at 05:34:28PM +1200, Sidney Markowitz wrote:
> Michael,
>
> I have two questions. 1) What do the numbers show? How much will we save
> if the hash function is twice as fast as SHA-1? Five times as fast?
I'm not really a profiling expert, Daniel might have better insight.
I do have a fairly reliable benchmark script so I can test changes for
overall performance gains.
For the MySQL run total elapsed time was 419.5182 Seconds,
Digest::SHA1::sha1 took 1.12% of that. The sha1 call appears to be
one of the most called, if not THE most called function in the entire
run. If I read it all right, no matter how much you better the
performance you're never going to gain more than a couple of seconds
on a run such as this. So it's possibly not worth it, but might be
interesting to test, and should be fairly easy to implement, assuming
the appropriate module exists.
> 2) can you do a similar profile for a spam filtering run, rather than
> sa-learn?
Yeah, it'll be tomorrow though.
Michael
Re: Hash function performance
Posted by Michael Parker <pa...@pobox.com>.
On Fri, Jun 25, 2004 at 05:34:28PM +1200, Sidney Markowitz wrote:
> 2) can you do a similar profile for a spam filtering run, rather than
> sa-learn?
This is from a spamassassin -L on 2000 ham msgs:
Total Elapsed Time = 631.9578 Seconds
User+System Time = 418.8978 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
12.1 50.72 50.722 465578 0.0001 0.0001 DBI::st::execute
6.45 27.03 27.031 485693 0.0001 0.0001 DBI::db::do
4.49 18.79 136.27 398251 0.0000 0.0003 Mail::SpamAssassin::BayesStore::SQ
5 L::_put_token
4.31 18.03 18.562 135655 0.0001 0.0001 Mail::SpamAssassin::Bayes::tokeniz
e_line
4.29 17.97 75.353 2000 0.0090 0.0377 Mail::SpamAssassin::Bayes::scan
3.81 15.96 55.118 3794 0.0042 0.0145 Mail::SpamAssassin::Bayes::tokeniz
e
3.56 14.91 22.302 632912 0.0000 0.0000 Mail::SpamAssassin::Message::Node:
:get_header
3.28 13.75 13.791 2000 0.0069 0.0069 Mail::SpamAssassin::PerMsgStatus::
UNRESOLVED_TEMPLATE_head_test
3.21 13.43 85.996 398251 0.0000 0.0002 Mail::SpamAssassin::BayesStore::SQ
L::tok_get
2.31 9.682 106.81 10000 0.0010 0.0107 Mail::SpamAssassin::PerMsgStatus::
5 run_eval_tests
2.31 9.659 9.659 893770 0.0000 0.0000 DBI::common::FETCH
2.23 9.333 20.992 767056 0.0000 0.0000 Mail::SpamAssassin::PerMsgStatus::
get
1.72 7.212 18.614 451580 0.0000 0.0000 DBD::_::db::prepare_cached
1.68 7.050 8.327 34000 0.0002 0.0002 Mail::SpamAssassin::PerMsgStatus::
_get_tag
1.66 6.938 7.394 527342 0.0000 0.0000 Mail::SpamAssassin::Message::Node:
:header
1.48 6.182 6.182 411649 0.0000 0.0000 DBI::st::fetchrow_array
1.42 5.966 177.48 1801 0.0033 0.0985 Mail::SpamAssassin::Bayes::learn_t
3 rapped
1.36 5.715 141.99 398251 0.0000 0.0004 Mail::SpamAssassin::BayesStore::SQ
0 L::tok_count_change
1.35 5.642 5.642 18648 0.0003 0.0003 Mail::SpamAssassin::Util::Registra
rBoundaries::split_domain
1.21 5.065 23.679 451580 0.0000 0.0001 DBI::db::prepare_cached
1.09 4.582 12.168 3794 0.0012 0.0032 Mail::SpamAssassin::Bayes::tokeniz
e_headers
1.04 4.361 8.472 141939 0.0000 0.0000 Mail::SpamAssassin::SHA1::sha1
0.98 4.111 4.111 141939 0.0000 0.0000 Digest::SHA1::sha1
0.95 3.972 3.972 465578 0.0000 0.0000 DBI::st::finish
0.93 3.897 21.337 13389 0.0003 0.0016 Mail::SpamAssassin::Message::Node:
:get_all_headers
0.81 3.391 79.142 2000 0.0017 0.0396 Mail::SpamAssassin::PerMsgStatus::
_body_tests_0
0.81 3.387 12.219 2000 0.0017 0.0061 Mail::SpamAssassin::BayesStore::SQ
L::tok_get_all
0.73 3.042 3.042 431921 0.0000 0.0000 Mail::SpamAssassin::Bayes::compute
_prob_for_token
0.60 2.518 32.122 2000 0.0013 0.0161 Mail::SpamAssassin::PerMsgStatus::
_head_tests_0
0.59 2.485 2.485 10039 0.0002 0.0002 DBI::st::fetchall_arrayref
0.59 2.461 4.363 2004 0.0012 0.0022 Mail::SpamAssassin::Message::new
0.59 2.457 2.457 2000 0.0012 0.0012 Mail::SpamAssassin::PerMsgStatus::
_check_unique_words
0.57 2.403 2.567 12680 0.0002 0.0002 Mail::SpamAssassin::Message::Metad
ata::parse_received_line
0.54 2.249 9.153 7801 0.0003 0.0012 Mail::SpamAssassin::PerMsgStatus::
get_uri_list
I'm with Daniel, I don't see a whole lot of benefit in replacing the
hash. I would fully support making Digest::SHA1 a required module and
removing the wrapper method.
Michael
Re: Hash function performance
Posted by Loren Wilton <lw...@earthlink.net>.
> Digest::FNV module in CPAN, but it would be trivial to create one that
> uses a C implementation just like Digest::SHA1, using the public domain
> C code from the link I mentioned above.
> The question I have now is whether the difference
> would be enough to bother making the change. It appears that the answer
> is no, but it would be worth it to require SHA-1 and drop the overhead
> of the wrapper function that handles the case of no Digest::SHA1
available.
An outside opinion, based on having done lots of performance tuning and
system maintainanece on other projects:
Is it worth doing the change for the fraction of a percent gain, by itself?
No.
However: Given that there is no FNV-1 module and one would have to be
created; you have a wrapper (I guess in case SHA1:Digest isn't installed);
and you can gain a slight performance increase from removing the wrapper and
changing the function; and that this would be a good time to do it - and
most importantly, it might slightly reduce code complexity -
Under those conditions I would suggest the following:
1. Make an FNV::Digest module and *include it as part of the SA distro*.
2. Optionally contribute the module to CPAN or whoever is appropriate as
a standard function
3. Delete the current wrapper and SHA-1 call and replace with the call to
the new code, which will be known to be present.
I suggest this mostly on the basis of code reduction rather than any
performance gain.
Loren
Re: Hash function performance
Posted by Michael Parker <pa...@pobox.com>.
On Sat, Jun 26, 2004 at 11:04:24AM +1200, Sidney Markowitz wrote:
> Michael Parker wrote:
>
> >There is an upgrade path for DBM files to
> >the new hash format
>
> Yes, that's better phrasing for what I meant. It won't make a difference
> to anyone who has not already converted to an svn or pre-release 3.0 if
> we change the hash function now. I think it is a low risk change. But
> the benefit is tiny. But doing it later is more painful, requiring yet
> another upgrade or recreation of the database. So do we go for it now? I
> think probably not, but I want to put the issue out there before we are
> any closer to 3.0 release.
I'm -1 on changing the hashing format at this point. I'm happy to
change that opinion if some large benefit is found.
Michael
Re: Hash function performance
Posted by Sidney Markowitz <si...@sidney.com>.
Michael Parker wrote:
> There is an upgrade path for DBM files to
> the new hash format
Yes, that's better phrasing for what I meant. It won't make a difference
to anyone who has not already converted to an svn or pre-release 3.0 if
we change the hash function now. I think it is a low risk change. But
the benefit is tiny. But doing it later is more painful, requiring yet
another upgrade or recreation of the database. So do we go for it now? I
think probably not, but I want to put the issue out there before we are
any closer to 3.0 release.
-- sidney
Re: Hash function performance
Posted by Michael Parker <pa...@pobox.com>.
On Sat, Jun 26, 2004 at 10:36:31AM +1200, Sidney Markowitz wrote:
>
> If we would want to save the fraction of a percent that switching from
> SHA-1 to FNV-1 would give us, now is the time, because everyone
> upgrading to version 3.0 will have to recreate their Bayes db with the
> new hash keys anyway.
>
Recreate is the wrong word. There is an upgrade path for DBM files to
the new hash format. Now folks who have already upgraded (via an svn
or pre1 installs) will need to recreate if we change the hash method.
Michael
Re: Hash function performance
Posted by Sidney Markowitz <si...@sidney.com>.
Correction and a link:
I just noticed that in earlier posts I typed "FMV" when it should have
been FNV. Trying to find the former would be quite confusing.
The correct reference is http://www.isthe.com/chongo/tech/comp/fnv/
Scott A Crosby wrote:
> Earlier Jenkin's
> hash was rejected because its output was only 32 bits. Run it twice
> with two different keys to get 64 bits of output.
Totally aside from the question of whether it is worth it to change
anything to have a faster hash function, the reason I started this
thread is that I discovered the FNV-1 hash function, which is faster
than Jenkin's and can be used to generate larger than 32 bit hashes. Bob
Jenkins now refers to hit on his hash function web page. There is no
Digest::FNV module in CPAN, but it would be trivial to create one that
uses a C implementation just like Digest::SHA1, using the public domain
C code from the link I mentioned above. If I knew this when we switched
to using hashes for Bayes a few months ago I would have gone with that
instead of SHA-1. The question I have now is whether the difference
would be enough to bother making the change. It appears that the answer
is no, but it would be worth it to require SHA-1 and drop the overhead
of the wrapper function that handles the case of no Digest::SHA1 available.
If we would want to save the fraction of a percent that switching from
SHA-1 to FNV-1 would give us, now is the time, because everyone
upgrading to version 3.0 will have to recreate their Bayes db with the
new hash keys anyway.
-- sidney
Re: Hash function performance
Posted by Scott A Crosby <sc...@cs.rice.edu>.
On 25 Jun 2004 18:26:17 -0500, Scott A Crosby <sc...@cs.rice.edu> writes:
Whoops, didn't intend this to go out till I got data.
> I'm doing a 3.0 from the CVS nightly on the web page.
>
> First thing I notice is that forking overhead is gone, and in the
> non-bayes case, regular expression matching looks to be a bottleneck
> with >40% of the CPU time. Either the other overheads have been
> reduced, or regexps have gotten a lot slower.
>
> With bayes, results look very different. Functions dealing with
> 'magic' have jumped, hugely in the profile compared to 2.63 w/ bayes
> and 3.0 w/o bayes. They're using at least three times more CPU time
> than regexp matching.
>
>
> In the non-bayes case:
>
> CPU: Athlon, speed 1837.72 MHz (estimated)
> Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 1000000
> samples % app name symbol name
> 278758 37.1061 perl S_regmatch
> 41368 5.5066 perl S_find_byclass
> 40040 5.3298 libc-2.3.2.so (no symbols)
> 25855 3.4416 perl S_regtry
> 25830 3.4383 perl S_reginclass
> 18666 2.4847 perl S_hv_fetch_common
> 17591 2.3416 perl S_regrepeat
> 16418 2.1854 perl Perl_leave_scope
> 10221 1.3605 perl Perl_sv_setsv_flags
> 9854 1.3117 perl Perl_pp_padsv
> 9761 1.2993 perl Perl_pp_nextstate
>
>
> In the bayes case:
After 20,000 messages:
Re: Hash function performance
Posted by Scott A Crosby <sc...@cs.rice.edu>.
On 25 Jun 2004 18:26:17 -0500, Scott A Crosby <sc...@cs.rice.edu> writes:
Whoops, didn't intend this to go out till I got data.
> I'm doing a 3.0 from the CVS nightly on the web page.
>
> First thing I notice is that forking overhead is gone, and in the
> non-bayes case, regular expression matching looks to be a bottleneck
> with >40% of the CPU time. Either the other overheads have been
> reduced, or regexps have gotten a lot slower.
>
> With bayes, results look very different. Functions dealing with
> 'magic' have jumped, hugely in the profile compared to 2.63 w/ bayes
> and 3.0 w/o bayes. They're using at least three times more CPU time
> than regexp matching.
>
>
> In the non-bayes case:
>
> CPU: Athlon, speed 1837.72 MHz (estimated)
> Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 1000000
> samples % app name symbol name
> 278758 37.1061 perl S_regmatch
> 41368 5.5066 perl S_find_byclass
> 40040 5.3298 libc-2.3.2.so (no symbols)
> 25855 3.4416 perl S_regtry
> 25830 3.4383 perl S_reginclass
> 18666 2.4847 perl S_hv_fetch_common
> 17591 2.3416 perl S_regrepeat
> 16418 2.1854 perl Perl_leave_scope
> 10221 1.3605 perl Perl_sv_setsv_flags
> 9854 1.3117 perl Perl_pp_padsv
> 9761 1.2993 perl Perl_pp_nextstate
>
>
> In the bayes case:
After 4,000 messages:
samples % app name symbol name
324700 8.9652 perl S_regmatch
206709 5.7074 perl restore_magic
205653 5.6782 perl Perl_mg_get
143322 3.9572 libc-2.3.2.so (no symbols)
142252 3.9277 perl S_save_magic
139293 3.8460 perl Perl_save_alloc
128485 3.5475 perl Perl_sv_setsv_flags
120541 3.3282 libdb3.so.3.0.2 (no symbols)
104162 2.8760 perl Perl_mg_set
102750 2.8370 perl Perl_save_destructor_x
102359 2.8262 perl Perl_pp_padsv
86991 2.4019 perl Perl_sv_magic
85570 2.3626 perl Perl_sv_2iv
80832 2.2318 perl Perl_runops_standard
61224 1.6904 perl Perl_sv_setiv
After 35k messages.
samples % app name symbol name
2534332 7.8080 perl S_regmatch
1892554 5.8308 perl restore_magic
1883650 5.8033 perl Perl_mg_get
1302141 4.0118 perl S_save_magic
1261665 3.8871 perl Perl_save_alloc
1256240 3.8704 libc-2.3.2.so (no symbols)
1168978 3.6015 perl Perl_sv_setsv_flags
1031635 3.1784 libdb3.so.3.0.2 (no symbols)
957873 2.9511 perl Perl_mg_set
937394 2.8880 perl Perl_save_destructor_x
922467 2.8420 perl Perl_pp_padsv
787831 2.4272 perl Perl_sv_magic
Scott
Re: Hash function performance
Posted by Scott A Crosby <sc...@cs.rice.edu>.
On Fri, 25 Jun 2004 15:01:18 -0700, Daniel Quinlan <qu...@pathname.com> writes:
> > After about 24,000 messages have been processed, bayes performance
> > declines by 40% (perhaps because it has autolearned enough spam and is
> > now classifying) and libdb3 is responsible for 11% of runtime. About
> > 6% of runtime seems to be identifiably caused by copy-on-write from
> > spamd's forking behavior.
>
> It should be classifying long before 24,000 messages have been scanned.
> More like 500 to 1000. It's probably because it's expiring some by that
> point.
>
> Can you generate some profiles using 3.0.0-pre1?
I'm doing a 3.0 from the CVS nightly on the web page.
First thing I notice is that forking overhead is gone, and in the
non-bayes case, regular expression matching looks to be a bottleneck
with >40% of the CPU time. Either the other overheads have been
reduced, or regexps have gotten a lot slower.
With bayes, results look very different. Functions dealing with
'magic' have jumped, hugely in the profile compared to 2.63 w/ bayes
and 3.0 w/o bayes. They're using at least three times more CPU time
than regexp matching.
In the non-bayes case:
CPU: Athlon, speed 1837.72 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 1000000
samples % app name symbol name
278758 37.1061 perl S_regmatch
41368 5.5066 perl S_find_byclass
40040 5.3298 libc-2.3.2.so (no symbols)
25855 3.4416 perl S_regtry
25830 3.4383 perl S_reginclass
18666 2.4847 perl S_hv_fetch_common
17591 2.3416 perl S_regrepeat
16418 2.1854 perl Perl_leave_scope
10221 1.3605 perl Perl_sv_setsv_flags
9854 1.3117 perl Perl_pp_padsv
9761 1.2993 perl Perl_pp_nextstate
In the bayes case:
Re: Hash function performance
Posted by Daniel Quinlan <qu...@pathname.com>.
Scott A Crosby <sc...@cs.rice.edu> writes:
> Function call overhead is less than 100ns. 420 times/message * 20
> messages/sec is only .1% of overall CPU time. SHA-1 is also fairly
> expensive, because it hashes in blocks of 64 bytes. Earlier Jenkin's
> hash was rejected because its output was only 32 bits. Run it twice
> with two different keys to get 64 bits of output.
Well, the intermediate SHA1 function does nearly doubles the time
(function call overhead, copying into a temporary variable that's not
really needed, the if-else statement).
> I've run spamassassin through OProfile.
Very nice, thanks.
> From the OProfile results, with bayes activated, it appears that only
> 10% or so of the runtime is spent in the regular expression
> code.
Body scanning does have costs in addition to the regular expression
matching itself.
> After about 24,000 messages have been processed, bayes performance
> declines by 40% (perhaps because it has autolearned enough spam and is
> now classifying) and libdb3 is responsible for 11% of runtime. About
> 6% of runtime seems to be identifiably caused by copy-on-write from
> spamd's forking behavior.
It should be classifying long before 24,000 messages have been scanned.
More like 500 to 1000. It's probably because it's expiring some by that
point.
Can you generate some profiles using 3.0.0-pre1?
Daniel
--
Daniel Quinlan
http://www.pathname.com/~quinlan/
Re: Hash function performance
Posted by Scott A Crosby <sc...@cs.rice.edu>.
On 24 Jun 2004 23:00:47 -0700, Daniel Quinlan <qu...@pathname.com> writes:
> I think the bigger performance issue is given the frequency with which
> we call the SHA1 routine (about 420 times per message for this data set)
> is to _avoid that extra function call_.
Function call overhead is less than 100ns. 420 times/message * 20
messages/sec is only .1% of overall CPU time. SHA-1 is also fairly
expensive, because it hashes in blocks of 64 bytes. Earlier Jenkin's
hash was rejected because its output was only 32 bits. Run it twice
with two different keys to get 64 bits of output.
> > I have two questions. 1) What do the numbers show? How much will we save
> > if the hash function is twice as fast as SHA-1? Five times as fast?
>
> Here are the results for a sa-learn on 2000 msgs under MySQL:
>
> Also, the time per call is not measurable, so I suspect most of the time
> is simply spent in the overhead of a function call, passing data in and
> out of Digest::SHA1, etc. I don't think it's worth it.
>
> I think more is to be gained in these areas:
>
> - global optimizations to regular expression body tests (the test set
> that's the most expensive)
> - general performance improvements (start with some Devel::DProf data)
> - the spamd architecture (too much overhead per message)
> - reexamining the idea of not doing work when it is not needed (not to
> be entered into lightly since it can often be more expensive)
I've run spamassassin through OProfile. Oprofile is a system wide
kernel level profiler that profiles without needing to modify binaries
or libraries. I've got a quick run on spamc/spamd 2.63 running on
stock perl 5.8.4 with the HTML::Parser from CPAN. I'm using the
default database library.
>From the OProfile results, with bayes activated, it appears that only
10% or so of the runtime is spent in the regular expression
code. After about 24,000 messages have been processed, bayes
performance declines by 40% (perhaps because it has autolearned enough
spam and is now classifying) and libdb3 is responsible for 11% of
runtime. About 6% of runtime seems to be identifiably caused by
copy-on-write from spamd's forking behavior.
After 127 minutes and 51,000 messages, it looks like:
CPU: Athlon, speed 1837.72 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 1000000
samples % app name symbol name
1619397 11.1000 libdb3.so.3.0.2 (no symbols)
1494937 10.2469 perl S_regmatch
1074194 7.3630 libc-2.3.2.so (no symbols)
983368 6.7404 vmlinux fast_copy_page
343397 2.3498 perl S_find_byclass
342439 2.3432 perl S_hv_fetch_common
265513 1.8168 perl Perl_sv_setsv_flags
223108 1.5267 perl Perl_leave_scope
222373 1.5216 perl Perl_sv_clear
206650 1.4140 perl Perl_pp_padsv
202517 1.3858 perl S_visit
197297 1.3500 perl S_regtry
Running 24,000 messages without bayes, I get these results, showing
about 10% from fork()ing overhead and 24% in the regexp engine.
CPU: Athlon, speed 1837.72 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 1000000
samples % app name symbol name
587894 19.1067 perl S_regmatch
321703 10.4554 vmlinux fast_copy_page
231942 7.5382 libc-2.3.2.so (no symbols)
144354 4.6915 perl S_find_byclass
79662 2.5890 perl S_regtry
70016 2.2755 perl S_visit
65777 2.1378 perl S_hv_fetch_common
Unfortunately, my libc and libdb3 are stripped so I can't break the
overheads there down any further. To get symbol-level accuracy
requires unstripped libraries/binaries.
Scott
Re: Hash function performance
Posted by Michael Parker <pa...@pobox.com>.
On Thu, Jun 24, 2004 at 11:00:47PM -0700, Daniel Quinlan wrote:
>
> I think the bigger performance issue is given the frequency with which
> we call the SHA1 routine (about 420 times per message for this data set)
> is to _avoid that extra function call_.
>
> Also, the time per call is not measurable, so I suspect most of the time
> is simply spent in the overhead of a function call, passing data in and
> out of Digest::SHA1, etc. I don't think it's worth it.
>
For grins I forced the use of the perl version of SHA1:
%Time ExclSec CumulS #Calls sec/call Csec/c Name
85.3 761.7 761.73 839953 0.0009 0.0009 Mail::SpamAssassin::SHA1::perl_sha1
It's number 1 on %Time.
It could be a reasonable thing to get rid of the extra method call to
determine if we should call Digest::SHA1 or our implementation and
just require Digest::SHA1 to use Bayes.
Michael
Re: Hash function performance
Posted by Daniel Quinlan <qu...@pathname.com>.
Sidney Markowitz <si...@sidney.com> writes:
> Michael,
>
> I have two questions. 1) What do the numbers show? How much will we save
> if the hash function is twice as fast as SHA-1? Five times as fast?
Here are the results for a sa-learn on 2000 msgs under MySQL:
%Time ExclSec CumulS #Calls sec/call Csec/c Name
1.29 2.800 5.230 839953 0.0000 0.0000 Mail::SpamAssassin::SHA1::sha1
1.12 2.430 2.430 839953 0.0000 0.0000 Digest::SHA1::sha1
Here are the results from an sa-learn on 2000 msgs under DBM:
%Time ExclSec CumulS #Calls sec/call Csec/c Name
1.91 2.640 5.090 839953 0.0000 0.0000 Mail::SpamAssassin::SHA1::sha1
1.78 2.450 2.450 839953 0.0000 0.0000 Digest::SHA1::sha1
So, we spend 1.12% of our time doing SHA1 when using MySQL and 1.78% of
our time doing SHA1 when using DBM.
I think the bigger performance issue is given the frequency with which
we call the SHA1 routine (about 420 times per message for this data set)
is to _avoid that extra function call_.
Also, the time per call is not measurable, so I suspect most of the time
is simply spent in the overhead of a function call, passing data in and
out of Digest::SHA1, etc. I don't think it's worth it.
I think more is to be gained in these areas:
- global optimizations to regular expression body tests (the test set
that's the most expensive)
- general performance improvements (start with some Devel::DProf data)
- the spamd architecture (too much overhead per message)
- reexamining the idea of not doing work when it is not needed (not to
be entered into lightly since it can often be more expensive)
> 2) can you do a similar profile for a spam filtering run, rather than
> sa-learn?
I'll leave this to Michael. I need to upgrade to Perl 5.8 so
Devel::DProf might start working for me again.
Daniel
--
Daniel Quinlan
http://www.pathname.com/~quinlan/
Re: Hash function performance
Posted by Sidney Markowitz <si...@sidney.com>.
Michael,
I have two questions. 1) What do the numbers show? How much will we save
if the hash function is twice as fast as SHA-1? Five times as fast?
2) can you do a similar profile for a spam filtering run, rather than
sa-learn?
-- sidney