david-mollitor-db opened a new pull request, #58731:
URL: https://github.com/apache/spark/pull/58731
### What changes were proposed in this pull request?
`BytesToBytesMap` tracked 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. This PR
changes `dataPages` to an `ArrayList`.
Because `getLast()` / `removeLast()` are `SequencedCollection` methods
available on `ArrayList` only
since Java 21 (Spark still supports Java 17), the call sites are rewritten:
- `spill()` / `reset()`: `getLast()` → `get(size() - 1)`, `removeLast()` →
`remove(size() - 1)`
(both O(1) for the last element, no shift).
- `free()`: the `Iterator.remove()` drain (O(n²) on an `ArrayList`) → remove
from the end in a loop
(O(n)), matching the existing `reset()` drain.
The sibling field `spillWriters` genuinely uses FIFO front removal
(`getFirst()` / `removeFirst()`)
and remains a `LinkedList`; only `dataPages` changes.
### Why are the changes needed?
`ArrayList` is a better fit for this access pattern: contiguous storage
(better cache locality when
iterating pages), no per-page `Node` allocation, and O(1) `get(index)` (used
by the destructive
`MapIterator` page advance, which is O(n) on a `LinkedList`). `dataPages`
holds few, large pages, so
the remaining O(n) `indexOf`/`remove(Object)` in the destructive iterator
are negligible.
### Does this PR introduce _any_ user-facing change?
No. Identical behavior; thread-safety is unchanged (access is guarded by the
same external
`synchronized` blocks).
### How was this patch tested?
Existing `BytesToBytesMapOnHeapSuite` and `BytesToBytesMapOffHeapSuite` pass
(34 tests, covering
spill, reset, free, and destructive iteration); checkstyle is clean.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 4.8
This pull request and its description were written by Isaac.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
