Skip to content

Commit ccc3842

Browse files
orlpritchie46
authored andcommitted
refactor(rust): Reduce code monomorphization in eager joins (#29087)
(cherry picked from commit 8619b75)
1 parent 22f274b commit ccc3842

7 files changed

Lines changed: 168 additions & 175 deletions

File tree

‎crates/polars-ops/src/frame/join/asof/groups.rs‎

Lines changed: 75 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,6 @@ use polars_utils::abs_diff::AbsDiff;
1212
use polars_utils::hashing::{DirtyHash, hash_to_partition};
1313
use polars_utils::nulls::IsNull;
1414
use polars_utils::total_ord::{ToTotalOrd, TotalEq, TotalHash};
15-
use rayon::prelude::*;
1615

1716
use super::*;
1817
use crate::frame::join::{prepare_binary, prepare_keys_multiple};
@@ -101,64 +100,56 @@ where
101100
let split_by_right = split_and_flatten(by_right, n_threads);
102101
let offsets = compute_len_offsets(split_by_left.iter().map(|s| s.len()));
103102

104-
let right_slices = split_by_right
103+
let right_arrays = split_by_right
105104
.iter()
106105
.map(|ca| {
107106
assert_eq!(ca.chunks().len(), 1);
108-
ca.downcast_iter()
109-
.next()
110-
.unwrap()
111-
.iter()
112-
.map(|v| v.copied())
107+
ca.downcast_iter().next().unwrap()
113108
})
114-
.collect();
115-
let hash_tbls = build_tables(right_slices, false);
109+
.collect::<Vec<_>>();
110+
let hash_tbls = build_tables_from_arrays::<S>(&right_arrays, false);
116111
let n_tables = hash_tbls.len();
117112

118113
// Now we probe the right hand side for each left hand side.
119-
let out = split_by_left
120-
.into_par_iter()
121-
.zip(offsets)
122-
.map(|(by_left, offset)| {
123-
let mut results = Vec::with_capacity(by_left.len());
124-
let mut group_states: PlHashMap<IdxSize, A> =
125-
PlHashMap::with_capacity(_HASHMAP_INIT_SIZE);
126-
127-
assert_eq!(by_left.chunks().len(), 1);
128-
let by_left_chunk = by_left.downcast_iter().next().unwrap();
129-
for (rel_idx_left, opt_by_left_k) in by_left_chunk.iter().enumerate() {
130-
let Some(by_left_k) = opt_by_left_k else {
131-
results.push(NullableIdxSize::null());
132-
continue;
133-
};
134-
let by_left_k = Some(*by_left_k).to_total_ord();
135-
let idx_left = (rel_idx_left + offset) as IdxSize;
136-
let Some(left_val) = left_val_arr.get(idx_left as usize) else {
137-
results.push(NullableIdxSize::null());
138-
continue;
139-
};
140-
141-
let group_probe_table = unsafe {
142-
hash_tbls.get_unchecked(hash_to_partition(by_left_k.dirty_hash(), n_tables))
143-
};
144-
let Some(right_grp_idxs) = group_probe_table.get(&by_left_k) else {
145-
results.push(NullableIdxSize::null());
146-
continue;
147-
};
148-
let id = asof_in_group::<T, A, &F>(
149-
left_val,
150-
right_val_arr,
151-
right_grp_idxs.as_slice(),
152-
&mut group_states,
153-
&filter,
154-
allow_eq,
155-
);
156-
results.push(materialize_nullable(id));
157-
}
158-
results
159-
});
160-
161-
let bufs = RAYON.install(|| out.collect::<Vec<_>>());
114+
let bufs = par_map_collect(split_by_left.len(), &|part_idx| {
115+
let by_left = &split_by_left[part_idx];
116+
let offset = offsets[part_idx];
117+
let mut results = Vec::with_capacity(by_left.len());
118+
let mut group_states: PlHashMap<IdxSize, A> = PlHashMap::with_capacity(_HASHMAP_INIT_SIZE);
119+
120+
assert_eq!(by_left.chunks().len(), 1);
121+
let by_left_chunk = by_left.downcast_iter().next().unwrap();
122+
for (rel_idx_left, opt_by_left_k) in by_left_chunk.iter().enumerate() {
123+
let Some(by_left_k) = opt_by_left_k else {
124+
results.push(NullableIdxSize::null());
125+
continue;
126+
};
127+
let by_left_k = Some(*by_left_k).to_total_ord();
128+
let idx_left = (rel_idx_left + offset) as IdxSize;
129+
let Some(left_val) = left_val_arr.get(idx_left as usize) else {
130+
results.push(NullableIdxSize::null());
131+
continue;
132+
};
133+
134+
let group_probe_table = unsafe {
135+
hash_tbls.get_unchecked(hash_to_partition(by_left_k.dirty_hash(), n_tables))
136+
};
137+
let Some(right_grp_idxs) = group_probe_table.get(&by_left_k) else {
138+
results.push(NullableIdxSize::null());
139+
continue;
140+
};
141+
let id = asof_in_group::<T, A, &F>(
142+
left_val,
143+
right_val_arr,
144+
right_grp_idxs.as_slice(),
145+
&mut group_states,
146+
&filter,
147+
allow_eq,
148+
);
149+
results.push(materialize_nullable(id));
150+
}
151+
results
152+
});
162153
Ok(flatten_nullable(&bufs))
163154
}
164155

