On Wed, 2010-04-21, Stefan Fuhrmann wrote: > Philip Martin wrote: > > Stefan Fuhrmann <[email protected]> writes: > > Philip Martin wrote: > >> Stefan Fuhrman <[email protected]> writes: > >>>> svn_cache_t lookup returns a copy of the value found. > >>>> For objects of variable size, this can be expensive. If you > >>>> checkout / export all N files of a specific directory, for > >>>> instance, every single path gets verified. The directory > >>>> information is cached for FSFS but the copy operation > >>>> will still be O(N). > >>>> > >>>> As a result, the whole check takes O(N2). The good > >>>> > >>> That sounds bad. Do you have any measurements to show how much > >>> improvement your patch gives? > >>> > >> Well, choose your N ;) For low square mean numbers of files > >> per folder as in TSVN and SVN, the gains were between 3 > >> and 4 percent of total "svn export" runtime. If you want me to, > >> I could run a test with 10k files in a folder (probably a realistic > >> upper limit). > > > > Sounds promising. In this case I think server performance is the more > > interesting. If you can be bothered then run a server, do a checkout > > of a 1K or a 10k directory (probably many times) and look at CPU or > > memory usage of the server. But if you are getting 3% on the client > > then the server is probably getting a bigger gain. > > > Took me a while to get to it but here are the results. > I created a format 5 FSFS repository with folders > containing 2^N almost empty files. Then I ran ls and > export on svn://localhost - with in svnserve patched > and non-patched variants. > > The following table shows the "real" part of "time svn ..." > on the client side. As far as I can tell, svnserve spawned > a child process for each command and that child process > was busy during the command execution (e.g. kept 1 core > @ 100% load). > > Files ls-1.7 ls-patched export-1.7 export-patched > 1 0.045s 0.046s 0.046s 0.045s > 2 0.045s 0.045s 0.046s 0.045s > 4 0.048s 0.045s 0.046s 0.047s > 8 0.045s 0.044s 0.085s 0.086s > 16 0.045s 0.046s 0.086s 0.086s > 32 0.049s 0.048s 0.091s 0.087s > 64 0.088s 0.089s 0.092s 0.100s > 128 0.098s 0.094s 0.104s 0.119s > 256 0.126s 0.107s 0.144s 0.154s > 512 0.208s 0.132s 0.218s 0.210s > 1024 0.350s 0.177s 0.390s 0.318s > 2048 0.899s 0.251s 0.970s 0.458s > 4096 3.058s 0.321s 3.413s 0.458s > 8192 11.322s 0.601s 11.712s 0.752s > 16384 44.282s 1.079s 44.234s 1.343s > > So, there is clearly a O(N^2) runtime that becomes relevant > at a few hundred entries in a folder. For the very small file > sizes (<20 bytes) used here, svn export is mainly limited > by server-side path validation.
A set of measurements like that is a *really* quick and convincing demonstration of the value of this patch. Thanks! - Julian > As for the patch itself, I think I will rewrite it to either allow > for multiple pins or to follow an svn_wc__call_with_write_lock- > like approach. > > -- Stefan^2. >
