Skip to content

Commit 04249b9

Browse files
authored
GH-45216: [C++][Compute] Refactor Rank implementation (#45217)
### Rationale for this change The Rank implementation currently mixes ties/duplicates detection and rank computation in a single function `CreateRankings`. This makes it poorly reusable for other Rank-like functions such as the Percentile Rank function proposed in GH-45190. ### What changes are included in this PR? Split duplicates detection into a dedicated function that sets a marker bit in the sort-indices array (it is private to the Rank implementation, so it is safe to mutate it). The rank computation itself (`CreateRankings`) becomes simpler and, moreover, it does not need to read the input values: it becomes therefore type-agnostic. This yields a code size reduction (around 45kB saved on the author's machine): * before: ```console $ size /build/build-release/relwithdebinfo/libarrow.so text data bss dec hex filename 26072218 353832 2567985 28994035 1ba69f3 /build/build-release/relwithdebinfo/libarrow.so ``` * after: ```console $ size /build/build-release/relwithdebinfo/libarrow.so text data bss dec hex filename 26028198 353832 2567985 28950015 1b9bdff /build/build-release/relwithdebinfo/libarrow.so ``` Rank benchmark results are mostly neutral, though there are slight improvements on some benchmarks, and slight regressions especially on all-nulls input. ### Are these changes tested? Yes, by existing tests. ### Are there any user-facing changes? No. * GitHub Issue: #45216 Authored-by: Antoine Pitrou <[email protected]> Signed-off-by: Antoine Pitrou <[email protected]>
1 parent b1bb480 commit 04249b9

4 files changed

Lines changed: 145 additions & 198 deletions

File tree

‎cpp/src/arrow/compute/kernels/vector_rank.cc‎

Lines changed: 73 additions & 84 deletions
Original file line numberDiff line numberDiff line change
@@ -28,114 +28,97 @@ namespace {
2828
// ----------------------------------------------------------------------
2929
// Rank implementation
3030

31-
template <typename ValueSelector,
32-
typename T = std::decay_t<std::invoke_result_t<ValueSelector, int64_t>>>
31+
// A bit that is set in the sort indices when the value at the current sort index
32+
// is the same as the value at the previous sort index.
33+
constexpr uint64_t kDuplicateMask = 1ULL << 63;
34+
35+
constexpr bool NeedsDuplicates(RankOptions::Tiebreaker tiebreaker) {
36+
return tiebreaker != RankOptions::First;
37+
}
38+
39+
template <typename ValueSelector>
40+
void MarkDuplicates(const NullPartitionResult& sorted, ValueSelector&& value_selector) {
41+
using T = decltype(value_selector(int64_t{}));
42+
43+
// Process non-nulls
44+
if (sorted.non_nulls_end != sorted.non_nulls_begin) {
45+
auto it = sorted.non_nulls_begin;
46+
T prev_value = value_selector(*it);
47+
while (++it < sorted.non_nulls_end) {
48+
T curr_value = value_selector(*it);
49+
if (curr_value == prev_value) {
50+
*it |= kDuplicateMask;
51+
}
52+
prev_value = curr_value;
53+
}
54+
}
55+
56+
// Process nulls
57+
if (sorted.nulls_end != sorted.nulls_begin) {
58+
// TODO this should be able to distinguish between NaNs and real nulls (GH-45193)
59+
auto it = sorted.nulls_begin;
60+
while (++it < sorted.nulls_end) {
61+
*it |= kDuplicateMask;
62+
}
63+
}
64+
}
65+
3366
Result<Datum> CreateRankings(ExecContext* ctx, const NullPartitionResult& sorted,
3467
const NullPlacement null_placement,
35-
const RankOptions::Tiebreaker tiebreaker,
36-
ValueSelector&& value_selector) {
68+
const RankOptions::Tiebreaker tiebreaker) {
3769
auto length = sorted.overall_end() - sorted.overall_begin();
3870
ARROW_ASSIGN_OR_RAISE(auto rankings,
3971
MakeMutableUInt64Array(length, ctx->memory_pool()));
4072
auto out_begin = rankings->GetMutableValues<uint64_t>(1);
4173
uint64_t rank;
4274

75+
auto is_duplicate = [](uint64_t index) { return (index & kDuplicateMask) != 0; };
76+
auto original_index = [](uint64_t index) { return index & ~kDuplicateMask; };
77+
4378
switch (tiebreaker) {
4479
case RankOptions::Dense: {
45-
T curr_value, prev_value{};
4680
rank = 0;
47-
48-
if (null_placement == NullPlacement::AtStart && sorted.null_count() > 0) {
49-
rank++;
50-
for (auto it = sorted.nulls_begin; it < sorted.nulls_end; it++) {
51-
out_begin[*it] = rank;
52-
}
53-
}
54-
55-
for (auto it = sorted.non_nulls_begin; it < sorted.non_nulls_end; it++) {
56-
curr_value = value_selector(*it);
57-
if (it == sorted.non_nulls_begin || curr_value != prev_value) {
58-
rank++;
59-
}
60-
61-
out_begin[*it] = rank;
62-
prev_value = curr_value;
63-
}
64-
65-
if (null_placement == NullPlacement::AtEnd) {
66-
rank++;
67-
for (auto it = sorted.nulls_begin; it < sorted.nulls_end; it++) {
68-
out_begin[*it] = rank;
81+
for (auto it = sorted.overall_begin(); it < sorted.overall_end(); ++it) {
82+
if (!is_duplicate(*it)) {
83+
++rank;
6984
}
85+
out_begin[original_index(*it)] = rank;
7086
}
7187
break;
7288
}
7389

7490
case RankOptions::First: {
7591
rank = 0;
7692
for (auto it = sorted.overall_begin(); it < sorted.overall_end(); it++) {
93+
// No duplicate marks expected for RankOptions::First
94+
DCHECK(!is_duplicate(*it));
7795
out_begin[*it] = ++rank;
7896
}
7997
break;
8098
}
8199

82100
case RankOptions::Min: {
83-
T curr_value, prev_value{};
84101
rank = 0;
85-
86-
if (null_placement == NullPlacement::AtStart) {
87-
rank++;
88-
for (auto it = sorted.nulls_begin; it < sorted.nulls_end; it++) {
89-
out_begin[*it] = rank;
90-
}
91-
}
92-
93-
for (auto it = sorted.non_nulls_begin; it < sorted.non_nulls_end; it++) {
94-
curr_value = value_selector(*it);
95-
if (it == sorted.non_nulls_begin || curr_value != prev_value) {
102+
for (auto it = sorted.overall_begin(); it < sorted.overall_end(); ++it) {
103+
if (!is_duplicate(*it)) {
96104
rank = (it - sorted.overall_begin()) + 1;
97105
}
98-
out_begin[*it] = rank;
99-
prev_value = curr_value;
100-
}
101-
102-
if (null_placement == NullPlacement::AtEnd) {
103-
rank = sorted.non_null_count() + 1;
104-
for (auto it = sorted.nulls_begin; it < sorted.nulls_end; it++) {
105-
out_begin[*it] = rank;
106-
}
106+
out_begin[original_index(*it)] = rank;
107107
}
108108
break;
109109
}
110110

111111
case RankOptions::Max: {
112-
// The algorithm for Max is just like Min, but in reverse order.
113-
T curr_value, prev_value{};
114112
rank = length;
115-
116-
if (null_placement == NullPlacement::AtEnd) {
117-
for (auto it = sorted.nulls_begin; it < sorted.nulls_end; it++) {
118-
out_begin[*it] = rank;
119-
}
120-
}
121-
122-
for (auto it = sorted.non_nulls_end - 1; it >= sorted.non_nulls_begin; it--) {
123-
curr_value = value_selector(*it);
124-
125-
if (it == sorted.non_nulls_end - 1 || curr_value != prev_value) {
126-
rank = (it - sorted.overall_begin()) + 1;
127-
}
128-
out_begin[*it] = rank;
129-
prev_value = curr_value;
130-
}
131-
132-
if (null_placement == NullPlacement::AtStart) {
133-
rank = sorted.null_count();
134-
for (auto it = sorted.nulls_begin; it < sorted.nulls_end; it++) {
135-
out_begin[*it] = rank;
113+
for (auto it = sorted.overall_end() - 1; it >= sorted.overall_begin(); --it) {
114+
out_begin[original_index(*it)] = rank;
115+
// If the current index isn't marked as duplicate, then it's the last
116+
// tie in a row (since we iterate in reverse order), so update rank
117+
// for the next row of ties.
118+
if (!is_duplicate(*it)) {
119+
rank = it - sorted.overall_begin();
136120
}
137121
}
138-
139122
break;
140123
}
141124
}
@@ -209,11 +192,14 @@ class Ranker<Array> : public RankerMixin<Array, Ranker<Array>> {
209192
array_sorter(indices_begin_, indices_end_, array, 0,
210193
ArraySortOptions(order_, null_placement_), ctx_));
211194

212-
auto value_selector = [&array](int64_t index) {
213-
return GetView::LogicalValue(array.GetView(index));
214-
};
215-
ARROW_ASSIGN_OR_RAISE(*output_, CreateRankings(ctx_, sorted, null_placement_,
216-
tiebreaker_, value_selector));
195+
if (NeedsDuplicates(tiebreaker_)) {
196+
auto value_selector = [&array](int64_t index) {
197+
return GetView::LogicalValue(array.GetView(index));
198+
};
199+
MarkDuplicates(sorted, value_selector);
200+
}
201+
ARROW_ASSIGN_OR_RAISE(*output_,
202+
CreateRankings(ctx_, sorted, null_placement_, tiebreaker_));
217203

218204
return Status::OK();
219205
}
@@ -238,13 +224,16 @@ class Ranker<ChunkedArray> : public RankerMixin<ChunkedArray, Ranker<ChunkedArra
238224
SortChunkedArray(ctx_, indices_begin_, indices_end_, physical_type_,
239225
physical_chunks_, order_, null_placement_));
240226

241-
const auto arrays = GetArrayPointers(physical_chunks_);
242-
auto value_selector = [resolver = ChunkedArrayResolver(span(arrays))](int64_t index) {
243-
return resolver.Resolve(index).Value<InType>();
244-
};
245-
ARROW_ASSIGN_OR_RAISE(*output_, CreateRankings(ctx_, sorted, null_placement_,
246-
tiebreaker_, value_selector));
247-
227+
if (NeedsDuplicates(tiebreaker_)) {
228+
const auto arrays = GetArrayPointers(physical_chunks_);
229+
auto value_selector = [resolver =
230+
ChunkedArrayResolver(span(arrays))](int64_t index) {
231+
return resolver.Resolve(index).Value<InType>();
232+
};
233+
MarkDuplicates(sorted, value_selector);
234+
}
235+
ARROW_ASSIGN_OR_RAISE(*output_,
236+
CreateRankings(ctx_, sorted, null_placement_, tiebreaker_));
248237
return Status::OK();
249238
}
250239

‎cpp/src/arrow/compute/kernels/vector_sort.cc‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -121,7 +121,7 @@ class ChunkedArraySorter : public TypeVisitor {
121121
CompressedChunkLocation* nulls_middle,
122122
CompressedChunkLocation* nulls_end,
123123
CompressedChunkLocation* temp_indices, int64_t null_count) {
124-
if (has_null_like_values<typename ArrayType::TypeClass>::value) {
124+
if (has_null_like_values<typename ArrayType::TypeClass>()) {
125125
PartitionNullsOnly<StablePartitioner>(nulls_begin, nulls_end, arrays,
126126
null_count, null_placement_);
127127
}
@@ -781,7 +781,7 @@ class TableSorter {
781781
CompressedChunkLocation* nulls_middle,
782782
CompressedChunkLocation* nulls_end,
783783
CompressedChunkLocation* temp_indices, int64_t null_count) {
784-
if constexpr (has_null_like_values<ArrowType>::value) {
784+
if constexpr (has_null_like_values<ArrowType>()) {
785785
// Merge rows with a null or a null-like in the first sort key
786786
auto& comparator = comparator_;
787787
const auto& first_sort_key = sort_keys_[0];

0 commit comments

Comments
 (0)