summaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set_benchmark.cc
Commit message (Collapse)AuthorAge
* Optimize SwissMap for ARM by 3-8% for all operationsGravatar Abseil Team2022-06-06
| | | | | | | | | | | https://pastebin.com/CmnzwUFN The key idea is to avoid using 16 byte NEON and use 8 byte NEON which has lower latency for BitMask::Match. Even though 16 byte NEON achieves higher throughput, in SwissMap it's very important to catch these Matches with low latency as probing on average happens at most once. I also introduced NonIterableMask as ARM has really great cbnz instructions and additional AND on scalar mask had 1 extra latency cycle PiperOrigin-RevId: 453216147 Change-Id: I842c50d323954f8383ae156491232ced55aacb78
* Export of internal Abseil changesGravatar Abseil Team2021-12-13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 07240ca7822d007cdcc79f2c40bd58b2c2010348 by Abseil Team <absl-team@google.com>: Correct the comment from "AlphaNum" to "Arg". PiperOrigin-RevId: 416139192 -- adcba4a6b3763626e1db7b1e8c108b3114903557 by Martijn Vels <mvels@google.com>: Fix NewExternalRep() to require data being non-empty, and remove nullptr return. PiperOrigin-RevId: 416135865 -- c0d14cd918fb16f15d1d84de9284b5c5ecc1f8f2 by Abseil Team <absl-team@google.com>: Fix doc comment for absl::ascii_isprint(). The comment was incorrectly saying that it includes all whitespace. It doesn't; the only whitespace char it includes is ' '. PiperOrigin-RevId: 416112524 -- d83327800159c07002b6865e21232a12463e02dd by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 416099978 -- baf11e9ca42ca9140cdbf8075f971db8d65b1195 by Ilya Tokar <tokarip@google.com>: Prevent compiler from optimizing Group_Match* benchmarks away. Currently we benchmark single store of precomputed value. Not all affected benchmarks show performance changes: BM_Group_Match 0.53ns ± 1% 0.53ns ± 0% -0.42% (p=0.038 n=10+10) BM_Group_MatchEmpty 0.26ns ± 1% 0.26ns ± 1% ~ (p=1.000 n=10+10) BM_Group_MatchEmptyOrDeleted 0.26ns ± 1% 0.26ns ± 1% ~ (p=0.121 n=10+10) BM_Group_CountLeadingEmptyOrDeleted 0.26ns ± 1% 0.45ns ± 0% +70.05% (p=0.000 n=10+8) BM_Group_MatchFirstEmptyOrDeleted 0.26ns ± 0% 0.44ns ± 1% +65.91% (p=0.000 n=8+9) But inspecting the generated code shows the difference, e. g. BM_Group_MatchFirstEmptyOrDeleted Before: add $0xffffffffffffffff,%rbx jne 30 After: pcmpeqd %xmm0,%xmm0 pcmpgtb -0x30(%rbp),%xmm0 pmovmskb %xmm0,%eax add: 0x23$0xffffffffffffffff,%rbx jne 40 PiperOrigin-RevId: 416083515 -- 122fbff893dc4571b3e75e4b241eb4495b925610 by Abseil Team <absl-team@google.com>: Put namespace guard in ABSL_DECLARE_FLAG to make declaring a flag in a namespace a compiler error instead of a linker error. PiperOrigin-RevId: 416036072 -- 020fd8a20f5fa319e948846e003391fcb9e03868 by Ilya Tokar <tokarip@google.com>: Make Cord::InlineRep::set_data unconditionally zero out memory. Currently there is a single case where we don't zero out memory as an optimization. Unconditional zeroing doesn't show any changes in benchmarks, except for the unrelated improvement: BM_CordPartialCopyToCord/1M/1 12.6ns ± 4% 12.6ns ± 4% ~ (p=0.857 n=16+19) BM_CordPartialCopyToCord/1M/128 44.9ns ± 7% 45.0ns ± 3% ~ (p=0.468 n=18+17) BM_CordPartialCopyToCord/1M/1k 64.5ns ± 4% 61.4ns ± 4% -4.82% (p=0.000 n=19+17) BM_CordPartialCopyToCord/1M/8k 139ns ± 3% 128ns ±15% -7.76% (p=0.009 n=17+20) BM_CordPartialCopyToCord/1M/16k 193ns ± 6% 168ns ± 6% -13.17% (p=0.000 n=17+17) BM_CordPartialCopyToCord/4M/16k 199ns ± 4% 177ns ± 4% -11.36% (p=0.000 n=17+18) BM_CordPartialCopyToCord/4M/32k 275ns ± 3% 250ns ± 4% -9.00% (p=0.000 n=18+18) BM_CordPartialCopyToCord/4M/64k 291ns ± 4% 266ns ± 5% -8.53% (p=0.000 n=18+16) BM_CordPartialCopyToCord/4M/128k 322ns ± 5% 291ns ± 4% -9.43% (p=0.000 n=20+18) BM_CordPartialCopyToCord/8M/32k 281ns ± 5% 251ns ± 4% -10.38% (p=0.000 n=20+16) BM_CordPartialCopyToCord/8M/64k 293ns ± 6% 267ns ± 4% -8.87% (p=0.000 n=16+19) BM_CordPartialCopyToCord/8M/128k 334ns ± 3% 305ns ± 2% -8.56% (p=0.000 n=17+16) This is clearly an alignmnet effect since number of the executed instructions is the same: M_CordPartialCopyToCord/1M/1 155 ± 0% 155 ± 0% ~ (all samples are equal) BM_CordPartialCopyToCord/1M/128 446 ± 0% 446 ± 0% ~ (p=0.332 n=36+39) BM_CordPartialCopyToCord/1M/1k 473 ± 0% 473 ± 0% ~ (p=0.969 n=40+40) BM_CordPartialCopyToCord/1M/8k 808 ± 0% 808 ± 0% ~ (p=0.127 n=40+39) BM_CordPartialCopyToCord/1M/16k 957 ± 0% 957 ± 0% ~ (p=0.532 n=40+40) BM_CordPartialCopyToCord/4M/16k 952 ± 0% 952 ± 0% ~ (p=0.686 n=39+39) BM_CordPartialCopyToCord/4M/32k 1.12k ± 0% 1.12k ± 0% ~ (p=0.690 n=40+40) BM_CordPartialCopyToCord/4M/64k 1.23k ± 0% 1.23k ± 0% ~ (p=0.182 n=40+39) BM_CordPartialCopyToCord/4M/128k 1.44k ± 0% 1.44k ± 0% ~ (p=0.711 n=40+40) BM_CordPartialCopyToCord/8M/32k 1.12k ± 0% 1.12k ± 0% ~ (p=0.697 n=40+40) BM_CordPartialCopyToCord/8M/64k 1.23k ± 0% 1.23k ± 0% +0.00% (p=0.049 n=40+40) BM_CordPartialCopyToCord/8M/128k 1.44k ± 0% 1.44k ± 0% ~ (p=0.507 n=40+40) This makes code simpler and doesn't regress performance. PiperOrigin-RevId: 415560574 -- 37305b2690b31682088749e4d62f40d7095bdc54 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 415558737 -- 86aaed569b9e743c1eb813a5f48def978a793db3 by Martijn Vels <mvels@google.com>: Internal change PiperOrigin-RevId: 415515201 -- 6cdb8786cdcb4fa0b8a4b72fc98940877d1fdeff by Abseil Team <absl-team@google.com>: Update SubmitMutexProfileData to accept wait_cycles instead of wait_timestamp PiperOrigin-RevId: 415360871 -- 9f979d307aa16ad09f214e04876cbe84395c0901 by Abseil Team <absl-team@google.com>: absl::flat_hash_set compiles with -Wconversion -Wsign-compare PiperOrigin-RevId: 415357498 -- 9eceb14174708f15e61259d449b214a8a4c7f9e7 by Abseil Team <absl-team@google.com>: Fix AddressIsReadable for the corner case of (aligned) addr == NULL. PiperOrigin-RevId: 415307792 -- 1a39ffe55898375e2d7f88c17c99db5a1b95b313 by Martijn Vels <mvels@google.com>: Internal change PiperOrigin-RevId: 415162872 -- 64378549b110d5f5762185a5906c520fba70f0e7 by Abseil Team <absl-team@google.com>: Fix a typo in the comments PiperOrigin-RevId: 415088461 -- 41aae8322e913b82710153c22b97c611fdb6e1fb by Abseil Team <absl-team@google.com>: Switch from `connect` to `rt_sigreturn` -- the latter is much less problematic for system call sandboxes. PiperOrigin-RevId: 415073965 -- 870c5e3388b6a35611bff538626fe7a1c8c87171 by Abseil Team <absl-team@google.com>: Add ABSL_HAVE_HWADDRESS_SANITIZER and ABSL_HAVE_LEAK_SANITIZER PiperOrigin-RevId: 414871189 -- f213ed60a66b58da7ac40555adfb1d529ff0a4db by Derek Mauro <dmauro@google.com>: Remove reference to __SANITIZE_MEMORY__, which does not exist It appears to have been copied by pattern matching from the ASAN/TSAN code blocks. https://github.com/gcc-mirror/gcc/blob/f47662204de27f7685699eeef89aa173ccf32d85/gcc/cppbuiltin.c#L79-L126 PiperOrigin-RevId: 414806587 -- b152891e73ab515f397ceb53f66c8ee2f33863ea by Abseil Team <absl-team@google.com>: Rollback previous commit: SYS_open is not defined in certain environments. PiperOrigin-RevId: 414521820 -- 5a1cbb282331023902e1374dd0d920c4effbe47f by Abseil Team <absl-team@google.com>: Use syscall(SYS_open, ...) instead of open() to avoid possible symbol interposition. Also add some warning notes. PiperOrigin-RevId: 414508186 -- 1824d6593612710aafdc599a89b0adced7d787f6 by Abseil Team <absl-team@google.com>: Correct aarch64 macro check The macro is __aarch64__, not __arch64__. PiperOrigin-RevId: 414446225 -- a1536a57b64dfd53945d33a01cfc08b18c99c97b by Abseil Team <absl-team@google.com>: Fix backwards comment in the last commit. PiperOrigin-RevId: 414281214 -- 11ac021ba779513667a31cf2563ddafc57d6d913 by Abseil Team <absl-team@google.com>: AddressIsReadable() didn't work correctly on ARM when the given pointer was misaligned at the end of the page. Fix that by aligning the pointer on an 8-byte boundary before checking it. PiperOrigin-RevId: 414203863 GitOrigin-RevId: 07240ca7822d007cdcc79f2c40bd58b2c2010348 Change-Id: If5f129194d59f5c9e5d84efd8cd9e17a70e072ab
* Export of internal Abseil changesGravatar Abseil Team2021-07-28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 69b5d0b2a5adb49a53e51f9da6848eaa484242fe by Derek Mauro <dmauro@google.com>: Changes the absl::Duration factory functions to disallow types that are convertible to int or double, instead requiring that the argument itself is indeed an integer or a floating-point number. This will prevent callers from passing arguments, such as std::atomic<T>. This change is an API break. Information and a tool to fix issues can be found at https://abseil.io/docs/cpp/tools/upgrades/duration-conversions PiperOrigin-RevId: 387153494 -- 786063e438ab6a55ac4baa88ad4d20a8293be52a by Evan Brown <ezb@google.com>: Make ctrl_t be an enum class. This adds type safety, and also when strict aliasing is enabled, the compiler will know that control bytes can't alias non-control bytes. Also make H2() return h2_t. PiperOrigin-RevId: 387120717 -- 7e537aabec1c255d6e7c9d21232c597c1c2077bf by Evan Brown <ezb@google.com>: Add some missing `const` keywords to ctrl_t* function parameters. PiperOrigin-RevId: 386976062 -- da53ac6d91cabd951e81dd0a145e1e52b918955f by Martijn Vels <mvels@google.com>: Change Seek and InitOffset to return nullptr instead of assert / fail. This makes it consistent with the rest of the API (Next, Previous, Skip) and hardens it against invariants that are harder (or less likey) to be upheld correctly by the caller. PiperOrigin-RevId: 386963283 -- a4d1faac020d5025edf53ce81808e5db68da7d89 by Abseil Team <absl-team@google.com>: PC / Backtrace / Symbolization for Emscripten. PiperOrigin-RevId: 386957724 -- 97f2c47d83ba9d3ac89e1f55bd06897686ffd063 by Martijn Vels <mvels@google.com>: Fix static casts ([-Wimplicit-int-conversion]) PiperOrigin-RevId: 386951646 -- 9530c795248543817cbc4013953baa09c35f5e1a by Abseil Team <absl-team@google.com>: Fix incorrect header guard in cord_rep_btree_navigator.h PiperOrigin-RevId: 386907904 -- 90ce5872406df2b7f4c428683741dc13a572267e by Abseil Team <absl-team@google.com>: Small grammar fixes for some StatusCode descriptions. PiperOrigin-RevId: 386906217 -- b30a2fd777f12a04a4d512f37a34614b0d05ce99 by Derek Mauro <dmauro@google.com>: Skip length checking when constructing absl::string_view from std::string. The length check causes unnecessary code bloat. PiperOrigin-RevId: 386857974 -- fa171536c359bfa2a1b80297e844519bb9ee7791 by Martijn Vels <mvels@google.com>: Introduce CordRepBtreeNavigator CordRepBtreeNavigator implements bi-directional navigation over all data edges stored inside a Cord Btree. PiperOrigin-RevId: 386519102 GitOrigin-RevId: 69b5d0b2a5adb49a53e51f9da6848eaa484242fe Change-Id: I1b35188d66133f8cb73d346bc5564aac4e0b3e80
* Export of internal Abseil changesGravatar Abseil Team2021-06-24
| | | | | | | | | | | | | | | | | | -- 2684e80d877b688b8d9e0af1b7acddbadc973152 by Evan Brown <ezb@google.com>: Add an insert codegen function for raw_hash_set_benchmark. PiperOrigin-RevId: 381052237 -- 8394ef3071714a41484cb5b271cba0611d954a7a by Abseil Team <absl-team@google.com>: Optimize raw_hash_set ctor for random-access iterators PiperOrigin-RevId: 380832215 GitOrigin-RevId: 2684e80d877b688b8d9e0af1b7acddbadc973152 Change-Id: Icf7929fdfab50a1b26f3dc5505575363b4f5838d
* Export of internal Abseil changesGravatar Abseil Team2020-12-07
-- ff793052bd01e1e4fcf639f94d7c30c4855a9372 by Evan Brown <ezb@google.com>: Roll forward of btree_iterator refactoring. PiperOrigin-RevId: 346116047 -- 17984679f16e3e2139b0f14fa76f4a6ca16a3ef9 by Chris Kennelly <ckennelly@google.com>: Extend absl::StrContains to accept single character needles. Single characters are more efficient to search for. Extending this API allows the abseil-string-find-str-contains Clang Tidy to include this pattern. The C++ committee has adopted http://wg21.link/P1679 for inclusion in C++23. PiperOrigin-RevId: 346095060 -- ef20b31c501b1dcaa25e244fd8f8aa43dec09bd6 by Jorg Brown <jorg@google.com>: Internal change for cord ring PiperOrigin-RevId: 346087545 -- b70f2c1cb77fc9e733a126e790967d45c5fd1dc7 by Derek Mauro <dmauro@google.com>: Release layout_benchmark PiperOrigin-RevId: 345968909 -- 3a0eda337ee43622f92cfe14c2aa06f72dc71ee5 by Derek Mauro <dmauro@google.com>: Release raw_hash_set_probe_benchmark PiperOrigin-RevId: 345965969 -- abffdb4bb241a2264cb4e73a6262b660bb10447d by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 345733599 -- 7c9e24a71188df945be17fe98f700bdb51f81b16 by Derek Mauro <dmauro@google.com>: Release hash_benchmark PiperOrigin-RevId: 345721635 -- d68f33f17f9a8cd3f6da8eee3870bdb46402cdc8 by Derek Mauro <dmauro@google.com>: Release raw_hash_set_benchmark PiperOrigin-RevId: 345708384 -- 6e6c547d4d1327b226c0ffe8ff34d0aa103ce24b by Abseil Team <absl-team@google.com>: Updates the implementation of InlinedVector to accurately express the value-initialization semantics of the default constructor PiperOrigin-RevId: 345548260 -- 1532424deda97d468444c217cc0fa4614099c7c1 by Evan Brown <ezb@google.com>: Rollback btree_iterator refactoring. PiperOrigin-RevId: 345543900 GitOrigin-RevId: ff793052bd01e1e4fcf639f94d7c30c4855a9372 Change-Id: I719831981fd056de41939f9addfee3d85e3b49b2
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-03 09:15:39 +0000