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

svn_io_open_unique_file: quadratic cost

From: Julian Foad <julianfoad_at_btopenworld.com>
Date: 2003-10-15 15:17:19 CEST

[Please excuse the tone of this e-mail. I accept that the function was/is doing a useful job in a manner that has been acceptable so far.]

The cost of opening N similar temporary files with svn_io_open_unique_file is proportional to N squared, and with a high constant of proportionality. Its cost scales linearly with the number of temp files of the same pattern that exist already, so the total cost of opening N such temp files is quadratic. If the application creates say 200 temp files of the same pattern, it will perform (200+199+...+1) = 20100 iterations of its loop which contains:



Presumably we don't open many temp files of the same pattern at once during "normal" use, but that's no excuse.

The comment of "historic inevitability" on it says why it replaces "tmpnam" and "tempname" (probably meaning "tempnam"?), but APR is the place to do this and APR has "apr_file_mktemp".

If APR's "apr_file_mktemp" is not good enough, then we should improve it or add a more suitable one to APR. The considerations are:

* controllability of the dir in which to create the file (APR's is undefined.)
* efficiency (Ha! APR's version can't be worse than this.)
* safety/correctness in threaded environment etc. (APR's uses mkstemp() and errno if mkstemp() is available.)

APR has its own implementation to use if "mkstemp()" is not available. That would be a good base for the algorithm[1], and works on an explicit path, so I think it just needs to be exposed through the API. Hmm... the implementation of apr_file_mktemp only seems to exist in the "unix" sub-tree - what about other platforms?

- Julian

[1] I can't tell what the algorithm is - it is almost completely uncommented, but it uses random numbers.

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Wed Oct 15 15:17:41 2003

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.