Rsync order of maginitude slower with twice as large directory

[Gerben Wierda]

I am in the habit of syncing my /usr/local tree over several computers 
(all Mac OS X). Recently my /usr/local tree has doubled in size, from 
300,000 files to 600,000 files because I have added a large subversion 
checkout (TeX Live). As a result, rsync has become a time hog. Instead 
of a minute or two or so to calculate what needs to be sent over, 
suddenly this process takes 18-20 minutes, 10-20 times as long for 
twice the tree. If I use --exclude to skip the subversion tree, the 
process goes back to a minute or so.

How can I find out what causes this?

I am using rsync 2.6.0 with Kevin Boyd's HFS+ extensions, because one 
of the systems runs OS X 10.3.9 and does not have a recent 
Apple-provided HFS+-aware rsync.

Thanks,

G