@@ -187,41 +178,39 @@ where
187178
let n_tables = hash_tbls.len();
188179

189180
// Now we probe the right hand side for each left hand side.
190-
let iter = prep_by_left
191-
.into_par_iter()
192-
.zip(offsets)
193-
.map(|(by_left, offset)| {
194-
let mut results = Vec::with_capacity(by_left.len());
195-
let mut group_states: PlHashMap<_, A> = PlHashMap::with_capacity(_HASHMAP_INIT_SIZE);
196-
197-
for (rel_idx_left, by_left_k) in by_left.iter().enumerate() {
198-
let idx_left = (rel_idx_left + offset) as IdxSize;
199-
let Some(left_val) = left_val_arr.get(idx_left as usize) else {
200-
results.push(NullableIdxSize::null());
201-
continue;
202-
};
181+
let bufs = par_map_collect(prep_by_left.len(), &|part_idx| {
182+
let by_left = &prep_by_left[part_idx];
183+
let offset = offsets[part_idx];
184+
let mut results = Vec::with_capacity(by_left.len());
185+
let mut group_states: PlHashMap<_, A> = PlHashMap::with_capacity(_HASHMAP_INIT_SIZE);
186+
187+
for (rel_idx_left, by_left_k) in by_left.iter().enumerate() {
188+
let idx_left = (rel_idx_left + offset) as IdxSize;
189+
let Some(left_val) = left_val_arr.get(idx_left as usize) else {
190+
results.push(NullableIdxSize::null());
191+
continue;
192+
};
193+
194+
let group_probe_table = unsafe {
195+
hash_tbls.get_unchecked(hash_to_partition(by_left_k.dirty_hash(), n_tables))
196+
};
197+
let Some(right_grp_idxs) = group_probe_table.get(by_left_k) else {
198+
results.push(NullableIdxSize::null());
199+
continue;
200+
};
201+
let id = asof_in_group::<T, A, &F>(
202+
left_val,
203+
right_val_arr,
204+
right_grp_idxs.as_slice(),
205+
&mut group_states,
206+
&filter,
207+
allow_eq,
208+
);
203209

204-
let group_probe_table = unsafe {
205-
hash_tbls.get_unchecked(hash_to_partition(by_left_k.dirty_hash(), n_tables))
206-
};
207-
let Some(right_grp_idxs) = group_probe_table.get(by_left_k) else {
208-
results.push(NullableIdxSize::null());
209-
continue;
210-
};
211-
let id = asof_in_group::<T, A, &F>(
212-
left_val,
213-
right_val_arr,
214-
right_grp_idxs.as_slice(),
215-
&mut group_states,
216-
&filter,
217-
allow_eq,
218-
);
219-
220-
results.push(materialize_nullable(id));
221-
}
222-
results
223-
});
224-
let bufs = RAYON.install(|| iter.collect::<Vec<_>>());
210+
results.push(materialize_nullable(id));
211+
}
212+
results
213+
});
225214
flatten_nullable(&bufs)
226215
}
227216

‎crates/polars-ops/src/frame/join/asof/mod.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ use polars_utils::total_ord::TotalOrd;
1111
#[cfg(feature = "serde")]
1212
use serde::{Deserialize, Serialize};
1313

14-
use super::{_finish_join, build_tables};
14+
use super::{_finish_join, build_tables, build_tables_from_arrays, par_map_collect};
1515
use crate::frame::IntoDf;
1616
use crate::series::SeriesMethods;
1717

‎crates/polars-ops/src/frame/join/hash_join/single_keys.rs‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -166,6 +166,24 @@ where
166166
})
167167
}
168168

