lriggs commented on code in PR #55608:
URL: https://github.com/apache/arrow/pull/55608#discussion_r4605025695


##########
cpp/src/gandiva/expression_cache_key.h:
##########
@@ -19,17 +19,295 @@
 
 #include <stddef.h>
 
+#include <algorithm>
+#include <string>
 #include <thread>
+#include <type_traits>
+#include <unordered_map>
+#include <vector>
 
 #include "arrow/util/hash_util.h"
 #include "gandiva/arrow.h"
 #include "gandiva/configuration.h"
 #include "gandiva/expression.h"
+#include "gandiva/node.h"
 #include "gandiva/selection_vector.h"
 #include "gandiva/visibility.h"
 
 namespace gandiva {
 
+namespace internal {
+
+// Debug strings are ambiguous when literal values or field names contain 
expression
+// syntax. Encode the tree in a compact binary form that has one possible 
parse: every
+// node starts with a one byte tag, variable size tokens carry their length, 
and child
+// lists carry their count. Keys are process-local, so values are stored as 
raw bytes.
+//
+// Repeated types and names are written in full once per expression and as a 
short
+// reference after that. A reference points at the n-th definition in the same 
key, so
+// it stays unambiguous. Types are compared by their fingerprint, not by 
pointer, so two
+// separately built `decimal128(10, 2)` still give the same key.
+//
+// The return type of a node is written only when the node does not already 
fix it:
+// a field node has the type of its field, and boolean and IN nodes are always 
boolean.
+// This runs before validation, and a cache hit skips validation, so the key 
has to tell
+// apart every expression that validation could tell apart. Null nodes and 
types must
+// be safe.
+class ExpressionKeyVisitor : public NodeVisitor {
+ public:
+  std::string MakeKey(const Expression* expression, const char* kind) {
+    key_.clear();
+    type_by_pointer_.clear();
+    type_by_definition_.clear();
+    name_index_.clear();
+    has_like_ = false;
+
+    AppendBytes(&key_, kind);
+    if (!expression) {
+      key_ += kNullExpression;
+      return key_;
+    }
+    key_ += kExpression;
+    if (expression->result()) {
+      key_ += kResult;
+      AppendType(expression->result()->type());
+    } else {
+      key_ += kNullResult;
+    }
+    AppendNode(expression->root());
+    return key_;
+  }
+
+  bool has_like() const { return has_like_; }
+
+  Status Visit(const FieldNode& node) override {
+    key_ += kFieldNode;
+    AppendField(node.field());
+    return Status::OK();
+  }
+
+  Status Visit(const FunctionNode& node) override {
+    key_ += kFunctionNode;
+    AppendType(node.return_type());
+    AppendName(node.descriptor()->name());
+    has_like_ |= node.descriptor()->name() == "like";
+    AppendNodes(node.children());
+    return Status::OK();
+  }
+
+  Status Visit(const IfNode& node) override {
+    key_ += kIfNode;
+    AppendType(node.return_type());
+    AppendNode(node.condition());
+    AppendNode(node.then_node());
+    AppendNode(node.else_node());
+    return Status::OK();
+  }
+
+  Status Visit(const LiteralNode& node) override {
+    key_ += kLiteralNode;
+    AppendType(node.return_type());
+    key_ += node.is_null() ? kNullLiteral : kValueLiteral;
+    // The variant index fixes how many bytes follow, so values need no length.
+    key_ += static_cast<char>(node.holder().index());
+    std::visit([this](const auto& value) { AppendValue(&key_, value); }, 
node.holder());
+    return Status::OK();
+  }
+
+  Status Visit(const BooleanNode& node) override {
+    key_ += kBooleanNode;
+    key_ += static_cast<char>(node.expr_type());
+    AppendNodes(node.children());
+    return Status::OK();
+  }
+
+  Status Visit(const InExpressionNode<int32_t>& node) override {
+    return AppendIn(node, 'a');
+  }
+  Status Visit(const InExpressionNode<int64_t>& node) override {
+    return AppendIn(node, 'b');
+  }
+  Status Visit(const InExpressionNode<float>& node) override {
+    return AppendIn(node, 'c');
+  }
+  Status Visit(const InExpressionNode<double>& node) override {
+    return AppendIn(node, 'd');
+  }
+  Status Visit(const InExpressionNode<std::string>& node) override {
+    return AppendIn(node, 's');
+  }
+
+  Status Visit(const InExpressionNode<DecimalScalar128>& node) override {
+    key_ += kInNode;
+    key_ += 'D';
+    AppendVarint(&key_, static_cast<uint64_t>(node.get_precision()));
+    AppendVarint(&key_, static_cast<uint64_t>(node.get_scale()));
+    return AppendInValues(node);
+  }
+
+ private:
+  static constexpr char kNullExpression = 'X';
+  static constexpr char kExpression = 'E';
+  static constexpr char kResult = 'R';
+  static constexpr char kNullResult = 'r';
+  static constexpr char kNullNode = 'z';
+  static constexpr char kFieldNode = 'f';
+  static constexpr char kFunctionNode = 'c';
+  static constexpr char kIfNode = 'i';
+  static constexpr char kLiteralNode = 'l';
+  static constexpr char kBooleanNode = 'b';
+  static constexpr char kInNode = 'I';
+  static constexpr char kNullLiteral = 'n';
+  static constexpr char kValueLiteral = 'v';
+  static constexpr char kNullType = 'N';
+  static constexpr char kTypeDefinition = 'T';
+  static constexpr char kTypeReference = 't';
+  static constexpr char kNullField = 'Z';
+  static constexpr char kField = 'F';
+  static constexpr char kNullable = '1';
+  static constexpr char kNonNullable = '0';
+  static constexpr char kNameDefinition = 'M';
+  static constexpr char kNameReference = 'm';
+
+  static void AppendVarint(std::string* out, uint64_t value) {
+    while (value >= 0x80) {
+      out->push_back(static_cast<char>(value | 0x80));
+      value >>= 7;
+    }
+    out->push_back(static_cast<char>(value));
+  }
+
+  static void AppendBytes(std::string* out, const std::string& value) {
+    AppendVarint(out, value.size());
+    out->append(value);
+  }
+
+  template <typename T>
+  static void AppendValue(std::string* out, const T& value) {
+    static_assert(std::is_arithmetic_v<T>);
+    // Preserve exact numeric bytes, including float NaN payloads and signed 
zero,
+    // without decimal formatting or rounding.
+    out->append(reinterpret_cast<const char*>(&value), sizeof(value));
+  }
+
+  static void AppendValue(std::string* out, const std::string& value) {
+    AppendBytes(out, value);
+  }
+
+  static void AppendValue(std::string* out, const DecimalScalar128& value) {
+    AppendValue(out, value.value().high_bits());
+    AppendValue(out, value.value().low_bits());
+    AppendValue(out, value.precision());
+    AppendValue(out, value.scale());
+  }
+
+  void AppendType(const DataTypePtr& type) {

Review Comment:
   You could consider refactoring this make it simpler and easier to maintain. 
The tradeoff is some keys are larger, but they are still smaller than the 
current cache key (see below). 
   
   **What's removed (diff: +16 / −48 in the header):**
   
   AppendName() and its name_index_ map.
   The two type maps (type_by_pointer_ and type_by_definition_) and the 
temporary definition string built for each type.
   4 tags (kTypeDefinition/Reference, kNameDefinition/Reference), replaced by 
one kType.
   Clearing the maps in MakeKey(), the <unordered_map> include, and the 
paragraph in the header comment about repeated types and names.
   
   **Why the key can still only be read one way:**
   
   A type is either N (null) or T followed by a varint id and a fingerprint 
with a length prefix.
   If the fingerprint is empty, the length is 0 and a ToString() with its own 
length prefix follows. A fingerprint that isn't empty never has anything after 
it, so a reader always knows which case it's in.
   Every name has a length prefix.
   
   **Proposed change:**
   
   ```  
   void AppendType(const DataTypePtr& type) {
       if (!type) {
         key_ += kNullType;
         return;
       }
       key_ += kType;
       // The fingerprint holds the type parameters: precision and scale, time 
unit and
       // time zone. It is computed once per type instance and cached. Types 
without a
       // fingerprint fall back to their full description.
       AppendVarint(&key_, static_cast<uint64_t>(type->id()));
       const std::string& fingerprint = type->fingerprint();
       AppendBytes(&key_, fingerprint);
       if (fingerprint.empty()) {
         AppendBytes(&key_, type->ToString());
       }
     }
   
     void AppendField(const FieldPtr& field) {
       if (!field) {
         key_ += kNullField;
         return;
       }
       key_ += kField;
       AppendBytes(&key_, field->name());
       AppendType(field->type());
       key_ += field->nullable() ? kNullable : kNonNullable;
     }
   ```
   
   
   **Key size and time to build a key:** this compares the old ToString(), the 
PR's encoder and the trimmed one on the same expressions. Times are medians and 
matched closely across two runs.
   
   Expression | Old | PR | Trimmed | Trimmed vs PR | Old ms | PR ms | Trimmed ms
   -- | -- | -- | -- | -- | -- | -- | --
   nested IF, 3 arms | 265 B | 149 B | 197 B | +32% | 0.007 | 0.0009 | 0.0006
   nested IF, 673 arms | 57.7 KB | 26.8 KB | 39.6 KB | +48% | 3.16 | 0.086 | 
0.104
   nested IF, 5000 arms | 438 KB | 204 KB | 299 KB | +47% | 119 | 0.69 | 0.84
   nested IF, 673 arms, 40-char column name | 83.9 KB | 26.9 KB | 65.9 KB | 
+145% | 3.93 | 0.085 | 0.106
   flat OR, ~1 MB | 851 KB | 531 KB | 691 KB | +30% | 16.0 | 1.05 | 1.24
   wide decimal, 500 columns | 77.1 KB | 28.3 KB | 70.1 KB | +148% | 2.97 | 
0.145 | 0.077
   
   Size: interning saves a lot when long column names or parameterized types 
repeat, as in the 40-char name and decimal rows. Even there, the trimmed key is 
smaller than the key Arrow stores today, so cache memory goes down with either 
version.
   
   Speed: nearly all of the speedup comes from replacing the recursive 
ToString(), and the trimmed encoder keeps it. It is up to about 20% slower than 
the PR on repeated short names, and about twice as fast on decimal-heavy 
expressions, where the PR's map lookups cost more than just writing the type.
   
   Worst case for the cache: it holds up to 5000 entries by default. If every 
entry were a 673-arm expression, the trimmed keys would use about 64 MB more 
than the PR's, but still less than today. A cache full of keys that large isn't 
realistic, and each entry's compiled code is usually much bigger than its key.



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

Reply via email to