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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
