[
https://issues.apache.org/jira/browse/LUCENE-9432?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17162146#comment-17162146
]
Uwe Schindler edited comment on LUCENE-9432 at 7/21/20, 4:23 PM:
-----------------------------------------------------------------
Hi,
the problematic part with linked list is two-kind:
- there is an index-based access to the list. This should be removed and
changed to getLast() or getFirst(), because index-based accesses in LinkedLists
always have a linear scan. If this is not a big slowdown here, it looks like
the list is small and does not grow much. In that case I tend to initialize the
ArrayList with a larger size. If we iterate over the list from back-to-front or
front-to-back, you should use iterator, not get(int) using an index (code looks
like it iterates from back to front).
- LinkedList has a large object allocation and maintenance overhead (one small
object for every entry), while arrays or ArrayLists are a block, which is also
cache-friendly.
So, two suggestions:
- If LinkedList, then remove index-based access and replace by getLast() or
getFirst() (if possible). If that's not possible its the completely wrong type
of list - sorry. LinkedList also implements Deque, so lets use that interface
as datatype in code! This also prevents us from accidentally using the
index-based access: get(int)
- If we use Deque, we can alternatively use ArrayDeque instead of LinkedList
(it's just a replacement). Here we may think of a good initial size.
Uwe
was (Author: thetaphi):
Hi,
the problematic part with linked list is two-kind:
- there is an index-based access to the list. This should be removed and
changed to getLast() or getFirst(), because index-based accesses in LinkedLists
always have a linear scan. If this is not a big slowdown here, it looks like
the list is small and does not grow much. In that case I tend to initialize the
ArrayList with a larger size
- LinkedList has a large object allocation and maintenance overhead (one small
object for every entry), while arrays or ArrayLists are a block, which is also
cache-friendly.
So, two suggestions:
- If LinkedList, then remove index-based access and replace by getLast() or
getFirst() (if possible). If that's not possible its the completely wrong type
of list - sorry. LinkedList also implements Deque, so lets use that interface
as datatype in code! This also prevents us from accidentally using the
index-based access: get(int)
- If we use Deque, we can alternatively use ArrayDeque instead of LinkedList
(it's just a replacement). Here we may think of a good initial size.
Uwe
> Use LinkedList instead of manual array re-sizing for better throughput.
> -----------------------------------------------------------------------
>
> Key: LUCENE-9432
> URL: https://issues.apache.org/jira/browse/LUCENE-9432
> Project: Lucene - Core
> Issue Type: Improvement
> Components: core/codecs
> Reporter: Mohammad Sadiq
> Priority: Minor
> Labels: patch-available, performance, pull-request-available
> Attachments: LUCENE-9432.patch
>
>
> I observed that using {{LinkedList}} instead of manually re-sizing and
> copying {{SegmentTermEnumFrame}}s improves red-line QPS. Does it make sense
> to include this?
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
