harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Stefano Mazzocchi <stef...@apache.org>
Subject Re: [optimization] Algorithmic tricks
Date Tue, 25 Jul 2006 16:13:39 GMT
Anton Luht wrote:
> Hello,
> 
> I'd like to suggest people that know some algorithmic tricks to look
> at the corresponding areas of classlib. Maybe some of the community
> members had (un)lucky experience of tuning performance of some
> application that led them to a deep knowledge of some very specific
> area has good approaches but not too widely known to an average
> developer. It might also be an interest for students and other people
> from institutes and universities.
> 
> What I'm talking about is not related to 'premature optimization' that
> is now being discussed in another thread but something very narrow,
> limited to maybe one method and not influencing anything else.
> 
> For example, consider current implementation of
> java.util.BitSet.cardinality() . It just checks all bits one by one
> and increments count. [1] Gives an overview of algorithms for checking
> set bit count. The fastest algorithms are with table lookup, which
> requires additional memory, but there are algorithms that are several
> times faster than iteration (in C) and don't require tables. I believe
> such local optimizations with good comments and links to corresponding
> resources won't do any harm and are a good point to start with.
> 
> Does it make sence?
> 
> [1] http://www-db.stanford.edu/~manku/bitcount/bitcount.html

I agree that there are some pretty clever algorithms out there that
would improve our ability to perform things... for example, the one that
comes to mind is sublinear string matching algorithm such as:

 http://citeseer.ist.psu.edu/361534.html

(but an entire class of others exist).

Of course, these algorithms have statistical properties... meaning that
they perform like they claim they do on average. Without a benchmark,
it's not clear how much it would improve things.

But I do agree with Anton that thinking about algorithm optimization is
 clearly a good exercise.

-- 
Stefano.


---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org


Mime
View raw message