[C++] Document the guarantees of ChunkResolver::Resolve and minimize branching #39815
Comments
felipecrv
added a commit
that referenced
this issue
Jan 29, 2024
…39817) ### Rationale for this change There has been interest in improving operations on chunked-arrays and even though `ChunkResolver::Resolve()` is not a big contributor in most kernels, the fact that it can be used from tight loops warrants careful attention to branch prediction and memory effects of its implementation. ### What changes are included in this PR? - Documentation of invariants and behavior of functions - Multiple optimizations justified by microbenchmarks - Addition of a variation of `Resolve` that takes a hint as parameter - Fix of an out-of-bounds memory access that doesn't affect correctness (it can only reduce effectiveness of cache in very rare situations, but is nevertheless an issue) ### Are these changes tested? Yes, by existing tests. ### Are there any user-facing changes? - The `arrow::internal::ChunkResolver::Bisect()` function was `protected` and is now `private` with a different signature * Closes: #39815 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Felipe Oliveira Carvalho <felipekde@gmail.com>
dgreiss
pushed a commit
to dgreiss/arrow
that referenced
this issue
Feb 19, 2024
…lve() (apache#39817) ### Rationale for this change There has been interest in improving operations on chunked-arrays and even though `ChunkResolver::Resolve()` is not a big contributor in most kernels, the fact that it can be used from tight loops warrants careful attention to branch prediction and memory effects of its implementation. ### What changes are included in this PR? - Documentation of invariants and behavior of functions - Multiple optimizations justified by microbenchmarks - Addition of a variation of `Resolve` that takes a hint as parameter - Fix of an out-of-bounds memory access that doesn't affect correctness (it can only reduce effectiveness of cache in very rare situations, but is nevertheless an issue) ### Are these changes tested? Yes, by existing tests. ### Are there any user-facing changes? - The `arrow::internal::ChunkResolver::Bisect()` function was `protected` and is now `private` with a different signature * Closes: apache#39815 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Felipe Oliveira Carvalho <felipekde@gmail.com>
zanmato1984
pushed a commit
to zanmato1984/arrow
that referenced
this issue
Feb 28, 2024
…lve() (apache#39817) ### Rationale for this change There has been interest in improving operations on chunked-arrays and even though `ChunkResolver::Resolve()` is not a big contributor in most kernels, the fact that it can be used from tight loops warrants careful attention to branch prediction and memory effects of its implementation. ### What changes are included in this PR? - Documentation of invariants and behavior of functions - Multiple optimizations justified by microbenchmarks - Addition of a variation of `Resolve` that takes a hint as parameter - Fix of an out-of-bounds memory access that doesn't affect correctness (it can only reduce effectiveness of cache in very rare situations, but is nevertheless an issue) ### Are these changes tested? Yes, by existing tests. ### Are there any user-facing changes? - The `arrow::internal::ChunkResolver::Bisect()` function was `protected` and is now `private` with a different signature * Closes: apache#39815 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Felipe Oliveira Carvalho <felipekde@gmail.com>
thisisnic
pushed a commit
to thisisnic/arrow
that referenced
this issue
Mar 8, 2024
…lve() (apache#39817) ### Rationale for this change There has been interest in improving operations on chunked-arrays and even though `ChunkResolver::Resolve()` is not a big contributor in most kernels, the fact that it can be used from tight loops warrants careful attention to branch prediction and memory effects of its implementation. ### What changes are included in this PR? - Documentation of invariants and behavior of functions - Multiple optimizations justified by microbenchmarks - Addition of a variation of `Resolve` that takes a hint as parameter - Fix of an out-of-bounds memory access that doesn't affect correctness (it can only reduce effectiveness of cache in very rare situations, but is nevertheless an issue) ### Are these changes tested? Yes, by existing tests. ### Are there any user-facing changes? - The `arrow::internal::ChunkResolver::Bisect()` function was `protected` and is now `private` with a different signature * Closes: apache#39815 Authored-by: Felipe Oliveira Carvalho <felipekde@gmail.com> Signed-off-by: Felipe Oliveira Carvalho <felipekde@gmail.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Describe the enhancement requested
The invariants of
ChunkResolverand pre-conditions ofChunkResolver::Resolve()are unclear which can lead to multiple problems:Request: document the class and implement possible micro-optmizations.
Component(s)
C++
The text was updated successfully, but these errors were encountered: