folly.git
11 years agoallow to dequeue the first IOBuf in an IOBufQueue
Alessandro Salvatori [Sat, 9 Mar 2013 02:16:59 +0000 (18:16 -0800)]
allow to dequeue the first IOBuf in an IOBufQueue

Summary: allow to dequeue the first IOBuf in an IOBufQueue

Test Plan: throughly tested with some dependent code in proxygen

Reviewed By: tudorb@fb.com

FB internal diff: D732484

11 years agoUse aligned loads for Range::find_first_of
Mike Curtiss [Fri, 22 Feb 2013 22:28:05 +0000 (14:28 -0800)]
Use aligned loads for Range::find_first_of

Summary:
Aligned loads are faster on some architectures. Let's refactor
qfind_first_of so that it uses aligned loads when possible.

Also modify the benchmarks to account for begin/end-of-string
logic.

Test Plan:
Tests pass. Updated benchmarks.  Generally seeing a 5-20%
speed-up, depending on the situation.

Reviewed By: philipp@fb.com

FB internal diff: D720369

11 years agoShort-circuit operator== based on size()
Tom Jackson [Wed, 13 Mar 2013 22:44:59 +0000 (15:44 -0700)]
Short-circuit operator== based on size()

Summary:
We don't do this today, but it looks like std::string does. For longer, similar strings, this is a big win.

Before:

```lang=text
============================================================================
./folly/test/FBStringTestBenchmarks.cpp.h       relative  time/iter  iters/s
============================================================================
BM_equality_string(65536)                                    5.13ms   194.87
BM_equality_fbstring(65536)                                 11.34ms    88.18
============================================================================
```

After:

```lang=text
============================================================================
./folly/test/FBStringTestBenchmarks.cpp.h       relative  time/iter  iters/s
============================================================================
BM_equality_string(65536)                                    5.01ms   199.74
BM_equality_fbstring(65536)                                  6.63ms   150.78
============================================================================
```

Test Plan: Benchmark, unit  tests

Reviewed By: tudorb@fb.com

FB internal diff: D737482

11 years agoFix unsplit(", ")
Tom Jackson [Wed, 13 Mar 2013 20:56:29 +0000 (13:56 -0700)]
Fix unsplit(", ")

Summary: Otherwise you get errors like `error: array used as initializer ./folly/experimental/StringGen-inl.h: In constructor ‘folly::gen::detail::UnsplitBuffer<Delimiter, OutputBuffer>::UnsplitBuffer(const Delimiter&, OutputBuffer*) [with Delimiter = char [3] ...]`, since literal strings bind as reference to fixed-length character arrays. Providing an explicit overload for `const char*` fixes this.

Test Plan: Unit tests

Reviewed By: tulloch@fb.com

FB internal diff: D737117

11 years agoadding is_non_positive traits
Marcelo Juchem [Tue, 12 Mar 2013 22:55:06 +0000 (15:55 -0700)]
adding is_non_positive traits

Summary:
template <typename SomeInt>
void foo(SomeInt x) {
// yields an error in clang when SomeInt is unsigned and -Werror is used
if(x <= 0) {
//...
}
}

Test Plan: added unit tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D735735

11 years agoMake hash_combine accept a configurable hash function
David Vickrey [Mon, 11 Mar 2013 22:34:18 +0000 (15:34 -0700)]
Make hash_combine accept a configurable hash function

Summary:
std::hash is not awesome and not configurable.  Typical cases you might want to customize are:
string: I happen to know that fnv isn't super awesome, for example, and that's what folly uses for std::hash fbstring.
pointers: you may want to hash the contents of the pointer instead of the address for certain types.

This is a very simple diff that lets you do that.  It provides StdHasher that passes through to std::hash and uses that for hash_combine, so this should be 100% backward compatible.

Test Plan: test_hash.  I will add another test for using a hasher besides StdHasher shortly.

Reviewed By: delong.j@fb.com

FB internal diff: D733899

11 years agoFixing namespace for GeneratorBuilder, more moves for Params
Tom Jackson [Fri, 8 Mar 2013 03:26:51 +0000 (19:26 -0800)]
Fixing namespace for GeneratorBuilder, more moves for Params

Summary:
GENERATOR was broken if you didn't `using namespace folly::gen`, and
we're still copying quite a few functors where we could move them.

Test Plan: Unit tests

Reviewed By: chaoyc@fb.com

FB internal diff: D731253

11 years agoAdd explicit assignment operator definitions to Optional
Lovro Puzar [Mon, 11 Mar 2013 20:52:42 +0000 (13:52 -0700)]
Add explicit assignment operator definitions to Optional

Summary:
See new test.  Under GCC 4.6 (which is what the folly tests build with) the old code works fine but under 4.7 building fails with:

folly/test/OptionalTest.cpp: In member function ‘virtual void Optional_AssignmentContained_Test::TestBody()’:
folly/test/OptionalTest.cpp:122:14: error: use of deleted function ‘ContainsOptional& ContainsOptional::operator=(const ContainsOptional&)’
folly/test/OptionalTest.cpp:106:21: note: ‘ContainsOptional& ContainsOptional::operator=(const ContainsOptional&)’ is implicitly deleted because the default definition would be ill-formed:
folly/test/OptionalTest.cpp:106:21: error: use of deleted function ‘folly::Optional<int>& folly::Optional<int>::operator=(const folly::Optional<int>&)’
In file included from folly/test/OptionalTest.cpp:17:0:
./folly/Optional.h:84:7: note: ‘folly::Optional<int>& folly::Optional<int>::operator=(const folly::Optional<int>&)’ is implicitly declared as deleted because ‘folly::Optional<int>’ declares a move constructor or move assignment operator
folly/test/OptionalTest.cpp:129:30: error: use of deleted function ‘ContainsOptional& ContainsOptional::operator=(ContainsOptional&&)’
folly/test/OptionalTest.cpp:108:21: note: ‘ContainsOptional& ContainsOptional::operator=(ContainsOptional&&)’ is implicitly deleted because the default definition would be ill-formed:
folly/test/OptionalTest.cpp:108:21: error: non-static data member ‘ContainsOptional::opt_’ does not have a move assignment operator or trivial copy assignment operator
folly/test/OptionalTest.cpp:137:14: error: use of deleted function ‘ContainsOptional& ContainsOptional::operator=(const ContainsOptional&)’

Test Plan:
(1) fbconfig folly/test && fbmake dbg && _build/dbg/folly/test/optional_test
(2) Remove folly/PLATFORM to build with gcc 4.7, then repeat (1).  Without the code fix, the new test fails to build.  With the fix, the test builds and runs fine.

Reviewed By: tjackson@fb.com

FB internal diff: D732402

11 years agofolly (easy): Disable GCC-specific warning disabling hacks in clang
Ben Gertzfield [Mon, 11 Mar 2013 18:27:34 +0000 (11:27 -0700)]
folly (easy): Disable GCC-specific warning disabling hacks in clang

Summary:
When compiling folly with clang, the compiler warns about our
use of GCC-specific pragmas to silence incorrect compiler warnings:

folly/Optional.h:79:33: warning: unknown warning group '-Wpragmas', ignored [-Wunknown-pragmas]
folly/Optional.h:80:33: warning: unknown warning group '-Wmaybe-uninitialized', ignored [-Wunknown-pragmas]

Thankfully, those incorrect compiler warnings are not emitted by
clang, so we can just disable the pragmas in clang.

Test Plan:
Built folly in gcc and ran it through clang. Warning above
is gone.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D733323

11 years agoAdd CHECK for out-of-range minRequests
Tudor Bosman [Thu, 7 Mar 2013 15:45:16 +0000 (07:45 -0800)]
Add CHECK for out-of-range minRequests

Test Plan: async_io_test

Reviewed By: philipp@fb.com

FB internal diff: D730100

11 years agoRemove File::tryOpen
Tom Jackson [Wed, 6 Mar 2013 23:27:38 +0000 (15:27 -0800)]
Remove File::tryOpen

Summary:
In hopes of keeping 'busywork' helpers out of folly, I've moved this
closer to the code that needed to do this.

Test Plan: Unit tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D729194

Blame Revision: D726916

11 years agoFile::tryOpen
Tom Jackson [Tue, 5 Mar 2013 19:05:28 +0000 (11:05 -0800)]
File::tryOpen

Summary:
Now that we have truthy files, it would be nice to be able to simply
//try// opening files and return a possibly-initialized File.

Test Plan: Unit tests

Reviewed By: chaoyc@fb.com

FB internal diff: D726916

11 years agoTruthy File
Tom Jackson [Tue, 5 Mar 2013 19:05:42 +0000 (11:05 -0800)]
Truthy File

Summary:
File has a default constructor so it can be initialized late, but it
doesn't have a good canonical way to see if it's been initialized. This adds an
//explicit// operator bool so you can test files like `if (file) ...`.

Test Plan: Unit tests

Reviewed By: chaoyc@fb.com

FB internal diff: D726914

11 years agoAdd resizing constructor to folly::padded::Adaptor
Tudor Bosman [Tue, 5 Mar 2013 00:31:58 +0000 (16:31 -0800)]
Add resizing constructor to folly::padded::Adaptor

Summary: Added Adaptor(size_t, const value_type&)

Test Plan: test added

Reviewed By: soren@fb.com

FB internal diff: D726358

11 years agoAdding useful error message for File
Tom Jackson [Mon, 4 Mar 2013 19:52:58 +0000 (11:52 -0800)]
Adding useful error message for File

Summary:
'open() failed' isn't too helpful. Seeing a filename there is. So I
added it.

Test Plan: Unit test

Reviewed By: mohittalwar@fb.com

FB internal diff: D725204

11 years agoprovide a flag to control the minimum number of iterations
Adam Simpkins [Fri, 1 Mar 2013 05:33:29 +0000 (21:33 -0800)]
provide a flag to control the minimum number of iterations

