harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mikhail Fursov" <mike.fur...@gmail.com>
Subject Re: [optimization] Algorithmic tricks
Date Tue, 25 Jul 2006 13:04:37 GMT
Anton,
it looks like a joke but while investigating potential performance problems
of our classlib with DeCapo benchmark I found that the same method (counting
signed bits in bitset) is the hottest method in antlr benchmark. But this
method is not from classlib, but from the benchmark and its implementation
is very close to ours and not optimized. I wonder if our JIT will be able to
automatically detect such algorithms and replace them with more optimized
version someday...


On 7/25/06, Mikhail Fursov <mike.fursov@gmail.com> wrote:
>
>
>
> On 7/25/06, Anton Luht <anton.luht@gmail.com> wrote:
> >
> > 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
> > <http://www-db.stanford.edu/%7Emanku/bitcount/bitcount.html>
> >
> > Yes, BitSet code looks not optimized but at least it's readable :)
>
> I always use wikipedia to read about classic algorithms implementation.
> E.g. here is bit counting algorithm too, but it with a reference to the
> book where it was published:
> http://en.wikipedia.org/wiki/Bit_array
> So when improving algorithm and making it not readable and 'tricky' I
> propose to add a reference to the original source.
>
> --
> Mikhail Fursov
>



-- 
Mikhail Fursov

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message