[
https://issues.apache.org/jira/browse/SPARK-59431?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
David Mollitor updated SPARK-59431:
-----------------------------------
Description:
h2. Summary
{{BytesToBytesMap}} tracks its allocated data pages in a
{{LinkedList<MemoryBlock>}}. The
access pattern on this field is append and remove at the tail (page allocation,
{{spill()}},
{{reset()}}, {{free()}}) plus remove at the head (the destructive
{{MapIterator}}, which frees
each page as it advances onto the next). That is a double-ended queue, which
{{ArrayDeque}} fits
with O(1) at both ends, contiguous storage, and no per-page {{Node}} allocation.
Replace {{dataPages}} with an {{ArrayDeque}}, declared through the {{Deque}}
interface:
* The destructive iterator removes the consumed head page in O(1)
({{removeFirst()}}) instead of
a front removal, which on an {{ArrayList}} is an O(n) array shift -- so a full
destructive
iteration was O(n^2) in the number of pages.
* Non-destructive iteration walks a stored forward iterator instead of
{{indexOf(currentPage)}} +
{{get(idx)}}, which is O(n) per advance (O(n^2) total) on {{LinkedList}}.,
was:
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{}}}.
> 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 a
> {{LinkedList<MemoryBlock>}}. The
> access pattern on this field is append and remove at the tail (page
> allocation, {{spill()}},
> {{reset()}}, {{free()}}) plus remove at the head (the destructive
> {{MapIterator}}, which frees
> each page as it advances onto the next). That is a double-ended queue, which
> {{ArrayDeque}} fits
> with O(1) at both ends, contiguous storage, and no per-page {{Node}}
> allocation.
> Replace {{dataPages}} with an {{ArrayDeque}}, declared through the {{Deque}}
> interface:
> * The destructive iterator removes the consumed head page in O(1)
> ({{removeFirst()}}) instead of
> a front removal, which on an {{ArrayList}} is an O(n) array shift -- so a
> full destructive
> iteration was O(n^2) in the number of pages.
> * Non-destructive iteration walks a stored forward iterator instead of
> {{indexOf(currentPage)}} +
> {{get(idx)}}, which is O(n) per advance (O(n^2) total) on {{LinkedList}}.,
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
