Optimize parsing of /etc/hosts.

Right now, Chrome won't parse hosts files larger than 64k, since the
parser is kind of slow.  This CL takes some steps to optimize it:

1. Replace nested StringTokenizers with a custom, one-pass parser.
2. Cache the literal IP from the previous line so we can skip parsing
   the same IP address if it's listed many times in a row.
   (Ad-blocking hosts files can have tens or hundreds of thousands of
   entries in a row that all point to 127.0.0.1.)
3. Replace std::map with a base::hash_map.

A rough benchmark suggests that these changes make ParseHosts run about
three times faster on a large (close to 6M and close to 200k lines)
ad-blocking hosts file.

TODO:
1. Break this into separate CLs, if we want?
2. Store the actual hosts file (converted to lowercase) in memory and
   store StringPieces pointing into it, instead of making copies of
   every hostname.
3. Fix on Android (it doesn't implement == on hash_map?).

BUG=107810
TEST=net_unittests still pass; may want nastier parsing tests

Review URL: https://chromiumcodereview.appspot.com/18407003

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@210237 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 33 insertions, 1 deletions

diff --git a/net/dns/dns_hosts.h b/net/dns/dns_hosts.h
index a75bb27..c2b2909 100644
--- a/net/dns/dns_hosts.h
+++ b/net/dns/dns_hosts.h
@@ -10,12 +10,39 @@
 #include <utility>
 #include <vector>
 
+#include "base/basictypes.h"
+#include "base/containers/hash_tables.h"
 #include "base/files/file_path.h"
 #include "net/base/address_family.h"
 #include "net/base/net_export.h"
 #include "net/base/net_util.h"  // can't forward-declare IPAddressNumber
 
 namespace net {
+  typedef std::pair<std::string, AddressFamily> DnsHostsKey;
+};
+
+namespace BASE_HASH_NAMESPACE {
+#if defined(COMPILER_GCC)
+
+template<>
+struct hash<net::DnsHostsKey> {
+  std::size_t operator()(const net::DnsHostsKey& key) const {
+    hash<base::StringPiece> string_piece_hash;
+    return string_piece_hash(key.first) + key.second;
+  }
+};
+
+#elif defined(COMPILER_MSVC)
+
+inline size_t hash_value(const net::DnsHostsKey& key) {
+  return hash_value(key.first) + key.second;
+}
+
+#endif  // COMPILER
+
+}  // namespace BASE_HASH_NAMESPACE
+
+namespace net {
 
 // Parsed results of a Hosts file.
 //
@@ -27,8 +54,13 @@ namespace net {
 // 127.0.0.1 localhost
 // 10.0.0.1 localhost
 // The expected resolution of localhost is 127.0.0.1.
-typedef std::pair<std::string, AddressFamily> DnsHostsKey;
+#if !defined(OS_ANDROID)
+typedef base::hash_map<DnsHostsKey, IPAddressNumber> DnsHosts;
+#else
+// Android's hash_map doesn't support ==, so fall back to map.  (Chromium on
+// Android doesn't use the built-in DNS resolver anyway, so it's irrelevant.)
 typedef std::map<DnsHostsKey, IPAddressNumber> DnsHosts;
+#endif
 
 // Parses |contents| (as read from /etc/hosts or equivalent) and stores results
 // in |dns_hosts|. Invalid lines are ignored (as in most implementations).