43

Estimation

xkcd

I know that the Windows copy dialog (in Windows XP) stores the copy in memory first, and it is still copying after the dialog closes, so the time is off, but why is the estimation of the time it will take to make a copy so inaccurate, even when memory copying has been disabled (in Vista and Windows 7)? It seems so arbitrary! How does the whole copy procedure work, and why can't Windows estimate it correctly?

6

18 Answers 18

29

In short: the poor algorithms and the jumpy estimation is actually an implementation weakness.

Other tools like TeraCopy do a better job. I think it is not worth explaining why their implementation is not good. They will have noticed it and will improve.

What is difficult:

  1. You have to take into account resource fluctuations (CPU/Network bandwidth/HDD speed mainly)
  2. You need to extrapolate the time it'll take by predicting the behavior (what Windows file copy definitively does badly right now).
  3. Make adjustments time over time to your original estimation (I mean small adjustments not like in the funny picture above!)

For this not only the amount of bytes but the amount of files to create play a role. If you have a million of 1KB files or thousand 1MB files the situation will be quite different because the former has the overhead of creating many many files. Depending on the filesystem used, this could take more time than actually transferring the data.

This dialog drove me mad also quite a couple of times:

  • On an older WinNT system, if you had a lot of small files to copy, it displayed the name and nice animation for each file slowing down the whole process to be practically unusable.

The modern Windows copy stuff is not much better:

  • To compute the amount of data to transfer it seems to make a lookup first (that is what I suppose it does) so it takes ages if you select many directories until it effectively starts to do the job.
  • Some built-in timeout impeaches big files to be copied (> about 60GB on my system). The pain is that it tell you that after having copied already more than 30GB over the network and this is lost bandwith and time because you have to restart from scratch!
  • Copy of files from one computer to another is damn slow for some reason. (I mean compared with the available network bandwidth, using other tools it is faster so it's not a computational limitation.)
0
49

Raymond Chen wrote a very nice article about this once. Basically, the dialog is just guessing :).

https://devblogs.microsoft.com/oldnewthing/20040106-00/?p=41193

"Because the copy dialog is just guessing. It can't predict the future, but it is forced to try. And at the very beginning of the copy, when there is very little history to go by, the prediction can be really bad.

Here's an analogy: Suppose somebody tells you, "I am going to count to 100, and you need to give continuous estimates as to when I will be done." They start out, "one, two, three...". You notice they are going at about one number per second, so you estimate 100 seconds. Uh-oh, now they're slowing down. "Four... ... ... five... ... ..." Now you have to change your estimate to maybe 200 seconds. Now they speed up: "six-seven-eight-nine" You have to update your estimate again.

Now somebody who is listening only to your estimates and not the the person counting thinks you are off your rocker. Your estimate went from 100 seconds to 200 seconds to 50 seconds; what's your problem? Why can't you give a good estimate?

File copying is the same thing. The shell knows how many files and how many bytes are going to be copied, but it doesn't know know how fast the hard drive or network or internet is going to be, so it just has to guess. If the copy throughput changes, the estimate needs to change to take the new transfer rate into account."

0
34

I am going to count to ten, 1....2....3....4 how many dots is it going to take to get to 10?

5.6.7 What about now? Do you take in to account all past dots between numbers and average it, do you only take the last 4 intervals and use that average, do you only look at the last interval?

You have the same problem with file transfers. The speed that the file transfers is not constant, it speeds up and slows down based on a lot of factors. The reason the number jumps around so much is Microsoft leaned toward the "only count the last interval" side of the spectrum.

There is nothing wrong with that side of the spectrum, it gives you more accurate "seconds per second" (one second in real time makes the counter go down by one second) but this causes the total ETA of the timer to jump around a lot.

A good example of the opposite side is 7-Zip when it is compressing. If the speed of the compression drops as it processes you can see that the ETA does not jump dramatically like a file transfer ETA, but it may take 2 to 3 real seconds before the timer ticks down one second (or it even may start counting up) until it stabilizes at the new speed.

0
15

There's actually a nearly canonical answer by Microsoft's Raymond Chen about this from WAAAAAY back, and there are a few pieces to the puzzle.

Because the copy dialog is just guessing. It can't predict the future, but it is forced to try. And at the very beginning of the copy, when there is very little history to go by, the prediction can be really bad.

