[
https://issues.apache.org/jira/browse/SPARK-59431?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
David Mollitor updated SPARK-59431:
-----------------------------------
Summary: Use ArrayDeque instead of LinkedList for BytesToBytesMap dataPages
(was: Use ArrayList instead of LinkedList for BytesToBytesMap dataPages)
> Use ArrayDeque instead of LinkedList for BytesToBytesMap dataPages
> ------------------------------------------------------------------
>
> Key: SPARK-59431
> URL: https://issues.apache.org/jira/browse/SPARK-59431
> Project: Spark
> Issue Type: Improvement
> Components: Spark Core
> Affects Versions: 4.1.0
> Reporter: David Mollitor
> Priority: Minor
> Labels: pull-request-available
>
> h2. Summary
> `BytesToBytesMap` tracks its allocated data pages in
> {{{}private final LinkedList<MemoryBlock> dataPages{}}}. Every operation on
> this field is an append at the end, a full iteration, an operation at the end
> (peek/remove last), or an index access – there are no head or middle
> insertions/removals. That access pattern is a better fit for {{ArrayList}}
> than{{{}LinkedList{}}}:
> * contiguous storage -> better cache locality when iterating the pages;
> * no per-page {{Node}} allocation;
> * {{get(index)}} is O(1) instead of O(n) (used in the destructive
> {{MapIterator}} page advance).
> This changes {{dataPages}} to an {{{}ArrayList{}}}.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
