[jira] [Commented] (CASSANDRA-15765) Get-by-index introduced in CASSANDRA-15394 could have negative performance impact on non-RandomAccess List

["Blake Eggleston (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/CASSANDRA-15765?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17102083#comment-17102083 ] 

Blake Eggleston commented on CASSANDRA-15765:
---------------------------------------------

Thanks for bringing this up Yifan. I'm not sure there's a clean solution to this. There are several "Array Lists" that we can encounter with these methods, so we can't enforce an {{ArrayList}} type ({{ArrayList#SubList}} and {{Arrays#ArrayList}}, for example), and the  {{List}} interface doesn't communicate it's preferred iteration style. Given this does have a measurable benefit and currently no instances where we're iterating over the wrong type of list, I'd be inclined to leave as is. The upside is that these are all fairly hot sections of code, so I'd expect people to be careful when making changes to data strucures, and hopefully running performance tests before committing.

> 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