You are viewing a plain text version of this content. The canonical link for it is here.

Posted to github@arrow.apache.org by "advitrocks9 (via GitHub)" <gi...@apache.org> on 2026/08/24 15:13:29 UTC

[PR] GH-48977: [C++] Fix quadratic field name index construction on libc++ [arrow]

advitrocks9 opened a new pull request, #50970:
URL: https://github.com/apache/arrow/pull/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

--
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] GH-48977: [C++] Fix quadratic field name index construction on libc++ [arrow]

Posted by "advitrocks9 (via GitHub)" <gi...@apache.org>.

advitrocks9 commented on code in PR #50970:
URL: https://github.com/apache/arrow/pull/50970#discussion_r3849636367


##########
cpp/src/arrow/type.cc:
##########
@@ -1333,8 +1333,10 @@ 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();
+    name_to_index.emplace_hint(name_to_index.find(name), name, static_cast<int>(i));

Review Comment:
   Done in 4cacc16.



##########
cpp/src/arrow/type.cc:
##########
@@ -2294,7 +2296,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_) {}

Review Comment:
   Copying the Impl copies the multimap, and libc++'s multimap copy constructor re-inserts each element without a hint, so it has the same quadratic problem. See https://github.com/llvm/llvm-project/blob/release/21.x/libcxx/include/unordered_map#L2319-L2324. Rebuilding through CreateNameToIndexMap uses the hinted path.



-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org