From f4b6854addbfc718a9362cbe7a34e25c5cb182c3 Mon Sep 17 00:00:00 2001 From: Nicholas Ormrod Date: Thu, 8 May 2014 16:23:13 -0700 Subject: [PATCH] Housekeeping Summary: Remvoed old fbvector folly/test/stl_test files. Have kept StlVectorTest, since it is still impressive and useful. Facebook: n/a Test Plan: enable StlVectorTest in the TARGETS fbconfig -r folly && fbmake runtests Reviewed By: robbert@fb.com FB internal diff: D1320254 --- folly/test/stl_tests/Benchmark.cpp | 1032 ---------------------------- folly/test/stl_tests/OFBVector.h | 924 ------------------------- 2 files changed, 1956 deletions(-) delete mode 100644 folly/test/stl_tests/Benchmark.cpp delete mode 100644 folly/test/stl_tests/OFBVector.h diff --git a/folly/test/stl_tests/Benchmark.cpp b/folly/test/stl_tests/Benchmark.cpp deleted file mode 100644 index 909b24e6..00000000 --- a/folly/test/stl_tests/Benchmark.cpp +++ /dev/null @@ -1,1032 +0,0 @@ -/* - * Copyright 2014 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -// @author Nicholas Ormrod - -/****************************************************************************** - * - * This file is not perfect - benchmarking is a finicky process. - * - * TAKE THE NUMBERS YOU SEE TO MIND, NOT TO HEART - * - *****************************************************************************/ - -#include -#include "OFBVector.h" -#define FOLLY_BENCHMARK_USE_NS_IFOLLY -#include "folly/FBVector.h" - -#include -#include -#include -#include -#include -#include -#include - -#include - -using namespace std; - -static const bool enableColors = true; - -//============================================================================= -// use the timestamp counter for time measurements - -static inline -void clear_icache() {} // placeholder - -// return the CPU timestamp counter -static uint64_t readTSC() { - unsigned reslo, reshi; - - __asm__ __volatile__ ( - "xorl %%eax,%%eax \n cpuid \n" - ::: "%eax", "%ebx", "%ecx", "%edx"); - __asm__ __volatile__ ( - "rdtsc\n" - : "=a" (reslo), "=d" (reshi) ); - __asm__ __volatile__ ( - "xorl %%eax,%%eax \n cpuid \n" - ::: "%eax", "%ebx", "%ecx", "%edx"); - - return ((uint64_t)reshi << 32) | reslo; -} - -//============================================================================= -// Timer - -// The TIME* macros expand to a sequence of functions and classes whose aim -// is to run a benchmark function several times with different types and -// sizes. -// -// The first and last thing that TIME* expands to is a function declaration, -// through the DECL macro. The declared function is templated on the full -// vector type, its value_type, its allocator_type, and a number N. -// The first DECL is a forward declaration, and is followed by a -// semicolon. The second DECL ends the macro - a function body is to be -// supplied after the macro invocation. -// The declared function returns a uint64_t, which is assumed to be a time. -// -// The GETTER macro calls the DECL function repeatedly. It returns the -// minimum time taken to execute DECL. GETTER runs DECL between 2 and 100 -// times (it will not run the full 100 if the tests take a long time). -// -// The EVALUATOR macro calls the GETTER macro with each of std::vector, -// the original fbvector (folly::fbvector), and the new fbvector -// (Ifolly::fbvector). It runs all three twice, and then calls the -// pretty printer to display the results. Before calling the pretty -// printer, the EVALUATOR outputs the three message strings. -// -// The EXECUTOR macro calls the EVALUATOR with different values of N. -// It also defines the string message for N. -// -// The RUNNER macro defines a struct. That struct defines the testname -// string. The constructor calls the EXECUTOR with each test type, and -// also defines the test type string. -// The RUNNER class is also instantiated, so the constructor will be run -// before entering main(). -// - -#define TIME(str, types) TIME_I(str, types, (0)) -#define TIME_N(str, types) TIME_I(str, types, (0)(16)(64)(1024)(16384)(262144)) - -#define TIME_I(str, types, values) \ - TIME_II(str, BOOST_PP_CAT(t_, __LINE__), types, values) - -#define TIME_II(str, name, types, values) \ - DECL(name); \ - GETTER(name) \ - EVALUATOR(name) \ - EXECUTOR(name, values) \ - RUNNER(str, name, types) \ - DECL(name) - -#define DECL(name) \ - template \ - static inline uint64_t BOOST_PP_CAT(run_, name) () - -#define GETTER(name) \ - template \ - static uint64_t BOOST_PP_CAT(get_, name) () { \ - auto s = chrono::high_resolution_clock::now(); \ - uint64_t minticks = ~uint64_t(0); \ - int burst = 0; \ - for (; burst < 100; ++burst) { \ - auto t = BOOST_PP_CAT(run_, name) (); \ - minticks = min(minticks, t); \ - if (minticks * burst > 10000000) break; \ - } \ - auto e = chrono::high_resolution_clock::now(); \ - chrono::nanoseconds d(e - s); \ - return minticks; \ - return d.count() / burst; \ - } - -#define EVALUATOR(name) \ - template \ - void BOOST_PP_CAT(evaluate_, name) \ - ( string& part1, string& part2, string& part3 ) { \ - cout << setw(25) << left << part1 \ - << setw(4) << left << part2 \ - << setw(6) << right << part3; \ - part1.clear(); part2.clear(); part3.clear(); \ - auto v1 = BOOST_PP_CAT(get_, name) \ - , N> (); \ - auto v2 = BOOST_PP_CAT(get_, name) \ - < folly::fbvector, N> (); \ - auto v3 = BOOST_PP_CAT(get_, name) \ - < std:: vector, N> (); \ - auto v1b = BOOST_PP_CAT(get_, name) \ - , N> (); \ - auto v2b = BOOST_PP_CAT(get_, name) \ - < folly::fbvector, N> (); \ - auto v3b = BOOST_PP_CAT(get_, name) \ - < std:: vector, N> (); \ - prettyPrint(min(v1, v1b), min(v2, v2b), min(v3, v3b)); \ - cout << endl; \ - } - -#define EXECUTOR(name, values) \ - template \ - void BOOST_PP_CAT(execute_, name) ( string& part1, string& part2 ) { \ - BOOST_PP_SEQ_FOR_EACH(EVALUATE, name, values) \ - } - -#define EVALUATE(r, name, value) \ - { string part3(BOOST_PP_STRINGIZE(value)); \ - BOOST_PP_CAT(evaluate_, name) \ - ( part1, part2, part3 ); } - -#define RUNNER(str, name, types) \ - struct BOOST_PP_CAT(Runner_, name) { \ - BOOST_PP_CAT(Runner_, name) () { \ - string part1(str); \ - BOOST_PP_SEQ_FOR_EACH(EXECUTE, (part1, name), types) \ - } \ - } BOOST_PP_CAT(runner_, name); - -#define EXECUTE(r, pn, type) \ - { string part2(BOOST_PP_STRINGIZE(type)); \ - BOOST_PP_CAT(execute_, BOOST_PP_TUPLE_ELEM(2, 1, pn)) \ - \ - ( BOOST_PP_TUPLE_ELEM(2, 0, pn), part2 ); } - -//============================================================================= -// pretty printer - -// The pretty printer displays the times for each of the three vectors. -// The fastest time (or times, if there is a tie) is highlighted in green. -// Additionally, if the new fbvector (time v1) is not the fastest, then -// it is highlighted with red or blue. It is highlighted with blue only -// if it lost by a small margin (5 clock cycles or 2%, whichever is -// greater). - -void prettyPrint(uint64_t v1, uint64_t v2, uint64_t v3) { - // rdtsc takes some time to run; about 157 clock cycles - // if we see a smaller positive number, adjust readtsc - uint64_t readtsc_time = 157; - if (v1 != 0 && v1 < readtsc_time) readtsc_time = v1; - if (v2 != 0 && v2 < readtsc_time) readtsc_time = v2; - if (v3 != 0 && v3 < readtsc_time) readtsc_time = v3; - - if (v1 == 0) v1 = ~uint64_t(0); else v1 -= readtsc_time; - if (v2 == 0) v2 = ~uint64_t(0); else v2 -= readtsc_time; - if (v3 == 0) v3 = ~uint64_t(0); else v3 -= readtsc_time; - - auto least = min({ v1, v2, v3 }); - // a good time is less than 2% or 5 clock cycles slower - auto good = max(least + 5, (uint64_t)(least * 1.02)); - - string w("\x1b[1;;42m"); // green - string g("\x1b[1;;44m"); // blue - string b("\x1b[1;;41m"); // red - string e("\x1b[0m"); // reset - - if (!enableColors) { - w = b = e = ""; - } - - cout << " "; - - if (v1 == least) cout << w; - else if (v1 <= good) cout << g; - else cout << b; - cout << setw(13) << right; - if (v1 == ~uint64_t(0)) cout << "-"; else cout << v1; - cout << " " << e << " "; - - if (v2 == least) cout << w; - cout << setw(13) << right; - if (v2 == ~uint64_t(0)) cout << "-"; else cout << v2; - cout << " " << e << " "; - - if (v3 == least) cout << w; - cout << setw(13) << right; - if (v3 == ~uint64_t(0)) cout << "-"; else cout << v3; - cout << " " << e << " "; -} - -//============================================================================= -// table formatting - -// Much like the TIME macros, the Leader and Line struct/macros -// instantiate a class before main, and work is done inside the -// constructors. The Leader and Line struct print out pretty -// table boundaries and titles. - -uint64_t leader_elapsed() { - static auto t = chrono::high_resolution_clock::now(); - chrono::nanoseconds d(chrono::high_resolution_clock::now() - t); - return d.count() / 1000000000; -} - -struct Leader { - Leader() { - leader_elapsed(); - std::cout.imbue(std::locale("")); - - cout << endl; - cout << "========================================" - << "========================================" << endl; - cout << setw(35) << left << "Test"; - cout << setw(15) << right << "new fbvector "; - cout << setw(15) << right << "old fbvector "; - cout << setw(15) << right << "std::vector "; - cout << endl; - cout << "========================================" - << "========================================" << endl; - } - ~Leader() { - cout << endl; - cout << "========================================" - << "========================================" << endl; - cout << setw(78) << right << leader_elapsed() << " s" << endl; - } -} leader; - -struct Line { - explicit Line(string text) { - cout << "\n--- " << text << " ---" << endl; - } -}; -#define SECTION(str) Line BOOST_PP_CAT(l_, __LINE__) ( str ) - -//============================================================================= -// Test types - -typedef pair> T1; -typedef pair, std::allocator>> T2; - -uint64_t v1_T1 = 0, v2_T1 = 0, v3_T1 = 0; -uint64_t v1_T2 = 0, v2_T2 = 0, v3_T2 = 0; - -#define BASICS (T1)(T2) - -//============================================================================= -// prevent optimizing - -std::vector O_vi(10000000); - -void O(int i) { - O_vi.push_back(i); -} -template -void O(const V& v) { - int s = v.size(); - for (int i = 0; i < s; ++i) O(v[i]); -} - -//============================================================================= -// Benchmarks - -// #if 0 -//----------------------------------------------------------------------------- -//SECTION("Dev"); -//#undef BASICS -//#define BASICS (T1) - - -// #else - -//----------------------------------------------------------------------------- -SECTION("Essentials"); - -TIME_N("~Vector()", BASICS) { - Vector a(N); - O(a); - clear_icache(); auto b = readTSC(); - a.~Vector(); - auto e = readTSC(); - new (&a) Vector(); - O(a); - return e - b; -} - -TIME_N("a.clear()", BASICS) { - Vector a(N); - O(a); - clear_icache(); auto b = readTSC(); - a.clear(); - auto e = readTSC(); - O(a); - return e - b; -} - -TIME("Vector u", BASICS) { - clear_icache(); auto b = readTSC(); - Vector u; - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("Vector u(a)", BASICS) { - static const Vector a(N); - clear_icache(); auto b = readTSC(); - Vector u(a); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("Vector u(move(a))", BASICS) { - Vector a(N); - clear_icache(); auto b = readTSC(); - Vector u(move(a)); - auto e = readTSC(); - O(u); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Constructors"); - -TIME_N("Vector u(n)", BASICS) { - clear_icache(); auto b = readTSC(); - Vector u(N); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("Vector u(n, t)", BASICS) { - static const T t(1); - clear_icache(); auto b = readTSC(); - Vector u(N, t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("Vector u(first, last)", BASICS) { - static const deque d(N); - clear_icache(); auto b = readTSC(); - Vector u(d.begin(), d.end()); - auto e = readTSC(); - O(u); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Assignment"); - -TIME_N("a = b", BASICS) { - Vector a(N); - static const Vector c(N/2 + 10); - O(a); - clear_icache(); auto b = readTSC(); - a = c; - auto e = readTSC(); - O(a); - return e - b; -} - -TIME_N("a = move(b)", BASICS) { - Vector a(N); - Vector c(N/2 + 10); - O(a); - O(c); - clear_icache(); auto b = readTSC(); - a = move(c); - auto e = readTSC(); - O(a); - O(c); - return e - b; -} - -TIME_N("a = destructive_move(b)", BASICS) { - Vector a(N); - Vector c(N/2 + 10); - O(a); - O(c); - clear_icache(); auto b = readTSC(); - a = move(c); - c.clear(); - auto e = readTSC(); - O(a); - O(c); - return e - b; -} - -TIME_N("a.assign(N, t)", BASICS) { - Vector a(N/2 + 10); - const T t(1); - O(a); - clear_icache(); auto b = readTSC(); - a.assign(N, t); - auto e = readTSC(); - O(a); - return e - b; -} - -TIME_N("a.assign(first, last)", BASICS) { - static const deque d(N); - Vector a(N/2 + 10); - clear_icache(); auto b = readTSC(); - a.assign(d.begin(), d.end()); - auto e = readTSC(); - O(a); - return e - b; -} - -TIME_N("a.swap(b)", BASICS) { - Vector a(N/2 + 10); - Vector c(N); - O(a); - O(c); - clear_icache(); auto b = readTSC(); - a.swap(c); - auto e = readTSC(); - O(a); - O(c); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Iterators"); - -TIME("a.begin()", BASICS) { - static Vector a(1); - clear_icache(); auto b = readTSC(); - auto r = a.begin(); - auto e = readTSC(); - O(*r); - return e - b; -} - -TIME("a.cbegin()", BASICS) { - static Vector a(1); - clear_icache(); auto b = readTSC(); - auto r = a.cbegin(); - auto e = readTSC(); - O(*r); - return e - b; -} - -TIME("a.rbegin()", BASICS) { - static Vector a(1); - clear_icache(); auto b = readTSC(); - auto r = a.rbegin(); - auto e = readTSC(); - O(*r); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Capacity"); - -TIME_N("a.size()", BASICS) { - static const Vector a(N); - clear_icache(); auto b = readTSC(); - int n = a.size(); - auto e = readTSC(); - O(n); - return e - b; -} - -TIME("a.max_size()", BASICS) { - static Vector a; - clear_icache(); auto b = readTSC(); - int n = a.max_size(); - auto e = readTSC(); - O(n); - return e - b; -} - -TIME_N("a.capacity()", BASICS) { - static const Vector a(N); - clear_icache(); auto b = readTSC(); - int n = a.capacity(); - auto e = readTSC(); - O(n); - return e - b; -} - -TIME_N("a.empty()", BASICS) { - static const Vector a(N); - clear_icache(); auto b = readTSC(); - int n = a.empty(); - auto e = readTSC(); - O(n); - return e - b; -} - -TIME_N("reserve(n)", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.reserve(N); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("resize(n)", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.resize(N); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("resize(n, t)", BASICS) { - static const T t(1); - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.resize(N, t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("staged reserve", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.reserve(500); - u.reserve(1000); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("staged resize", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.resize(500); - u.resize(1000); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("resize then reserve", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.resize(500); - u.reserve(1000); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("shrink", BASICS) { - Vector u; - O(u); - u.resize(500); - u.reserve(1000); - clear_icache(); auto b = readTSC(); - u.shrink_to_fit(); - auto e = readTSC(); - O(u); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Access"); - -TIME("operator[]", BASICS) { - static const Vector a(10); - clear_icache(); auto b = readTSC(); - const auto& v = a[8]; - auto e = readTSC(); - O(v); - return e - b; -} - -TIME("at()", BASICS) { - static const Vector a(10); - clear_icache(); auto b = readTSC(); - const auto& v = a.at(8); - auto e = readTSC(); - O(v); - return e - b; -} - -TIME("front()", BASICS) { - static const Vector a(10); - clear_icache(); auto b = readTSC(); - const auto& v = a.front(); - auto e = readTSC(); - O(v); - return e - b; -} - -TIME("back()", BASICS) { - static const Vector a(10); - clear_icache(); auto b = readTSC(); - const auto& v = a.back(); - auto e = readTSC(); - O(v); - return e - b; -} - -TIME("data()", BASICS) { - static const Vector a(10); - clear_icache(); auto b = readTSC(); - const auto& v = a.data(); - auto e = readTSC(); - O(*v); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Append"); - -TIME("reserved emplace", BASICS) { - Vector u; - u.reserve(1); - O(u); - clear_icache(); auto b = readTSC(); - u.emplace_back(0); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("full emplace", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.emplace_back(0); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("reserved push_back", BASICS) { - static T t(0); - Vector u; - u.reserve(1); - O(u); - clear_icache(); auto b = readTSC(); - u.push_back(t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("full push_back", BASICS) { - static T t(0); - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.push_back(t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("reserved push_back&&", BASICS) { - T t(0); - Vector u; - u.reserve(1); - O(u); - clear_icache(); auto b = readTSC(); - u.push_back(std::move(t)); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("full push_back&&", BASICS) { - T t(0); - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.push_back(std::move(t)); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("reserved push emplace", BASICS) { - Vector u; - u.reserve(1); - O(u); - clear_icache(); auto b = readTSC(); - u.push_back(T(0)); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("full push emplace", BASICS) { - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - u.push_back(T(0)); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("bulk append", BASICS) { - static deque d(N); - Vector u(N/2 + 10); - O(u); - clear_icache(); auto b = readTSC(); - u.insert(u.end(), d.begin(), d.end()); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("erase end", BASICS) { - Vector u(N); - O(u); - auto it = u.begin(); - it += u.size() / 2; - if (it != u.end()) O(*it); - clear_icache(); auto b = readTSC(); - u.erase(it, u.end()); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("pop_back", BASICS) { - Vector u(1); - O(u); - clear_icache(); auto b = readTSC(); - u.pop_back(); - auto e = readTSC(); - O(u); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Insert/Erase - Bad Ops"); - -TIME("insert", BASICS) { - Vector u(100); - T t(1); - auto it = u.begin(); - it += 50; - O(u); - O(*it); - O(t); - clear_icache(); auto b = readTSC(); - u.insert(it, t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("insert&&", BASICS) { - Vector u(100); - T t(1); - auto it = u.begin(); - it += 50; - O(u); - O(*it); - O(t); - clear_icache(); auto b = readTSC(); - u.insert(it, std::move(t)); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("insert n few", BASICS) { - Vector u(100); - T t(1); - auto it = u.begin(); - it += 50; - O(u); - O(*it); - O(t); - clear_icache(); auto b = readTSC(); - u.insert(it, 10, t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("insert n many", BASICS) { - Vector u(100); - T t(1); - auto it = u.begin(); - it += 50; - O(u); - O(*it); - O(t); - clear_icache(); auto b = readTSC(); - u.insert(it, 200, t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("iterator insert few", BASICS) { - static deque d(10); - Vector u(100); - T t(1); - auto it = u.begin(); - it += 50; - O(u); - O(*it); - O(t); - clear_icache(); auto b = readTSC(); - u.insert(it, d.begin(), d.end()); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("iterator insert many", BASICS) { - static deque d(200); - Vector u(100); - T t(1); - auto it = u.begin(); - it += 50; - O(u); - O(*it); - O(t); - clear_icache(); auto b = readTSC(); - u.insert(it, d.begin(), d.end()); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("erase", BASICS) { - Vector u(100); - O(u); - auto it = u.begin(); - it += 50; - O(*it); - clear_icache(); auto b = readTSC(); - u.erase(it); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("erase many", BASICS) { - Vector u(100); - O(u); - auto it1 = u.begin(); - it1 += 33; - O(*it1); - auto it2 = u.begin(); - it2 += 66; - O(*it2); - clear_icache(); auto b = readTSC(); - u.erase(it1, it2); - auto e = readTSC(); - O(u); - return e - b; -} - -//----------------------------------------------------------------------------- -SECTION("Large Tests"); - -TIME_N("reserved bulk push_back", BASICS) { - Vector u; - u.reserve(N); - T t(0); - O(u); - clear_icache(); auto b = readTSC(); - for (int i = 0; i < N; ++i) u.emplace_back(t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("reserved bulk emplace", BASICS) { - Vector u; - u.reserve(N); - O(u); - clear_icache(); auto b = readTSC(); - for (int i = 0; i < N; ++i) u.emplace_back(0); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("populate", BASICS) { - static T t(0); - Vector u; - O(u); - clear_icache(); auto b = readTSC(); - for (int i = 0; i < N; ++i) u.push_back(t); - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("jigsaw growth", BASICS) { - int sizes[] = - { 1, 5, 2, 80, 17, 8, 9, 8, 140, 130, 1000, 130, 10000, 0, 8000, 2000 }; - clear_icache(); auto b = readTSC(); - Vector u; - for (auto s : sizes) { - if (s < u.size()) { - int toAdd = u.size() - s; - for (int i = 0; i < toAdd / 2; ++i) u.emplace_back(0); - u.insert(u.end(), (toAdd + 1) / 2, T(1)); - } else { - int toRm = u.size() - s; - for (int i = 0; i < toRm / 2; ++i) u.pop_back(); - auto it = u.begin(); - std::advance(it, s); - if (it < u.end()) u.erase(it, u.end()); - } - } - auto e = readTSC(); - O(u); - return e - b; -} - -TIME("random access and modify", (T1)) { - static const int n = 1024 * 1024 * 16; - Vector u(n); - O(u); - clear_icache(); auto b = readTSC(); - int j = 7; - for (int i = 0; i < 100000; ++i) { - j = (j * 2 + j) ^ 0xdeadbeef; - j = j & (n - 1); - u[j] = i; - u.at(n - j) = -i; - } - auto e = readTSC(); - O(u); - return e - b; -} - -TIME_N("iterate", (T1)) { - static Vector u(N); - O(u); - clear_icache(); auto b = readTSC(); - int acc = 0; - for (auto& e : u) { - acc += e; - e++; - } - auto e = readTSC(); - O(acc); - O(u); - return e - b; -} - -TIME("emplace massive", BASICS) { - clear_icache(); auto b = readTSC(); - Vector u; - for (int i = 0; i < 10000000; ++i) { - u.emplace_back(0); - } - auto e = readTSC(); - O(u); - return e - b; -} - -// #endif - -//============================================================================= - -int main() { - return 0; -} - diff --git a/folly/test/stl_tests/OFBVector.h b/folly/test/stl_tests/OFBVector.h deleted file mode 100644 index 802e7f2e..00000000 --- a/folly/test/stl_tests/OFBVector.h +++ /dev/null @@ -1,924 +0,0 @@ -/* - * Copyright 2014 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -// Andrei Alexandrescu (aalexandre) - -/** - * Vector type. Drop-in replacement for std::vector featuring - * significantly faster primitives, see e.g. benchmark results at - * https:*phabricator.fb.com/D235852. - * - * In order for a type to be used with fbvector, it must be - * relocatable, see Traits.h. - * - * For user-defined types you must specialize templates - * appropriately. Consult Traits.h for ways to do so and for a handy - * family of macros FOLLY_ASSUME_FBVECTOR_COMPATIBLE*. - * - * For more information and documentation see folly/docs/FBVector.md - */ - -#ifndef FOLLY_FBVECTOR_H_ -#define FOLLY_FBVECTOR_H_ - -#include "folly/Foreach.h" -#include "folly/Malloc.h" -#include "folly/Traits.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include - -namespace folly { -/** - * Forward declaration for use by FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2, - * see folly/Traits.h. - */ -template > -class fbvector; -} - -// You can define an fbvector of fbvectors. -FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2(folly::fbvector); - -namespace folly { -namespace fbvector_detail { - -/** - * isForwardIterator::value yields true if T is a forward iterator - * or better, and false otherwise. - */ -template struct isForwardIterator { - enum { value = boost::is_convertible< - typename std::iterator_traits::iterator_category, - std::forward_iterator_tag>::value - }; -}; - -/** - * Destroys all elements in the range [b, e). If the type referred to - * by the iterators has a trivial destructor, does nothing. - */ -template -void destroyRange(It b, It e) { - typedef typename boost::remove_reference::type T; - if (boost::has_trivial_destructor::value) return; - for (; b != e; ++b) { - (*b).~T(); - } -} - -/** - * Moves the "interesting" part of value to the uninitialized memory - * at address addr, and leaves value in a destroyable state. - */ - -template -typename boost::enable_if_c< - boost::has_trivial_assign::value ->::type -uninitialized_destructive_move(T& value, T* addr) { - // Just assign the thing; this is most efficient - *addr = value; -} - -template -typename boost::enable_if_c< - !boost::has_trivial_assign::value && - boost::has_nothrow_constructor::value ->::type -uninitialized_destructive_move(T& value, T* addr) { - // Cheap default constructor - move and reinitialize - memcpy(addr, &value, sizeof(T)); - new(&value) T; -} - -template -typename std::enable_if< - !boost::has_trivial_assign::value && - !boost::has_nothrow_constructor::value ->::type -uninitialized_destructive_move(T& value, T* addr) { - // User defined move construction. - - // TODO: we should probably prefer this over the above memcpy() - // version when the type has a user-defined move constructor. We - // don't right now because 4.6 doesn't implement - // std::is_move_constructible<> yet. - new (addr) T(std::move(value)); -} - -/** - * Fills n objects of type T starting at address b with T's default - * value. If the operation throws, destroys all objects constructed so - * far and calls free(b). - */ -template -void uninitializedFillDefaultOrFree(T * b, size_t n) { - if (boost::is_arithmetic::value || boost::is_pointer::value) { - if (n <= 16384 / sizeof(T)) { - memset(b, 0, n * sizeof(T)); - } else { - goto duff_fill; - } - } else if (boost::has_nothrow_constructor::value) { - duff_fill: - auto i = b; - auto const e1 = b + (n & ~size_t(7)); - for (; i != e1; i += 8) { - new(i) T(); - new(i + 1) T(); - new(i + 2) T(); - new(i + 3) T(); - new(i + 4) T(); - new(i + 5) T(); - new(i + 6) T(); - new(i + 7) T(); - } - for (auto const e = b + n; i != e; ++i) { - new(i) T(); - } - } else { - // Conservative approach - auto i = b; - try { - for (auto const e = b + n; i != e; ++i) { - new(i) T; - } - } catch (...) { - destroyRange(b, i); - free(b); - throw; - } - } -} - -/** - * Fills n objects of type T starting at address b with value. If the - * operation throws, destroys all objects constructed so far and calls - * free(b). - */ -template -void uninitializedFillOrFree(T * b, size_t n, const T& value) { - auto const e = b + n; - if (FOLLY_IS_TRIVIALLY_COPYABLE(T)) { - auto i = b; - auto const e1 = b + (n & ~size_t(7)); - for (; i != e1; i += 8) { - new(i) T(value); - new(i + 1) T(value); - new(i + 2) T(value); - new(i + 3) T(value); - new(i + 4) T(value); - new(i + 5) T(value); - new(i + 6) T(value); - new(i + 7) T(value); - } - for (; i != e; ++i) { - new(i) T(value); - } - } else { - // Conservative approach - auto i = b; - try { - for (; i != e; ++i) { - new(i) T(value); - } - } catch (...) { - destroyRange(b, i); - free(b); - throw; - } - } -} -} // namespace fbvector_detail - -/** - * This is the std::vector replacement. For conformity, fbvector takes - * the same template parameters, but it doesn't use the - * allocator. Instead, it uses malloc, and when present, jemalloc's - * extensions. - */ -template -class fbvector : private boost::totally_ordered > { - bool isSane() const { - return - begin() <= end() && - empty() == (size() == 0) && - empty() == (begin() == end()) && - size() <= max_size() && - capacity() <= max_size() && - size() <= capacity() && - - // Either we have no capacity or our pointers should make sense: - ((!b_ && !e_ && !z_) || (b_ != z_ && e_ <= z_)); - } - - struct Invariant { -#ifndef NDEBUG - explicit Invariant(const fbvector& s) : s_(s) { - assert(s_.isSane()); - } - ~Invariant() { - assert(s_.isSane()); - } - private: - const fbvector& s_; -#else - explicit Invariant(const fbvector&) {} -#endif - Invariant& operator=(const Invariant&); - }; - -public: - -// types: - typedef T value_type; - typedef value_type& reference; - typedef const value_type& const_reference; - typedef T* iterator; - typedef const T* const_iterator; - typedef size_t size_type; - typedef ssize_t difference_type; - // typedef typename allocator_traits::pointer pointer; - // typedef typename allocator_traits::const_pointer const_pointer; - typedef Allocator allocator_type; - typedef typename Allocator::pointer pointer; - typedef typename Allocator::const_pointer const_pointer; - typedef std::reverse_iterator reverse_iterator; - typedef std::reverse_iterator const_reverse_iterator; - -// 23.3.6.1 construct/copy/destroy: - fbvector() : b_(nullptr), e_(nullptr), z_(nullptr) {} - - explicit fbvector(const Allocator&) { - new(this) fbvector; - } - - explicit fbvector(const size_type n) { - if (n == 0) { - b_ = e_ = z_ = 0; - return; - } - - auto const nBytes = goodMallocSize(n * sizeof(T)); - b_ = static_cast(checkedMalloc(nBytes)); - fbvector_detail::uninitializedFillDefaultOrFree(b_, n); - e_ = b_ + n; - z_ = b_ + nBytes / sizeof(T); - } - - fbvector(const size_type n, const T& value) { - if (!n) { - b_ = e_ = z_ = 0; - return; - } - - auto const nBytes = goodMallocSize(n * sizeof(T)); - b_ = static_cast(checkedMalloc(nBytes)); - fbvector_detail::uninitializedFillOrFree(b_, n, value); - e_ = b_ + n; - z_ = b_ + nBytes / sizeof(T); - } - - fbvector(const size_type n, const T& value, const Allocator&) { - new(this) fbvector(n, value); - } - - template - fbvector(InputIteratorOrNum first, InputIteratorOrNum last) { - new(this) fbvector; - assign(first, last); - } - - template - fbvector(InputIterator first, InputIterator last, - const Allocator&) { - new(this) fbvector(first, last); - } - - fbvector(const fbvector& rhs) { - new(this) fbvector(rhs.begin(), rhs.end()); - } - fbvector(const fbvector& rhs, const Allocator&) { - new(this) fbvector(rhs); - } - - fbvector(fbvector&& o, const Allocator& = Allocator()) - : b_(o.b_) - , e_(o.e_) - , z_(o.z_) - { - o.b_ = o.e_ = o.z_ = 0; - } - - fbvector(std::initializer_list il, const Allocator& = Allocator()) { - new(this) fbvector(il.begin(), il.end()); - } - - ~fbvector() { - // fbvector only works with relocatable objects. We insert this - // static check inside the destructor because pretty much any - // instantiation of fbvector will generate the destructor (and - // therefore refuse compilation if the assertion fails). To see - // how you can enable IsRelocatable for your type, refer to the - // definition of IsRelocatable in Traits.h. - BOOST_STATIC_ASSERT(IsRelocatable::value); - if (!b_) return; - fbvector_detail::destroyRange(b_, e_); - free(b_); - } - fbvector& operator=(const fbvector& rhs) { - assign(rhs.begin(), rhs.end()); - return *this; - } - - fbvector& operator=(fbvector&& v) { - clear(); - swap(v); - return *this; - } - - fbvector& operator=(std::initializer_list il) { - assign(il.begin(), il.end()); - return *this; - } - - bool operator==(const fbvector& rhs) const { - return size() == rhs.size() && std::equal(begin(), end(), rhs.begin()); - } - - bool operator<(const fbvector& rhs) const { - return std::lexicographical_compare(begin(), end(), - rhs.begin(), rhs.end()); - } - -private: - template - void assignImpl(InputIterator first, InputIterator last, boost::false_type) { - // Pair of iterators - if (fbvector_detail::isForwardIterator::value) { - auto const oldSize = size(); - auto const newSize = std::distance(first, last); - - if (static_cast(oldSize) >= newSize) { - // No reallocation, nice - auto const newEnd = std::copy(first, last, b_); - fbvector_detail::destroyRange(newEnd, e_); - e_ = newEnd; - return; - } - - // Must reallocate - just do it on the side - auto const nBytes = goodMallocSize(newSize * sizeof(T)); - auto const b = static_cast(checkedMalloc(nBytes)); - std::uninitialized_copy(first, last, b); - this->fbvector::~fbvector(); - b_ = b; - e_ = b + newSize; - z_ = b_ + nBytes / sizeof(T); - } else { - // Input iterator sucks - FOR_EACH (i, *this) { - if (first == last) { - fbvector_detail::destroyRange(i, e_); - e_ = i; - return; - } - *i = *first; - ++first; - } - FOR_EACH_RANGE (i, first, last) { - push_back(*i); - } - } - } - - void assignImpl(const size_type newSize, const T value, boost::true_type) { - // Arithmetic type, forward back to unambiguous definition - assign(newSize, value); - } - -public: - // Classic ambiguity (and a lot of unnecessary complexity) in - // std::vector: assign(10, 20) for vector means "assign 10 - // elements all having the value 20" but is intercepted by the - // two-iterators overload assign(first, last). So we need to - // disambiguate here. There is no pretty solution. We use here - // overloading based on is_arithmetic. Method insert has the same - // issue (and the same solution in this implementation). - template - void assign(InputIteratorOrNum first, InputIteratorOrNum last) { - assignImpl(first, last, boost::is_arithmetic()); - } - - void assign(const size_type newSize, const T& value) { - if (b_ <= &value && &value < e_) { - // Need to check for aliased assign, sigh - return assign(newSize, T(value)); - } - - auto const oldSize = size(); - if (oldSize >= newSize) { - // No reallocation, nice - auto const newEnd = b_ + newSize; - fbvector_detail::destroyRange(newEnd, e_); - e_ = newEnd; - return; - } - - // Need to reallocate - if (reserve_in_place(newSize)) { - // Careful here, fill and uninitialized_fill may throw. The - // latter is transactional, so no need to worry about a - // buffer partially filled in case of exception. - std::fill(b_, e_, value); - auto const newEnd = b_ + newSize; - std::uninitialized_fill(e_, newEnd, value); - e_ = newEnd; - return; - } - - // Cannot expand or jemalloc not present at all; must just - // allocate a new chunk and discard the old one. This is - // tantamount with creating a new fbvector altogether. This won't - // recurse infinitely; the constructor implements its own. - fbvector temp(newSize, value); - temp.swap(*this); - } - - void assign(std::initializer_list il) { - assign(il.begin(), il.end()); - } - - allocator_type get_allocator() const { - // whatevs - return allocator_type(); - } - -// iterators: - iterator begin() { - return b_; - } - const_iterator begin() const { - return b_; - } - iterator end() { - return e_; - } - const_iterator end() const { - return e_; - } - reverse_iterator rbegin() { - return reverse_iterator(end()); - } - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } - reverse_iterator rend() { - return reverse_iterator(begin()); - } - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } - const_iterator cbegin() const { - return b_; - } - const_iterator cend() const { - return e_; - } - -// 23.3.6.2 capacity: - size_type size() const { - return e_ - b_; - } - - size_type max_size() { - // good luck gettin' there - return ~size_type(0); - } - - void resize(const size_type sz) { - auto const oldSize = size(); - if (sz <= oldSize) { - auto const newEnd = b_ + sz; - fbvector_detail::destroyRange(newEnd, e_); - e_ = newEnd; - } else { - // Must expand - reserve(sz); - auto newEnd = b_ + sz; - std::uninitialized_fill(e_, newEnd, T()); - e_ = newEnd; - } - } - - void resize(const size_type sz, const T& c) { - auto const oldSize = size(); - if (sz <= oldSize) { - auto const newEnd = b_ + sz; - fbvector_detail::destroyRange(newEnd, e_); - e_ = newEnd; - } else { - // Must expand - reserve(sz); - auto newEnd = b_ + sz; - std::uninitialized_fill(e_, newEnd, c); - e_ = newEnd; - } - } - - size_type capacity() const { - return z_ - b_; - } - bool empty() const { - return b_ == e_; - } - -private: - bool reserve_in_place(const size_type n) { - auto const crtCapacity = capacity(); - if (n <= crtCapacity) return true; - if (!rallocm) return false; - - // using jemalloc's API. Don't forget that jemalloc can never grow - // in place blocks smaller than 4096 bytes. - auto const crtCapacityBytes = crtCapacity * sizeof(T); - if (crtCapacityBytes < jemallocMinInPlaceExpandable) return false; - - auto const newCapacityBytes = goodMallocSize(n * sizeof(T)); - void* p = b_; - if (rallocm(&p, nullptr, newCapacityBytes, 0, ALLOCM_NO_MOVE) - != ALLOCM_SUCCESS) { - return false; - } - - // Managed to expand in place, reflect that in z_ - assert(b_ == p); - z_ = b_ + newCapacityBytes / sizeof(T); - return true; - } - - void reserve_with_move(const size_type n) { - // Here we can be sure we'll need to do a full reallocation - auto const crtCapacity = capacity(); - assert(crtCapacity < n); // reserve_in_place should have taken - // care of this - auto const newCapacityBytes = goodMallocSize(n * sizeof(T)); - auto b = static_cast(checkedMalloc(newCapacityBytes)); - auto const oldSize = size(); - memcpy(b, b_, oldSize * sizeof(T)); - // Done with the old chunk. Free but don't call destructors! - free(b_); - b_ = b; - e_ = b_ + oldSize; - z_ = b_ + newCapacityBytes / sizeof(T); - // done with the old chunk - } - -public: - void reserve(const size_type n) { - if (reserve_in_place(n)) return; - reserve_with_move(n); - } - - void shrink_to_fit() { - if (!rallocm) return; - - // using jemalloc's API. Don't forget that jemalloc can never - // shrink in place blocks smaller than 4096 bytes. - void* p = b_; - auto const crtCapacityBytes = capacity() * sizeof(T); - auto const newCapacityBytes = goodMallocSize(size() * sizeof(T)); - if (crtCapacityBytes >= jemallocMinInPlaceExpandable && - rallocm(&p, nullptr, newCapacityBytes, 0, ALLOCM_NO_MOVE) - == ALLOCM_SUCCESS) { - // Celebrate - z_ = b_ + newCapacityBytes / sizeof(T); - } - } - -// element access - reference operator[](size_type n) { - assert(n < size()); - return b_[n]; - } - const_reference operator[](size_type n) const { - assert(n < size()); - return b_[n]; - } - const_reference at(size_type n) const { - if (n > size()) { - throw std::out_of_range("fbvector: index is greater than size."); - } - return (*this)[n]; - } - reference at(size_type n) { - auto const& cThis = *this; - return const_cast(cThis.at(n)); - } - reference front() { - assert(!empty()); - return *b_; - } - const_reference front() const { - assert(!empty()); - return *b_; - } - reference back() { - assert(!empty()); - return e_[-1]; - } - const_reference back() const { - assert(!empty()); - return e_[-1]; - } - -// 23.3.6.3 data access - T* data() { - return b_; - } - const T* data() const { - return b_; - } - -private: - size_t computePushBackCapacity() const { - return empty() ? std::max(64 / sizeof(T), size_t(1)) - : capacity() < jemallocMinInPlaceExpandable ? capacity() * 2 - : (capacity() * 3) / 2; - } - -public: -// 23.3.6.4 modifiers: - template - void emplace_back(Args&&... args) { - if (e_ == z_) { - if (!reserve_in_place(size() + 1)) { - reserve_with_move(computePushBackCapacity()); - } - } - new (e_) T(std::forward(args)...); - ++e_; - } - - void push_back(T x) { - if (e_ == z_) { - if (!reserve_in_place(size() + 1)) { - reserve_with_move(computePushBackCapacity()); - } - } - fbvector_detail::uninitialized_destructive_move(x, e_); - ++e_; - } - -private: - bool expand() { - if (!rallocm) return false; - auto const capBytes = capacity() * sizeof(T); - if (capBytes < jemallocMinInPlaceExpandable) return false; - auto const newCapBytes = goodMallocSize(capBytes + sizeof(T)); - void * bv = b_; - if (rallocm(&bv, nullptr, newCapBytes, 0, ALLOCM_NO_MOVE) != ALLOCM_SUCCESS) { - return false; - } - // Managed to expand in place - assert(bv == b_); // nothing moved - z_ = b_ + newCapBytes / sizeof(T); - assert(capacity() > capBytes / sizeof(T)); - return true; - } - -public: - void pop_back() { - assert(!empty()); - --e_; - if (!boost::has_trivial_destructor::value) { - e_->T::~T(); - } - } - // template - // iterator emplace(const_iterator position, Args&&... args); - - iterator insert(const_iterator position, T x) { - size_t newSize; // intentionally uninitialized - if (e_ == z_ && !reserve_in_place(newSize = size() + 1)) { - // Can't reserve in place, make a copy - auto const offset = position - cbegin(); - fbvector tmp; - tmp.reserve(newSize); - memcpy(tmp.b_, b_, offset * sizeof(T)); - fbvector_detail::uninitialized_destructive_move( - x, - tmp.b_ + offset); - memcpy(tmp.b_ + offset + 1, b_ + offset, (size() - offset) * sizeof(T)); - // Brutally reassign this to refer to tmp's guts - free(b_); - b_ = tmp.b_; - e_ = b_ + newSize; - z_ = tmp.z_; - // get rid of tmp's guts - new(&tmp) fbvector; - return begin() + offset; - } - // Here we have enough room - memmove(const_cast(&*position) + 1, - const_cast(&*position), - sizeof(T) * (e_ - position)); - fbvector_detail::uninitialized_destructive_move( - x, - const_cast(&*position)); - ++e_; - return const_cast(position); - } - - iterator insert(const_iterator position, const size_type n, const T& x) { - if (e_ + n >= z_) { - if (b_ <= &x && &x < e_) { - // Ew, aliased insert - auto copy = x; - return insert(position, n, copy); - } - auto const m = position - b_; - reserve(size() + n); - position = b_ + m; - } - memmove(const_cast(position) + n, - position, - sizeof(T) * (e_ - position)); - if (FOLLY_IS_TRIVIALLY_COPYABLE(T)) { - std::uninitialized_fill(const_cast(position), - const_cast(position) + n, - x); - } else { - try { - std::uninitialized_fill(const_cast(position), - const_cast(position) + n, - x); - } catch (...) { - // Oops, put things back where they were - memmove(const_cast(position), - position + n, - sizeof(T) * (e_ - position)); - throw; - } - } - e_ += n; - return const_cast(position); - } - -private: - template - iterator insertImpl(const_iterator position, - InputIterator first, InputIterator last, - boost::false_type) { - // Pair of iterators - if (fbvector_detail::isForwardIterator::value) { - // Can compute distance - auto const n = std::distance(first, last); - if (e_ + n >= z_) { - auto const m = position - b_; - reserve(size() + n); - position = b_ + m; - } - memmove(const_cast(position) + n, - position, - sizeof(T) * (e_ - position)); - try { - std::uninitialized_copy(first, last, - const_cast(position)); - } catch (...) { - // Oops, put things back where they were - memmove(const_cast(position), - position + n, - sizeof(T) * (e_ - position)); - throw; - } - e_ += n; - return const_cast(position); - } else { - // Cannot compute distance, crappy approach - // TODO: OPTIMIZE - fbvector result(cbegin(), position); - auto const offset = result.size(); - FOR_EACH_RANGE (i, first, last) { - result.push_back(*i); - } - result.insert(result.end(), position, cend()); - result.swap(*this); - return begin() + offset; - } - } - - iterator insertImpl(const_iterator position, - const size_type count, const T value, boost::true_type) { - // Forward back to unambiguous function - return insert(position, count, value); - } - -public: - template - iterator insert(const_iterator position, InputIteratorOrNum first, - InputIteratorOrNum last) { - return insertImpl(position, first, last, - boost::is_arithmetic()); - } - - iterator insert(const_iterator position, std::initializer_list il) { - return insert(position, il.begin(), il.end()); - } - - iterator erase(const_iterator position) { - if (position == e_) return e_; - auto p = const_cast(position); - (*p).T::~T(); - memmove(p, p + 1, sizeof(T) * (e_ - p - 1)); - --e_; - return p; - } - - iterator erase(const_iterator first, const_iterator last) { - assert(first <= last); - auto p1 = const_cast(first); - auto p2 = const_cast(last); - fbvector_detail::destroyRange(p1, p2); - memmove(p1, last, sizeof(T) * (e_ - last)); - e_ -= last - first; - return p1; - } - - void swap(fbvector& rhs) { - std::swap(b_, rhs.b_); - std::swap(e_, rhs.e_); - std::swap(z_, rhs.z_); - } - - void clear() { - fbvector_detail::destroyRange(b_, e_); - e_ = b_; - } - -private: - // Data - T *b_, *e_, *z_; -}; - -template -bool operator!=(const fbvector& lhs, - const fbvector& rhs) { - return !(lhs == rhs); -} - -template -void swap(fbvector& lhs, fbvector& rhs) { - lhs.swap(rhs); -} - -/** - * Resizes *v to exactly n elements. May reallocate the vector to a - * smaller buffer if too much space will be left unused. - */ -template -static void compactResize(folly::fbvector * v, size_t size) { - auto const oldCap = v->capacity(); - if (oldCap > size + 1024 && size < oldCap * 0.3) { - // Too much slack memory, reallocate a smaller buffer - auto const oldSize = v->size(); - if (size <= oldSize) { - // Shrink - folly::fbvector(v->begin(), v->begin() + size).swap(*v); - } else { - // Expand - folly::fbvector temp; - temp.reserve(size); - copy(v->begin(), v->end(), back_inserter(temp)); - temp.resize(size); - temp.swap(*v); - } - } else { - // Nolo contendere - v->resize(size); - } -} - -} // namespace folly - -#endif // FOLLY_FBVECTOR_H_ -- 2.34.1