fallintoplace opened a new pull request, #1184: URL: https://github.com/apache/arrow-go/pull/1184
## What does this PR do? - compares List and LargeList child values once per contiguous valid parent run - checks every parent list length before combining its child range - compares FixedSizeList child values once per valid parent run - avoids creating two child array slices for every valid parent value ListView and LargeListView are not included because their child ranges can be non-contiguous. ## Why? List equality currently creates two temporary child arrays and recursively calls `Equal` for every valid parent value. For 65,536 all-valid lists, that creates about 131,000 temporary child arrays. A valid-run comparison checks the parent lengths and compares one contiguous child range instead. This follows the same approach as Arrow C++ list equality. ## Benchmarks Apple M1 Pro, 65,536 equal parent values: | case | before | after | change | allocations before | allocations after | | --- | ---: | ---: | ---: | ---: | ---: | | List<Int32>, size 1, all valid | 15.6 ms | 0.82 ms | -95% | 262,145 | 5 | | List<Int32>, size 4, all valid | 16.5 ms | 2.39 ms | -86% | 262,145 | 5 | | List<Int32>, size 16, all valid | 22.3 ms | 8.50 ms | -62% | 262,145 | 5 | | List<String>, size 16, all valid | 23.0 ms | 8.65 ms | -62% | 262,145 | 5 | | LargeList<Int32>, size 16, all valid | 22.3 ms | 8.47 ms | -62% | 262,145 | 5 | | FixedSizeList<Int32>, size 16, all valid | 22.5 ms | 8.50 ms | -62% | 262,145 | 5 | | List<Int32>, size 16, clustered 10% null | 20.1 ms | 7.90 ms | -61% | 235,933 | 9 | Alternating valid and null parents stays around 11.2 ms in both versions. This is the most fragmented case, where each valid run contains one parent value. ```text go test ./arrow/array -run '^$' -bench '^BenchmarkListEqual$' -benchmem -benchtime=200ms -count=3 ``` ## Tests - checks equal and different child values - checks different parent list lengths with the same flattened child values - checks that null parent payloads are ignored - checks sliced parents with different left and right offsets - covers List, LargeList, and FixedSizeList - ran `go test ./arrow/...` - ran `go test -race ./arrow/array` - ran `go vet ./arrow/array` -- 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]