169+
/// Reduces monomorphization: keeps `build_tables` instantiated once per key type.
170+
pub(crate) fn build_tables_from_arrays<T>(
171+
arrays: &[&T::Array],
172+
nulls_equal: bool,
173+
) -> Vec<PlHashMap<<Option<T::Native> as ToTotalOrd>::TotalOrdItem, IdxVec>>
174+
where
175+
T: PolarsNumericType,
176+
Option<T::Native>: TotalHash + TotalEq + ToTotalOrd,
177+
<Option<T::Native> as ToTotalOrd>::TotalOrdItem:
178+
Send + Sync + Copy + Hash + Eq + DirtyHash + IsNull,
179+
{
180+
let keys = arrays
181+
.iter()
182+
.map(|arr| arr.iter().map(|v| v.copied()))
183+
.collect();
184+
build_tables(keys, nulls_equal)
185+
}
186+
169187
// we determine the offset so that we later know which index to store in the join tuples
170188
pub(super) fn probe_to_offsets<T, I>(probe: &[I]) -> Vec<usize>
171189
where

‎crates/polars-ops/src/frame/join/hash_join/single_keys_outer.rs‎

Lines changed: 35 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -50,49 +50,44 @@ where
5050
// We will create a hashtable in every thread.
5151
// We use the hash to partition the keys to the matching hashtable.
5252
// Every thread traverses all keys/hashes and ignores the ones that doesn't fall in that partition.
53-
RAYON.install(|| {
54-
(0..n_partitions)
55-
.into_par_iter()
56-
.map(|partition_no| {
57-
let hashes_and_keys = &hashes_and_keys;
58-
let mut hash_tbl: PlHashMap<T::TotalOrdItem, (bool, IdxVec)> =
59-
PlHashMap::with_hasher(build_hasher.clone());
53+
par_map_collect(n_partitions, &|partition_no| {
54+
let hashes_and_keys = &hashes_and_keys;
55+
let mut hash_tbl: PlHashMap<T::TotalOrdItem, (bool, IdxVec)> =
56+
PlHashMap::with_hasher(build_hasher.clone());
6057

61-
let mut offset = 0;
62-
for hashes_and_keys in hashes_and_keys {
63-
let len = hashes_and_keys.len();
64-
hashes_and_keys
65-
.iter()
66-
.enumerate()
67-
.for_each(|(idx, (h, k))| {
68-
let k = k.to_total_ord();
69-
let idx = idx as IdxSize;
70-
// partition hashes by thread no.
71-
// So only a part of the hashes go to this hashmap
72-
if partition_no == hash_to_partition(*h, n_partitions) {
73-
let idx = idx + offset;
74-
let entry = hash_tbl
75-
.raw_entry_mut()
76-
// uses the key to check equality to find and entry
77-
.from_key_hashed_nocheck(*h, &k);
58+
let mut offset = 0;
59+
for hashes_and_keys in hashes_and_keys {
60+
let len = hashes_and_keys.len();
61+
hashes_and_keys
62+
.iter()
63+
.enumerate()
64+
.for_each(|(idx, (h, k))| {
65+
let k = k.to_total_ord();
66+
let idx = idx as IdxSize;
67+
// partition hashes by thread no.
68+
// So only a part of the hashes go to this hashmap
69+
if partition_no == hash_to_partition(*h, n_partitions) {
70+
let idx = idx + offset;
71+
let entry = hash_tbl
72+
.raw_entry_mut()
73+
// uses the key to check equality to find and entry
74+
.from_key_hashed_nocheck(*h, &k);
7875

79-
match entry {
80-
RawEntryMut::Vacant(entry) => {
81-
entry.insert_hashed_nocheck(*h, k, (false, unitvec![idx]));
82-
},
83-
RawEntryMut::Occupied(mut entry) => {
84-
let (_k, v) = entry.get_key_value_mut();
85-
v.1.push(idx);
86-
},
87-
}
88-
}
89-
});
76+
match entry {
77+
RawEntryMut::Vacant(entry) => {
78+
entry.insert_hashed_nocheck(*h, k, (false, unitvec![idx]));
79+
},
80+
RawEntryMut::Occupied(mut entry) => {
81+
let (_k, v) = entry.get_key_value_mut();
82+
v.1.push(idx);
83+
},
84+
}
85+
}
86+
});
9087

91-
offset += len as IdxSize;
92-
}
93-
hash_tbl
94-
})
95-
.collect()
88+
offset += len as IdxSize;
89+
}
90+
hash_tbl
9691
})
9792
}
9893

0 commit comments

Comments
 (0)