[C++] arrow::schema construction performance degrades to O(n^2) on libc++ for duplicate/unnamed fields

Describe the bug, including details regarding any error messages, version, and platform.

arrow::schema construction performance degrades to quadratic time on libc++ when there's a lot of fields with duplicate or no names. This is most critical when creating wide schemas programmatically.

The performance degradation is caused by the function CreateNameToIndexMap. The function calls std::unordered_multimap::emplace once per field. On libc++, this function call has linear runtime (amortized) for duplicate keys because it iterates past every existing entry to emplace the new element at the end of the range (see LLVM bugzilla 16747 and 21275).

Some performance benchmarks creating a schema with N int32 fields:

N	Time (s)	Growth factor (vs previous input)
500	0.000464958s	NA
5000	0.041429s	89.1x
50000	4.12813s	99.6x
500000	416.985s	101.0x

One fix is to use map.emplace_hint(map.find(key), ...) as recommended by libc++ maintainers. This avoids the linear scan but may reverse order for duplicates. Alternatively, using std::unordered_map<std::string_view, std::vector<int>> keeps the order but is a slightly larger refactor.

The same benchmark fixing the issue with the latter approach (unordered_map + vector):

N	Time (s)	Growth factor (vs previous input)
500	0.000040s	NA
5000	0.000066s	1.65x
50000	0.000681s	10.3x
500000	0.007084s	10.4x

I can submit a PR if a fix is worth pursuing.

Component(s)

C++

Can we improve performance by the following like the change in https://bugs.llvm.org/show_bug.cgi?id=16747#c2 ?

diff --git a/cpp/src/arrow/type.cc b/cpp/src/arrow/type.cc
index cba4a0ecd3..8959655aea 100644
--- a/cpp/src/arrow/type.cc
+++ b/cpp/src/arrow/type.cc
@@ -1331,7 +1331,8 @@ namespace {
 
 std::unordered_multimap<std::string_view, int> CreateNameToIndexMap(
     const FieldVector& fields) {
-  std::unordered_multimap<std::string_view, int> name_to_index;
+  std::unordered_multimap<std::string_view, int> name_to_index(fields.size());
+  name_to_index.max_load_factor(std::numeric_limits<float>::infinity());
   for (size_t i = 0; i < fields.size(); ++i) {
     name_to_index.emplace(fields[i]->name(), static_cast<int>(i));
   }

Can we improve performance by the following like the change in https://bugs.llvm.org/show_bug.cgi?id=16747#c2 ?

Probably yes, however I think the greatest improvement from that thread was done by changing map.insert({i % 4, i}) to map.insert(map.find(i % 4), {i % 4, i}). That will according to the libc++ maintainer insert elements at the beginning of equal ranges instead of linearly searching for the end of them.

Since we are using emplace we'd need emplace_hint to get the same effect:

 std::unordered_multimap<std::string_view, int> CreateNameToIndexMap(
     const FieldVector& fields) {
   std::unordered_multimap<std::string_view, int> name_to_index;
   for (size_t i = 0; i < fields.size(); ++i) {
-    name_to_index.emplace(fields[i]->name(), static_cast<int>(i));
+    name_to_index.emplace_hint(name_to_index.find(fields[i]->name()), fields[i]->name(), static_cast<int>(i));
   }
   return name_to_index;
 }

apacheGH-48977: [C++] Comment the hinted-insert motivation

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

Issue resolved by pull request 50970
#50970

@advitrocks9

@advitrocks9 Can you post here so that we assign this to you?

Fixed in #50970

Navigation Menu

Repository navigation

[C++] `arrow::schema` construction performance degrades to O(n^2) on libc++ for duplicate/unnamed fields #48977

Describe the bug, including details regarding any error messages, version, and platform.

Component(s)

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

[C++] arrow::schema construction performance degrades to O(n^2) on libc++ for duplicate/unnamed fields #48977

Description

Describe the bug, including details regarding any error messages, version, and platform.

Component(s)

Activity

kou commented on Jan 26, 2026

arvidjonasson commented on Jan 26, 2026

pitrou commented on Aug 25, 2026

pitrou commented on Aug 25, 2026

advitrocks9 commented on Aug 25, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

[C++] `arrow::schema` construction performance degrades to O(n^2) on libc++ for duplicate/unnamed fields #48977