felipecrv commented on code in PR #35003:
URL: https://github.com/apache/arrow/pull/35003#discussion_r1370822464
##########
cpp/src/arrow/util/ree_util.cc:
##########
@@ -61,6 +61,62 @@ int64_t LogicalNullCount(const ArraySpan& span) {
return LogicalNullCount<int64_t>(span);
}
+namespace internal {
+
+/// \pre 0 <= i < array_span_.length()
+template <typename RunEndCType>
+int64_t FindPhysicalIndexImpl(PhysicalIndexFinder<RunEndCType>& self, int64_t
i) {
+ DCHECK_LT(i, self.array_span.length);
+ const int64_t run_ends_size = ree_util::RunEndsArray(self.array_span).length;
+ DCHECK_LT(self.last_physical_index, run_ends_size);
+ // This access to self.run_ends_[last_physical_index_] is always safe
because:
+ // 1. 0 <= i < array_span_.length() implies there is at least one run and
the initial
+ // value 0 will be safe to index with.
+ // 2. last_physical_index_ > 0 is always the result of a valid call to
+ // internal::FindPhysicalIndex.
+ if (ARROW_PREDICT_TRUE(self.array_span.offset + i <
+ self.run_ends[self.last_physical_index])) {
+ // The cached value is an upper-bound, but is it the least upper-bound?
+ if (self.last_physical_index == 0 ||
+ self.array_span.offset + i >= self.run_ends[self.last_physical_index -
1]) {
+ return self.last_physical_index;
+ }
+ // last_physical_index_ - 1 is a candidate for the least upper-bound,
+ // so search for the least upper-bound in the range that includes it.
+ const int64_t j = ree_util::internal::FindPhysicalIndex<RunEndCType>(
+ self.run_ends, /*run_ends_size=*/self.last_physical_index, i,
+ self.array_span.offset);
+ DCHECK_LT(j, self.last_physical_index);
+ return self.last_physical_index = j;
Review Comment:
The advantage being? Binary size reduciton?
##########
cpp/src/arrow/util/ree_util.cc:
##########
@@ -61,6 +61,62 @@ int64_t LogicalNullCount(const ArraySpan& span) {
return LogicalNullCount<int64_t>(span);
}
+namespace internal {
+
+/// \pre 0 <= i < array_span_.length()
+template <typename RunEndCType>
+int64_t FindPhysicalIndexImpl(PhysicalIndexFinder<RunEndCType>& self, int64_t
i) {
+ DCHECK_LT(i, self.array_span.length);
+ const int64_t run_ends_size = ree_util::RunEndsArray(self.array_span).length;
+ DCHECK_LT(self.last_physical_index, run_ends_size);
+ // This access to self.run_ends_[last_physical_index_] is always safe
because:
+ // 1. 0 <= i < array_span_.length() implies there is at least one run and
the initial
+ // value 0 will be safe to index with.
+ // 2. last_physical_index_ > 0 is always the result of a valid call to
+ // internal::FindPhysicalIndex.
+ if (ARROW_PREDICT_TRUE(self.array_span.offset + i <
+ self.run_ends[self.last_physical_index])) {
+ // The cached value is an upper-bound, but is it the least upper-bound?
+ if (self.last_physical_index == 0 ||
+ self.array_span.offset + i >= self.run_ends[self.last_physical_index -
1]) {
+ return self.last_physical_index;
+ }
+ // last_physical_index_ - 1 is a candidate for the least upper-bound,
+ // so search for the least upper-bound in the range that includes it.
+ const int64_t j = ree_util::internal::FindPhysicalIndex<RunEndCType>(
+ self.run_ends, /*run_ends_size=*/self.last_physical_index, i,
+ self.array_span.offset);
+ DCHECK_LT(j, self.last_physical_index);
+ return self.last_physical_index = j;
+ }
+
+ // last_physical_index_ is not an upper-bound, and the logical index i MUST
be
+ // in the runs that follow it. Since i is a valid logical index, we know
that at least
+ // one extra run is present.
+ DCHECK_LT(self.last_physical_index + 1, run_ends_size);
+ const int64_t lower_physical_index = self.last_physical_index + 1;
Review Comment:
Indeed. I will rename.
--
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]
