lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Paul Elschot (JIRA)" <>
Subject [jira] Commented: (LUCENE-2232) Use VShort to encode positions
Date Tue, 02 Feb 2010 08:36:21 GMT


Paul Elschot commented on LUCENE-2232:

After the update on the profile, the upperbound on practical gain for from the profile data
would be about:
1/3 of total time spent in readDeltaPosition(),
of this, 7% is used for decoding the VInt when using a disk, and 31% when using SSD.
So the upperbound on the gain is about 2,3% on a disk, and 10% when using SSD.

I'll try and give a rought estimation based on CPU cycles of actual savings.
(Add the usual disclaimers here.)

Assuming delta positions typically take two bytes:
readVInt does 2 getByte, 1 shift, 2 masks + cond. jumps.
readVShortInt does 2 getByte, 1 shift, 1 mask + cond. jump (this patch does not avoid the
So the difference is 1 mask + cond. jump on 2 getByte, 1 shift, 2 mask + cond. jump.
When getByte() is inlined, it reduces to an incremented index array read and a test.
Excluding the cond. jumps, each mask/shift/index/increment should take about one clock cycle
when no I/O is necessary.
Another assumption: a mispredicted branch takes 6 cycles, a correctly predicted branch takes

Assuming all branches are predicted correctly, the total #cycles for readVInt would be 7.
and 1 mask would be saved by the patch, or about 1/7 of time spent in readVInt (14%).
With one mispredicted branch, readVInt would take 13 cycles, of which 6 would be saved (just
under 50%)
With two mispredicted branches, 19 cycles, of which 12 would be saved. (about 63%).

Overall (search time) on a disk, from 1/3 * 7% * 14% = 0.3 % to 1/3 * 7% * 64% = 1.4 % would
be saved.
On SSD, this would be about 4,5  (=31/7) times as much, 1.3% to 5.8%.

So on a disk, there is probably no loss or gain because of the extra i/o for the initial positions,
On ssd this patch could help a few percent, depending on how badly the branches in readVInt
are predicted now.

> Use VShort to encode positions
> ------------------------------
>                 Key: LUCENE-2232
>                 URL:
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>            Reporter: Paul Elschot
>         Attachments: LUCENE-2232-nonbackwards.patch, LUCENE-2232-nonbackwards.patch
> Improve decoding speed for typical case of two bytes for a delta position at the cost
of increasing the size of the proximity file.

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:
For additional commands, e-mail:

View raw message