Autocomplete changes
Brett Wilson
algorithm a bit. Mostly it will stay the same. There are many things
that would be nice to add to the algorithm, but that's not in the cards
now. Historically, there has been a lot of argument about how
autocomplete should be. I'm keeping it basically the same and am not
considering changing that.
This will go in after the alpha.
---
Advertisement: please look at my post about changing anchor behavior
above, I want more feedback.
---
Performance:
I believe that the new implementation will be faster a lot of the time
than the mork implementation. I tried to benchmarck this but
autocomplete was totally b0rken in my non-places build. Pressing
g-backspace really fast seems to indicate that my debug places trunk
build is reasonably faster than my optimized 1.5 build at this search.
Performance varies based on the query, however, whereas with Mork,
performance was always the same.
The biggest performance problem at this point is that the first query
with a given letter often causes the necessary data to be paged in from
disk. In the future, I may try to prime the cache after startup. This
lag is the startup time that we save by being lazy coming back to bite us.
Algorithm changes:
- Added a small boost to bookmarked URLs. This is the same as for typed
URLs. I don't think it will be too noticable. It will help break ties in
the case of similar scores.
- Fewer results. The previous autocomplete returned every match in
history. This made it slow. The new system checks the top 50 results (by
visit count) for each possible prefix (ie prepend "http://",
"http://www.", etc.). The results should be basically the same unless
you scroll down past 50, where the results are pretty useless anyway. I
don't think people will be able to notice this.
- Added a penalty if the typed input matches exactly the beginning of
the spec for unknown prefixes. This will place "fido.com" above
similarly-scored "file://" URLs when you type "fi". We still won't match
"http://" or "https://" if you start typing "ht" (this behavior is
unchanged).
- Suggest the host name first: If the first result has a path (ie
"http://cnn.com/asdfjksldfkjs") we'll add a new result above that out of
thin air without the path. Therefore, you will see "http://cnn.com/",
then "http://cnn.com/asdfjksldfkjs" even if you've never visited
"http://cnn.com/". We don't want to break the case where you often go to
the same URL that has a long path, and therefore want that URL to be
first. So, we only do this if the first result has only been visited a
few times; for frequently visited first suggestions, we won't bump it
from the top spot and the behavior will be the same as today.
- Matches for "www": Previously if you typed in "www" it would never
match "www.mozilla.org" or whatever your favorite site is. We now match
these but with a substantial scoring penalty. Therefore, sites "like
http://washingtonpost.com" will appear before "www.foo.com" unless
"www.foo.com" is one of your absolute favorite sites. By the time you
type "ww" there are basically no matches for anything but "www." and you
get basically your favorite sites in order. The old system wouldn't show
anything, which is strange given how often many people type "www." and
want to go to one of their favorite sites.
Brett
Benjamin Smedberg
> I'm rewriting autocomplete to be more efficient and also tweaking the
> algorithm a bit. Mostly it will stay the same. There are many things
> that would be nice to add to the algorithm, but that's not in the cards
> now. Historically, there has been a lot of argument about how
> autocomplete should be. I'm keeping it basically the same and am not
> considering changing that.
You're talking about urlbar autocomplete in particular, and not the generic
XUL autocomplete APIs, right?
--BDS
Brett Wilson
> You're talking about urlbar autocomplete in particular, and not the
> generic XUL autocomplete APIs, right?
Right, I'm only changing how the URL autocomplete results are generated
and sorted.
I would, however, really like to add favicons to the autocomplete
dropdown in the future, which would require changes to specify images
(style rules won't work here). I think favicons, even sucky ones, help
the history views a lot.
Brett
Nikitas Liogkas
You might want to take a look at an extension I just released, which adds
some more features to the default Autocomplete framework. I believe there
are several good ideas in there.
All in all, I'm happy you people are looking into improving Autocomplete
even more. I think there is definitely more to be done in this area.
</shameless plug>
nikitas
"Brett Wilson" <bre...@gmail.com> wrote in message
news:7aOdnTbd8f8WaofZ...@mozilla.org...
Brett Wilson
> <shameless plug>
> You might want to take a look at an extension I just released, which adds
> some more features to the default Autocomplete framework. I believe there
> are several good ideas in there.
>
> All in all, I'm happy you people are looking into improving Autocomplete
> even more. I think there is definitely more to be done in this area.
> </shameless plug>
>
> nikitas
Your extension has some nice extra features. There is a lot we can add
to autocomplete to make it better along these lines, but unfortunately
it probably won't get into FF2.
Brett
Mossop
just tried out a build with the patch you wrote for this and I have just
one word to say. Awesome. Well maybe I'll expand on that a little...
> I believe that the new implementation will be faster a lot of the time
> than the mork implementation. I tried to benchmarck this but
> autocomplete was totally b0rken in my non-places build. Pressing
> g-backspace really fast seems to indicate that my debug places trunk
> build is reasonably faster than my optimized 1.5 build at this search.
Certainly my brief tested seems plenty fast enough for me.
> - Added a small boost to bookmarked URLs. This is the same as for typed
> URLs. I don't think it will be too noticable. It will help break ties in
> the case of similar scores.
I haven't yet exactly seen this in action but it seems like a very good
idea.
> - Fewer results. The previous autocomplete returned every match in
> history. This made it slow. The new system checks the top 50 results (by
> visit count) for each possible prefix (ie prepend "http://",
> "http://www.", etc.). The results should be basically the same unless
> you scroll down past 50, where the results are pretty useless anyway. I
> don't think people will be able to notice this.
Certainly enough for my use, I'm unlikely to scroll through 20 entries,
let alone 50.
> - Suggest the host name first: If the first result has a path (ie
> "http://cnn.com/asdfjksldfkjs") we'll add a new result above that out of
> thin air without the path. Therefore, you will see "http://cnn.com/",
> then "http://cnn.com/asdfjksldfkjs" even if you've never visited
> "http://cnn.com/". We don't want to break the case where you often go to
> the same URL that has a long path, and therefore want that URL to be
> first. So, we only do this if the first result has only been visited a
> few times; for frequently visited first suggestions, we won't bump it
> from the top spot and the behavior will be the same as today.
This is the single best change from my point of view, something I've
always felt needed to be there.
However my brief testing has seen some issues with this. Typing lxr into
the bar revealed http://lxr.mozilla.org/mozilla as the first entry and
http://lxr.mozilla.org as the second. Using a string of
"lxr.mozilla.org/mozilla/source/browser/components/places/" does not
show "http://lxr.mozilla.org" at the top of the list (not even anywhere
in the list) while
"lxr.mozilla.org/mozilla/source/browser/components/places/s" does.
Other than that minor oddity and of course I releaise that I'm using an
early patch here, this is all looking excellent to me.
Mossop
Nikitas Liogkas
http://www.cs.ucla.edu/~nikitas/acmanager
nikitas
"Nikitas Liogkas" <nik...@cs.ucla.edu> wrote in message
news:eumdnUVQguIpgYbZ...@mozilla.org...
Nikitas Liogkas
anyway...
nikitas
"Brett Wilson" <bre...@gmail.com> wrote in message
news:iIydnY15N6Xkv4bZ...@mozilla.org...
Brett Wilson
>> - Suggest the host name first: If the first result has a path (ie
>> "http://cnn.com/asdfjksldfkjs") we'll add a new result above that out
>> of thin air without the path. Therefore, you will see
>> "http://cnn.com/", then "http://cnn.com/asdfjksldfkjs" even if you've
>> never visited "http://cnn.com/". We don't want to break the case where
>> you often go to the same URL that has a long path, and therefore want
>> that URL to be first. So, we only do this if the first result has only
>> been visited a few times; for frequently visited first suggestions, we
>> won't bump it from the top spot and the behavior will be the same as
>> today.
>
>
> This is the single best change from my point of view, something I've
> always felt needed to be there.
>
> However my brief testing has seen some issues with this. Typing lxr into
> the bar revealed http://lxr.mozilla.org/mozilla as the first entry and
> http://lxr.mozilla.org as the second. Using a string of
> "lxr.mozilla.org/mozilla/source/browser/components/places/" does not
> show "http://lxr.mozilla.org" at the top of the list (not even anywhere
> in the list) while
> "lxr.mozilla.org/mozilla/source/browser/components/places/s" does.
>
> Other than that minor oddity and of course I releaise that I'm using an
> early patch here, this is all looking excellent to me.
Thanks for the feedback. My threshold for not adding a new entry for the
hostname was two in the patch. So anything you've visited more than
twice won't trigger this code. I was thinking that we usually want to
show the destination pages first.
Your comment and some thinking led me to now think that we usually want
to show the host, and only override that for very popular pages. I
changed AUTOCOMPLETE_MAX_TRUNCATION_VISIT to 20 and it seems better. You
might try it with that change.
Brett
Mossop
> Your comment and some thinking led me to now think that we usually want
> to show the host, and only override that for very popular pages. I
> changed AUTOCOMPLETE_MAX_TRUNCATION_VISIT to 20 and it seems better. You
> might try it with that change.
Ah right that makes sense, I'll have an experiment with that.
In the bug you asked how I thought the performance compared with Firefox
1.5. I'm probably not the best person to ask, my machine is reasonably
quick. Yes the initial popup is slower, I'd estimate it at around a
quarter of a second where 1.5 seems almost instantaneous. That is still
plenty fast enough in my opinion. Subsequent changes to the list seems
almost instant and I couldn't say whether this or 1.5 was faster, the
speed is just too quick to gauge.
FYI my system is a 1.7GHz Pentium M with 1GB RAM.
Mossop
Axel Hecht
<...>
> Algorithm changes:
>
> - Added a small boost to bookmarked URLs. This is the same as for typed
> URLs. I don't think it will be too noticable. It will help break ties in
> the case of similar scores.
Regarding typed URLs, could we unboost typed URLs that end in a
redirect? I always see the completion for some forum, and go through the
redirect again, because I'm lazy, or I need to go down in the list to
get to the real one.
> - Fewer results. The previous autocomplete returned every match in
> history. This made it slow. The new system checks the top 50 results (by
> visit count) for each possible prefix (ie prepend "http://",
> "http://www.", etc.). The results should be basically the same unless
> you scroll down past 50, where the results are pretty useless anyway. I
> don't think people will be able to notice this.
My most commonly used autocomplete start is "bugz". I guess I have more,
and the irrelevant entries like "submitted change to attachement.." etc
are in the way with my bug list. And I occasionally need to go to rarely
seen bugs. I may want to use the places UI for that in the future :-)