better

benchmark/bench_ondemand.cpp

@@ -40,6 +40,7 @@ SIMDJSON_POP_DISABLE_WARNINGS
 #include "json2msgpack/boostjson.h"
 
 #include "partial_tweets/simdjson_ondemand.h"
+#include "partial_tweets/simdjson_ondemand_key_selector.h"
 #include "partial_tweets/simdjson_dom.h"
 #include "partial_tweets/yyjson.h"
 #if SIMDJSON_COMPETITION_ONDEMAND_SAJSON

include/simdjson/concepts.h

@@ -59,6 +59,14 @@ concept appendable_containers =
     details::supports_add<T> || details::supports_append<T> ||
     details::supports_insert<T>) && !string_view_keyed_map<T>;
 
+/// Check if T is a key_selector type for efficient JSON field lookup
+template <typename T>
+concept key_selector_type = requires(T selector) {
+    { selector.size() } -> std::same_as<std::size_t>;
+    { selector.index_of(std::string_view{}) } -> std::same_as<std::size_t>;
+    { selector.get_key(std::size_t{}) } -> std::same_as<std::string_view>;
+};
+
 /// Insert into the container however possible
 template <appendable_containers T, typename... Args>
 constexpr decltype(auto) emplace_one(T &vec, Args &&...args) {

include/simdjson/generic/ondemand/amalgamated.h

@@ -20,6 +20,7 @@
 #include "simdjson/generic/ondemand/document.h"
 #include "simdjson/generic/ondemand/document_stream.h"
 #include "simdjson/generic/ondemand/field.h"
+#include "simdjson/generic/ondemand/key_selector.h"
 #include "simdjson/generic/ondemand/object.h"
 #include "simdjson/generic/ondemand/object_iterator.h"
 #include "simdjson/generic/ondemand/serialization.h"

include/simdjson/generic/ondemand/key_selector.h

@@ -0,0 +1,339 @@
+#ifndef SIMDJSON_GENERIC_ONDEMAND_KEY_SELECTOR_H
+#define SIMDJSON_GENERIC_ONDEMAND_KEY_SELECTOR_H
+
+#include "simdjson/base.h"
+#include "simdjson/common_defs.h"
+#include <array>
+#include <string_view>
+#include <cstddef>
+#include <cstdint>
+#include <cstring>
+
+#if SIMDJSON_SUPPORTS_CONCEPTS
+
+namespace simdjson {
+namespace SIMDJSON_IMPLEMENTATION {
+namespace ondemand {
+
+
+
+// Forward declaration
+class object;
+
+/**
+ * A compile-time key selector for efficient JSON object field lookup.
+ * Uses perfect hashing (gperf-style) to map keys to identifiers.
+ */
+template <std::size_t N>
+class key_selector {
+    static_assert(N > 0, "key_selector requires at least one key");
+    static_assert(N <= 100, "key_selector supports at most 100 keys");
+
+    // Perfect hash table data (gperf-style)
+    static constexpr std::size_t MAX_POSITIONS = 16;
+    static constexpr std::size_t POS_LAST_CHAR = std::size_t(-1);
+    static constexpr std::size_t MAX_TABLE_SIZE = 256; // Power of 2, fits in uint8_t
+
+    std::array<std::array<std::uint8_t, 256>, MAX_POSITIONS> asso_values_{};
+    std::uint8_t num_positions_{};
+    std::array<std::size_t, MAX_POSITIONS> positions_{};
+    std::array<std::uint8_t, MAX_TABLE_SIZE> slot_to_key_{};
+    std::array<std::uint8_t, N> key_to_slot_{};
+    std::array<std::array<char, 64>, N> key_data_{};
+    std::array<std::uint8_t, N> key_lengths_{};
+    std::size_t table_size_{};
+
+public:
+    // Validate keys at compile time
+    constexpr void validate_keys(const std::array<std::string_view, N>& keys) {
+        for (std::size_t i = 0; i < N; ++i) {
+            auto key = keys[i];
+            if (key.empty()) {
+                throw "Empty keys are not allowed in key_selector";
+            }
+            if (key.size() > SIMDJSON_PADDING) {
+                throw "Key length exceeds SIMDJSON_PADDING (64 bytes)";
+            }
+            for (char c : key) {
+                if (c == '\\') {
+                    throw "Escape characters (\\) are not allowed in key_selector keys";
+                }
+                if (c == '\0') {
+                    throw "Null characters are not allowed in key_selector keys";
+                }
+            }
+        }
+    }
+
+    // Gperf-style perfect hash generation using partition-based algorithm
+    constexpr void generate_hash_table(const std::array<std::string_view, N>& keys) {
+        // Try power-of-two table sizes starting from next_power_of_2(N)
+        constexpr std::size_t START_M = next_power_of_2(N);
+        if constexpr (START_M <= MAX_TABLE_SIZE) {
+            if (try_compute_phf<START_M>(keys)) return;
+            if constexpr (START_M * 2 <= MAX_TABLE_SIZE) {
+                if (try_compute_phf<START_M * 2>(keys)) return;
+                if constexpr (START_M * 4 <= MAX_TABLE_SIZE) {
+                    if (try_compute_phf<START_M * 4>(keys)) return;
+                    if constexpr (START_M * 8 <= MAX_TABLE_SIZE) {
+                        if (try_compute_phf<START_M * 8>(keys)) return;
+                    }
+                }
+            }
+        }
+
+        // Fallback: linear table
+        table_size_ = N;
+        num_positions_ = 0;
+        std::fill(slot_to_key_.begin(), slot_to_key_.begin() + MAX_TABLE_SIZE, static_cast<std::uint8_t>(N));
+        for (std::size_t i = 0; i < N; ++i) {
+            slot_to_key_[i] = static_cast<std::uint8_t>(i);
+            key_to_slot_[i] = static_cast<std::uint8_t>(i);
+        }
+    }
+
+private:
+    // Helper functions for gperf algorithm
+    static constexpr std::size_t next_power_of_2(std::size_t n) {
+        if (n == 0) return 1;
+        std::size_t p = 1;
+        while (p < n) p <<= 1;
+        return p;
+    }
+
+    static constexpr std::size_t char_at(std::string_view key, std::size_t pos) {
+        if (pos == POS_LAST_CHAR) {
+            return key.empty() ? 256 : static_cast<unsigned char>(key.back());
+        }
+        return (pos < key.size()) ? static_cast<unsigned char>(key[pos]) : 256;
+    }
+
+    template <std::size_t M>
+    constexpr bool try_compute_phf(const std::array<std::string_view, N>& keys) {
+        // Initialize
+        std::array<std::array<std::size_t, 256>, MAX_POSITIONS> asso{};
+        std::size_t npos = 0;
+        std::array<std::size_t, MAX_POSITIONS> pos{};
+        std::array<std::size_t, M> s2k{};
+
+        // Try to generate gperf
+        if (try_generate_gperf<M>(keys, asso, npos, pos, s2k)) {
+            table_size_ = M;
+            num_positions_ = static_cast<std::uint8_t>(npos);
+            for (std::size_t p = 0; p < MAX_POSITIONS; ++p) {
+                positions_[p] = pos[p];
+                for (std::size_t c = 0; c < 256; ++c) {
+                    asso_values_[p][c] = static_cast<std::uint8_t>(asso[p][c]);
+                }
+            }
+            for (std::size_t i = 0; i < M; ++i) {
+                slot_to_key_[i] = static_cast<std::uint8_t>(s2k[i]);
+            }
+            // Fill remaining slots with sentinel
+            for (std::size_t i = M; i < MAX_TABLE_SIZE; ++i) {
+                slot_to_key_[i] = static_cast<std::uint8_t>(N);
+            }
+
+            // Build key_to_slot mapping
+            for (std::size_t i = 0; i < N; ++i) {
+                key_to_slot_[i] = static_cast<std::uint8_t>(N); // Initialize
+            }
+            for (std::size_t slot = 0; slot < M; ++slot) {
+                std::size_t key_idx = s2k[slot];
+                if (key_idx < N) {
+                    key_to_slot_[key_idx] = static_cast<std::uint8_t>(slot);
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    template <std::size_t M>
+    static constexpr bool try_generate_gperf(
+        const std::array<std::string_view, N>& keys,
+        std::array<std::array<std::size_t, 256>, MAX_POSITIONS>& asso_values,
+        std::size_t& num_positions,
+        std::array<std::size_t, MAX_POSITIONS>& positions,
+        std::array<std::size_t, M>& slot_to_key)
+    {
+        // Initialize
+        for (std::size_t p = 0; p < MAX_POSITIONS; ++p) {
+            for (std::size_t c = 0; c < 256; ++c) {
+                asso_values[p][c] = 0;
+            }
+        }
+        for (std::size_t i = 0; i < M; ++i) {
+            slot_to_key[i] = N;
+        }
+
+        // Try length-only hashing first
+        bool success = true;
+        for (std::size_t i = 0; i < N && success; ++i) {
+            std::size_t slot = keys[i].size() % M;
+            if (slot_to_key[slot] != N) {
+                success = false;
+            } else {
+                slot_to_key[slot] = i;
+            }
+        }
+
+        if (success) {
+            num_positions = 0;
+            return true;
+        }
+
+        // Try with position 0
+        positions[0] = 0;
+        num_positions = 1;
+
+        // Find a working assignment of asso_values for position 0
+        // Use a simple approach: try different offsets
+        for (std::size_t offset = 0; offset < M; ++offset) {
+            // Reset
+            for (std::size_t i = 0; i < M; ++i) {
+                slot_to_key[i] = N;
+            }
+
+            // Assign asso_values based on offset
+            for (std::size_t c = 0; c < 256; ++c) {
+                asso_values[0][c] = (c + offset) % M;
+            }
+
+            success = true;
+            for (std::size_t i = 0; i < N && success; ++i) {
+                std::size_t h = keys[i].size();
+                std::size_t ch = char_at(keys[i], 0);
+                if (ch < 256) h += asso_values[0][ch];
+                std::size_t slot = h % M;
+
+                if (slot_to_key[slot] != N) {
+                    success = false;
+                } else {
+                    slot_to_key[slot] = i;
+                }
+            }
+
+            if (success) {
+                return true;
+            }
+        }
+
+        // Try with positions {0, last_char}
+        if (N <= 50) { // Only for smaller N to avoid complexity
+            positions[0] = 0;
+            positions[1] = POS_LAST_CHAR;
+            num_positions = 2;
+
+            for (std::size_t offset1 = 0; offset1 < 4 && !success; ++offset1) {
+                for (std::size_t offset2 = 0; offset2 < 4 && !success; ++offset2) {
+                    // Reset
+                    for (std::size_t i = 0; i < M; ++i) {
+                        slot_to_key[i] = N;
+                    }
+
+                    // Assign asso_values
+                    for (std::size_t c = 0; c < 256; ++c) {
+                        asso_values[0][c] = (c + offset1) % M;
+                        asso_values[1][c] = (c + offset2) % M;
+                    }
+
+                    success = true;
+                    for (std::size_t i = 0; i < N && success; ++i) {
+                        std::size_t h = keys[i].size();
+                        std::size_t ch1 = char_at(keys[i], 0);
+                        if (ch1 < 256) h += asso_values[0][ch1];
+                        std::size_t ch2 = char_at(keys[i], POS_LAST_CHAR);
+                        if (ch2 < 256) h += asso_values[1][ch2];
+                        std::size_t slot = h % M;
+
+                        if (slot_to_key[slot] != N) {
+                            success = false;
+                        } else {
+                            slot_to_key[slot] = i;
+                        }
+                    }
+
+                    if (success) {
+                        return true;
+                    }
+                }
+            }
+        }
+
+        return false;
+    }
+
+
+
+public:
+    constexpr key_selector(const std::array<std::string_view, N>& keys) {
+        validate_keys(keys);
+
+        // Store key data
+        for (std::size_t i = 0; i < N; ++i) {
+            key_lengths_[i] = static_cast<std::uint8_t>(keys[i].size());
+            std::copy(keys[i].begin(), keys[i].end(), key_data_[i].begin());
+        }
+
+        generate_hash_table(keys);
+    }
+
+    [[nodiscard]] constexpr std::size_t size() const noexcept { return N; }
+
+    [[nodiscard]] constexpr simdjson_really_inline std::size_t compute_hash(std::string_view key) const noexcept {
+        std::size_t h = key.size();
+        const char* kp = key.data();
+        for (std::uint8_t i = 0; i < num_positions_; ++i) {
+            std::size_t pos = positions_[i];
+            std::size_t ch;
+            if (pos == POS_LAST_CHAR) {
+                ch = static_cast<unsigned char>(key.back());
+            } else {
+                ch = static_cast<unsigned char>(kp[pos]);
+            }
+            h += asso_values_[i][ch];
+        }
+        return h & (table_size_ - 1);
+    }
+
+    [[nodiscard]] constexpr simdjson_really_inline  bool contains(std::string_view key) const noexcept {
+        std::size_t slot = compute_hash(key);
+        if (slot >= table_size_) return false;
+
+        std::uint8_t key_idx = slot_to_key_[slot];
+        if (key_idx >= N) return false;
+
+        // Compare key
+        if (key_lengths_[key_idx] != key.size()) return false;
+        return std::equal(key.begin(), key.end(), key_data_[key_idx].begin());
+    }
+
+    [[nodiscard]] constexpr simdjson_really_inline std::size_t index_of(std::string_view key) const noexcept {
+        std::size_t slot = compute_hash(key);
+        if (slot >= table_size_) return N; // Invalid index
+
+        std::uint8_t key_idx = slot_to_key_[slot];
+        if (key_idx >= N) return N;
+
+        // Compare key
+        if (key_lengths_[key_idx] != key.size()) return N;
+        if (!std::equal(key.begin(), key.end(), key_data_[key_idx].begin())) return N;
+
+        return key_idx;
+    }
+
+    // Accessors for key data (used by object::find_field)
+    [[nodiscard]] constexpr std::string_view get_key(std::size_t index) const noexcept {
+        if (index >= N) return {};
+        return std::string_view(key_data_[index].data(), key_lengths_[index]);
+    }
+};
+
+} // namespace ondemand
+} // namespace SIMDJSON_IMPLEMENTATION
+} // namespace simdjson
+
+#endif // SIMDJSON_SUPPORTS_CONCEPTS
+
+#endif // SIMDJSON_GENERIC_ONDEMAND_KEY_SELECTOR_H

include/simdjson/generic/ondemand/object-inl.h

@@ -63,6 +63,42 @@ simdjson_inline simdjson_result<value> object::find_field(const std::string_view
   return value(iter.child());
 }
 
+#if SIMDJSON_SUPPORTS_CONCEPTS
+template <concepts::key_selector_type Selector>
+simdjson_inline std::pair<std::size_t, simdjson_result<value>> object::find_field(const Selector& selector) & noexcept {
+  // Try to find any of the keys in the selector
+  for (std::size_t i = 0; i < selector.size(); ++i) {
+    std::string_view key = selector.get_key(i);
+    auto result = iter.find_field_unordered_raw(key);
+    if (result.error()) {
+      return {selector.size(), result.error()};
+    }
+    bool has_value = result.value();
+    if (has_value) {
+      return {i, value(iter.child())};
+    }
+  }
+  return {selector.size(), NO_SUCH_FIELD}; // Return size() as invalid index
+}
+
+template <concepts::key_selector_type Selector>
+simdjson_inline std::pair<std::size_t, simdjson_result<value>> object::find_field(const Selector& selector) && noexcept {
+  // Try to find any of the keys in the selector
+  for (std::size_t i = 0; i < selector.size(); ++i) {
+    std::string_view key = selector.get_key(i);
+    auto result = iter.find_field_unordered_raw(key);
+    if (result.error()) {
+      return {selector.size(), result.error()};
+    }
+    bool has_value = result.value();
+    if (has_value) {
+      return {i, value(iter.child())};
+    }
+  }
+  return {selector.size(), NO_SUCH_FIELD}; // Return size() as invalid index
+}
+#endif
+
 simdjson_inline simdjson_result<object> object::start(value_iterator &iter) noexcept {
   SIMDJSON_TRY( iter.start_object().error() );
   return object(iter);
@@ -334,6 +370,20 @@ simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> simdjs
   return std::forward<SIMDJSON_IMPLEMENTATION::ondemand::object>(first).find_field(key);
 }
 
+#if SIMDJSON_SUPPORTS_CONCEPTS
+template <concepts::key_selector_type Selector>
+simdjson_inline std::pair<std::size_t, simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value>> simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::object>::find_field(const Selector& selector) & noexcept {
+  if (error()) { return {0, error()}; }
+  return first.find_field(selector);
+}
+
+template <concepts::key_selector_type Selector>
+simdjson_inline std::pair<std::size_t, simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value>> simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::object>::find_field(const Selector& selector) && noexcept {
+  if (error()) { return {0, error()}; }
+  return std::forward<SIMDJSON_IMPLEMENTATION::ondemand::object>(first).find_field(selector);
+}
+#endif
+
 simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::object>::at_pointer(std::string_view json_pointer) noexcept {
   if (error()) { return error(); }
   return first.at_pointer(json_pointer);

include/simdjson/generic/ondemand/object.h

@@ -5,6 +5,7 @@
 #include "simdjson/generic/ondemand/base.h"
 #include "simdjson/generic/implementation_simdjson_result_base.h"
 #include "simdjson/generic/ondemand/value_iterator.h"
+#include "simdjson/generic/ondemand/key_selector.h"
 #include <vector>
 #if SIMDJSON_STATIC_REFLECTION && SIMDJSON_SUPPORTS_CONCEPTS
 #include "simdjson/generic/ondemand/json_string_builder.h"  // for constevalutil::fixed_string
@@ -122,6 +123,23 @@ public:
   /** @overload simdjson_inline simdjson_result<value> find_field_unordered(std::string_view key) & noexcept; */
   simdjson_inline simdjson_result<value> operator[](std::string_view key) && noexcept;
 
+#if SIMDJSON_SUPPORTS_CONCEPTS
+  /**
+   * Look up a field by name using a key_selector. This method is similar to find_field_unordered()
+   * but uses a compile-time generated perfect hash table for efficient lookup.
+   *
+   * @tparam Selector The key_selector type
+   * @param selector The key selector instance
+   * @returns A pair containing the key identifier (index in the selector) and the value,
+   *          or NO_SUCH_FIELD if the field is not in the object.
+   */
+  template <concepts::key_selector_type Selector>
+  simdjson_inline std::pair<std::size_t, simdjson_result<value>> find_field(const Selector& selector) & noexcept;
+  /** @overload template <concepts::key_selector_type Selector> simdjson_inline std::pair<std::size_t, simdjson_result<value>> find_field(const Selector& selector) & noexcept; */
+  template <concepts::key_selector_type Selector>
+  simdjson_inline std::pair<std::size_t, simdjson_result<value>> find_field(const Selector& selector) && noexcept;
+#endif
+
   /**
    * Get the value associated with the given JSON pointer. We use the RFC 6901
    * https://tools.ietf.org/html/rfc6901 standard, interpreting the current node
@@ -324,6 +342,12 @@ public:
   simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> find_field(std::string_view key) && noexcept;
   simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> find_field_unordered(std::string_view key) & noexcept;
   simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> find_field_unordered(std::string_view key) && noexcept;
+#if SIMDJSON_SUPPORTS_CONCEPTS
+  template <concepts::key_selector_type Selector>
+  simdjson_inline std::pair<std::size_t, simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value>> find_field(const Selector& selector) & noexcept;
+  template <concepts::key_selector_type Selector>
+  simdjson_inline std::pair<std::size_t, simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value>> find_field(const Selector& selector) && noexcept;
+#endif
   simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> operator[](std::string_view key) & noexcept;
   simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> operator[](std::string_view key) && noexcept;
   simdjson_inline simdjson_result<SIMDJSON_IMPLEMENTATION::ondemand::value> at_pointer(std::string_view json_pointer) noexcept;

tests/ondemand/CMakeLists.txt

@@ -25,6 +25,7 @@ add_cpp_test(ondemand_misc_tests                     LABELS ondemand acceptance
 add_cpp_test(ondemand_number_tests                   LABELS ondemand acceptance per_implementation)
 add_cpp_test(ondemand_number_in_string_tests         LABELS ondemand acceptance per_implementation)
 add_cpp_test(ondemand_object_tests                   LABELS ondemand acceptance per_implementation)
+add_cpp_test(ondemand_object_find_field_tests        LABELS ondemand acceptance per_implementation)
 add_cpp_test(ondemand_object_error_tests             LABELS ondemand acceptance per_implementation)
 add_cpp_test(ondemand_ordering_tests                 LABELS ondemand acceptance per_implementation)
 add_cpp_test(ondemand_parse_api_tests                LABELS ondemand acceptance per_implementation)

tests/ondemand/ondemand_object_find_field_tests.cpp

@@ -173,6 +173,36 @@ namespace object_tests {
     TEST_SUCCEED();
   }
 
+#if SIMDJSON_SUPPORTS_CONCEPTS
+  bool object_find_field_key_selector() {
+    TEST_START();
+    auto json = R"({ "name": "John", "age": 30, "city": "New York" })"_padded;
+    constexpr std::array<std::string_view, 3> keys = {"name", "age", "city"};
+    constexpr auto selector = ondemand::key_selector<3>(keys);
+
+    SUBTEST("ondemand::object with key_selector", test_ondemand_doc(json, [&](auto doc_result) {
+      ondemand::object object;
+      ASSERT_SUCCESS( doc_result.get(object) );
+
+      auto [index, value_result] = object.find_field(selector);
+      ASSERT_TRUE(index < 3);
+      ASSERT_SUCCESS(value_result);
+      std::string_view str_val;
+      ASSERT_SUCCESS(value_result.get(str_val));
+      ASSERT_EQUAL(str_val, "John");
+
+      // Test that we can find different keys
+      ASSERT_EQUAL(selector.index_of("name"), 0);
+      ASSERT_EQUAL(selector.index_of("age"), 1);
+      ASSERT_EQUAL(selector.index_of("city"), 2);
+      ASSERT_EQUAL(selector.index_of("invalid"), 3); // Not found
+
+      return true;
+    }));
+    TEST_SUCCEED();
+  }
+#endif
+
   bool run() {
     return
            object_find_field_unordered() &&
@@ -181,6 +211,9 @@ namespace object_tests {
            object_find_field() &&
            document_object_find_field() &&
            value_object_find_field() &&
+#if SIMDJSON_SUPPORTS_CONCEPTS
+           object_find_field_key_selector() &&
+#endif
            true;
   }