Most visited thumbnails and favicons need id-based urls

Most visited thumbnails and favicons need id-based urls

Extends ThumbnailSouce and FaviconSource to serve requests of
the form:
  chrome-search://favicon/<id>
  chrome-search://thumb/<id>

BUG=180371
TEST=Manual, look at NTP Most Visited on 1993
R=sreeram@chromium.org

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=187480

[dhollowa, 2013-03-09 00:03:10]

This is not quite ready for full review.  Sreeram, posting so you can advise on
the click-handling for the Most Visited items.

Thanks.

[dhollowa, 2013-03-09 01:43:17]

Sreeram, the ThumbnailSource is working on both UI and IO threads now.  PTAL.

[dhollowa, 2013-03-11 15:19:38]

+palmer -> chrome/common/render_messages.h
+estade -> chrome/browser/ui/webui/...

[dhollowa, 2013-03-11 16:10:29]

On 2013/03/11 15:19:38, dhollowa wrote:
> +palmer -> chrome/common/render_messages.h
> +estade -> chrome/browser/ui/webui/...

[sreeram, 2013-03-11 17:18:18]

First glance looks okay; will review in more detail shortly. Main comment is
that the map in InstantService grows unbounded (slowly, but surely). We should
add a mechanism to drop old entries somehow (it isn't reasonable to ask the user
to restart the browser to achieve that effect).

[Evan Stade, 2013-03-11 19:47:07]

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:52: // Returns true if the |url| is
known, and |restricted_id| is set.
this comment format doesn't make sense to me. What is "known"? "is set" sounds
like it's something that may have happened before you pass the parameter.
"Returns false otherwise" is implied.

How about: If there is a mapping for |url|, sets |restricted_id| and returns
true.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:54: bool GetRestrictedIDForURL(const
GURL& url, uint64 *restricted_id);
asterisk always on left

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:77: std::map<uint64, GURL>
id_to_url_map_;
what kind of ID is this?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
File chrome/browser/ui/webui/ntp/thumbnail_source.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
chrome/browser/ui/webui/ntp/thumbnail_source.h:52: // Transient copy of the
request in play.  Valid between
one space after period.

[dhollowa, 2013-03-11 20:05:23]

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:52: // Returns true if the |url| is
known, and |restricted_id| is set.
On 2013/03/11 19:47:08, Evan Stade wrote:
> this comment format doesn't make sense to me. What is "known"? "is set" sounds
> like it's something that may have happened before you pass the parameter.
> "Returns false otherwise" is implied.
> 
> How about: If there is a mapping for |url|, sets |restricted_id| and returns
> true.

Done.  And below.  (Thanks for the better wording.)

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:54: bool GetRestrictedIDForURL(const
GURL& url, uint64 *restricted_id);
On 2013/03/11 19:47:08, Evan Stade wrote:
> asterisk always on left

Done.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:77: std::map<uint64, GURL>
id_to_url_map_;
On 2013/03/11 19:47:08, Evan Stade wrote:
> what kind of ID is this?

I'm not quite sure what you're asking here.  It is a restricted id.  Are you
looking for better comments, or objecting to the shortened member name and you'd
prefer |url_to_restricted_id_map_|?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
File chrome/browser/ui/webui/ntp/thumbnail_source.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
chrome/browser/ui/webui/ntp/thumbnail_source.h:52: // Transient copy of the
request in play.  Valid between
On 2013/03/11 19:47:08, Evan Stade wrote:
> one space after period.

Done.

