You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Yifan Cai (Jira)" <ji...@apache.org> on 2020/05/07 23:33:00 UTC
[jira] [Comment Edited] (CASSANDRA-15765) Get-by-index introduced
in CASSANDRA-15394 could have negative performance impact on
non-RandomAccess List
[ https://issues.apache.org/jira/browse/CASSANDRA-15765?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17102103#comment-17102103 ]
Yifan Cai edited comment on CASSANDRA-15765 at 5/7/20, 11:32 PM:
-----------------------------------------------------------------
The concern is really just about the type. In practice, code review _should_ guard the introduction of wrong types. However, it would be really nice if compiler can do the job. _(no human error)_
There is bit verbose solution to declare the type of the acceptable parameter should be a List with RandomAccess.
Pasting the conceptual code here.
{code:java}
public static class ScannerList<RandomAccessList extends List<ISSTableScanner> & RandomAccess> implements AutoCloseable
{
public final RandomAccessList scanners;
public ScannerList(RandomAccessList scanners)
{
this.scanners = scanners;
}
...
}{code}
The upside: compiler checks if the type satisfies, and no check performed at runtime.
The downside: code gets verbose.
What do you think?
was (Author: yifanc):
The concern is really just about the type. In practice, code review _should_ guard the introduction of wrong types. However, it would be really nice if compiler can do the job. _(no human error)_
There is bit verbose solution to declare the type of the acceptable parameter should be a List with RandomAccess.
Pasting the conceptual code here.
{code:java}
public static class ScannerList<RandomAccessList extends List<ISSTableScanner> & RandomAccess> implements AutoCloseable
{
public final RandomAccessList scanners;
public ScannerList(RandomAccessList scanners)
{
this.scanners = scanners;
}
...
}{code}
The upside: compiler checks if the type satisfies, and no check performed at runtime.
The downside: code gets verbose.
What do you think?
> Get-by-index introduced in CASSANDRA-15394 could have negative performance impact on non-RandomAccess List
> ----------------------------------------------------------------------------------------------------------
>
> Key: CASSANDRA-15765
> URL: https://issues.apache.org/jira/browse/CASSANDRA-15765
> Project: Cassandra
> Issue Type: Improvement
> Components: Legacy/Core
> Reporter: Yifan Cai
> Assignee: Yifan Cai
> Priority: Normal
>
> CASSANDRA-15394 replaced the iterator based iteration with the get-by-index one to avoid allocation iterators.
> It works for the lists that support RandomAccess, i.e. the big O of {{get()}} is {{O(1)}}.
> However, it fails when the list does not support RandomAccess. The {{get()}} method's time complexity can be linear, and it leads to {{O(n^2)}} for the overall iteration.
> The implementation should provide different behaviors based on the property.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org