andygrove commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3604513315
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from
each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map
is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
+ for (idx, entry) in str_list.iter().enumerate() {
+ map.entry(*entry).or_insert(idx + 1);
+ }
+ map
+ });
+
let values: Vec<T::Native> = (0..len)
.map(|i| {
if nulls.as_ref().is_some_and(|n| n.is_null(i)) {
return zero;
}
let string = string_array.value(i);
- let position = str_list
- .iter()
- .position(|s| *s == string)
- .map_or(0, |idx| idx + 1);
+ let position = match &map {
Review Comment:
Good question — I benchmarked it. Hoisting the match into two loops is a
tradeoff rather than a win: the map path gets ~5–7% faster (`long_list_64`
−5.0%, `long_list_256` −7.2%), but the short-list linear-scan path regresses
~8% (`short_list_4` +7.7%). Since lists below the threshold stay on the linear
scan and short lists are the common case for `find_in_set`, I would rather not
regress them for a gain on the path that is already HashMap-optimized. Keeping
the single loop. Results were stable across three runs and two builds.
(Disclosure: I used an LLM-based coding assistant to run these benchmarks
and help draft this reply.)
--
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]