Summary:
Add a --bm_min_iters flag to control the minimum number of iterations
that the benchmark code starts with on each epoch.

This can be used on benchmarks that test very cheap operations, but take
a long time to set up.  Otherwise the benchmark code may have to retry
many times before it hits a large enough number of iterations to get a
meaningful result, and each time it still pays the fixed setup cost.

This also helps with benchmarks when some of the setup cost cannot be
hidden with BenchmarkSuspender for some reason.  --bm_min_iters can be
set to a large enough value so that the extra startup cost will not
affect the measurements too much.

Test Plan:
Used this with the thread local stats benchmark.  During setup/cleanup,
this benchmark starts and synchronizes with many threads.  The entire
setup time cannot be reliably hidden with BenchmarkSuspender; the
synchronization between the threads takes a relatively long time
compared to the cost of the operation being benchmarked.  --bm_min_iters
allows a relatively high number of iterations to be used, masking this
cost.

Reviewed By: rajat@fb.com

FB internal diff: D723304

11 years agofolly::make_optional
Mike Curtiss [Thu, 28 Feb 2013 03:53:14 +0000 (19:53 -0800)]
folly::make_optional

Summary:
Helper method for creating a folly::Optional<T> by just passing
in a T reference.  Analogous to boost::make_optional.

Test Plan: Added test case

Reviewed By: tjackson@fb.com

FB internal diff: D721762

11 years agoMemoryMapping::data() returns StringPiece ::range() returns ByteRange
Lucian Grijincu [Wed, 27 Feb 2013 23:44:37 +0000 (15:44 -0800)]
MemoryMapping::data() returns StringPiece ::range() returns ByteRange

Summary: MemoryMapping::data() returns StringPiece ::range() returns ByteRange

Test Plan: tests

Reviewed By: philipp@fb.com

FB internal diff: D720985

11 years agoAbstract ifunc support into a define
Owen Yamauchi [Tue, 19 Feb 2013 20:20:43 +0000 (12:20 -0800)]
Abstract ifunc support into a define

Summary:
There are platforms other than clang that don't support ifuncs. (The one
I'm concerned about is ARM.) I changed the ifdef __clang__ around the
ifunc attributes to be more abstract, so we can can pass in this flag on
the command line, or use autoconf to detect it.

Test Plan:
fbmake runtests. Manually define HAVE_IFUNC 0 and make sure the
popcount() and popcountll() functions get compiled as calls to
popcount_builtin.

Run autoreconf, ./configure, make sure the feature gets detected
properly by looking at config.h.

Reviewed By: andrewjcg@fb.com

FB internal diff: D712192

11 years agoRenaming flag in MemoryMapping
Tom Jackson [Sat, 23 Feb 2013 03:07:11 +0000 (19:07 -0800)]
Renaming flag in MemoryMapping

Summary:
This flag conflicts with the flag with the same purpose in
`common/files/MemoryMappedFile.cpp`. Just renaming it for now.

Test Plan: Build

Reviewed By: lucian@fb.com

FB internal diff: D717067

11 years agoMemoryMapping
Tom Jackson [Thu, 21 Feb 2013 00:13:00 +0000 (16:13 -0800)]
MemoryMapping

Summary: MemoryMapping is a C++ wrapper object around mmap. It works with `folly::File`s, and provides bitwise-range access for reading and writing files.

Test Plan: Unit test

Reviewed By: lucian@fb.com

FB internal diff: D452384

11 years agofolly: AsyncIO: add debuging helper
Lucian Grijincu [Fri, 22 Feb 2013 18:36:01 +0000 (10:36 -0800)]
folly: AsyncIO: add debuging helper

Summary: Change State to enum class, and add debugging helper to AsyncIOOp and AsyncIO.

Test Plan: n/a

Reviewed By: philipp@fb.com

FB internal diff: D715676

11 years agofolly/{experimental => .}/File
Tom Jackson [Thu, 21 Feb 2013 00:50:50 +0000 (16:50 -0800)]
folly/{experimental => .}/File

Summary: Moving File into `/folly`.

Test Plan: Same unit tests, rebuild affected code outside folly.

Reviewed By: philipp@fb.com

FB internal diff: D714462

11 years agoFix SIGSEGV in StringPiece::find_first_of
Mike Curtiss [Tue, 12 Feb 2013 22:39:13 +0000 (14:39 -0800)]
Fix SIGSEGV in StringPiece::find_first_of

Summary:
Our SSE version of find_first_of was reading past the end of
the StringPiece in some cases, which (very rarely) caused a seg-fault
when we were reading outside of our allotted virtual address space.

Modify the code to never read past the end of the underlying buffers
except when we think it's "safe" because we're still within the same
page. (ASSUMPTION: if a process is allowed to read a byte within a
page, then it is allowed to read _all_ bytes within that page.)

Test Plan:
Added tests that verify we won't go across page boundaries.

Sadly, this code hurts our benchmarks -- sometimes by up to 50% for
smaller strings.

Reviewed By: philipp@fb.com

FB internal diff: D707923

Blame Revision: D638500

11 years agoRework folly::AsyncIO interface to make it easier for other classes to use Op
Tudor Bosman [Thu, 14 Feb 2013 23:26:26 +0000 (15:26 -0800)]
Rework folly::AsyncIO interface to make it easier for other classes to use Op

Summary:
AsyncIOOp no longer requires derivation to be able to use callbacks; the
callback is passed in.  This makes composition easier (see AsyncIOQueue, added
in this diff).

Test Plan: async_io_test, test added

Reviewed By: lucian@fb.com

FB internal diff: D709648

11 years agofix comment
Tudor Bosman [Fri, 15 Feb 2013 00:48:32 +0000 (16:48 -0800)]
fix comment

Test Plan: No

Reviewed By: philipp@fb.com

FB internal diff: D709795

11 years agovalue_ might be uninitialized
Rajat Goel [Wed, 13 Feb 2013 20:38:02 +0000 (12:38 -0800)]
value_ might be uninitialized

Summary: Compilation is failing in 'opt' build

Test Plan: compile

Reviewed By: andrewjcg@fb.com

FB internal diff: D707869

11 years agoDefine ALLOCM_LG_ALIGN
Tudor Bosman [Wed, 13 Feb 2013 20:04:41 +0000 (12:04 -0800)]
Define ALLOCM_LG_ALIGN

Test Plan: No

Reviewed By: philipp@fb.com

FB internal diff: D707792

11 years agoMinor clang compiler fixes
Gaurav Jain [Wed, 13 Feb 2013 00:59:25 +0000 (16:59 -0800)]
Minor clang compiler fixes

Summary: Minor clang compiler fixes

Test Plan: - fbmake runtest

Reviewed By: andrewjcg@fb.com

FB internal diff: D707663

11 years agoMake AsyncIO::capacity_ const
Sergey Doroshenko [Tue, 12 Feb 2013 17:17:53 +0000 (09:17 -0800)]
Make AsyncIO::capacity_ const

Summary: It is set once, and is never changed afterwards.

Test Plan: compiled, unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D706125

11 years agoCodemod time\(NULL\) to time(nullptr)
Jordan DeLong [Thu, 31 Jan 2013 00:09:43 +0000 (16:09 -0800)]
Codemod time\(NULL\) to time(nullptr)

Summary: codemod with 'Yes to all'.

Test Plan: None really.

Reviewed By: abirchall@fb.com

FB internal diff: D693769

11 years agoFix subtle double-free in trimEnd; optionally pack IOBufQueue after append
Tudor Bosman [Fri, 8 Feb 2013 01:56:55 +0000 (17:56 -0800)]
Fix subtle double-free in trimEnd; optionally pack IOBufQueue after append

Test Plan: folly/io/test, both dbg and opt, standalone and in valgrind

Reviewed By: philipp@fb.com

FB internal diff: D702755

11 years agoall(), better any()
Tom Jackson [Thu, 7 Feb 2013 18:18:15 +0000 (10:18 -0800)]
all(), better any()

Summary: TSIA

Test Plan: Unit tests

Reviewed By: tulloch@fb.com

FB internal diff: D701890

11 years agofix typos
Tudor Bosman [Tue, 5 Feb 2013 21:12:26 +0000 (13:12 -0800)]
fix typos

Test Plan: async_io_test

Reviewed By: lucian@fb.com

FB internal diff: D699175

11 years agoAdd some CursorBase::operator-() implementations
Peter Griess [Mon, 28 Jan 2013 18:05:16 +0000 (10:05 -0800)]
Add some CursorBase::operator-() implementations

Summary:
- Add CursorBase::operator-() implementations for Cursor and BufType;
useful for figuring out the distance between two objects

Test Plan: - Used in some other code

Reviewed By: simpkins@fb.com

FB internal diff: D690046

11 years agoassert on self move assignment
Philip Pronin [Sat, 2 Feb 2013 06:41:53 +0000 (22:41 -0800)]
assert on self move assignment

Test Plan: ran tests in dbg

Reviewed By: tudorb@fb.com

FB internal diff: D696964

11 years agoAsyncIO: CHECK preconditions
Tudor Bosman [Tue, 5 Feb 2013 18:51:48 +0000 (10:51 -0800)]
AsyncIO: CHECK preconditions

Test Plan: async_io_test

Reviewed By: delong.j@fb.com

FB internal diff: D698919

11 years agoAsyncIO in folly
Tudor Bosman [Tue, 5 Feb 2013 02:38:14 +0000 (18:38 -0800)]
AsyncIO in folly

Summary:
Interface extended and cleaned up.  Also, now
actually allows you to retrieve IO errors.  Also moved some useful functions
out of Subprocess.cpp into a separate header file.

Test Plan: async_io_test, subprocess_test

Reviewed By: philipp@fb.com

FB internal diff: D698412

11 years agounsplit
Andrew Tulloch [Tue, 5 Feb 2013 00:54:37 +0000 (16:54 -0800)]
unsplit

