Very interesting post Vitaliy. I have given it a little thought during the day, and to tell the truth, I have found it quit a quest to figure out how to account for non-uniformity in computations. Initially I thought of the solution being a GPS-like algorithm. This way, by imposing a "speed limit", one could calculate the required time to do a calculation. Slower calculations would lead to a re-calculations of the time estimate. But who would want to slow down a computation? My conclusion was thus, that "estimate" was the keyword.

Please forgive my novice level of Mathematica programming. Based on your code:

There are most likely better ways. But thought i'd contribute to the discussion, despite my poor proficiency :-)

The code delivers two estimates. One averaged, based partially on the most common computation-speed, and the slowest computations-speeds within the last few computations. Second estimate is based on the current computation-speed, applied to the remaining number of calculations to be done.  Of course it does not predict the exact time of the end of the computation, but it gives an idea of how long it will take, supposing one does not pause or stall the computation.

Hello again Vitaliy. Yes, my apologies. There is an error. I attempt to find the few recent iterations, berfore the required quantity actually exists. Hence the error.

Yes. The "Realtime prediction" is based on some of the tail iterations. It might of couse seem that this is not completely valid, and not a true forecasting algorithm. Some preliminary investigation made prior the posting of the code showed that that time it takes for a single computation, in a long row of computations, increases and then flattens out, i.e. the longer a computation takes, the more appropriate it should be to assume the latest iterations mirrors the progression speed of the entire process. I have to admit, I am not entirely sure my logic holds, nonetheless, I gave it a shot ;-)

The Image below shows a longer computation. As you can see, the pace of computations "flattens" out. (Computation progress on the y axis, AbsoluteTime on the x axis).

  

This approach truly minimizes the resources required for forecasting, which instead can be used on the actual computation.

I am not sure an algorithm for predicting progress of a non-uniform progress exists. But I am sure, if we combine the 'Realtime prediction' with some kind of logarithmic FindFit(?), then we can pull it off :-)

Edit: Not to leave errorneous code behind in the community, I took the liberty to correcting the previous excerpt of code.

@PatrickStevens Yes, good idea, we could do that type of forecasting, but that would require accumulation of points and time spending on fitting. This will slow down the monitored computation. So I guess the question is how do we find a proper balance between small enough slow down and sophisticated enough forecasting. I wonder if there are some standard algorithms for this.