Incremental loading of directory contents

["Bogdan Butnaru" <bogdanb gmail com>]

Hello!

As I said in a previous mail, I'm working on improving the way
Nautilus displays icons in the file manager. I'd like to constrain
myself as much as possible to
libnautilus-private/nautilus-icon-canvas-item, but I'm hitting some
interdependencies with the nautilus-icon-container (in particular, it
expects to finds the icon text in some specific positions).

I'm going to do everything for now to keep the way
nautilus-icon-container works, but in the future I'd like to change
that, too, and I was wondering if someone can guide me towards that.
We can take the discussion off this list if you think it's better, it
might become long (I'd like to experiment with a lot of different
icon/folder layout methods).

Some things I'd like to try (I expect all of these would get in
"production" Nautilus, but tell me if something seems unreasonable)
are listed below, and I'd like some input. The overarching goals are
(a) compact and quick display of folders and (b) good-looking folders.

1) (very) different ways of placing icon labels: RTL/vertical text, on
any of the icon's sides, depending on the label's content (size and
script, I think), and on the user's preference.
2) Point (1) means that at least some of the folder layout options
become harder, so I'll have to change that too, at least for some
layout types (icon/list, tight/regular).
3) Nautilus is very slow in some ways I use it (big folders, thousands
of items), and (1) will make an individual icon's layout time a bit
longer, so I'd like to understand how Nautilus lays out a folder and
try to make it "incremental". In particular, I'd like to change all
the icon layout algorithms (point 2) so they only need to look at the
icons in the window.

The last point is the most difficult. I'd like to get some input from
whoever knows most about that part to see how feasible that is. If you
don't care much about what I've said until now, you can stop reading.
Below I'll continue ranting a bit about what I've been thinking
of/trying until now:

The whole thing started because I don't like the way Nautilus lays out
icons with extreme image and/or label sizes. I've already changed
things to make the layout much more efficient in some of those cases.
(In short, by doing wrapping smarter very long icons we can be more
compact). However that hits some limits when trying to layout labels
that aren't LTR, mostly from a prettiness perspective, so I've started
thinking about how to change icons layout too.

(Remember, this mostly concerns "big" icons/labels. Things will remain
more or less the same in cases where Nautilus works nicely now. I
don't intend to modify the "list view" yet.)

As far as I can tell, there are a few big classes of layouts:

(I) The Desktop. Fixed canvas size. Relatively few icons. (Even a
2000x1500 desktop, with 32x32 icons, no spacing, no labels = ~3000
icons; usually less than 100). All icons visible at all times. Must be
as pretty/useful as possible. Can have variable sized icons. Labels
can vary widely in size. Grid-based positioning user usually place
icons by hand–easy and quick, few problems with placement of
strange-sized icons; however, we might like to allow the user to
customize their icons (we already enable stretching icons by default).

The pretty-layouts I have in mind might benefit this most, though I'm
more interested in the other cases.

(II) Folders: Scrollable canvas. From very few (say, 3) to very many
icons (say, ten thousand). Very variable use cases:
  (II.a) Generic browsing: can pass through many directories, varied
in content. Must be quick and adaptable.
  (II.b) Specific positions: "My Computer"-like locations, that users
might want to customize a lot. (For instance, I have a music folder
with thousand of sub-directories, each of which has a custom icon and
a long name. I also have a "movies" folder, where each item has big
icons (128px or bigger). A user's "Documents" folder might also be set
to a large zoom size to see thumbnails better.)

For different uses we'd need layouts that range from list-like (small
icons, one-line text beside them) to "presentation" (big icons, often
long titles below). Generally I prefer a regular grid in the first
case and the tight layout in the second case. Problems:

(1) the regular grid layout scrolls vertically, so for a huge
directory it has to lay out huge columns next to one another. This is
slow. Also it's inefficient when icons vary widely in size, because
the column is sized by the maximums. I'd prefer we changed it to
horizontal scrolling (like windows does, but we'd make sure a vertical
scroll wheel/touchpad can scroll it). This way each column is "short"
(no taller than the screen), which minimizes the first two problems.
This would allow "incremental" layouting (we only need to layout the
visible columns at first).

Aaa Baa ....
Aab Bab
Aac Bbc

(2) The tight icon layout is nice because it works with lines first
(so vertical scrolling works well). However it still doesn't work very
well with wildly varying icon sizes, so I'd like to look at smarter
ways to layout this case, too.

* * *
Big issues I have about incremental layout (ie, layouting first what
fits the window, to display big folders quick, and doing the rest of
the work in the background, perhaps correlated with where the user
scrolls):

1) How to feed icons to the canvas incrementally (without reading the
whole directory); ideally this should work with sorting too. It should
work like this:
       * a set amount of items (say, 100 files), feed them to the folder window.
       * the icons are sorted if necessary.
       * the icons are laid out quickly.
       * we keep feeding items to the folder window in reasonably-sized batches.
       * if sorting is enabled they are inserted in the folder window,
which only lays them out if they arrive inside the visible portion,
until we fed all icons. Alternatively, the canvas can lay them out in
the background, too (slower, uses more memory).
       * when the user scrolls around, we keep laying out the icons they reach.

2) How to do scrolling if we don't know how big icons will be in the
final layout. I suggest we scroll by icon numbers rather than size, at
least for very big folders (eg, those we can't finish laying out in a
half second or so). This would mean the scrolling speed would be a bit
non-uniform visual, but that's not a huge problem for big folders.
(This only concerts the scroll-bar, not arrow/page navigation.)

3) How to layout icons incrementally. Most layout types need the sizes
of all icons, or at least all icons up to the point we reached, to
compute positions. The best I could come up with is:
       a) layout icons to fill the window; this should be generally quick.
       b) keep layouting icons in the background until we finish, on
low priority
       c) if the user scrolls to a part where the layout is at least
partially complete (ie, we know at least where it starts), we
prioritize layouting until we fill the window again.
       d) if the user scrolls farther than we laid things out, we have
a problem: we don't know where to start putting things;
           d1) we layout the icons as if it were the start of the page
on high priority and display them.
           d2) we resume background layout of the icons before the current page.
           d3) if we reach the current position before the user leaves
that page, we'll sometimes need to move the icons. This is annoying,
but we already move icons around (eg, when thumbnailing, or after we
read icon info like size in some display modes.)
           d4) if the user navigates around the current point (using
arrows/pg-up), we prioritize layouting the icons close to the "cursor"
relative to the context, at least until the "main" layout reaches the
current page (when we revert to d3 and then d2).


Whew, big post. Sorry. What do you think?

-- Bogdan Butnaru — bogdanb gmail com