Firstly, that Windows is guessing. It knows how many files, and how big they are, but the transfer rate per file is highly variable. It depends on things like size, or even location on the drive in some cases. As time goes on, it's adjusting its guess based off current and past conditions, and as such you have inaccurate estimated transfer speeds under real-world conditions.

2
  • @JourneymanGeek "someone on chat" reporting in! Yea, while this is a pretty authoritative source, it's important to keep in mind that it's from 2004, and is heavily outdated and likely only vaguely related to the current algorithms in use on Windows 8.
    – Bob
    Feb 1, 2014 at 16:54
  • 1
    Here is a related blog post on Windows 8: "Estimating the time remaining to complete a copy is nearly impossible to do with any precision... Rather than invest a lot of time coming up with a low confidence estimate that would be only slightly improved over the current one, we focused on presenting the information we were confident about..." Feb 1, 2014 at 17:22
12

Here's the explanation by Raymond Chen, Principal Software Design Engineer at Microsoft:

Why does the copy dialog give such horrible estimates?

Because the copy dialog is just guessing. It can't predict the future, but it is forced to try. And at the very beginning of the copy, when there is very little history to go by, the prediction can be really bad.

Here's an analogy: Suppose somebody tells you, "I am going to count to 100, and you need to give continuous estimates as to when I will be done." They start out, "one, two, three...". You notice they are going at about one number per second, so you estimate 100 seconds. Uh-oh, now they're slowing down. "Four... ... ... five... ... ..." Now you have to change your estimate to maybe 200 seconds. Now they speed up: "six-seven-eight-nine" You have to update your estimate again.

The blog post quoted above has a long discussion of this issue, with some interesting comments.

Raymond Chen is a legendary person, "Microsoft's Chuck Norris", I don't suppose you're going to get a more authoritative answer. I'm sure he had at least seen the code in question.

11

The obvious reason is that the speed of the transfer varies over time, and so does the average, and so does prediction. To explain this to a non-tech friend, I've used an analogy involving travel by air. You're going to fly over the Atlantic. When you arrive with a taxi at the departing airport, your ETA is about two months. When you disembark at the arriving airport, based on your average speed so far, you will reach your friend's house in 5 seconds.

But you need to appreciate how much the speed can actually vary, even with what seems like a predictable scenario, like copying files within the same disk, or between two local disks. One of the new features I like in Windows 8 is the ability to graph the speed over time if you click "more details". If you don't have access to a Windows 8 machine, search images for Windows 8 copy dialog for a lot of examples. Many of them are fairly flat, but many of them are also disturbingly bumpy, to the point that you wonder whether the hard drive is actually healthy, when it dips to zero.

Some of these bumps are likely due to variations in file size—smaller fields yield more accesses, which slows things down, especially on a mechanical hard drive which has to seek by moving its read head—but some it might just be a cheap drive which stalls on the slightest touch to prevent damage to the platters.

There are better and worse ETA prediction algorithms, but for an accurate prediction, the computer would have to be all-knowing. The risk of trying to make the algorithm "smart" is that it might create new, unforeseen, cases where it's even more hilariously wrong.

Windows 8 copy dialog

Windows 8 copy dialog 2

4

The only way to know how long it'll take to compress a set of files is to compress them. Sometimes Windows' best guess is close, sometimes it's wildly wrong. The same is true of copying large numbers of files, as I'm sure you've noticed.

It's not so much a bug as a useless display of seldom-accurate information. The best way to fix it is to close your eyes. Ignore it. ;-)

Perhaps there's a program out there that can copy/compress files and make an alarm sound when it finishes. That would be truly useful. We could have a little nap while we wait for Windows to finish the housecleaning.

4

In order to expedite the copy process (not spend too much time calculating time estimates instead of performing copy-related operations), the windows copy utility built into Explorer maintains a limited amount of information about how fast previous write operations completed. Each time it needs to calculate the time remaining, it just figures out the average amount of time write operations have been taking, and then multiplies by the number of remaining write operations.

The problem is that the amount of time is takes to perform a write operation is not constant - it can actually vary significantly. So this, in turn, produces significant changes in the time estimate.

3
  • I don't think you're quite right on this one - you can maintain a usable average of writes using just 2 numbers - the current average [A] and the number of data points used to get that average [n]. Then to update it, it's just a case of (A*n + [New value])/[n+1]. Also, since copy operations are almost always IO-bound not CPU-bound, a simple calculation like that every few seconds is nothing. On the other hand, keeping an average of the last n writes requires an array/queue/stack of n elements - so you know which value is due to be evicted.
    – Basic
    Feb 1, 2014 at 9:42
  • Good point! So why the heck is it so all over the place? :P Feb 2, 2014 at 18:56
  • I assume they tried to be clever by doing a more responsive average, taking into account only the last few writes - and picked too few. That said, I don't have the source so who knows?
    – Basic
    Feb 2, 2014 at 20:37
