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.
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.
