david-mollitor-db commented on PR #58731: URL: https://github.com/apache/spark/pull/58731#issuecomment-5638664378
Thanks @viirya for the careful review — you're right on both points, and I appreciate you catching them. You're correct that the destructive `MapIterator` removes from the front (`dataPages.remove(currentPage)` on the head each advance), so on an `ArrayList` a full destructive iteration is O(n²) in the number of pages. My "no head or middle removals" claim was simply wrong — apologies for the oversight. I'd originally passed over `ArrayDeque` because I misremembered it as fixed-capacity, which wouldn't suit a page list that grows as the map fills. That recollection was mistaken: `ArrayDeque` is a resizable circular array (amortized O(1) append, grows automatically), so it's actually the right fit here — O(1) at both ends including the destructive head removal, contiguous storage, and no per-page `Node` allocation. I've reworked the PR to use it (declared through `Deque`). As a bonus, it also lets the non-destructive walk use a stored forward iterator instead of `indexOf(currentPage)` + `get(idx)`, which removes a pre-existing O(n²) there as well. You were also right about the tests: the existing `destructiveIteratorTest` uses 64 MiB pages, so all 4096 records land in a single page and no page is ever removed during iteration. I've added `destructiveIteratorManyPagesTest` that uses a small page size so the records span many pages (31 here), exercising the repeated head-removal path and asserting each record is returned exactly once and that all but the last page are freed as the iterator advances. (This also surfaced a latent assertion in the shared test helper that only held for a single page, now fixed.) Would you mind taking another look? Thanks again. -- 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]
