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