[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: [PATCH] Fix O(n) runtime in cache lookup, part 1/2

From: Philip Martin <philip.martin_at_wandisco.com>
Date: Wed, 21 Apr 2010 14:40:07 +0100

Stefan Fuhrmann <stefanfuhrmann_at_alice-dsl.de> writes:

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

If you use "svnserve -T" then it will use threads instead of processes
and you should be able to track the total CPU use of the server.

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

The numbers look promising.

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

Part 2/2 of your original patch is problematic. You posted a
corrected version because the first version had a pool problem, but
the corrected version doesn't apply cleanly (extra arguments to
svn_io_file_read_full etc.).

-- 
Philip
Received on 2010-04-21 15:40:42 CEST

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.