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:
apr_psprintf
Yuck!
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.)
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.
---------------------------------------------------------------------
|
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.