Summary:
1. Incorporates @tjackson's offline comments.
2. See docstrings and examples for basic usage.
3. The usecase this covers (for me and others) was where I have some map or
vector of elements, and I want to form a string representation of this (for
logging, fb303 exported values, etc.). Various uses have existed in fbcode (e.g.
UP2X shard representations), and this seemed like a useful utility.

Test Plan: unit tests.

Reviewed By: tjackson@fb.com

FB internal diff: D696794

11 years agoUpdate example in folly::gen
Jordan DeLong [Mon, 4 Feb 2013 03:58:18 +0000 (19:58 -0800)]
Update example in folly::gen

Summary: asVector() doesn't exist.

Test Plan: Nope.

Reviewed By: tjackson@fb.com

FB internal diff: D697240

11 years agocontains()
Tom Jackson [Wed, 16 Jan 2013 04:02:16 +0000 (20:02 -0800)]
contains()

Summary: TSIA

Test Plan: Unit tests

Reviewed By: tulloch@fb.com

FB internal diff: D680177

11 years agofolly/dynamic: fix explicit specializations after instantiation
Andrew Gallagher [Tue, 29 Jan 2013 06:54:19 +0000 (22:54 -0800)]
folly/dynamic: fix explicit specializations after instantiation

Summary:
clang complains that the explicit specializations in dynamic.cpp
come after references in dynamic-inl.h.

Test Plan:
- built dyamic.o with clang
- built folly normally and ran unittests

Reviewed By: delong.j@fb.com

FB internal diff: D691081

11 years agoadding some missing remove_reference in make_stl_allocator and is_simple_allocator
Marcelo Juchem [Sat, 26 Jan 2013 01:22:57 +0000 (17:22 -0800)]
adding some missing remove_reference in make_stl_allocator and is_simple_allocator

Summary: adding some missing remove_reference in make_stl_allocator and is_simple_allocator

Test Plan: unit tests

Reviewed By: jon.coens@fb.com

FB internal diff: D689524

11 years agoRemove a bit of debug code in folly::Range
Jordan DeLong [Sun, 20 Jan 2013 20:18:07 +0000 (12:18 -0800)]
Remove a bit of debug code in folly::Range

Summary:
Seems like we can drop this, as the case that motivated
adding it wouldn't have been caught by it.

Test Plan: Compiled folly/test.

Reviewed By: tudorb@fb.com

FB internal diff: D684200

11 years agofixing rwspinlock test Summary:
Xin Liu [Fri, 25 Jan 2013 18:21:44 +0000 (10:21 -0800)]
fixing rwspinlock test Summary:

Summary:
gcc seems to treat this as declaration:

RWSpinLock::UpgradedHolder ug(
RWSpinLock::WriteHolder(
RWSpinLock::ReadHolder(&lock)));

Test Plan: add LOG(INFO) to make sure the holder converstions did get executed.

Reviewed By: marcelo.juchem@fb.com

FB internal diff: D688748

11 years agoA few fixes for clang support
Marcelo Juchem [Fri, 25 Jan 2013 04:49:47 +0000 (20:49 -0800)]
A few fixes for clang support

Summary: fixes for clang support

