etseidl commented on issue #7582: URL: https://github.com/apache/arrow-rs/issues/7582#issuecomment-5702793840
Another data point. I've added a bench of fetching the column index from various shapes of `PageIndex`. The results are not surprising. The dense form has O(1) lookup behavior, and the sparse is O(log(n)) where n is the number of kept indices. For the special case of `n == span` we fall back to O(1). ``` page_index_dense(10,1/100) 1.00 6.4±0.20ns ? ?/sec ... page_index_dense(10,7500/10000) 1.00 6.4±0.18ns ? ?/sec page_index_sparse(10,1/100) 1.00 9.0±0.20ns ? ?/sec page_index_sparse(10,10/100) 1.00 15.7±0.44ns ? ?/sec page_index_sparse(10,10/1000) 1.00 15.6±0.37ns ? ?/sec page_index_sparse(10,10/10000) 1.00 15.7±0.41ns ? ?/sec page_index_sparse(10,100/100) 1.00 7.6±0.15ns ? ?/sec page_index_sparse(10,100/1000) 1.00 27.0±0.52ns ? ?/sec page_index_sparse(10,100/10000) 1.00 26.9±0.38ns ? ?/sec page_index_sparse(10,1000/1000) 1.00 7.7±0.20ns ? ?/sec page_index_sparse(10,1000/10000) 1.00 39.2±0.66ns ? ?/sec page_index_sparse(10,10000/10000) 1.00 7.7±0.21ns ? ?/sec page_index_sparse(10,5/100) 1.00 12.7±0.28ns ? ?/sec page_index_sparse(10,50/100) 1.00 22.9±0.54ns ? ?/sec page_index_sparse(10,50/1000) 1.00 22.8±0.40ns ? ?/sec page_index_sparse(10,50/10000) 1.00 22.8±0.43ns ? ?/sec page_index_sparse(10,500/1000) 1.00 35.7±0.59ns ? ?/sec page_index_sparse(10,500/10000) 1.00 35.6±0.53ns ? ?/sec page_index_sparse(10,5000/10000) 1.00 54.9±1.29ns ? ?/sec page_index_sparse(10,75/100) 1.00 27.0±0.72ns ? ?/sec page_index_sparse(10,750/1000) 1.00 39.2±0.39ns ? ?/sec page_index_sparse(10,750/10000) 1.00 39.2±0.51ns ? ?/sec page_index_sparse(10,7500/10000) 1.00 54.9±1.23ns ? ?/sec ``` Honestly I don't think even the worst case is all that bad considering the space savings. Here's the memory use for the 10k column cases ``` rg: 10 col: 10/10000 dense 23205340 sparse 28364 rg: 10 col: 50/10000 dense 23225740 sparse 141724 rg: 10 col: 100/10000 dense 23251240 sparse 283424 rg: 10 col: 500/10000 dense 23455240 sparse 1417024 rg: 10 col: 750/10000 dense 23582740 sparse 2125524 rg: 10 col: 1000/10000 dense 23710240 sparse 2834024 rg: 10 col: 5000/10000 dense 25750240 sparse 14170024 rg: 10 col: 7500/10000 dense 27025240 sparse 21255024 rg: 10 col: 10000/10000 dense 28300240 sparse 28300000 ``` I think this argues heavily for simply replacing the dense `Vec<Vec<Option<T>>>` with `Grid<T>`. -- 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]
