mbutrovich opened a new issue, #27616:
URL: https://github.com/apache/datafusion/issues/27616

   ### Is your feature request related to a problem or challenge?
   
   #27559 adds `set_bits` to `datafusion/common/src/hash_utils.rs`, an iterator 
over the positions of the set bits of a `u64`:
   
   
https://github.com/apache/datafusion/blob/8f07d4c17813ef1caa9881c9b94312ab0769196d/datafusion/common/src/hash_utils.rs#L325-L335
   
   Three other places walk the set bits of a `u64` with the same 
`trailing_zeros` and `word &= word - 1` loop:
   
   - `hash_dictionary_scatter`, in the same file: 
https://github.com/apache/datafusion/blob/477c7b9ebc88b879d5b8c8d60b21ba4a80593b9d/datafusion/common/src/hash_utils.rs#L602-L609
   - The matched-row tracking in nested loop join: 
https://github.com/apache/datafusion/blob/477c7b9ebc88b879d5b8c8d60b21ba4a80593b9d/datafusion/physical-plan/src/joins/nested_loop_join.rs#L2054-L2063
   - `powerset_indices`, which builds the GROUPING SETS of a CUBE: 
https://github.com/apache/datafusion/blob/477c7b9ebc88b879d5b8c8d60b21ba4a80593b9d/datafusion/expr/src/utils.rs#L59-L71
   
   arrow-buffer's `BitIndexIterator` walks a whole bitmap, not one word, so it 
doesn't fit these loops.
   
   ### Describe the solution you'd like
   
   Use `set_bits` in `hash_dictionary_scatter`. Its loop also stops at the 
first index past the end of the slice, so the call would be 
`set_bits(word).map(|i| start + i).take_while(|&i| i < len)`, or the last word 
could be masked to `len` before the walk.
   
   For the other two sites, move `set_bits` to `datafusion_common::utils` as a 
`pub` function, marked `#[doc(hidden)]` with the "Public Only for Internal Use" 
comment from the [API health 
guide](https://github.com/apache/datafusion/blob/a616831122aa525ed843ee3c5e11f4803f557c98/docs/source/contributor-guide/api-health.md?plain=1#L35-L68).
 It needs `#[inline]`, because it isn't generic, so without LTO another crate 
can't inline it.
   
   `hash_dictionary_scatter` and the nested loop join loop are hot. Each change 
should come with the generated code of both versions and a benchmark run: 
`with_hashes` (the dictionary cases) for the first, and `benchmarks/src/nlj.rs` 
for the second. `powerset_indices` runs once per query plan, so it needs only 
the existing tests.
   
   ### Describe alternatives you've considered
   
   Keep the copies. Each is a few lines, and the nested loop join loop would 
then not depend on a function in another crate inlining.
   
   ### Additional context
   
   None.
   


-- 
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]

Reply via email to