4

There are 3 factors to take into account:

  1. The total size of the transfer.
  2. The number of files to be transferred.
  3. The "busy-ness" of the media, and possibly the connection.

Numbers 1 and 3 would seem to have the most obvious effect on the transfer time calculation, but a great many people do not account for number 2. This can have a huge effect on how long the transfer will take, and is difficult to quantify.

Basically, each time a file is written the filesystem needs to write a bit of metadata about the file, eg. ownership, permissions, creation/modification/access times, etc. Depending on the particular filesystem, this information may be written to a part of the disk very 'far away' from where they file is being written. This filesystem overhead is what can make a seemingly simple transfer take a long time, and/or make the time estimate fluctuate wildly.

eg: Transferring one large file you'll notice that the estimate holds steady and is fairly accurate, but transferring hundreds of files of varying sizes, but the same total size, can take longer and cause the time estimate to pitch a fit.

4

There are three deficiencies in current estimation algorithms.

Contrary to popular belief they are not nearly difficult enough to throw our hands up over.

The reason most people writing the blogs, and people here aren't aware of the possibility is as best as I can tell due to field of study and schooling breadth. A modest yet also very comfortable remedy should be possible for [a graduate with more recent training than the blog writers] [a multibillion dollar company] Microsoft.

I will attempt to roughly explain why.


The points of failure are as follows. The kernel:

1. cannot reliably predict future IO load due to circumstances outside scope of the kernel

  • nothing should be done about this as it's a very unbounded P=NP problem.

2. does not track IO heuristics in any useful level of detail. Utilization is a much broader concept than disk/network read/write speed.

  • very little needs to be done about this, little more than to track the most basic IO usage information

    • from the disk
      • the average read speed dimension 1a
      • the average write speed of files dimension 2a
    • on a per-quanta* basis according to
      • the file's size dimension b
      • the file's location on disk dimension c
    • *quantized into [likely] no more than 3 categories. Dimensionality reduction would help us determine for certain but 3 should be plenty for (probably rather effective) better-than-nothing prediction mechanisms:
      • file size
        • light
        • medium
        • heavy
      • location [informs of seek latency]
        • beginning
        • middle
        • you get the point
      • file size and location are redundant / overlap with read/write speed, this is intentional
    • we need to know how "busy" the disk has been so that we can assume it will continue being that busy dimension d
      • computed from quantity of files being read, convolved with their respective weights
      • used to estimate time at start of copying... dialog based on future expected load if everything else aside from this copy dialog continues as it is now
    • the method of recording for purpose of... here is patentable

3. were they tracked, would not have use for the heuristics

  • little has been done here, where we do most of the work
  • this is where we put the data from #2 to use
    • rough statistical analysis of file weights and locations to determine how much hopping we're going to do. The weight + location gives us a prediction
    • combine with current disk load weights and locations
    • to estimate what we think average read / write speed of the number of files dimension f will be
    • which we compare to fine tune our model
    • which will let us quite accurately estimate the progress bar and time to completion
  • the method of analyzing for purpose of predicting... here is patentable

The point of all this is our model is only 2a = F*(b x c) + d complex

Where a, b, and c have 3 states each: the file manager peeks at the files (or just the metadata) before copying, and F*(b x c) + d is not an expensive computation; if you want something more accurate use a lookup table with more states-- there's hardly any calculation at all.

note: dimensions here are for a platter, would be different with an SSD-- beginning/middle/end wouldn't matter

The key difference between what I described and previous implementations that we've seen so far would be, in short, observing filesize and file distrubtion/entropy on the disk and using it to [more] accurately account for the time element of disk usage.

(the patent is left as an exercise for the reader...)

0
4

I think the reason was nicely explained in one of the comments of the blog post linked by Roald's answer:

It has a horrible estimate algorithm. There are no excuses. If has to copy 1000 1KB files and 10 1MB files it thinks it will be as busy with the 1 MB file as with the 1KB files.

The reason it gives such horrible estimates is that it's not well done. Obviously it can never be 100% precise but it could be much, much better.

