You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Shai Erera <se...@gmail.com> on 2013/01/13 16:37:10 UTC
A minor optimization for Fixed/OpenBitSet?
Hi
Both these classes set/get do this:
int bit = index & 0x3f; // mod 64
long bitmask = 1L << bit;
Since bit has only 64 values, bitmask can only be 1, 10, 100... etc. I was
thinking that instead of doing the <<, we can have a static BIT_MASK array,
indexed by bit, and then we could use it to compute bitmask.
But that replaces a bitwise shift by an array access, so I'm not sure how
much more efficient it will be? If the array is *hot* and in the L1 cache,
then it's supposed to be faster?
Thoughts?
Shai
Re: A minor optimization for Fixed/OpenBitSet?
Posted by Yonik Seeley <yo...@lucidworks.com>.
On Sun, Jan 13, 2013 at 10:39 AM, Dawid Weiss
<da...@cs.put.poznan.pl> wrote:
> I doubt it'll be faster,
Yeah, this shift will be pretty simple - 1 cycle, and normally with a
max throughput of 2 to 3 per cycle for x86 server CPUs.
Even without java bounds checking, the most you could hope for would
be to match the performance with a lookup. Also, L1 access is still
greater than 1 cycle on a number of processors.
-Yonik
http://lucidworks.com
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: A minor optimization for Fixed/OpenBitSet?
Posted by Dawid Weiss <da...@cs.put.poznan.pl>.
I doubt it'll be faster, not with array bounds checking and the
typical Java overhead. Feel free to benchmark using Caliper, for
example:
http://code.google.com/p/caliper/
Dawid
On Sun, Jan 13, 2013 at 4:37 PM, Shai Erera <se...@gmail.com> wrote:
> Hi
>
> Both these classes set/get do this:
>
> int bit = index & 0x3f; // mod 64
> long bitmask = 1L << bit;
>
> Since bit has only 64 values, bitmask can only be 1, 10, 100... etc. I was
> thinking that instead of doing the <<, we can have a static BIT_MASK array,
> indexed by bit, and then we could use it to compute bitmask.
>
> But that replaces a bitwise shift by an array access, so I'm not sure how
> much more efficient it will be? If the array is *hot* and in the L1 cache,
> then it's supposed to be faster?
>
> Thoughts?
>
> Shai
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: A minor optimization for Fixed/OpenBitSet?
Posted by Shai Erera <se...@gmail.com>.
Thanks guys!
Shai
On Sun, Jan 13, 2013 at 7:59 PM, Adrien Grand <jp...@gmail.com> wrote:
> In addition to what Dawid and Yonik said, Packed64 used to have such
> optimizations but they have been removed because they were slower than
> computing masks on the fly (see
> https://issues.apache.org/jira/browse/LUCENE-4171).
>
> --
> Adrien Grand
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>
Re: A minor optimization for Fixed/OpenBitSet?
Posted by Adrien Grand <jp...@gmail.com>.
In addition to what Dawid and Yonik said, Packed64 used to have such
optimizations but they have been removed because they were slower than
computing masks on the fly (see
https://issues.apache.org/jira/browse/LUCENE-4171).
--
Adrien Grand
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org