Introduce a merge() function for folly::sorted_vector_map
authorMarc Celani <marccelani@fb.com>
Fri, 14 Mar 2014 02:52:09 +0000 (19:52 -0700)
committerDave Watson <davejwatson@fb.com>
Tue, 18 Mar 2014 17:02:24 +0000 (10:02 -0700)
commitb2d3a93b2a2bac05087d4294dc09d59cca64c90e
tree663f770adb9f5a5d034829dec7fa1964426d2ae9
parentf8e187f69922979c386394e6b39fcbab0c0d4ef3
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
folly/sorted_vector_types.h
folly/test/SortedVectorBenchmark.cpp [new file with mode: 0644]
folly/test/sorted_vector_test.cpp