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

Yifan Cai updated CASSANDRA-15765:
----------------------------------
    Description: 
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. 

  was:
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 {{O(n)}}, and it leads to {{O(n^2)}} for the 
overall iteration. 
The implementation should provide different behaviors based on the property. 


> 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-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org

Reply via email to