lucene-dev mailing list archives

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

    [ https://issues.apache.org/jira/browse/LUCENE-2232?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12828535#action_12828535
] 

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 IndexSearcher.search 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
shift).
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
0.

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: https://issues.apache.org/jira/browse/LUCENE-2232
>             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: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message