David Mollitor created SPARK-59431:
--------------------------------------
Summary: Use ArrayList 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
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]
