I'm a bit late to this thread, so ignore me if I'm talking about
something off topic...

I think the time it takes to do an incremental depends both the number
of files and the organization of files in directories.   Take two
filesystems, one with 100,000 files in the root directory of the fs, one
with two levels of directories, 100 at the top, 100 in each of those,
and 100 files in each of those 10,000.  Any access to the former fs will
be slower than that of the latter.  That is the whole point of a
hierarchical fs; for the fs to locate a file on disk, it traverses the
directory tree (in the latter case, three lookups in directories
containing 100 entries, in the former, one lookup in a directory of
100,000 entries) to find the pointer to the inode.  I don't think
directories use hashing to store entries, so lookups would be linear in
the number of files (300 vs. 100,000).

On the server, given that the API requires a high-level name (the part
of the path below the filesystem mountpoint down to the directory that
the file is in) and a low-level name (name of the file in the
directory), any lookups done on the server would be linear in the number
of directories on the fs (each HL name is a directory on the fs) and the
number of files in each directory, assuming no hashing to store the
entries.  But I don't think the lookups for incrementals occur on the
server.

When you start an incr, you see sometimes several MB of data sent to the
client.  I think this is the list of active files as of the last
backup.  The client must then compare this with what is on the fs,
sending files that have changed and expiring ones that don't exist.  The
old slowincr option (now the memory efficient option) must send the list
of active files a directory at a time, incurring more transaction
overhead in the transfer.  The compare for each file is probably done by
stat'ing active file.  Each stat will traverse the tree as above.

Cheers...
Bruce