Camino

Since this is the last week of Summer of Code, I plan to write as much as I can since it will be my last chance to do so : (

First, a quick overview of where we’re at. Basically, a lot of stuff got put on hold while I continue to work on the speed issues of autocomplete with a gigantic history database. I know I have spent a long time working on this issue, but I’ve rewritten the whole autocomplete system multiple times in order to get this right. And once I do get it right, some of the previous problems with autocomplete will evaporate. For example, autocompleting from an arbitrary domain fragment should work. Bookmarks will always show up under bookmarks, instead of sometimes showing up under history. And the autocomplete window shouldn’t randomly pop up, although I’m making no promises about that one because I don’t really know what caused it.

A few things I wanted to get to, but that got put on hold: dealing with redirected URLs and improving the autocomplete ranking. There are some cosmetic things I wanted to do, too, but those are probably last priority (although the most fun!). Of course there is the whole second half of my proposal (ahem, social bookmarking), but that will have to be put on hold as well until the basics of autocomplete are stronger. If I had dreams about Camino, I’m pretty sure they would involve integrating it with social bookmarking/media sites and implementing one-click bookmarking. Someday, I plan to make these things happen.

Searching the URLs and (sometimes very long) titles of tens of thousands of websites very fast is not an easy problem. But, I think I’ve come up with at least the beginnings of a solution. Here is a movie of title searching 20,000+ websites in Camino:

It is fast. However:

• Does not search URLs yet (although that’s the easy part)
• Preloads a bunch of data
• I have no idea if this will work in languages other than English

Patch forthcoming…

It has been brought to my attention that the recently-landed autocomplete overhaul I’ve been working on is slow. It’s not “horrendously” slow, at least not for what I presume to be the majority of Camino users—it’s only slow if you happen to have a VERY large collection of bookmarks and/or history. How large is very large? Well, probably around 10,000 of either will do the trick, but that probably depends on how fast your machine is. After spending a couple of days doing some tests, these are my observations:

• Regular expressions are slow. The previous autocomplete implementation did not use them. It used a brute-force method of chopping up the URLs and comparing what’s left over to the search string. Regular expressions are a much more elegant way of matching, not to mention it’s also easier to develop/maintain. If you are doing a title search, they are pretty much required. But they are slow.
• Title matching is slow. If you are solely matching to the beginning of a URL, there are a number of tricks you can employ to speed up matching. If the user types in the letter “a”, all of the matching URLs probably look like “http://www.a…” or “http://a”. You can pull all of the URLs that start with “a” and keep them separate, and if the next search string is simply an extension of “a” (let’s say “ap”), you can then search the much-smaller pool of “a” URLs for URLs that match “ap”. That’s relatively fast. However, if you are doing title matching as well and the user types in “a”, the pool of matching URLs is going to be huge. A lot of webpages out there have “a” in the title, so your “a” pool is going to be much larger than the URL-matching-only pool.
• Note: in the bug I linked to above, there is talk of the autocomplete search causing the GUI to freeze up. This is one problem I have fixed. The issue was that ALL of the history items were being loaded at one time on the main thread—giving no time to anything else. I can load the history items in “chunks” instead, similar to how the search is done. This will free up some time for the GUI to update. However, this still doesn’t fix the problem that, once all of the bookmark/history data is loaded, autocomplete searches are still slow.

I don’t have a solution to this problem yet. One thing I’ve played around with is adding a progress indicator to autocomplete searches that take a long time:

Notice it next to the History heading? It’s definitely not an ideal solution, but when you have to wait ~1-2 seconds for the search to finish, it’s better than nothing. The other things I’ve come up with are to not use regular expressions and to not search the title (or maybe only search the fist word of the title, although I don’t know how useful that will be or how much that would speed things up).

Don’t be sad, though—like I said, for the majority of users, autocomplete is still nice and snappy.

Sometimes URLs are very big. You know the kind:

The problem with long URLs and autocomplete is that the autocomplete window offers relatively little space to display a URL. In general, URLs get about half the size they do in the location field, pictured above. Traditionally, this can be dealt with in one of two ways, neither of which is ideal. First, the end of the URL can simply be truncated off:

The problem here is that two URLs that differ only at the end appear the same. The Get Involved  and Partnerships sites look like they have the same URL. The other option is to truncate the URL in the middle:

This option isn’t so great, either, because a vital part of the URL is lost—the host. The host is the part of the URL that tells you what the main site is. For the Get Involved and Partnerships sites, the host is www.mozilla.com. For the Mozilla Licensing Policies site, the host is www.mozilla.org. This is useful information when scanning a list of URLs, but it’s often lost when we truncate URLs in the middle.

What is the ideal solution, then? I’ll illustrate with an example. Let’s say we have the following URL:

http://www.apple.com/downloads/macosx/development_tools/index_sp.html

If it can’t fit in the space allotted to it in the autocomplete window, the first part we want to chop off is ‘downloads’. The URL now looks like this:

http://www.apple.com/…/macosx/development_tools/index_sp.html

It’s much shorter! However, it also still gives us a pretty good idea where it leads to. The last part of the URL is still intact (index_sp.html) and the host is still intact (www.apple.com). If the window continues to get smaller, we need to continue to shrink the URL:

http://www.apple.com/…/development_tools/index_sp.html
http://www.apple.com/…/index_sp.html

Finally, if we need to shrink the URL even further, we simply truncate the middle:

http://www.app…index_sp.html

Hopefully, it won’t come down to this too often. Today I’m pleased to announce a new patch I’m working on that follows these rules. Here’s a screenshot of the same set of URLs pictured above, smartly truncated:

Yes, I know the window size is a little bigger than the windows above. I showed the worst cases in the first two pictures in order to illustrate the point. I haven’t filed a bug for this yet, but will update this post when I do. This is now known as Bug 507653.

For anyone who has been checking the blog, I know it probably seemed that nothing was getting done. My last update was several weeks ago. But, believe it or not, some of my work has actually landed—which means it’s included in the latest builds of Camino. You can download the nightly builds of what will eventually be released as Camino 2.1 right here. So exactly what did I do? Well, two things. First, I updated the appearance of the autocomplete popup window to make it easier to read (more whitespace!) and also just to make it prettier. This change is also known as Bug 495496. The second thing I did was make it possible to autocomplete from bookmarks (in Camino < 2.1, autocomplete suggestions only come from history). This was Bug 166288. As you can tell by its relatively low number, this bug was filed a long time ago. Here’s some before and after shots for good measure:

What’s next? Well, in response to these new changes, many complaints have been filed. Things don’t work exactly as they did before and some things should just work better. Here’s a couple things I broke:

• Apparently, the autocomplete popup window doesn’t always go away on its own. It’s rare and you can always hit esc to force it to go away (Bug 505263).
• Some pseudo-protocols don’t show up during autocomplete anymore. What is a pseudo-protocol? If you don’t know, you probably don’t care, but basically it’s a part of a URL that tells the browser to do something special. If any of the URLs in your history begin with about: or file: or javascript: or data: or a few others, they won’t show up in autocomplete. A fix for this is coming (Bug 504688), but it’s not my top priority right now.

There are many other requests for improvements to the location bar and/or autocomplete window, and I will try to get to them all. Right now, however, I’m focusing on two things: speeding up the autocomplete search and doing something about redirected URLs, which currently show up with blank titles and generic favicons.

I’m trying to get caught up with my blog posts, going into the third week of SoC. First things first, I should mention that I have updated my proposal and it is now available here. The new proposal reflects a lot of what I’ve learned since starting SoC: the current state of the Camino codebase, the review process, and what I feel like I’m able to do when it comes down to actually writing code.

Basically, to sum up the changes, less emphasis is placed on the social bookmarking ideas I had in my original proposal. What I’ve found is that more attention needs to be placed on the basics of the location bar: bookmark searches and the ranking algorithm. Even getting the code for the appearance patch up to snuff has been more challenging and time-consuming than I original planned. Hopefully, I will still get to work on the social bookmarking code, but I do not think it will ever land, or certainly not this summer.

This first week has been frustrating, to say the least. I spent a few hours just trying to get my new classes to build in the Camino project. Then I started to integrate some of the code from my demo into the Camino code. This was actually not too bad, except for one thing: Camino still runs on 10.4! I knew this somewhere in the back of my mind. But unfortunately it was not something I thought of when I was writing the demo, so I used a few things from the 10.5 api.

One such thing was the foreach loop, but that wasn’t so hard to fix. The big thing was the tableView:dataCellForTableColumn:row: method in the tableview delegate. This is a 10.5-only method

What I ended up doing is subclassing NSCell and using a single column to draw all of the content (favicon, url, title). Typically, each of these values would have its own column, but then the header text would have to fall into one of those columns as well. What I needed was to be able to draw the header text across all columns, and the only way to do that was to make one big column. The result looks identical to the 10.5 implementation:

Header row in Camino popup window

Well, I was accepted to Google Summer of Code 2009. This is my first time participating in GSoC. This is my first time working on open source software. This is also my first blog. It’s a summer of firsts, I suppose. More on my specific project in the next post. But I thought I’d use this post to talk about why I want to work on Camino.

I’ve been using Macs for a long time (since the Mac SE) and I’ve been using Camino a long time (since it was known as Chimera). When Chimera first came out, it was competing against browsers like Netscape and Internet Explorer for Mac. There wasn’t a Safari or Firefox yet, or any other of the many browsers out there now. While Netscape and IE have always looked and acted like bad Windows ports on Macs—especially OS X—Chimera was different from the start. It looked like a real OS X application and it was very fast. I remember if I ever needed to use a friend’s computer to do some work, the first thing I’d do was download Camino.

Part of the reason I was interested in working on Camino during Summer of Code is because I’ve always liked the browser. However, I have to admit that recently I’ve been using Safari 4. It’s very fast and it has some nice features. One thing I like about it most is the address bar. It has an updated look that really brings it into the world of Leopard, and the URL autocomplete works very well. It always seems to suggest exactly the site I’m looking for. However, more importantly, it presents the results in a way that is immediately readable. Here’s where I’m going to show some screenshots of various popular browsers and say what I like and dislike about each. At the end, you’ll get to see what I think the Camino address bar and autocomplete list should look like.

Firefox

Auto-complete popup list in Firefox 3+

This is what Firefox 3’s autocomplete popup looks like. First the good: it does a decent job of suggesting URLs. It matches keywords against page titles and URLs, and even tags that you can assign to pages à la delicious. Brains is good, but it’s not everything. Now the bad: if the list is so poorly presented that the user does not recognize the URL they are looking for among the results, it doesn’t matter how smart it is. This has happened to me before in Firefox. There are a few reasons I think the Firefox list is so hard to read:

For one thing, people generally don’t know the title of the pages they visit, yet this is the most prominent information in the list. Also, even if the user does know the title, there may be more than one page with that exact same title. For example, how many About Us pages are out there?

Overly complicated. Two lines, two font sizes, bold and underlined letters (once a search is started), favicons, little yellow stars. Some of these properties are nice features on their own, but when they are all combined, it is daunting and discourages the user from quickly scanning the results. This is probably the #1 reason why it’s possible to miss the result you’re looking for, even though the list is only six items long. The worst offender here is the two lines. Reading this list is like reading a newspaper article.

What’s the point of having scrollbars? If you have to scroll to see the result you want, you may as well spend the time to do a google search—it would probably be faster.

Overall, I think Firefox’s autocomplete list is poorly implemented, but I will look at the sorting algorithm (known as “frecuency” sorting) later this summer.

Safari

Auto-complete popup list in Safari 4 beta

This one is from Safari 4 beta. I’m not going to show the autocomplete list from Safari 3 because I don’t like it. But there is a lot to like about this one. For starters, my personal perception is that is does an even better job of suggesting URLs than Firefox. Apple doesn’t publicly document their algorithm like Mozilla does, so I don’t know how they do it. But there are very few times when the “Top Hit” is not exactly the website I’m looking for.

I think the design of the popup window is also spot on. Like I said earlier, the fact that it mimics the look of a Leopard menu is very clever. People are used to scanning menus to find the item they are looking for, even if it’s not at the top of the list. Many common menu items, such as Quit, Print, Save, Duplicate, etc. are often near the middle or end of the menu. Thus, I think people are much less likely to miss the result if it’s in the list. Important features of this design are the one line per URL and the menu-like dividers that separate Top Hit, History, and Bookmarks.

There is not a whole lot I don’t like about Safari 4’s autocomplete list. If it were up to me, I would switch the order of History and Bookmarks because I think sites that users have bookmarked are a lot more important to them than sites that they have merely visited before (and thus should be higher up on the list). I also miss favicons whenever I use Safari because they are often the easiest way to spot a site you are familiar with.

Camino

Auto-complete popup list in Camino 1.6.7

Finally, this is what the Camino autocomplete list looks like. It is very similar to Safari 3’s list in that it’s just a plain NSTableView, but with the addition of some icons to the left of each item. However, these icons don’t seem to be favicons—they always show up as little globes on my machine. The major problems I have with this design are:

The important part of the URL often gets cut off. The hostname can only get you so far. What if the path is several directories deep and what you really need to see is the file name? With this design, you’re out of luck. You have to rely on the page name, which you probably don’t know anyway.

Too crowded. All the text seems too close together, which makes it harder to read. Plus, the descenders on the bottom line get cut off.

Scrollbars.

New Camino

Redesigned URL autocomplete list for Camino

Here’s my current “mockup” of what the new Camino autocomplete list will look like. It’s actually mostly not a mockup—it’s taken from my working demo. However, my demo doesn’t currently fetch favicons, so that part is Photoshopped. I’m not sure at this point if I’m going to keep them or not (they look a little crowded to me). Here’s what else I’ve included in the design, based on my observations of the implementations in other browsers:

Menu-like appearance. Familiar interface that is easily digested by the user.

Separate sections for bookmarks, history, and popular bookmarks (history not yet implemented). The popular bookmarks section is pulled from delicious.com and is activated when a word is typed into the location bar that matches a tag on delicious. In the screenshot, “apple” was typed into the location bar.

Integration with delicious.com. In addition to the popular section, the new autocomplete list will also contain bookmarks from the user’s own delicious account. These are listed under “Bookmarks.” Matches are based on page title, url, and tags the user has assigned the bookmark.

Source icons. These icons—on the far right of the list—show where the item came from. The delicious logo indicates the item was found on delicious.com, while no icon means it’s local. Currently, only integration with delicious is implemented, but in the future other sources could be implemented as well.

Size 11 font used throughout. Controversial, I know. But I really don’t see the point of making the page title a larger font size.

That’s it for this post. I’m sure there will be changes to the design in the future and there’s still a lot to do in terms of coding. You can check out my current status in the sidebar in the upper-left corner of the page. I will try to keep it as up-to-date as possible.