Re: Tuning for throughput

<[email protected]> writes:

> I am investigating using libcrm114 for mass classification and I need
> to understand the run-time space and time characteristics. Has anyone
> else looked at this aspect?

Yes, we have.

> I have running test cases with different volumes of mail that has
> already been classified. What I see is that the time to classify a
> message increases in a generally linear fashion as the size of the
> classifier grows until I get a "large" classifier (15,000 messages or
> more) where the time required kicks up sharply.  I am guessing that
> this is due to memory requirements and swapping starts to occur.

It all depends on the classifier, and how much space is left in
various fixed-size hash-tables.  Now, speaking ONLY of classification
(not training!) here's my recollections, which may be wrong:

The Bayes, Markov, and Winnow classifiers use a fixed-size table with in-place
hash overflows; when you get too many features, you start spending
more and more time in chasing the overflow chains.  So yeah, you
can get a "hockey-stick" graph.  The fix is to use a bigger hash
table ("-S" on the command line if you're doing it that way; memory
is cheap).

The Hyperspace and Correlation classifiers takes time linear in the
number of examples, times the length of the input stream.

The LZ compressive classifier takes time proportional to the length
of the input stream and (approximately) the log of the size of
the example set.

The Bit Entropy, SVM, and Neural Network classifier takes time
proportional to the number of bits in the input file.  Nothing else
matters during classification.


> Other than the process memory requirements, are there any other known
> issues with libcrm114 that make its performance non-linear for larger
> volumes of mail?  If it is using a hash lookup then I expect see
> linear performance on insertion and lookup.

The trick is to get a fixed-size footprint in memory, the hash
system uses in-table overflows.  When the table fills up, lookups
become no better than sequential searches.

So, you DO have to pick your table size "wisely".   If it slows down
with your real data, double the table size.  RAM is cheap. :-)

    - Bill

------------------------------------------------------------------------------
Minimize network downtime and maximize team effectiveness.
Reduce network management and security costs.Learn how to hire 
the most talented Cisco Certified professionals. Visit the 
Employer Resources Portal
http://www.cisco.com/web/learning/employer_resources/index.html