viirya commented on code in PR #58731:
URL: https://github.com/apache/spark/pull/58731#discussion_r3990126694
##########
core/src/main/java/org/apache/spark/unsafe/map/BytesToBytesMap.java:
##########
@@ -103,9 +104,9 @@ public interface KeyOperationsFactory {
private final TaskMemoryManager taskMemoryManager;
/**
- * A linked list for tracking all allocated data pages so that we can free
all of our memory.
+ * A list for tracking all allocated data pages so that we can free all of
our memory.
*/
- private final LinkedList<MemoryBlock> dataPages = new LinkedList<>();
+ private final ArrayList<MemoryBlock> dataPages = new ArrayList<>();
Review Comment:
Switching this list to `ArrayList` introduces a quadratic cost in
destructive iteration. In `advanceToNextPage()`, `currentPage` is normally the
first remaining page, so the existing `indexOf(currentPage)`,
`remove(currentPage)`, and subsequent `get(0)` are all O(1) with `LinkedList`.
With `ArrayList`, removing that first page shifts every remaining reference,
making the page-removal work O(P²) over P pages.
This path is used by `UnsafeFixedWidthAggregationMap.iterator()`. Could we
avoid the repeated front shifts, or retain `LinkedList` until benchmarks
establish the tradeoff?
--
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]
