Consider implementing V4Store::GetMatchingHashPrefix with std::binary_search |
|||
Issue descriptionMy guess is that just using std::binary_search with a custom iterator could be better performing than the current custom recursive solution. The custom iterator is necessary since the backing array is a single std::string, with each hash "element" a fixed length substring. I noticed this in some Linux traces, might be worthwhile to write a benchmark.
,
Dec 1 2017
Sure I can own this, although I can't make any guarantees about actually doing it :D The only annoying thing is writing a custom iterator that supports random access is a bunch of boilerplate. I do think it would be an overall code health with though since a custom iterator is almost certainly easier to reason about than a hand-rolled binary search.
,
Mar 12 2018
Worked on this a bit today and wrote a benchmark. Using a custom iterator + std::binary search yields a 30-40% improvement on a store with 2 million 4-byte prefixes. I'll upload a CL which includes the benchmark I used.
,
Mar 14 2018
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/efc929346c9e9bca7cb761beaddd4f2291e4c9b0 commit efc929346c9e9bca7cb761beaddd4f2291e4c9b0 Author: Charles Harrison <csharrison@chromium.org> Date: Wed Mar 14 00:56:35 2018 [safe-browsing] Log prefix check in microseconds Most prefix checks take between 0 and 1 ms. This CL improves the resolution by logging the check in micros. The CL also removes the SB2.FilterCheck metric which is not really needed anymore. Bug: 787092 Change-Id: I18a81d6eb7891f5a4c8c6fd6e7e956dc653d5379 Reviewed-on: https://chromium-review.googlesource.com/960248 Commit-Queue: Charlie Harrison <csharrison@chromium.org> Reviewed-by: Ilya Sherman <isherman@chromium.org> Reviewed-by: Varun Khaneja <vakh@chromium.org> Cr-Commit-Position: refs/heads/master@{#542976} [modify] https://crrev.com/efc929346c9e9bca7cb761beaddd4f2291e4c9b0/chrome/browser/safe_browsing/local_database_manager.cc [modify] https://crrev.com/efc929346c9e9bca7cb761beaddd4f2291e4c9b0/components/safe_browsing/db/v4_local_database_manager.cc [modify] https://crrev.com/efc929346c9e9bca7cb761beaddd4f2291e4c9b0/tools/metrics/histograms/histograms.xml
,
Mar 15 2018
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/178097512c9eb5e93746f45349ed05860fd82a74 commit 178097512c9eb5e93746f45349ed05860fd82a74 Author: Charles Harrison <csharrison@chromium.org> Date: Thu Mar 15 16:15:48 2018 [safe-browsing] prefix matching improvements and perftest This CL does a few things: 1. Replaces HashPrefixMatches which was implemented with a custom binary search with a custom iterator and std::binary_search. 2. Adds a perftest stress testing this method. Running the perftest before and after the binary_search change shows that using binary_search improves performance by 30-40%. This was measured on Linux using a release (non-official) build. It is also imo a code health win, as an iterator is easier to reason about than a custom binsearch algorithm. Bug: 787092 Change-Id: Ic8be26b11ef750c70ee241dfb2718a3c0855fc8c Reviewed-on: https://chromium-review.googlesource.com/959623 Commit-Queue: Charlie Harrison <csharrison@chromium.org> Reviewed-by: Scott Violet <sky@chromium.org> Reviewed-by: Varun Khaneja <vakh@chromium.org> Cr-Commit-Position: refs/heads/master@{#543391} [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/BUILD.gn [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/BUILD.gn [add] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/prefix_iterator.cc [add] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/prefix_iterator.h [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/v4_store.cc [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/v4_store.h [add] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/v4_store_perftest.cc [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/v4_store_unittest.cc [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/v4_test_util.cc [modify] https://crrev.com/178097512c9eb5e93746f45349ed05860fd82a74/components/safe_browsing/db/v4_test_util.h
,
Mar 22 2018
On recent canaries it looks like we're improving the 99.9th %ile by ~50% (from 2ms to 1ms). 99.99th doesn't look terribly different but it's noisy. Marking as fixed for now. |
|||
►
Sign in to add a comment |
|||
Comment 1 by nparker@chromium.org
, Dec 1 2017Owner: csharrison@chromium.org
Status: Assigned (was: Untriaged)