Doc #76806 [Opn]: md5_file() time complexity undocumented

Edit report at https://bugs.php.net/bug.php?id=76806&edit=1 ID: 76806 User updated by: chealer at gmail dot com Reported by: chealer at gmail dot com Summary: md5_file() time complexity undocumented Status: Open Type: Documentation Problem Package: *Encryption and hash functions PHP Version: Irrelevant Block user comment: N Private report: N New Comment: Thank you cmb The time complexity is not simple to document, but it can be documented to some degree. The function call overhead should not cause md5() not to be O(n), as it should be constant. microtime() can return a float which may be inaccurate, but it should at least be accurate to the nearest microsecond. If you think it may not even be accurate to the nearest millisecond (which is what I need for this test) on a platform as major as Microsoft Windows 8, this should be documented. I have run the benchmark several times anyway and get consistent results. I did replace the call to md5_file() with a call to file_get_contents() to confirm that the non-hashing time between 0.15 and 0.5 ms is spent recovering file contents. I was not saying there was a superfluous syscall, just pointing out that the cost of a syscall may explain that considerable non-hashing time. Previous Comments: ------------------------------------------------------------------------ [2018-08-28 21:59:50] cmb@php.net I agree with @requinix, that we can *not* document the time complexity, since it's too dependend. While MD5 is likely O(n) in theory, it may not be in practise (consider the function call overhead, and possibly even swapping for very large strings, just to mention both extremes). md5_file() is still another beast, since it always has to read a file. @chealer microtime() is far from exact on older Windows versions (not sure about Windows 8; Windows 7 is definitely bad). Instead use hrtime()[1] or the hrtime extension[2]. Also consider to replace md5_file() with file_get_contents(), just for comparison. Anyhow, if you think that there is a potentially unnecessary syscall, check that with some strace for Windows tool. [1] <http://php.net/manual/en/function.hrtime.php> [2] <http://php.net/manual/en/book.hrtime.php> ------------------------------------------------------------------------ [2018-08-28 20:51:14] chealer at gmail dot com Performance information could let us determine if a function other than md5_file() should be used instead, and how it should be called. I ended up benchmarking md5_file() on CSS files with PHP 7.1.3. The results surprised me. First, while there is some variation in results from test to test, and while bigger files do require more time, the time taken is far from being directly proportional to file size. We have a 5801 byte file which is consistently hashed faster than a 652 B file. There seems to be a big base cost, around 0.15 ms, making all times in the following list comparable despite big differences in size: 0,43 ms to hash 120822 B from temp/public/codemirror_modes.css 0,46 ms to hash 91760 B from themes/base_files/css/tiki_base.css 0,46 ms to hash 31000 B from vendor_bundled/vendor/fortawesome/font-awesome/css/font-awesome.min.css 0,57 ms to hash 188330 B from themes/default/css/default.css 0,34 ms to hash 9948 B from lib/openlayers/theme/default/style.css 0,37 ms to hash 8308 B from vendor_bundled/vendor/codemirror/codemirror/lib/codemirror.css 0,21 ms to hash 1060 B from themes/base_files/feature_css/codemirror_tiki.css 0,45 ms to hash 36444 B from vendor_bundled/vendor/components/jqueryui/themes/flick/jquery-ui.css 0,36 ms to hash 1945 B from vendor_bundled/vendor/jquery/jquery-timepicker-addon/dist/jquery-ui-timepicker-addon.css 0,35 ms to hash 4474 B from vendor_bundled/vendor/jquery/plugins/colorbox/example1/colorbox.css 0,30 ms to hash 652 B from vendor_bundled/vendor/jquery/plugins/treetable/css/jquery.treetable.css 0,17 ms to hash 5801 B from themes/base_files/feature_css/admin.css This benchmark was done with files from the Tiki Wiki CMS Groupware project, with the following code in HeaderLib::get_minified_css(): $time_start = microtime(true); $hash = md5_file($originalFile); echo substr((microtime(true) - $time_start)* 1000, 0, 4) . ' ms to hash ' . filesize($originalFile) . ' B from '. $originalFile . "\n<br>"; It turns out this non-hashing time between 0.15 and 0.5 ms is spent recovering file contents. It presumably does not come from disk seeks as I run this benchmark multiple times quickly and times don't improve even when these files should still be cached. This time must represent the cost of a syscall needed to obtain file contents from RAM. I ran this on Windows 8, with 8 GB of RAM and a 3300 MHz Intel Core i5-4590. The bottom line is that on my setup, with Microsoft Windows 8, hashing 200 kB takes roughly the same time as reading a cached file's contents, that is about 0,3 ms. ------------------------------------------------------------------------ [2018-08-28 18:02:12] requinix@php.net MD5 is theta(n). Meanwhile it's impossible to say how long it will take because there is no such thing as an average computer and there are too many variables to account for. But I still don't understand how this is supposed to help you. md5_file is going to be the best method. ------------------------------------------------------------------------ [2018-08-28 17:57:16] chealer at gmail dot com From another angle, how much data can a modern computer hash with MD5 in 1 second? According to https://gist.github.com/Antnee/02ef377403d806dec132 the cost for computing the hash of a small string is very low. ------------------------------------------------------------------------ [2018-08-28 16:38:33] chealer at gmail dot com Thanks requinix, Putting lower and upper bounds on computation time would help. Examples could also help - for example, how long does hashing a 10-character file take on a typical computer? How long does hashing a 10 kB file take? ------------------------------------------------------------------------ The remainder of the comments for this report are too long. To view the rest of the comments, please view the bug report online at https://bugs.php.net/bug.php?id=76806 -- Edit this bug report at https://bugs.php.net/bug.php?id=76806&edit=1