[palmer, 2013-03-11 20:42:31]

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_controller.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_controller.cc:200: bool
GetURLForRestrictedId(Profile* profile, uint64 restricted_id, GURL* url) {
|profile| should be declared const, or const & — it's not an out parameter.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_controller.cc:209: size_t
GetRestrictedIDForURL(Profile* profile, const GURL& url) {
const |profile|.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_controller.cc:210: InstantService*
instant_service =
Perhaps the caller of these two functions should pass a const InstantService*
(or &), instead of Profile.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:53:
InstantServiceFactory::GetForProfile(profile);
Seems like you can make |profile| const?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:58: if (base::StringToUint64(path,
&restricted_id)) {
I see. You should add this expectation to the documentation for this function in
the .h file.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:96: last_url_id_++;
Since incrementation is your ID creation discipline, you could make
id_to_url_map_ a vector and save some space. Also, this means you're never going
to really use up the uint64 space; you could probably use uint16 and do just as
well (again saving a tiny amount of space). In fact the maximum # of entries is
probably well below 2**16 - 1?

uint64 would make sense if you intended to generate the IDs randomly (for
example, as a way to avoid keeping last_url_id_ state).

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:97:
id_to_url_map_.insert(std::make_pair(last_url_id_, url));
Why not use the usual map[key] = value syntax?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:31: // form.  If path is a restricted
ID and we have a URL for it, then
What kind of path? What is in these strings?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:33: static const std::string
MaybeTranslateInstantPath(Profile* profile,
Can |profile| be const?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/fa...
File chrome/browser/ui/webui/favicon_source.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/fa...
chrome/browser/ui/webui/favicon_source.cc:98: raw_path);
NIT: This might all fit on one line?

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
File chrome/browser/ui/webui/ntp/thumbnail_source.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
chrome/browser/ui/webui/ntp/thumbnail_source.cc:27: const std::string
MaybeTranslateInstantPath(
This is (or is nearly) duplicate code. Unify it by making this function public
and having InstantService::MaybeTranslateInstantPath call into it?

https://codereview.chromium.org/12732005/diff/3001/chrome/renderer/searchbox/...
File chrome/renderer/searchbox/searchbox_extension.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/renderer/searchbox/...
chrome/renderer/searchbox/searchbox_extension.cc:68: ostr <<
"chrome-search://thumb/" << restricted_id;
This seems kind of heavy-weight (including having to convert it to a string,
below). Maybe just use base/stringprintf.h (already #included)?

https://codereview.chromium.org/12732005/diff/3001/chrome/renderer/searchbox/...
chrome/renderer/searchbox/searchbox_extension.cc:893: SearchBox* search_box =
SearchBox::Get(render_view);
Can |search_box| be declared const?

[Evan Stade, 2013-03-11 21:01:27]

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:48: // If |url| is known the exiting
restricted ID is returned.  Otherwise a new
sp: existing

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:77: std::map<uint64, GURL>
id_to_url_map_;
On 2013/03/11 20:05:23, dhollowa wrote:
> On 2013/03/11 19:47:08, Evan Stade wrote:
> > what kind of ID is this?
> 
> I'm not quite sure what you're asking here.  It is a restricted id.  Are you
> looking for better comments, or objecting to the shortened member name and
you'd
> prefer |url_to_restricted_id_map_|?

I don't know what a restricted ID is. By looking at other parts of your patch
(which would be hard to find once the code is committed), I find the comment:

// A private identifier used on the browser side when retrieving assets.

this provides some assistance, except it seems like the identifier is not
private; the instant page actually knows the ID but doesn't know what URL it
refers to. So something like opaque_id (with comments as to its purpose) would
make more sense, if I'm understanding it correctly.

[dhollowa, 2013-03-11 21:29:27]

On 2013/03/11 17:18:18, sreeram wrote:
> First glance looks okay; will review in more detail shortly. Main comment is
> that the map in InstantService grows unbounded (slowly, but surely). We should
> add a mechanism to drop old entries somehow (it isn't reasonable to ask the
user
> to restart the browser to achieve that effect).

Added code to cull the IDs/URLs as they get culled from the History backend.

[sreeram, 2013-03-11 22:39:12]

instant and searchbox lgtm

[dhollowa, 2013-03-11 23:27:59]

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_controller.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_controller.cc:200: bool
GetURLForRestrictedId(Profile* profile, uint64 restricted_id, GURL* url) {
On 2013/03/11 20:42:31, Chris P. wrote:
> |profile| should be declared const, or const & — it's not an out parameter.

This is endemic in Chrome code.  Pretty much nowhere supports const Profile.  So
doing anywhere becomes a viral nightmare.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_controller.cc:209: size_t
GetRestrictedIDForURL(Profile* profile, const GURL& url) {
On 2013/03/11 20:42:31, Chris P. wrote:
> const |profile|.

Ditto.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_controller.cc:210: InstantService*
instant_service =
On 2013/03/11 20:42:31, Chris P. wrote:
> Perhaps the caller of these two functions should pass a const InstantService*
> (or &), instead of Profile.

Pushing that up to the caller becomes quite cluttered.  I could keep a cached
member variable for a new |instant_service_| but that feels like overkill for
this modest replication.  If this pattern continues to grow I will do so
however.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:53:
InstantServiceFactory::GetForProfile(profile);
On 2013/03/11 20:42:31, Chris P. wrote:
> Seems like you can make |profile| const?

Difficult.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:58: if (base::StringToUint64(path,
&restricted_id)) {
On 2013/03/11 20:42:31, Chris P. wrote:
> I see. You should add this expectation to the documentation for this function
in
> the .h file.

Done.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:96: last_url_id_++;
On 2013/03/11 20:42:31, Chris P. wrote:
> Since incrementation is your ID creation discipline, you could make
> id_to_url_map_ a vector and save some space. Also, this means you're never
going
> to really use up the uint64 space; you could probably use uint16 and do just
as
> well (again saving a tiny amount of space). In fact the maximum # of entries
is
> probably well below 2**16 - 1?
> 
> uint64 would make sense if you intended to generate the IDs randomly (for
> example, as a way to avoid keeping last_url_id_ state).

It is a time/space trade-off yes.  I'd prefer to keep it as is since the savings
are minimal and the convenience is large not having to search linearly through
lists.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:97:
id_to_url_map_.insert(std::make_pair(last_url_id_, url));
On 2013/03/11 20:42:31, Chris P. wrote:
> Why not use the usual map[key] = value syntax?

Done.  Much better, thanks.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:31: // form.  If path is a restricted
ID and we have a URL for it, then
On 2013/03/11 20:42:31, Chris P. wrote:
> What kind of path? What is in these strings?

Done.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:33: static const std::string
MaybeTranslateInstantPath(Profile* profile,
On 2013/03/11 20:42:31, Chris P. wrote:
> Can |profile| be const?

No, very difficult as mentioned.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:48: // If |url| is known the exiting
restricted ID is returned.  Otherwise a new
On 2013/03/11 21:01:27, Evan Stade wrote:
> sp: existing

Done.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.h:77: std::map<uint64, GURL>
id_to_url_map_;
On 2013/03/11 21:01:27, Evan Stade wrote:
> On 2013/03/11 20:05:23, dhollowa wrote:
> > On 2013/03/11 19:47:08, Evan Stade wrote:
> > > what kind of ID is this?
> > 
> > I'm not quite sure what you're asking here.  It is a restricted id.  Are you
> > looking for better comments, or objecting to the shortened member name and
> you'd
> > prefer |url_to_restricted_id_map_|?
> 
> I don't know what a restricted ID is. By looking at other parts of your patch
> (which would be hard to find once the code is committed), I find the comment:
> 
> // A private identifier used on the browser side when retrieving assets.
> 
> this provides some assistance, except it seems like the identifier is not
> private; the instant page actually knows the ID but doesn't know what URL it
> refers to. So something like opaque_id (with comments as to its purpose) would
> make more sense, if I'm understanding it correctly.

I've changed to most_visited_item_id to make things clearer.   And renamed
methods accordingly.  I've left the 'opaque' terminology off as that seemed
implied by the 'id' part.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/fa...
File chrome/browser/ui/webui/favicon_source.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/fa...
chrome/browser/ui/webui/favicon_source.cc:98: raw_path);
On 2013/03/11 20:42:31, Chris P. wrote:
> NIT: This might all fit on one line?

Not quite, no.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
File chrome/browser/ui/webui/ntp/thumbnail_source.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/ui/webui/nt...
chrome/browser/ui/webui/ntp/thumbnail_source.cc:27: const std::string
MaybeTranslateInstantPath(
On 2013/03/11 20:42:31, Chris P. wrote:
> This is (or is nearly) duplicate code. Unify it by making this function public
> and having InstantService::MaybeTranslateInstantPath call into it?

I considered that, but the two code paths are on different threads and have
quite different inputs.  So I opted to keep them separate (with according
DCHECKS).

But I agree, they are super-similar, so I've moved this "IO" version into the
InstantService so the two parallel implementations are less likely to drift.

https://codereview.chromium.org/12732005/diff/3001/chrome/renderer/searchbox/...
File chrome/renderer/searchbox/searchbox_extension.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/renderer/searchbox/...
chrome/renderer/searchbox/searchbox_extension.cc:68: ostr <<
"chrome-search://thumb/" << restricted_id;
On 2013/03/11 20:42:31, Chris P. wrote:
> This seems kind of heavy-weight (including having to convert it to a string,
> below). Maybe just use base/stringprintf.h (already #included)?

Done.  I was blindly copy/pasting...

https://codereview.chromium.org/12732005/diff/3001/chrome/renderer/searchbox/...
chrome/renderer/searchbox/searchbox_extension.cc:893: SearchBox* search_box =
SearchBox::Get(render_view);
On 2013/03/11 20:42:31, Chris P. wrote:
> Can |search_box| be declared const?

Yes. Done.

[palmer, 2013-03-11 23:47:17]

Personally I would make the performance improvement before committing. But not
doing so is not a deal-breaker, so LGTM.

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
File chrome/browser/instant/instant_service.cc (right):

https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
chrome/browser/instant/instant_service.cc:96: last_url_id_++;
On 2013/03/11 23:27:59, dhollowa wrote:
> On 2013/03/11 20:42:31, Chris P. wrote:
> > Since incrementation is your ID creation discipline, you could make
> > id_to_url_map_ a vector and save some space. Also, this means you're never
> going
> > to really use up the uint64 space; you could probably use uint16 and do just
> as
> > well (again saving a tiny amount of space). In fact the maximum # of entries
> is
> > probably well below 2**16 - 1?
> > 
> > uint64 would make sense if you intended to generate the IDs randomly (for
> > example, as a way to avoid keeping last_url_id_ state).
> 
> It is a time/space trade-off yes.  I'd prefer to keep it as is since the
savings
> are minimal and the convenience is large not having to search linearly through
> lists.

I'm only suggesting using a vector for id_to_url_map_; we'd still want to use a
map for the reverse mapping, precisely to avoid O(N) lookup. But a vector would
be a notable savings in both space and (micro-benchmarked) time (O(1) vs. (O(log
N) of std::map's balanced tree).

Since we had that thread about keeping Chrome's memory down, I thought I'd bring
it up. A map costs you significantly more memory per item than a vector; you
have to store the key (in a std::pair), and you have to store at least two
pointers per node (left and right children), and possibly tree balancing
overhead (like red vs. black status of each node).

Performance aside, I'm more concerned about the implied API contract of uint64 —
in this context, it seems to mean "almost a GUID", because it's so obvious that
we will never really have 2**64 - 1 URLs in this map. And yet it's not an
almost-GUID; the IDs are sequential. So, shrinking the size of the key removes
that potential confusion, plus it increases your memory savings even further.

[dhollowa, 2013-03-11 23:56:45]

On 2013/03/11 23:47:17, Chris P. wrote:
> Personally I would make the performance improvement before committing. But not
> doing so is not a deal-breaker, so LGTM.
> 
>
https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
> File chrome/browser/instant/instant_service.cc (right):
> 
>
https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
> chrome/browser/instant/instant_service.cc:96: last_url_id_++;
> On 2013/03/11 23:27:59, dhollowa wrote:
> > On 2013/03/11 20:42:31, Chris P. wrote:
> > > Since incrementation is your ID creation discipline, you could make
> > > id_to_url_map_ a vector and save some space. Also, this means you're never
> > going
> > > to really use up the uint64 space; you could probably use uint16 and do
just
> > as
> > > well (again saving a tiny amount of space). In fact the maximum # of
entries
> > is
> > > probably well below 2**16 - 1?
> > > 
> > > uint64 would make sense if you intended to generate the IDs randomly (for
> > > example, as a way to avoid keeping last_url_id_ state).
> > 
> > It is a time/space trade-off yes.  I'd prefer to keep it as is since the
> savings
> > are minimal and the convenience is large not having to search linearly
through
> > lists.
> 
> I'm only suggesting using a vector for id_to_url_map_; we'd still want to use
a
> map for the reverse mapping, precisely to avoid O(N) lookup. But a vector
would
> be a notable savings in both space and (micro-benchmarked) time (O(1) vs.
(O(log
> N) of std::map's balanced tree).
> 
> Since we had that thread about keeping Chrome's memory down, I thought I'd
bring
> it up. A map costs you significantly more memory per item than a vector; you
> have to store the key (in a std::pair), and you have to store at least two
> pointers per node (left and right children), and possibly tree balancing
> overhead (like red vs. black status of each node).
> 
> Performance aside, I'm more concerned about the implied API contract of uint64
—
> in this context, it seems to mean "almost a GUID", because it's so obvious
that
> we will never really have 2**64 - 1 URLs in this map. And yet it's not an
> almost-GUID; the IDs are sequential. So, shrinking the size of the key removes
> that potential confusion, plus it increases your memory savings even further.

Understood Chris, yes.  Points taken.  We have some other use of uint64 for
id-like things.  So I'll take it as an action to optimize these once we've
settled on the behavior.  Thanks for the insights here.

[gideonwald, 2013-03-11 23:59:05]

Evan, your approval here would likely let us make the Dev cut. Any chance you
have time to take a (third, I now see) look at this one to see whether David's
renaming makes sense to you? I apologize for bugging you both on chat and on the
review!

Chris, thank you so much again for your speedy help.

On 2013/03/11 23:56:45, dhollowa wrote:
> On 2013/03/11 23:47:17, Chris P. wrote:
> > Personally I would make the performance improvement before committing. But
not
> > doing so is not a deal-breaker, so LGTM.
> > 
> >
>
https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
> > File chrome/browser/instant/instant_service.cc (right):
> > 
> >
>
https://codereview.chromium.org/12732005/diff/3001/chrome/browser/instant/ins...
> > chrome/browser/instant/instant_service.cc:96: last_url_id_++;
> > On 2013/03/11 23:27:59, dhollowa wrote:
> > > On 2013/03/11 20:42:31, Chris P. wrote:
> > > > Since incrementation is your ID creation discipline, you could make
> > > > id_to_url_map_ a vector and save some space. Also, this means you're
never
> > > going
> > > > to really use up the uint64 space; you could probably use uint16 and do
> just
> > > as
> > > > well (again saving a tiny amount of space). In fact the maximum # of
> entries
> > > is
> > > > probably well below 2**16 - 1?
> > > > 
> > > > uint64 would make sense if you intended to generate the IDs randomly
(for
> > > > example, as a way to avoid keeping last_url_id_ state).
> > > 
> > > It is a time/space trade-off yes.  I'd prefer to keep it as is since the
> > savings
> > > are minimal and the convenience is large not having to search linearly
> through
> > > lists.
> > 
> > I'm only suggesting using a vector for id_to_url_map_; we'd still want to
use
> a
> > map for the reverse mapping, precisely to avoid O(N) lookup. But a vector
> would
> > be a notable savings in both space and (micro-benchmarked) time (O(1) vs.
> (O(log
> > N) of std::map's balanced tree).
> > 
> > Since we had that thread about keeping Chrome's memory down, I thought I'd
> bring
> > it up. A map costs you significantly more memory per item than a vector; you
> > have to store the key (in a std::pair), and you have to store at least two
> > pointers per node (left and right children), and possibly tree balancing
> > overhead (like red vs. black status of each node).
> > 
> > Performance aside, I'm more concerned about the implied API contract of
uint64
> —
> > in this context, it seems to mean "almost a GUID", because it's so obvious
> that
> > we will never really have 2**64 - 1 URLs in this map. And yet it's not an
> > almost-GUID; the IDs are sequential. So, shrinking the size of the key
removes
> > that potential confusion, plus it increases your memory savings even
further.
> 
> Understood Chris, yes.  Points taken.  We have some other use of uint64 for
> id-like things.  So I'll take it as an action to optimize these once we've
> settled on the behavior.  Thanks for the insights here.

[Evan Stade, 2013-03-12 01:30:23]

lgtm

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/instant/in...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/instant/in...
chrome/browser/instant/instant_service.h:81: // IDs if |all_history| is true. 
|deleted_ids| is filled with the newly
I would turn this into 2 functions, one which deletes some, and one which
deletes all.

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/instant/in...
chrome/browser/instant/instant_service.h:92: // A mapping of Most Visited IDs to
URLs.  Used to hide Most Visted and
nit: Visited

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/ui/webui/f...
File chrome/browser/ui/webui/favicon_source.cc (right):

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/ui/webui/f...
chrome/browser/ui/webui/favicon_source.cc:96: // chrome-search://favicon/<rid>,
where rid is a uint64.
nit: rid no longer makes sense here

[dhollowa, 2013-03-12 01:48:07]

Thanks for the fast turn-around Evan.  Much appreciated.

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/instant/in...
File chrome/browser/instant/instant_service.h (right):

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/instant/in...
chrome/browser/instant/instant_service.h:81: // IDs if |all_history| is true. 
|deleted_ids| is filled with the newly
On 2013/03/12 01:30:23, Evan Stade wrote:
> I would turn this into 2 functions, one which deletes some, and one which
> deletes all.

Done.

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/instant/in...
chrome/browser/instant/instant_service.h:92: // A mapping of Most Visited IDs to
URLs.  Used to hide Most Visted and
On 2013/03/12 01:30:23, Evan Stade wrote:
> nit: Visited

Done.

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/ui/webui/f...
File chrome/browser/ui/webui/favicon_source.cc (right):

https://codereview.chromium.org/12732005/diff/21005/chrome/browser/ui/webui/f...
chrome/browser/ui/webui/favicon_source.cc:96: // chrome-search://favicon/<rid>,
where rid is a uint64.
On 2013/03/12 01:30:23, Evan Stade wrote:
> nit: rid no longer makes sense here

Done.

[dhollowa, 2013-03-12 03:56:15]

Committed patchset #9 manually as r187480.