lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Toke Eskildsen (JIRA)" <j...@apache.org>
Subject [jira] Updated: (LUCENE-1990) Add unsigned packed int impls in oal.util
Date Fri, 26 Feb 2010 14:04:27 GMT

     [ https://issues.apache.org/jira/browse/LUCENE-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Toke Eskildsen updated LUCENE-1990:
-----------------------------------

    Attachment: LUCENE-1990-te20100226.patch

Now we're getting somewhere. I finally squashed the persistence bug and the tests has been
turned up another notch. Everything seems to run as it should. Pending issues, as I see them:

- Review of the code
- Should we make a MutableWriter?
- Should we drop support for aligned?

The last one is interesting. The code for getting a value from aligned uses devision and a
single RAM-request:
{code}
  public long get(final int index) {
    final int blockPos = index / valuesPerBlock;
    final int bitPos = (index - (blockPos * valuesPerBlock)) * bitsPerValue;
    return (blocks[blockPos] >>> shifts[bitPos]) & readMask;
{code}

where the code for packed uses shift and two RAM-requests:
{code}
    final long majorBitPos = index * bitsPerValue;
    final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
    final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);

    final int base = bitPos * FAC_BITPOS;

    return ((blocks[elementPos] << shifts[base]) >>> shifts[base+1]) |
            ((blocks[elementPos+1] >>> shifts[base+2]) & readMasks[bitPos]);
{code}

I have done some tests (see the TODO-file in the attached patch) and on 64 bit machines, the
difference in access-speed for aligned vs. packed is not that great and not always in favor
of aligned. Probably because some space is wasted and the RAM-cache is not so well utilized.
If this is also the case for 32 bit machines, I vote for removing aligned and only used packed
with the special-case optimizations direct8, direct16, direct32 and direct64. This would also
mean that there is only one persistent format.

{code}
java -cp lucene-core-3.1-dev.jar org.apache.lucene.util.packed.PackedIntsPerformance
{code}
Runs throught the performance tests and delivers a simple report, so it should be very easy
to test on different platforms. It only measures access speed.

I consider this patch ready for review and concentrate on other matters until I hear more.

> Add unsigned packed int impls in oal.util
> -----------------------------------------
>
>                 Key: LUCENE-1990
>                 URL: https://issues.apache.org/jira/browse/LUCENE-1990
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>            Reporter: Michael McCandless
>            Priority: Minor
>         Attachments: LUCENE-1990-te20100122.patch, LUCENE-1990-te20100210.patch, LUCENE-1990-te20100212.patch,
LUCENE-1990-te20100223.patch, LUCENE-1990-te20100226.patch, LUCENE-1990.patch, LUCENE-1990_PerformanceMeasurements20100104.zip
>
>
> There are various places in Lucene that could take advantage of an
> efficient packed unsigned int/long impl.  EG the terms dict index in
> the standard codec in LUCENE-1458 could subsantially reduce it's RAM
> usage.  FieldCache.StringIndex could as well.  And I think "load into
> RAM" codecs like the one in TestExternalCodecs could use this too.
> I'm picturing something very basic like:
> {code}
> interface PackedUnsignedLongs  {
>   long get(long index);
>   void set(long index, long value);
> }
> {code}
> Plus maybe an iterator for getting and maybe also for setting.  If it
> helps, most of the usages of this inside Lucene will be "write once"
> so eg the set could make that an assumption/requirement.
> And a factory somewhere:
> {code}
>   PackedUnsignedLongs create(int count, long maxValue);
> {code}
> I think we should simply autogen the code (we can start from the
> autogen code in LUCENE-1410), or, if there is an good existing impl
> that has a compatible license that'd be great.
> I don't have time near-term to do this... so if anyone has the itch,
> please jump!

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message