Test Plan:
rm -rf ~/fbcode/_build/* && fbconfig --clang folly/test && fbmake
rm -rf ~/fbcode/_build/* && fbconfig folly/test && fbmake
_bin/folly/test/format_test
_bin/folly/test/optional_test
_bin/folly/test/has_member_fn_traits_test

Reviewed By: tudorb@fb.com

FB internal diff: D688295

11 years agoqfind_first_byte_of may suffer from global initialization order
Philip Pronin [Fri, 25 Jan 2013 00:36:11 +0000 (16:36 -0800)]
qfind_first_byte_of may suffer from global initialization order

Summary: ##static## handling adds ~2 more ns overhead per call (and the first call is kinda slow), but now the logic is correct now. Also inlined ##qfind_first_byte_of##.

Test Plan: unittests

Reviewed By: tudorb@fb.com

FB internal diff: D687947

11 years agoImplementing unique/shared_ptr for custom allocators (like Arena) in folly
Marcelo Juchem [Tue, 8 Jan 2013 03:05:53 +0000 (19:05 -0800)]
Implementing unique/shared_ptr for custom allocators (like Arena) in folly

Summary:
- moving simple allocator *_ptr and convenience functions to folly
- getting rid of arena_new - it encourages manually constructing smart pointers when folly::allocate_* should be used instead
- using std::allocate_shared to construct shared_ptrs, thus properly using the allocator for the ref-counter too
- fixing forwarding of parameters in the convenience functions
- uniform allocation of smart pointers using both stl and non stl-like allocators

Test Plan:
- build + tests of existing client code
- basic unit tests for arena smart pointers

Reviewed By: delong.j@fb.com

FB internal diff: D672818

11 years agotemporary get rid of ifunc in folly::Range
Philip Pronin [Thu, 24 Jan 2013 18:55:10 +0000 (10:55 -0800)]
temporary get rid of ifunc in folly::Range

Summary:
See discussion in D638500.

valgrind 3.7 contains a bug that makes it hung up
(https://bugs.kde.org/show_bug.cgi?id=301204).

glibc 2.5.1 doesn't support ifunc.

In the future we should conditionally compile ifunc stuff (this is also
required to support clang).

Test Plan:
unittests, ran range_benchmark to confirm there is no
significant performance drop, this additional level of indirection adds overhead of ~1ns.

tested on CPUs with and without SSE4.2 support.

Reviewed By: mmcurtiss@fb.com

FB internal diff: D687351

11 years agoFix comment in folly::dynamic
Jordan DeLong [Sun, 20 Jan 2013 04:02:45 +0000 (20:02 -0800)]
Fix comment in folly::dynamic

Summary: That's all.

Test Plan: Nope.

Reviewed By: simpkins@fb.com

FB internal diff: D684144

11 years agoBoost system is now needed
Nathan Smith [Mon, 17 Dec 2012 21:09:14 +0000 (16:09 -0500)]
Boost system is now needed

Summary: https://github.com/facebook/folly/pull/22

Test Plan: .

Reviewed By: andrewjcg@fb.com

FB internal diff: D683793

11 years agoAdd optional description which complains on newer versions of autoconf
Nathan Smith [Mon, 17 Dec 2012 19:50:05 +0000 (14:50 -0500)]
Add optional description which complains on newer versions of autoconf

Summary: https://github.com/facebook/folly/pull/22

Test Plan: none

Reviewed By: andrewjcg@fb.com

FB internal diff: D683791

11 years agoopen source Elias-Fano coding implementation
Philip Pronin [Sun, 13 Jan 2013 08:40:23 +0000 (00:40 -0800)]
open source Elias-Fano coding implementation

Test Plan: unittests

Reviewed By: mmcurtiss@fb.com

FB internal diff: D677750

11 years agoset pid_=-1 after wait, actually implement pid()
Tudor Bosman [Wed, 16 Jan 2013 22:52:04 +0000 (14:52 -0800)]
set pid_=-1 after wait, actually implement pid()

Summary: minor issues in folly::Subprocess

Test Plan: subprocess_test

Reviewed By: philipp@fb.com

FB internal diff: D680959

11 years agofix some of the warning/errors clang 3.1 reports - 2
Philip Pronin [Mon, 14 Jan 2013 23:54:13 +0000 (15:54 -0800)]
fix some of the warning/errors clang 3.1 reports - 2

Test Plan:
fbconfig -r folly && fbmake opt -j32

to make sure gcc is still able to compile it

Reviewed By: tudorb@fb.com

FB internal diff: D678500

11 years agofix some of the warning/errors clang 3.1 reports
Philip Pronin [Mon, 14 Jan 2013 23:03:00 +0000 (15:03 -0800)]
fix some of the warning/errors clang 3.1 reports

Summary: One step closer to build folly with clang

Test Plan:
fbconfig -r folly && fbmake opt -j32

to make sure gcc is still able to compile it

Reviewed By: tudorb@fb.com

FB internal diff: D677716

11 years agograduate IOBuf out of folly/experimental
Tudor Bosman [Mon, 14 Jan 2013 21:52:31 +0000 (13:52 -0800)]
graduate IOBuf out of folly/experimental

Summary: Move IOBuf and related code to folly/io.

Test Plan: fbconfig -r folly && fbmake runtests_opt, fbconfig unicorn/test && fbmake opt

Reviewed By: andrewcox@fb.com

FB internal diff: D678331

11 years agoCreate a benchmark for ProducerConsumerQueue
Bert Maher [Mon, 14 Jan 2013 19:18:16 +0000 (11:18 -0800)]
Create a benchmark for ProducerConsumerQueue

Summary: This is a basic benchmark harness for testing ProducerConsumerQueue, which tests a single producer/consumer pair with and without CPU affinity set.  The change to ProducerConsumerQueue.h (not for committing) tests the effect of cache-aligning the read and write indices to reduce false sharing.

Test Plan: Run the benchmark with the cache alignment (un)commented.

Reviewed By: rituraj@fb.com

FB internal diff: D665948

11 years agoRemove some unnecessary uses of LOG(FATAL) in folly
Jordan DeLong [Fri, 11 Jan 2013 20:52:50 +0000 (12:52 -0800)]
Remove some unnecessary uses of LOG(FATAL) in folly

Summary:
ScopeGuard::execute will already call std::terminate if an
exception is thrown, as it's noexcept, and the case in
ConcurrentSkipList should be a check.

Test Plan:
Ran folly tests.  Will look at phabricator to see if
anything breaks downstream from removing glog/logging.h from
scopeguard.

Reviewed By: chip@fb.com

FB internal diff: D677038

11 years agoSpeed-up StringPiece::find_first_of()
Mike Curtiss [Fri, 23 Nov 2012 21:44:46 +0000 (13:44 -0800)]
Speed-up StringPiece::find_first_of()

Summary:
Wrote an SSE4.2-optimized version of find_first_of (>10x faster in
some cases).  For cases where SSE4.2 is not supported, rewrote
find_first_of to use Aho/Hopcroft/Ullman's "sparse, lazy" set (which
is faster than std::find_first_of in most cases).

Note that the overhead of ifunc (especially the lack of inlining)
means that the new implementations could be slightly slower for
super-tiny strings, but the inflection point is around 3-4 characters
in haystack, which seems reasonable.

Test Plan:
Added tests and benchmarks:

string length 1:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         5.91ns  169.16M
FindSingleCharRange                              130.02%     4.55ns  219.95M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     11.37ns   87.98M
FindFirstOf2NeedlesNoSSE                         108.69%    10.46ns   95.63M
FindFirstOf2NeedlesStd                           147.04%     7.73ns  129.37M
FindFirstOf2NeedlesMemchr                         57.66%    19.71ns   50.73M
FindFirstOf2NeedlesByteSet                        83.32%    13.64ns   73.30M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     10.91ns   91.64M
FindFirstOf4NeedlesNoSSE                          88.87%    12.28ns   81.45M
FindFirstOf4NeedlesStd                           114.28%     9.55ns  104.73M
FindFirstOf4NeedlesMemchr                         34.77%    31.38ns   31.87M
FindFirstOf4NeedlesByteSet                        60.00%    18.19ns   54.98M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     10.91ns   91.64M
FindFirstOf8NeedlesNoSSE                          48.00%    22.73ns   43.99M
FindFirstOf8NeedlesStd                            54.54%    20.01ns   49.99M
FindFirstOf8NeedlesMemchr                         16.27%    67.06ns   14.91M
FindFirstOf8NeedlesByteSet                        39.99%    27.28ns   36.65M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    10.91ns   91.64M
FindFirstOf16NeedlesNoSSE                         33.33%    32.74ns   30.54M
FindFirstOf16NeedlesStd                           36.36%    30.01ns   33.32M
FindFirstOf16NeedlesMemchr                        10.25%   106.42ns    9.40M
FindFirstOf16NeedlesByteSet                       24.00%    45.46ns   22.00M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    18.91ns   52.89M
FindFirstOf32NeedlesNoSSE                         21.00%    90.02ns   11.11M
FindFirstOf32NeedlesStd                           39.99%    47.28ns   21.15M
FindFirstOf32NeedlesMemchr                         8.48%   223.04ns    4.48M
FindFirstOf32NeedlesByteSet                       22.35%    84.60ns   11.82M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    25.92ns   38.58M
FindFirstOf64NeedlesNoSSE                         17.45%   148.51ns    6.73M
FindFirstOf64NeedlesStd                           33.93%    76.39ns   13.09M
FindFirstOf64NeedlesMemchr                         6.07%   426.94ns    2.34M
FindFirstOf64NeedlesByteSet                       18.10%   143.22ns    6.98M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       23.28ns   42.95M
FindFirstOfRandomNoSSE                            88.96%    26.17ns   38.21M
FindFirstOfRandomStd                             112.78%    20.64ns   48.44M
FindFirstOfRandomMemchr                           35.68%    65.24ns   15.33M
FindFirstOfRandomByteSet                          62.62%    37.18ns   26.90M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      12.73ns   78.54M
----------------------------------------------------------------------------
============================================================================
string length 8:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         7.05ns  141.75M
FindSingleCharRange                               50.05%    14.10ns   70.95M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     11.37ns   87.98M
FindFirstOf2NeedlesNoSSE                          53.04%    21.43ns   46.67M
FindFirstOf2NeedlesStd                            37.87%    30.01ns   33.32M
FindFirstOf2NeedlesMemchr                         54.81%    20.74ns   48.22M
FindFirstOf2NeedlesByteSet                        33.78%    33.65ns   29.72M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     10.91ns   91.64M
FindFirstOf4NeedlesNoSSE                          25.53%    42.74ns   23.40M
FindFirstOf4NeedlesStd                            24.49%    44.56ns   22.44M
FindFirstOf4NeedlesMemchr                         33.66%    32.42ns   30.85M
FindFirstOf4NeedlesByteSet                        28.57%    38.19ns   26.18M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     10.91ns   91.64M
FindFirstOf8NeedlesNoSSE                          21.05%    51.84ns   19.29M
FindFirstOf8NeedlesStd                            13.56%    80.48ns   12.43M
FindFirstOf8NeedlesMemchr                         17.32%    62.99ns   15.88M
FindFirstOf8NeedlesByteSet                        23.08%    47.28ns   21.15M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    10.91ns   91.64M
FindFirstOf16NeedlesNoSSE                         15.58%    70.02ns   14.28M
FindFirstOf16NeedlesStd                            7.23%   150.84ns    6.63M
FindFirstOf16NeedlesMemchr                         9.52%   114.63ns    8.72M
FindFirstOf16NeedlesByteSet                       16.67%    65.47ns   15.27M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    18.91ns   52.89M
FindFirstOf32NeedlesNoSSE                         18.42%   102.62ns    9.74M
FindFirstOf32NeedlesStd                            7.08%   266.97ns    3.75M
FindFirstOf32NeedlesMemchr                         8.43%   224.41ns    4.46M
FindFirstOf32NeedlesByteSet                       19.29%    98.00ns   10.20M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    25.92ns   38.58M
FindFirstOf64NeedlesNoSSE                         16.13%   160.73ns    6.22M
FindFirstOf64NeedlesStd                            4.58%   565.53ns    1.77M
FindFirstOf64NeedlesMemchr                         6.05%   428.22ns    2.34M
FindFirstOf64NeedlesByteSet                       16.58%   156.33ns    6.40M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       23.28ns   42.96M
FindFirstOfRandomNoSSE                            44.00%    52.91ns   18.90M
FindFirstOfRandomStd                              24.62%    94.56ns   10.58M
FindFirstOfRandomMemchr                           30.88%    75.38ns   13.27M
FindFirstOfRandomByteSet                          43.33%    53.72ns   18.62M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      12.73ns   78.54M
----------------------------------------------------------------------------
============================================================================
string length 10:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         7.06ns  141.61M
FindSingleCharRange                               41.98%    16.82ns   59.44M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     11.37ns   87.98M
FindFirstOf2NeedlesNoSSE                          52.05%    21.84ns   45.79M
FindFirstOf2NeedlesStd                            31.25%    36.37ns   27.49M
FindFirstOf2NeedlesMemchr                         52.48%    21.66ns   46.17M
FindFirstOf2NeedlesByteSet                        29.07%    39.10ns   25.57M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     10.91ns   91.64M
FindFirstOf4NeedlesNoSSE                          28.93%    37.71ns   26.52M
FindFirstOf4NeedlesStd                            20.00%    54.57ns   18.33M
FindFirstOf4NeedlesMemchr                         30.39%    35.91ns   27.85M
FindFirstOf4NeedlesByteSet                        25.00%    43.65ns   22.91M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     10.91ns   91.64M
FindFirstOf8NeedlesNoSSE                          17.02%    64.12ns   15.60M
FindFirstOf8NeedlesStd                            11.16%    97.77ns   10.23M
FindFirstOf8NeedlesMemchr                         17.52%    62.30ns   16.05M
FindFirstOf8NeedlesByteSet                        25.00%    43.65ns   22.91M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    10.91ns   91.64M
FindFirstOf16NeedlesNoSSE                         16.28%    67.02ns   14.92M
FindFirstOf16NeedlesStd                            5.98%   182.32ns    5.48M
FindFirstOf16NeedlesMemchr                         9.09%   120.06ns    8.33M
FindFirstOf16NeedlesByteSet                       17.65%    61.84ns   16.17M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    19.10ns   52.36M
FindFirstOf32NeedlesNoSSE                         17.91%   106.63ns    9.38M
FindFirstOf32NeedlesStd                            5.79%   329.70ns    3.03M
FindFirstOf32NeedlesMemchr                         7.89%   241.91ns    4.13M
FindFirstOf32NeedlesByteSet                       18.92%   100.95ns    9.91M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    26.15ns   38.24M
FindFirstOf64NeedlesNoSSE                         15.84%   165.05ns    6.06M
FindFirstOf64NeedlesStd                            3.71%   704.28ns    1.42M
FindFirstOf64NeedlesMemchr                         5.49%   476.63ns    2.10M
FindFirstOf64NeedlesByteSet                       16.48%   158.68ns    6.30M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       22.83ns   43.81M
FindFirstOfRandomNoSSE                            43.25%    52.78ns   18.95M
FindFirstOfRandomStd                              22.33%   102.23ns    9.78M
FindFirstOfRandomMemchr                           31.61%    72.23ns   13.85M
FindFirstOfRandomByteSet                          41.64%    54.82ns   18.24M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      12.73ns   78.54M
----------------------------------------------------------------------------
============================================================================
string length 16:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         7.06ns  141.72M
FindSingleCharRange                               28.21%    25.01ns   39.98M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     15.91ns   62.84M
FindFirstOf2NeedlesNoSSE                          72.89%    21.84ns   45.80M
FindFirstOf2NeedlesStd                            28.68%    55.48ns   18.02M
FindFirstOf2NeedlesMemchr                         74.47%    21.37ns   46.79M
FindFirstOf2NeedlesByteSet                        23.34%    68.19ns   14.66M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     15.46ns   64.68M
FindFirstOf4NeedlesNoSSE                          40.77%    37.92ns   26.37M
FindFirstOf4NeedlesStd                            18.28%    84.59ns   11.82M
FindFirstOf4NeedlesMemchr                         42.97%    35.97ns   27.80M
FindFirstOf4NeedlesByteSet                        25.76%    60.02ns   16.66M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     15.46ns   64.68M
FindFirstOf8NeedlesNoSSE                          24.03%    64.34ns   15.54M
FindFirstOf8NeedlesStd                             9.74%   158.74ns    6.30M
FindFirstOf8NeedlesMemchr                         24.55%    62.98ns   15.88M
FindFirstOf8NeedlesByteSet                        28.33%    54.57ns   18.33M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    15.46ns   64.68M
FindFirstOf16NeedlesNoSSE                         19.83%    77.98ns   12.82M
FindFirstOf16NeedlesStd                            5.56%   277.82ns    3.60M
FindFirstOf16NeedlesMemchr                        12.95%   119.35ns    8.38M
FindFirstOf16NeedlesByteSet                       21.25%    72.75ns   13.75M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    32.80ns   30.49M
FindFirstOf32NeedlesNoSSE                         27.86%   117.69ns    8.50M
FindFirstOf32NeedlesStd                            6.33%   517.97ns    1.93M
FindFirstOf32NeedlesMemchr                        13.72%   239.09ns    4.18M
FindFirstOf32NeedlesByteSet                       29.06%   112.85ns    8.86M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    46.83ns   21.35M
FindFirstOf64NeedlesNoSSE                         26.68%   175.50ns    5.70M
FindFirstOf64NeedlesStd                            4.20%     1.11us  897.48K
FindFirstOf64NeedlesMemchr                        10.04%   466.39ns    2.14M
FindFirstOf64NeedlesByteSet                       27.47%   170.50ns    5.87M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       23.41ns   42.72M
FindFirstOfRandomNoSSE                            38.00%    61.61ns   16.23M
FindFirstOfRandomStd                              13.91%   168.34ns    5.94M
FindFirstOfRandomMemchr                           29.03%    80.64ns   12.40M
FindFirstOfRandomByteSet                          33.31%    70.28ns   14.23M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      15.12ns   66.15M
----------------------------------------------------------------------------
============================================================================
string length 32:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         8.23ns  121.52M
FindSingleCharRange                               17.57%    46.83ns   21.35M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     20.46ns   48.88M
FindFirstOf2NeedlesNoSSE                          82.29%    24.86ns   40.22M
FindFirstOf2NeedlesStd                            17.69%   115.65ns    8.65M
FindFirstOf2NeedlesMemchr                         85.17%    24.02ns   41.63M
FindFirstOf2NeedlesByteSet                        28.19%    72.58ns   13.78M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     20.01ns   49.99M
FindFirstOf4NeedlesNoSSE                          48.57%    41.19ns   24.28M
FindFirstOf4NeedlesStd                            11.52%   173.72ns    5.76M
FindFirstOf4NeedlesMemchr                         50.55%    39.58ns   25.27M
FindFirstOf4NeedlesByteSet                        26.33%    75.99ns   13.16M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     20.01ns   49.99M
FindFirstOf8NeedlesNoSSE                          26.94%    74.27ns   13.46M
FindFirstOf8NeedlesStd                             6.73%   297.31ns    3.36M
FindFirstOf8NeedlesMemchr                         27.44%    72.90ns   13.72M
FindFirstOf8NeedlesByteSet                        23.91%    83.66ns   11.95M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    20.01ns   49.99M
FindFirstOf16NeedlesNoSSE                         18.37%   108.92ns    9.18M
FindFirstOf16NeedlesStd                            3.75%   532.80ns    1.88M
FindFirstOf16NeedlesMemchr                        14.53%   137.71ns    7.26M
FindFirstOf16NeedlesByteSet                       19.55%   102.32ns    9.77M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    45.92ns   21.78M
FindFirstOf32NeedlesNoSSE                         31.17%   147.32ns    6.79M
FindFirstOf32NeedlesStd                            4.50%     1.02us  980.43K
FindFirstOf32NeedlesMemchr                        16.13%   284.64ns    3.51M
FindFirstOf32NeedlesByteSet                       32.63%   140.73ns    7.11M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    68.20ns   14.66M
FindFirstOf64NeedlesNoSSE                         29.97%   227.55ns    4.39M
FindFirstOf64NeedlesStd                            3.08%     2.21us  452.08K
FindFirstOf64NeedlesMemchr                        12.51%   545.17ns    1.83M
FindFirstOf64NeedlesByteSet                       30.74%   221.86ns    4.51M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       29.99ns   33.35M
FindFirstOfRandomNoSSE                            45.10%    66.49ns   15.04M
FindFirstOfRandomStd                              10.28%   291.67ns    3.43M
FindFirstOfRandomMemchr                           34.56%    86.76ns   11.53M
FindFirstOfRandomByteSet                          28.64%   104.72ns    9.55M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      19.55ns   51.15M
----------------------------------------------------------------------------
============================================================================
string length 64:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        10.91ns   91.65M
FindSingleCharRange                               13.26%    82.29ns   12.15M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     29.56ns   33.83M
FindFirstOf2NeedlesNoSSE                         100.77%    29.33ns   34.09M
FindFirstOf2NeedlesStd                            13.59%   217.44ns    4.60M
FindFirstOf2NeedlesMemchr                        104.83%    28.19ns   35.47M
FindFirstOf2NeedlesByteSet                        22.01%   134.28ns    7.45M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     29.10ns   34.36M
FindFirstOf4NeedlesNoSSE                          56.14%    51.84ns   19.29M
FindFirstOf4NeedlesStd                             8.72%   333.84ns    3.00M
FindFirstOf4NeedlesMemchr                         58.18%    50.02ns   19.99M
FindFirstOf4NeedlesByteSet                        19.73%   147.48ns    6.78M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     29.10ns   34.36M
FindFirstOf8NeedlesNoSSE                          30.48%    95.48ns   10.47M
FindFirstOf8NeedlesStd                             5.07%   573.76ns    1.74M
FindFirstOf8NeedlesMemchr                         30.92%    94.11ns   10.63M
FindFirstOf8NeedlesByteSet                        19.26%   151.13ns    6.62M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    29.10ns   34.36M
FindFirstOf16NeedlesNoSSE                         15.84%   183.68ns    5.44M
FindFirstOf16NeedlesStd                            2.79%     1.04us  959.63K
FindFirstOf16NeedlesMemchr                        16.04%   181.41ns    5.51M
FindFirstOf16NeedlesByteSet                       16.54%   175.95ns    5.68M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    73.21ns   13.66M
FindFirstOf32NeedlesNoSSE                         32.76%   223.49ns    4.47M
FindFirstOf32NeedlesStd                            3.62%     2.02us  494.08K
FindFirstOf32NeedlesMemchr                        19.49%   375.70ns    2.66M
FindFirstOf32NeedlesByteSet                       33.45%   218.87ns    4.57M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                   109.95ns    9.09M
FindFirstOf64NeedlesNoSSE                         38.99%   282.01ns    3.55M
FindFirstOf64NeedlesStd                            2.49%     4.41us  226.78K
FindFirstOf64NeedlesMemchr                        15.21%   723.03ns    1.38M
FindFirstOf64NeedlesByteSet                       39.68%   277.13ns    3.61M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       40.57ns   24.65M
FindFirstOfRandomNoSSE                            47.65%    85.15ns   11.74M
FindFirstOfRandomStd                               7.62%   532.10ns    1.88M
FindFirstOfRandomMemchr                           39.23%   103.43ns    9.67M
FindFirstOfRandomByteSet                          22.95%   176.82ns    5.66M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      28.65ns   34.91M
----------------------------------------------------------------------------
============================================================================
string length 128:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        16.37ns   61.09M
FindSingleCharRange                               11.62%   140.85ns    7.10M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     47.74ns   20.95M
FindFirstOf2NeedlesNoSSE                         118.64%    40.24ns   24.85M
FindFirstOf2NeedlesStd                            11.33%   421.18ns    2.37M
FindFirstOf2NeedlesMemchr                        120.68%    39.56ns   25.28M
FindFirstOf2NeedlesByteSet                        21.47%   222.36ns    4.50M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     47.28ns   21.15M
FindFirstOf4NeedlesNoSSE                          63.80%    74.11ns   13.49M
FindFirstOf4NeedlesStd                             7.23%   653.94ns    1.53M
FindFirstOf4NeedlesMemchr                         65.40%    72.30ns   13.83M
FindFirstOf4NeedlesByteSet                        19.96%   236.85ns    4.22M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     47.28ns   21.15M
FindFirstOf8NeedlesNoSSE                          33.87%   139.59ns    7.16M
FindFirstOf8NeedlesStd                             4.20%     1.13us  887.82K
FindFirstOf8NeedlesMemchr                         34.43%   137.32ns    7.28M
FindFirstOf8NeedlesByteSet                        18.98%   249.17ns    4.01M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    47.28ns   21.15M
FindFirstOf16NeedlesNoSSE                         16.83%   281.00ns    3.56M
FindFirstOf16NeedlesStd                            2.30%     2.06us  485.36K
FindFirstOf16NeedlesMemchr                        16.98%   278.50ns    3.59M
FindFirstOf16NeedlesByteSet                       15.75%   300.13ns    3.33M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                   128.45ns    7.79M
FindFirstOf32NeedlesNoSSE                         37.09%   346.28ns    2.89M
FindFirstOf32NeedlesStd                            3.19%     4.03us  248.02K
FindFirstOf32NeedlesMemchr                        23.13%   555.26ns    1.80M
FindFirstOf32NeedlesByteSet                       37.74%   340.32ns    2.94M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                   193.23ns    5.18M
FindFirstOf64NeedlesNoSSE                         47.76%   404.60ns    2.47M
FindFirstOf64NeedlesStd                            2.20%     8.80us  113.61K
FindFirstOf64NeedlesMemchr                        17.91%     1.08us  926.70K
FindFirstOf64NeedlesByteSet                       48.35%   399.64ns    2.50M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       59.66ns   16.76M
FindFirstOfRandomNoSSE                            53.67%   111.17ns    9.00M
FindFirstOfRandomStd                               6.41%   930.67ns    1.07M
FindFirstOfRandomMemchr                           46.01%   129.68ns    7.71M
FindFirstOfRandomByteSet                          19.80%   301.38ns    3.32M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      46.83ns   21.35M
----------------------------------------------------------------------------
============================================================================
string length 256:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        27.28ns   36.65M
FindSingleCharRange                               10.62%   256.90ns    3.89M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     61.39ns   16.29M
FindFirstOf2NeedlesNoSSE                          99.28%    61.84ns   16.17M
FindFirstOf2NeedlesStd                             7.41%   828.62ns    1.21M
FindFirstOf2NeedlesMemchr                        100.01%    61.39ns   16.29M
FindFirstOf2NeedlesByteSet                        15.36%   399.65ns    2.50M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     83.65ns   11.95M
FindFirstOf4NeedlesNoSSE                          71.03%   117.77ns    8.49M
FindFirstOf4NeedlesStd                             6.46%     1.29us  772.77K
FindFirstOf4NeedlesMemchr                         72.14%   115.95ns    8.62M
FindFirstOf4NeedlesByteSet                        20.66%   404.81ns    2.47M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     83.66ns   11.95M
FindFirstOf8NeedlesNoSSE                          35.38%   236.46ns    4.23M
FindFirstOf8NeedlesStd                             3.75%     2.23us  447.99K
FindFirstOf8NeedlesMemchr                         35.71%   234.26ns    4.27M
FindFirstOf8NeedlesByteSet                        20.13%   415.56ns    2.41M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    83.66ns   11.95M
FindFirstOf16NeedlesNoSSE                         18.04%   463.82ns    2.16M
FindFirstOf16NeedlesStd                            2.04%     4.10us  244.06K
FindFirstOf16NeedlesMemchr                        18.14%   461.09ns    2.17M
FindFirstOf16NeedlesByteSet                       14.81%   564.87ns    1.77M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                   237.14ns    4.22M
FindFirstOf32NeedlesNoSSE                         38.92%   609.24ns    1.64M
FindFirstOf32NeedlesStd                            2.95%     8.05us  124.26K
FindFirstOf32NeedlesMemchr                        25.90%   915.44ns    1.09M
FindFirstOf32NeedlesByteSet                       39.21%   604.86ns    1.65M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                   360.78ns    2.77M
FindFirstOf64NeedlesNoSSE                         54.03%   667.71ns    1.50M
FindFirstOf64NeedlesStd                            2.05%    17.59us   56.86K
FindFirstOf64NeedlesMemchr                        20.04%     1.80us  555.45K
FindFirstOf64NeedlesByteSet                       54.61%   660.63ns    1.51M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       98.24ns   10.18M
FindFirstOfRandomNoSSE                            47.37%   207.40ns    4.82M
FindFirstOfRandomStd                               5.24%     1.88us  533.28K
FindFirstOfRandomMemchr                           39.75%   247.14ns    4.05M
FindFirstOfRandomByteSet                          17.69%   555.45ns    1.80M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      62.75ns   15.94M
----------------------------------------------------------------------------
============================================================================
string length 10240:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                       613.80ns    1.63M
FindSingleCharRange                                6.57%     9.34us  107.12K
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                      1.23us  813.01K
FindFirstOf2NeedlesNoSSE                         100.01%     1.23us  813.07K
FindFirstOf2NeedlesStd                             3.77%    32.61us   30.67K
FindFirstOf2NeedlesMemchr                        100.08%     1.23us  813.67K
FindFirstOf2NeedlesByteSet                         8.65%    14.21us   70.37K
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                      2.94us  340.63K
FindFirstOf4NeedlesNoSSE                         119.61%     2.45us  407.44K
FindFirstOf4NeedlesStd                             5.73%    51.23us   19.52K
FindFirstOf4NeedlesMemchr                        119.77%     2.45us  407.97K
FindFirstOf4NeedlesByteSet                        20.66%    14.21us   70.38K
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                      2.94us  340.63K
FindFirstOf8NeedlesNoSSE                          59.95%     4.90us  204.21K
FindFirstOf8NeedlesStd                             3.32%    88.48us   11.30K
FindFirstOf8NeedlesMemchr                         59.96%     4.90us  204.25K
FindFirstOf8NeedlesByteSet                        20.68%    14.20us   70.43K
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                     2.94us  340.63K
FindFirstOf16NeedlesNoSSE                         29.98%     9.79us  102.13K
FindFirstOf16NeedlesStd                            1.80%   162.97us    6.14K
FindFirstOf16NeedlesMemchr                        29.98%     9.79us  102.11K
FindFirstOf16NeedlesByteSet                       20.65%    14.22us   70.33K
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                     8.77us  114.07K
FindFirstOf32NeedlesNoSSE                         44.71%    19.61us   51.00K
FindFirstOf32NeedlesStd                            2.73%   321.22us    3.11K
FindFirstOf32NeedlesMemchr                        43.44%    20.18us   49.55K
FindFirstOf32NeedlesByteSet                       44.67%    19.63us   50.95K
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    13.43us   74.44K
FindFirstOf64NeedlesNoSSE                         68.26%    19.68us   50.81K
FindFirstOf64NeedlesStd                            1.91%   702.62us    1.42K
FindFirstOf64NeedlesMemchr                        33.81%    39.74us   25.17K
FindFirstOf64NeedlesByteSet                       68.25%    19.68us   50.81K
----------------------------------------------------------------------------
FindFirstOfRandomBase                                        3.01us  331.81K
FindFirstOfRandomNoSSE                            75.38%     4.00us  250.10K
FindFirstOfRandomStd                               6.81%    44.25us   22.60K
FindFirstOfRandomMemchr                           76.46%     3.94us  253.71K
FindFirstOfRandomByteSet                          15.01%    20.08us   49.81K
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                       1.23us  811.29K
----------------------------------------------------------------------------
============================================================================
string length 1048576:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        85.07us   11.76K
FindSingleCharRange                                8.92%   953.48us    1.05K
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                    170.23us    5.87K
FindFirstOf2NeedlesNoSSE                         100.01%   170.21us    5.87K
FindFirstOf2NeedlesStd                             5.09%     3.34ms   299.18
FindFirstOf2NeedlesMemchr                        100.02%   170.20us    5.88K
FindFirstOf2NeedlesByteSet                        11.64%     1.46ms   683.69
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                    298.04us    3.36K
FindFirstOf4NeedlesNoSSE                          87.48%   340.68us    2.94K
FindFirstOf4NeedlesStd                             5.68%     5.25ms   190.41
FindFirstOf4NeedlesMemchr                         87.53%   340.51us    2.94K
FindFirstOf4NeedlesByteSet                        20.37%     1.46ms   683.55
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                    298.04us    3.36K
FindFirstOf8NeedlesNoSSE                          43.75%   681.27us    1.47K
FindFirstOf8NeedlesStd                             3.29%     9.07ms   110.24
FindFirstOf8NeedlesMemchr                         43.74%   681.36us    1.47K
FindFirstOf8NeedlesByteSet                        20.37%     1.46ms   683.55
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                   298.03us    3.36K
FindFirstOf16NeedlesNoSSE                         21.83%     1.37ms   732.40
FindFirstOf16NeedlesStd                            1.78%    16.72ms    59.81
FindFirstOf16NeedlesMemchr                        21.83%     1.37ms   732.49
FindFirstOf16NeedlesByteSet                       20.37%     1.46ms   683.60
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                   896.95us    1.11K
FindFirstOf32NeedlesNoSSE                         44.21%     2.03ms   492.89
FindFirstOf32NeedlesStd                            2.67%    33.53ms    29.82
FindFirstOf32NeedlesMemchr                        31.84%     2.82ms   354.97
FindFirstOf32NeedlesByteSet                       44.25%     2.03ms   493.31
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                     1.38ms   725.72
FindFirstOf64NeedlesNoSSE                         67.96%     2.03ms   493.18
FindFirstOf64NeedlesStd                            1.90%    72.34ms    13.82
FindFirstOf64NeedlesMemchr                        24.82%     5.55ms   180.11
FindFirstOf64NeedlesByteSet                       67.97%     2.03ms   493.30
----------------------------------------------------------------------------
FindFirstOfRandomBase                                      657.10us    1.52K
FindFirstOfRandomNoSSE                            31.60%     2.08ms   480.94
FindFirstOfRandomStd                               2.05%    32.07ms    31.18
FindFirstOfRandomMemchr                           24.06%     2.73ms   366.13
FindFirstOfRandomByteSet                          31.56%     2.08ms   480.22
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                     170.28us    5.87K
----------------------------------------------------------------------------
============================================================================

Reviewed By: philipp@fb.com

FB internal diff: D638500

11 years agofbstring: avoid including Likely.h
Andrew Gallagher [Thu, 10 Jan 2013 01:37:57 +0000 (17:37 -0800)]
fbstring: avoid including Likely.h

Summary:
Including Likely.h causes issues when import fbstring into
libstdc++, so provide internal definitions for these macros that
we can undef afterwards.

Test Plan: built folly

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D675366

11 years agoMake FindFirstOf[Offset]Range benchmarks traverse haystack.
Soren Lassen [Mon, 7 Jan 2013 06:37:22 +0000 (22:37 -0800)]
Make FindFirstOf[Offset]Range benchmarks traverse haystack.

Summary:
Doh. Thank you Mike for pointing this out.
Renamed "needle" to "needles" and added DCHECK to clarify the semantics.

Test Plan: Ran benchmark.

Reviewed By: mmcurtiss@fb.com

FB internal diff: D672154

11 years agofolly/comprehensions - fixing exceptions
Rafael Sagula [Fri, 4 Jan 2013 00:54:31 +0000 (16:54 -0800)]
folly/comprehensions - fixing exceptions

Summary:
need to open up the visibility of std::exception, otherwise
try..catch(const std::exception& e) won't work for these cases.

Test Plan: unit tests from D670355

Reviewed By: delong.j@fb.com

FB internal diff: D670633

11 years agoMake folly/fbstring test wchar compatible
Abhinav Vora [Wed, 2 Jan 2013 20:25:31 +0000 (12:25 -0800)]
Make folly/fbstring test wchar compatible

Summary:
(This is a preliminary diff only)

Existing tests will be run again with a folly::basic_fbstring<wchar_t> object.

I have (temporarily) commented out tests that dont work yet.

Test Plan: Test code update only

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D669151

11 years agounbreak fbstring<wchar_t> default constructor (!!!)
Tudor Bosman [Tue, 18 Dec 2012 03:00:40 +0000 (19:00 -0800)]
unbreak fbstring<wchar_t> default constructor (!!!)

Test Plan: folly/test/fbstring_test in debug mode

Reviewed By: sdoroshenko@fb.com

FB internal diff: D661622

11 years agoUnbreak folly.
Florent Thoumie [Mon, 17 Dec 2012 22:12:57 +0000 (14:12 -0800)]
Unbreak folly.

Summary: Extra '#' in there.

Test Plan: fbconfig nagios/plugins && fbmake opt

Reviewed By: carl.moran1@fb.com

FB internal diff: D660977

11 years agoGet rid of some gcc-ism's in Portability.h
Anton Korobeynikov [Sat, 13 Oct 2012 21:27:31 +0000 (01:27 +0400)]
Get rid of some gcc-ism's in Portability.h

Summary:
handle at least clang. It will be better to turn this into
configure check, though.

Test Plan: .

Reviewed By: tudorb@fb.com

FB internal diff: D660139

11 years agoFixed mistake with Makefile.am for spooky tests.
Thomas Whitton [Sat, 17 Nov 2012 11:57:49 +0000 (11:57 +0000)]
Fixed mistake with Makefile.am for spooky tests.

Summary: Tests not compiling due to a copy and paste error in Makefile.am.

Test Plan: .

Reviewed By: tudorb@fb.com

FB internal diff: D660138

11 years agoMake sure there is no signed int overflow
Anton Korobeynikov [Sat, 13 Oct 2012 21:39:24 +0000 (01:39 +0400)]
Make sure there is no signed int overflow

Summary: use proper type for index.

Test Plan: .

Reviewed By: tudorb@fb.com

FB internal diff: D660142

11 years agoMake dynamic::object callable with initializer lists
Jordan DeLong [Mon, 17 Dec 2012 19:12:47 +0000 (11:12 -0800)]
Make dynamic::object callable with initializer lists

Summary:
Using perfect forwarding here prevents the ability to create
dynamic arrays.

Test Plan: Added unit test case that compiles now with this.

Reviewed By: tudorb@fb.com

FB internal diff: D660662

11 years agoFixed a potential deadlock in folly::RWSpinLock
Yang Ni [Sat, 15 Dec 2012 18:05:15 +0000 (10:05 -0800)]
Fixed a potential deadlock in folly::RWSpinLock

Summary:
The current UpgradedHolder implementation may lead to a deadlock when upgrading from a reader lock, because it is blocking.

A reader that has failed to set the UPGRADED bit may block the
winner (upgrader) that has successfully set the UPGRADED bit, while
waiting to upgrade in an infinite loop without releasing its own
reader lock. The upgrader needs to wait for all reader locks to be
released before it can move forward.

This is the code pattern:

{
ReadHolder reader(lock);
UpgradedHolder upgrader(std::move(reader));
WriteHolder writer(std::move(upgrader));
}

To avoid this to happen, removed UpgradedHolder(ReadHolder&&)
constructor and the function that impelments it
unlock_shared_and_lock_upgrade. This would require a programmer explicitly
release a read lock before acquiring an upgrade lock, therefore
avoid the above mentioned deadlock.

In addition, the current folly::RWSpinLock::try_lock_shared()
implementation does not check the UPGRADED bit at all. The UPGRADED bit can be used to avoid starving writers.  This diff fixed this by correctly checking the UPGRADED bit.

Test Plan:
Passed folly unit tests.
Tested in a Facebook service that uses the
folly::RWSpinLock::UpgradedHolder.

Reviewed By: xliux@fb.com

FB internal diff: D659875

11 years agoMake sure the op does not change the sign of the operand
Anton Korobeynikov [Sat, 13 Oct 2012 21:40:58 +0000 (01:40 +0400)]
Make sure the op does not change the sign of the operand

Summary: .

Test Plan: .

Reviewed By: soren@fb.com

FB internal diff: D660143

Blame Revision:

11 years agotrivial typo
Jonathan Wakely [Fri, 16 Nov 2012 12:47:30 +0000 (12:47 +0000)]
trivial typo

Summary: I wouldn't even bother reporting this if github didn't make it so easy!

Test Plan: .

Reviewed By: soren@fb.com

FB internal diff: D660136

11 years agoRemove unnecessary branch in Range::find_first_of(Range,size_t)
Soren Lassen [Sun, 16 Dec 2012 21:46:32 +0000 (13:46 -0800)]
Remove unnecessary branch in Range::find_first_of(Range,size_t)

Summary:
Added benchmarks.

Before:

folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
string length 10:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       2.15ns  464.16M
============================================================================
string length 256:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       1.42ns  704.22M
============================================================================
string length 10240:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       3.72ns  268.70M
============================================================================
string length 10485760:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       5.00ns  199.96M

After:

string length 10:
FindFirstOfRange                                             1.36ns  732.92M
FindFirstOfOffsetRange                                       1.36ns  732.61M
============================================================================
string length 256:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       1.38ns  727.16M
============================================================================
string length 10240:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       1.79ns  558.40M
============================================================================
string length 10485760:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       2.73ns  366.44M

Test Plan: fbconfig folly && fbmake runtests

Reviewed By: delong.j@fb.com

FB internal diff: D660125

11 years agoFix some clang compiler warnings/errors
Gaurav Jain [Thu, 6 Dec 2012 19:26:17 +0000 (11:26 -0800)]
Fix some clang compiler warnings/errors

Summary:
Fixes instances of the following problems:
error: offset of on non-POD type 'folly::fbstring_core<char>::RefCounted'
[-Werror,-Winvalid-offsetof]
Solution: Since the atomic is not a POD I used sizeof() instead to calculate
the offset

warning: C++11 requires lambda with omitted result type to consist of a single
return statement
Solution: Specify a return type

error: in-class initializer for static data member is not a constant expression
Solution: Move initializer

Test Plan: - Compiled folly and ran fbmake runtests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D656963

11 years agoFix bug in Bits<T>::get / set
Tudor Bosman [Thu, 13 Dec 2012 20:16:32 +0000 (12:16 -0800)]
Fix bug in Bits<T>::get / set

Summary:
Everything worked except for getting properly aligned full blocks
because 1ULL << 64 is invalid (the shift amount must be strictly less than
the value size in bits)

Test Plan: test added

Reviewed By: philipp@fb.com

FB internal diff: D657800

11 years agoSilence -Wuninitialized in some cases
Tudor Bosman [Thu, 13 Dec 2012 18:31:51 +0000 (10:31 -0800)]
Silence -Wuninitialized in some cases

Test Plan: compiles

Reviewed By: philipp@fb.com

FB internal diff: D657623

11 years agofolly::padded_sequence -> folly::padded
Tudor Bosman [Wed, 5 Dec 2012 23:51:36 +0000 (15:51 -0800)]
folly::padded_sequence -> folly::padded

Summary: Mechanical.

Test Plan: fbconfig unicorn/test unicorn/diskindex3 unicorn/diskindex4/test common/datastruct:css_tree_test folly/test:padded_test dragon/test:posting_list_test && fbmake opt

Reviewed By: soren@fb.com

FB internal diff: D649539

11 years agoRemoving test code from `first`
Tom Jackson [Fri, 7 Dec 2012 22:32:25 +0000 (14:32 -0800)]
Removing test code from `first`

Summary: TSIA

Test Plan: Unit tests

Reviewed By: kedarb@fb.com

FB internal diff: D652180

11 years agodummy results in stl_vector_test on gcc 4.6
Nicholas Ormrod [Fri, 7 Dec 2012 22:34:19 +0000 (14:34 -0800)]
dummy results in stl_vector_test on gcc 4.6

Summary:
The test doesn't run when GCC < 4.7, however our test framework
needs some output anyways. I've added a placeholder test that does
nothing, but does cause something to be printed.

Test Plan: run fbmake runtests on folly/test/stl_tests/

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D652161

11 years agoAdd converter for containers of pairs
Christopher Berner [Fri, 7 Dec 2012 21:38:28 +0000 (13:38 -0800)]
Add converter for containers of pairs

Summary:
Add specialized dynamic converter for containers of pairs,
which can convert from a list of pairs, or from a object

Test Plan: added a unit test

Reviewed By: njormrod@fb.com

FB internal diff: D650730

11 years agoFBVector 2.0 - now standard compliant
Nicholas Ormrod [Fri, 7 Dec 2012 21:31:55 +0000 (13:31 -0800)]
FBVector 2.0 - now standard compliant

Summary:
This is FBVector 2.0. It supports all of the original FBVector
optimizations and is standard compliant.
Accompanying this diff are two suites, StlVectorTest and Benchmark.
StlVectorTest runs an extensive battery of tests against a vector
implementation per the N3337 standard. In addition to checking normal
correctness, StlVectorTest checks the use of allocators, exception
safety, memory leaks, and type requirements.
Benchmark run a wide range of speed tests between std::vector, the
original fbvector, and the new fbvector.

Test Plan:
First test: run StlVectorTest.
Second test: run Benchmark.
Third test: compile and run some fbcode (e.g. multifeed/).

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D566719

11 years agoAdded two new traits and a way to specify them
Nicholas Ormrod [Wed, 5 Dec 2012 21:15:57 +0000 (13:15 -0800)]
Added two new traits and a way to specify them

Summary:
Added IsBits (has value semantics; can be copied by memcpy and
deleted by free. Implies IsRelocatable) and Is0Initializable (new (ptr)
T() is equivalent to memset(ptr, 0, sizeof(T))).
Converted the boost types for IsRelocatable to std types (now available
from <type_traits>).
Added a new way to specify IsRelocatable, IsBits, and Is0Initializable:
typedef std::true_type <property-name> in your class. No namespace
exiting required. This method also supports inheritance, and may be
overriden in base classes.
Added a test file to test Traits.

Test Plan:
Run new test file. Compile some real-world code (in my case,
multifeed).

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D610996

11 years agoFixing GENERATOR benchmark
Tom Jackson [Tue, 4 Dec 2012 06:18:11 +0000 (22:18 -0800)]
Fixing GENERATOR benchmark

Summary: I forgot fbmake runtests doesn't build all that's configured, oops.

Test Plan: Build folly/experimental/test, run benchmark.

Reviewed By: tudorb@fb.com

FB internal diff: D647191

11 years agofix GroupVarintDecoder::rest()
Philip Pronin [Tue, 4 Dec 2012 05:51:49 +0000 (21:51 -0800)]
fix GroupVarintDecoder::rest()

Summary:
It makes sense to return subpiece of the original data
from ##rest()##.

Test Plan: gv tests

Reviewed By: soren@fb.com

FB internal diff: D647179

11 years agoSimplifying GENERATOR to be like ScopeGuard
Tom Jackson [Tue, 4 Dec 2012 01:07:59 +0000 (17:07 -0800)]
Simplifying GENERATOR to be like ScopeGuard

Summary:
It was previously breaking any time a generator included a comma, which
is pretty stupid. Now, it's modelled after `ScopeGuard`, using a little operator
overloading to get rid of the trailing `)` and sidestepping preprocessor issues.

Test Plan: Unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D646825

11 years agofolly/PaddedSequence.h
Tudor Bosman [Mon, 3 Dec 2012 20:54:57 +0000 (12:54 -0800)]
folly/PaddedSequence.h

Summary:
Code that aids in storing data aligned on block (possibly cache-line)
boundaries, perhaps with padding. There's class Node which represents one
block, and Iterator which, given an iterator to a container of Nodes, gives you
an iterator to the underlying elements.  There's also Adaptor, which converts a
sequence of Node into a sequence of underlying elements. (with enough
functionality to make it useful, although it's not fully STL compatible)

Split off from https://phabricator.fb.com/D641114

Also includes changes to make TypedIOBuf container-like so it can be used with padded_sequence::Adaptor.

I plan to rename this to Padded.h / folly::padded in a separate diff.

Test Plan: test added

Reviewed By: soren@fb.com

FB internal diff: D646249

11 years agotiny fbstring push_back(Char) optimization
Soren Lassen [Mon, 3 Dec 2012 08:28:28 +0000 (00:28 -0800)]
tiny fbstring push_back(Char) optimization

Summary:
I noticed that push_back(Char) was slower for fbstring than
for std::string for long strings and found that I could make
it faster by inlining the call to mutable_data() and
exploit that it's always non-small and non-shared.

Benchmarks before:

./folly/test/FBStringTestBenchmarks.cpp.h       relative  time/iter  iters/s
BM_push_back_string(1)                                      69.42ns   14.41M
BM_push_back_string(23)                                    582.31ns    1.72M
BM_push_back_string(127)                                     1.47us  682.12K
BM_push_back_string(1024)                                    5.52us  181.07K
BM_push_back_fbstring(1)                                     9.55ns  104.74M
BM_push_back_fbstring(23)                                  212.45ns    4.71M
BM_push_back_fbstring(127)                                 864.00ns    1.16M
BM_push_back_fbstring(1024)                                  6.73us  148.52K

and after:

BM_push_back_fbstring(1)                                     9.55ns  104.74M
BM_push_back_fbstring(23)                                  212.45ns    4.71M
BM_push_back_fbstring(127)                                 783.08ns    1.28M
BM_push_back_fbstring(1024)                                  4.03us  248.05K

Test Plan: fbconfig folly/test && fbmake runtests

Reviewed By: tudorb@fb.com

FB internal diff: D646081

11 years agoAdded missing curly braces
Helios Alonso Cabanillas [Fri, 30 Nov 2012 23:14:27 +0000 (15:14 -0800)]
Added missing curly braces

Summary:
Added closing curly braces at 173.
Sorry, must make diff if it's a new commit.

Test Plan: nothing really

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D644925

11 years agoAdd samples to FBVector documentation
Helios Alonso Cabanillas [Fri, 30 Nov 2012 22:50:50 +0000 (14:50 -0800)]
Add samples to FBVector documentation

Summary: Added two samples of use for FBVector in docs

Test Plan: just check if FBVector.md looks good.

Reviewed By: njormrod@fb.com

FB internal diff: D636813

11 years agofolly/stats - fix c++ spec compliance for call to template name
Yiding Jia [Thu, 29 Nov 2012 23:05:39 +0000 (15:05 -0800)]
folly/stats - fix c++ spec compliance for call to template name

Summary:
This code is not strictly correct per c++ spec section 14.2.4:

> When the name of a member template specialization appears after . or -> in a
> postfix-expression or after a nested-name-specifier in a qualified-id, and the
> object or pointer expression of the postfix-expression or the
> nested-name-specifier in the qualified-id depends on a template parameter
> (14.6.2) but does not refer to a member of the current instantiation
> (14.6.2.1), the member template name must be prefixed by the keyword template.
> Otherwise the name is assumed to name a non-template.

This causes clang to complain, but gcc is lax about this, as usual.

Test Plan: compile stuff that use this.

Reviewed By: delong.j@fb.com

FB internal diff: D643515

11 years agofolly/dynamic fix use of incomplete type in template definition
Yiding Jia [Thu, 29 Nov 2012 22:34:41 +0000 (14:34 -0800)]
folly/dynamic fix use of incomplete type in template definition

Summary:
the old code is ill-formed per spec (section 14.6.8):

> If a type used in a non-dependent name is incomplete at the point at which a
> template is defined but is complete at the point at which an instantiation is
> done, and if the completeness of that type affects whether or not the program
> is well-formed or affects the semantics of the program, the program is
> ill-formed; no diagnostic is required.

GCC is lax and allows this, clang gives an error.

Test Plan: compiles.

Reviewed By: delong.j@fb.com

FB internal diff: D643431

11 years agofix std::out_of_range calls to use real constructors
Yiding Jia [Thu, 29 Nov 2012 22:03:25 +0000 (14:03 -0800)]
fix std::out_of_range calls to use real constructors

Summary:
curiously, std::out_of_range doesn't have a zero-argument constructor according
to the spec. This was causing issues in my clang setup...

Test Plan: compiles.

Reviewed By: delong.j@fb.com

FB internal diff: D643363

11 years agofix Traits.md
Tudor Bosman [Thu, 29 Nov 2012 16:58:48 +0000 (08:58 -0800)]
fix Traits.md

Test Plan: looked at the generated html in a browser

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D642998

11 years agoFix output of 128 bit integer to string conversion.
Davide Bolcioni [Wed, 21 Nov 2012 03:27:14 +0000 (19:27 -0800)]
Fix output of 128 bit integer to string conversion.

Summary:
Added specializations of folly::to<String> for __int128_t
and __uint128_t.

Test Plan: Added tests of the above to the integral to string tests.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D636992

11 years agoAdd bytesUsed() to folly::Arena
Sergey Doroshenko [Wed, 21 Nov 2012 03:16:12 +0000 (19:16 -0800)]
Add bytesUsed() to folly::Arena

Summary:
Returns number of bytes "really used by the user", i.e. number of bytes
allocated on the arena via calls to `allocate()`.

Test Plan: compiled, unit tests

Reviewed By: azzolini@fb.com

FB internal diff: D636976

11 years agoSupressing GCC 4.7 warning for Optional
Tom Jackson [Tue, 20 Nov 2012 18:55:08 +0000 (10:55 -0800)]
Supressing GCC 4.7 warning for Optional

Summary:
Supressing the warning for GCC4.7, and supressing the error supressing
the warning in GCC4.6.

Test Plan: Compile, run unit tests on GCC4.6 and GCC4.7

Reviewed By: ldbrandy@fb.com

FB internal diff: D635982

11 years agouse std::underlying_type to support enum classes
Soren Lassen [Sun, 18 Nov 2012 22:43:07 +0000 (14:43 -0800)]
use std::underlying_type to support enum classes

Summary:
Noticed these TODOs in Conv.h and decided to fix them.
Discovered that the underlying_type implementation also
covers enum classes, which didn't work with the pre-existing code.

Test Plan:
fbconfig -r folly --platform=gcc-4.7.1-glibc-2.14.1-fb
fbmake dbg _bin/folly/test/conv_test
_bin/folly/test/conv_test

--platform=gcc-4.6.2-glibc-2.13
fbmake dbg _bin/folly/test/conv_test
_bin/folly/test/conv_test

Reviewed By: tudorb@fb.com

FB internal diff: D634309

11 years agoFix IOBufQueue::preallocate for callers who really wanted a hard max
Alan Frindell [Mon, 19 Nov 2012 21:43:41 +0000 (13:43 -0800)]
Fix IOBufQueue::preallocate for callers who really wanted a hard max

Summary: D633912 broke unicorn because it relied on preallocate having a hard max.  Add an optional hard max parameter and rename maxHint to newAllocationSize.  Pass the hard max in for unicorn

Test Plan: folly and unicorn unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D634894

11 years agoReturn the maximum available space from IOBufQueue::preallocate
Alan Frindell [Fri, 16 Nov 2012 23:49:56 +0000 (15:49 -0800)]
Return the maximum available space from IOBufQueue::preallocate

Summary: IOBufQueue::preallocate currently takes a min and max size, and will return to the caller a buffer with N writable bytes with min <= N <= max.  This is a bit wasteful, since there may be more than max bytes available at the end if the queue with no extra cost.  Now preallocate will return the full amount of contigious space to the caller, even if it is larger than the requested max.

Test Plan: folly and proxygen unit tests

Reviewed By: simpkins@fb.com

FB internal diff: D633912