Introduce a merge() function for folly::sorted_vector_map
Summary:
Feed spends a non trivial amount of time merging two sorted_vector_maps. Writing code for this efficiently is actually a little tricky, and its much easier to maintain the simpler code. This adds merge() to folly so that its easy for feed and fast. Benchmarks with large input sizes show this is a gigantic win (moving from O(n^2) to O(n).
Test Plan: unit tests, benchmark
Reviewed By: delong.j@fb.com
FB internal diff:
D1221725
@override-unit-failures