2
  • 1
    Knowing how big a file is in windows requires opening it, and opening a file in Windows means reading it. And instead of opening all of the files to see how big they are to get a good estimate for how long the copy will take, Windows decides to use its time actually copying the files - after all, that's what you asked it to do. Mar 8, 2012 at 1:02
  • 1
    @SecurityMatt: If that were the case, it would take ages to get a directory listing. I'm sure file sizes are stored in the directory and updated whenever the file is changed. Therefore, there should be a way to get a quick and fairly accurate estimation of the copy time based on the file sizes listed in the directory and some assumptions about transfer speed. A really smart OS would pay attention to average transfer speed over time and use that in its estimates.
    – RobH
    Feb 3, 2014 at 17:45
3

There are a lot of "unknown" variables when you are trying to predict how long something is going to take. For example, while the program knows that there are 3500 files, and that the files amount to 3.5 GB (3500 MB), does that mean that each file is 1 MB? Not necessarily. There could be a lot of 4 KB files, and a lot of 100 MB files, and some other in between. Also, you have to take into consideration where the files are coming from and where they're going (e.g. media.) What is the biggest bottleneck? How do you account trying to copy files from an HDD through a VPN tunnel? You give a best case scenario, and then adjust your counters in real time. This is why you see those progress meters change on the fly.

2

The mathematically correct model is to actually do a naïve averaging and extrapolation:

transfer speed = data copied / time elapsed
time remaining = data remaining / transfer speed

The reason is that by the Law of Large Numbers the local fluctuations will cancel out in the averaged transfer speed, and this will give you the most stable result.

What Microsoft seems to do is to calculate the transfer speed at the latest time frame. This means that each local fluctuation changes the result significantly.

5
  • 3
    Your model will not properly handle long-running disturbances, like starting other file transfers in parallel, and will continue to tell me it'll just take 5 more minutes even though the same amount of data had just taken 20 minutes. A weighted moving average might be more accurate.
    – Daniel Beck
    May 11, 2012 at 16:48
  • @DanielBeck: Not exactly correct. The expected time will gradually increase. The question is how fast will it increase? Well, it depends on the elapsed time. If it was a long operation, e.g. it was already copying for 5 hours, then it won't increase the expectation much. But does the 15 minute inaccuracy matter for 5 hour operation? No. The point is that it gives you the best approximation in terms of relative error. Also you can't do something that will work much better in every scenario. May 11, 2012 at 17:15
  • 3
    The problem of your model is that it absolutely does not react to transfer rate changes midway through the transfer. This will be just as insufferable as the fast-reacting Windows file transfer Example: 60GB transfer at 10MB/s at first. Time left at start: 100min. Transfer 54GB and drop to 2MB/s. After 90 minutes: Estimated time left at 54GB: 10min. Real time left at 54GB: 50min. After 115 minutes: Estimated time left at 57GB: 6min. Real time left at 57GB: 25min. After 131.67 minutes: Estimated time left at 59GB: 2.23 minutes. Real time left at 59GB: 8.33 minutes.
    – Daniel Beck
    May 11, 2012 at 17:44
  • @DanielBeck: the whole transfer lasts 150 minutes, so the maximal relative error is 50% in the beginning of the transfer where you can't do any better. At the 54th GB it's just ~14% off of total. (if it takes you 150 minutes, why 20 minutes matter?) Actually a very good estimate...That said, I understand your point. The way to improve this is not weighted moving average because you can't know what size of the window it should be (does this operation expected to take minutes like copying a file, May 11, 2012 at 18:53
  • or hours through a p2p file sharing protocol where you get 10 minutes of 10 MB/s and 10 minutes of 0 MB/s). The way to improve this is to take the average weighted by time, not by size. May 11, 2012 at 18:54
2

There are some interesting answers in the MSDN blog post Improving our file management basics: copy, move, rename, and delete about this. As to why it is hard:

Estimating the time remaining to complete a copy is nearly impossible to do with any precision because there are many unpredictable and uncontrollable variables involved – for instance, how much network bandwidth will be available for the length of the copy job? Will your anti-virus software spin up and start scanning files? Will another application need to access the hard drive? Will the user start another copy job?

And how they are improving,

Rather than invest a lot of time coming up with a low confidence estimate that would be only slightly improved over the current one, we focused on presenting the information we were confident about in a useful and compelling way. This makes the most reliable information we have available to you so you can make more informed decisions.

