(arrow) branch main updated: GH-48977: [C++] Fix quadratic field name index construction on libc++ (#50970)

[apitrou]

This is an automated email from the ASF dual-hosted git repository.

pitrou pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow.git


The following commit(s) were added to refs/heads/main by this push:
     new 6b419a1035b GH-48977: [C++] Fix quadratic field name index 
construction on libc++ (#50970)
6b419a1035b is described below

commit 6b419a1035bdf3bd413138a004ca4ca2d597cfd2
Author: Advit Arora <advitaro...@gmail.com>
AuthorDate: Tue Aug 25 12:41:06 2026 +0530

    GH-48977: [C++] Fix quadratic field name index construction on libc++ 
(#50970)
    
    ### Rationale for this change
    
    Building a schema with 500,000 identically named fields takes about 300 
seconds.
    
    `CreateNameToIndexMap` fills an `unordered_multimap` with one bare 
`emplace` per field. libc++ keeps equal keys contiguous, so each unhinted 
insert walks to the end of the equal range before splicing, making the loop 
quadratic. libstdc++ splices next to the first match and is already linear.
    
    ### What changes are included in this PR?
    
    `emplace_hint(find(name), ...)`, the shape arvidjonasson worked out on the 
issue from the LLVM bug kou linked. `reserve(fields.size())` goes in alongside 
to pay for the extra `find`. `SchemaBuilder::Impl::AppendField` had the same 
pattern, and `Schema`'s copy constructor now rebuilds from `fields_` instead of 
copying the multimap node by node.
    
    ### Are these changes tested?
    
    `arrow-type-test` passes 157/157. Nothing observable changes, so no new 
unit test. `type_benchmark.cc` gains a schema construction case: 
`duplicate_names/10000` goes from 117 ms to 0.41 ms, `distinct_names` is level 
to 7% faster.
    
    ### Are there any user-facing changes?
    
    Fields sharing a name come back from `GetAllFieldsByName` in a different 
order. That order isn't a contract: `GetAllFieldIndices` sorts, both pyarrow 
callers reject more than one field, and the two standard libraries already 
disagree.
    
    * GitHub Issue: #48977
    
    Authored-by: Advit Arora <advitaro...@gmail.com>
    Signed-off-by: Antoine Pitrou <anto...@python.org>
---
 cpp/src/arrow/type.cc           | 11 ++++++++---
 cpp/src/arrow/type_benchmark.cc | 22 ++++++++++++++++++++++
 2 files changed, 30 insertions(+), 3 deletions(-)

diff --git a/cpp/src/arrow/type.cc b/cpp/src/arrow/type.cc
index 1dedf1978da..e841f091809 100644
--- a/cpp/src/arrow/type.cc
+++ b/cpp/src/arrow/type.cc
@@ -1333,8 +1333,11 @@ namespace {
 std::unordered_multimap<std::string_view, int> CreateNameToIndexMap(
     const FieldVector& fields) {
   std::unordered_multimap<std::string_view, int> name_to_index;
+  name_to_index.reserve(fields.size());
   for (size_t i = 0; i < fields.size(); ++i) {
-    name_to_index.emplace(fields[i]->name(), static_cast<int>(i));
+    const std::string_view name = fields[i]->name();
+    // The find() hint avoids libc++'s quadratic scan of equal keys on plain 
emplace.
+    name_to_index.emplace_hint(name_to_index.find(name), name, 
static_cast<int>(i));
   }
   return name_to_index;
 }
@@ -2294,7 +2297,7 @@ Schema::Schema(FieldVector fields, std::shared_ptr<const 
KeyValueMetadata> metad
       impl_(new Impl(std::move(fields), Endianness::Native, 
std::move(metadata))) {}
 
 Schema::Schema(const Schema& schema)
-    : detail::Fingerprintable(), impl_(new Impl(*schema.impl_)) {}
+    : Schema(schema.impl_->fields_, schema.impl_->endianness_, 
schema.impl_->metadata_) {}
 
 Schema::~Schema() = default;
 
@@ -2568,7 +2571,9 @@ class SchemaBuilder::Impl {
   }
 
   Status AppendField(const std::shared_ptr<Field>& field) {
-    name_to_index_.emplace(field->name(), static_cast<int>(fields_.size()));
+    const std::string_view name = field->name();
+    name_to_index_.emplace_hint(name_to_index_.find(name), name,
+                                static_cast<int>(fields_.size()));
     fields_.push_back(field);
     return Status::OK();
   }
diff --git a/cpp/src/arrow/type_benchmark.cc b/cpp/src/arrow/type_benchmark.cc
index f502c4b7c86..6544e3e4f99 100644
--- a/cpp/src/arrow/type_benchmark.cc
+++ b/cpp/src/arrow/type_benchmark.cc
@@ -170,6 +170,20 @@ static void SchemaEqualsWithMetadata(
   state.SetItemsProcessed(state.iterations() * 2);
 }
 
+static void SchemaConstruct(benchmark::State& state,  // NOLINT non-const 
reference
+                            bool duplicate_names) {
+  const int num_fields = static_cast<int>(state.range(0));
+  FieldVector fields(num_fields);
+  for (int i = 0; i < num_fields; ++i) {
+    fields[i] = field(duplicate_names ? "f" : "f" + std::to_string(i), 
int32());
+  }
+
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(::arrow::schema(fields));
+  }
+  state.SetItemsProcessed(state.iterations() * num_fields);
+}
+
 // ------------------------------------------------------------------------
 // Micro-benchmark various error reporting schemes
 
@@ -541,6 +555,14 @@ BENCHMARK(TypeEqualsComplex);
 BENCHMARK(TypeEqualsWithMetadata);
 BENCHMARK(SchemaEquals);
 BENCHMARK(SchemaEqualsWithMetadata);
+BENCHMARK_CAPTURE(SchemaConstruct, distinct_names, /*duplicate_names=*/false)
+    ->Arg(100)
+    ->Arg(1000)
+    ->Arg(10000);
+BENCHMARK_CAPTURE(SchemaConstruct, duplicate_names, /*duplicate_names=*/true)
+    ->Arg(100)
+    ->Arg(1000)
+    ->Arg(10000);
 
 BENCHMARK(ErrorSchemeNoError);
 BENCHMARK(ErrorSchemeBool);