That said, if you really want to improve just the given estimate and keep the progress bar as it is, you could do something suggested in a Slashdot comment:

Maintain a table of expected speeds for each storage device on the filesystem. Record how long it takes to read the filesystem information. When a device is mounted, if it's reasonable for the device type, seek to the middle and end, measuring speeds there, too. Get approximate curves for the read and write speeds across locations, and use those for future estimates. For future read and write operations, take note of where they are and how fast they go, and adjust the curves accordingly.

When an operation starts, look at the curves for input and output for the respective devices. Find the expected speed for the target location. Whichever speed is lower should be used for the estimate.

1
There is some way to refine or correct this kind of "bug"?

As Roald van Doorn said, it's basically just guessing. Of course, that does not mean it couldn't be a better guesser. There are plenty of heuristics that could be used to calculate this.

  1. The best way, most expensive way, would be to keep a history of previous 'copies' and then use artificial intelligence algorithms to calculate a guess
  2. One could construct a formula based on research of how long it should take. They could take in account things like: file system, number of files, size of files, disk seek time, disk bulk read/write speeds, location of files on disk (fragmentation), current disk utilization.
  3. A mix of the two. Ie. do some benchmarks to find out how long certain operations take and then use those as a history for simple formulas.

Obviously none of this is easily implemented.. and I only mentioned file copies. Similar work would need to be done for all sorts of transfers.
The question you have to ask yourself- Would you rather microsoft spend it's time giving you a better estimate or would you rather they make your files transfer faster.

However, If you compress something with 7-zip, you'll notice it's much better as guessing than windows is. I doubt it's doing something that complicated, just a slightly better guesser.

1

In short, the calculation is based on the current transfer speed.

For example: If your transfer rate sinks because windows has to copy huge amount of tiny files, the expected time goes up linearly and vice versa for large files.

It is nearly impossible to predict what the transfer speed will be over the whole transfer process, because it depends on a lot of factors like filesize, CPU usage, transmission erros etc.

1

Just wanted to add that the total number of files is easily the most time consuming factor of file copying operations on a PC. I can always remember as a young student, deliberately inducing failure of PC's in my computing class by starting with 1 file with no contents, and copying it, then selecting the 2 files and copying again and so on. Once it got past about 1024 files it started to take huge amounts of time to do anything even when it was copying no information save for the file header. Try it yourself even on a new OS, exponential file copy and you will see what happens. Food for thought.

1
0

I just copied 200GB from USB HDD to my main drive. There were about 130000 files

After the first 4-5 minutes I observed that:

  • For the smallest files, the rate was about 100 files per second at about 600KB/s
  • And for big files it was like 70MB/s

At beginning windows changed the estimation from like 1 hour to 5+ hours then back to 1 hour and so on. At the end like in 95% it was still changing the estimation from 10 minutes to 10+ hours. So it instead of become more accurate it was going less and less precise.

Simple math shows:

130,000 files at 100 files per sec = 22 minutes

200,000 MB at 70 MB per sec = 47 minutes

22 minutes - loosed in seek time copying files of few kilobytes in size. 47 minutes - the time it will need to transfer the actual data if there is no seek time.

Sum of the 22min + 47min is the absolute maximum time that it could possibly take.

So obviously the estimate should be somewhere between 47 and 69 minutes.

What the dialog shows at about 90%: "I am copying some small files at 1MB/s, there is 20GB more data, it will take 5:30 hours to complete.

Few seconds later: "I am copying a big file here, at 70mb/s it will take 4 minutes to complete.

What human actually sees from the same dialog: 120,000 files and 180GB are already copied for 40 minutes. The rest 10000 files and 20GB should take about 5min

The dialog gives enough information to make calculation that gets more and more accurate each second. It knows rate at which small files are copied. It knows at what speed big files are copied. It also knows how many files and how many bytes there are left.

It is so simple to make so accurate assumption only by setting the upper and lower limit.

The dialog shows a bit more correct data only in case when the big files are before the small files. If this is the case it starts at 40 minutes, and after 30 minutes it starts copying small files and says "well I need 20 minutes more".

But when the small files at the beginning and big files are at the end. The dialog does not actually care at what "files per second" it transfers the small files. It make its calculation like the small files count is infinity, and that like they will forever be small.

1
  • It actually answers it, if you are reading carefully. They are two types of bad estimation and I have explained why they happen from a example based reverse engineering point of view.
    – Xizario
    Dec 22, 2016 at 9:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .