Author: toad
Date: 2006-06-28 23:40:09 +0000 (Wed, 28 Jun 2006)
New Revision: 9398
Modified:
trunk/freenet/src/freenet/node/Node.java
trunk/freenet/src/freenet/node/Version.java
trunk/freenet/src/freenet/support/math/TimeDecayingRunningAverage.java
Log:
843: Fix very long standing bug in TimeDecayingRunningAverage. Affected many
parts of the node.
SELF MANDATORY AT 0:00 GMT 30/09/06.
Modified: trunk/freenet/src/freenet/node/Node.java
===================================================================
--- trunk/freenet/src/freenet/node/Node.java 2006-06-28 19:10:58 UTC (rev
9397)
+++ trunk/freenet/src/freenet/node/Node.java 2006-06-28 23:40:09 UTC (rev
9398)
@@ -2080,6 +2080,7 @@
Logger.minor(this, "Reporting 0 because
throttle uncontended: now "+throttledPacketSendAverage.currentValue());
throttledPacketSendAverage.report(0);
Logger.minor(this, "New average:
"+throttledPacketSendAverage.currentValue());
+ Logger.minor(this, "Average:
"+throttledPacketSendAverage.toString());
} else
Logger.minor(this, "Not uncontended");
}
@@ -2982,7 +2983,7 @@
}
public double getBwlimitDelayTime() {
- return this.throttledPacketSendAverage.currentValue();
+ return throttledPacketSendAverage.currentValue();
}
public double getNodeAveragePingTime() {
Modified: trunk/freenet/src/freenet/node/Version.java
===================================================================
--- trunk/freenet/src/freenet/node/Version.java 2006-06-28 19:10:58 UTC (rev
9397)
+++ trunk/freenet/src/freenet/node/Version.java 2006-06-28 23:40:09 UTC (rev
9398)
@@ -18,12 +18,12 @@
public static final String protocolVersion = "1.0";
/** The build number of the current revision */
- private static final int buildNumber = 842;
+ private static final int buildNumber = 843;
/** Oldest build of Fred we will talk to */
private static final int oldLastGoodBuild = 839;
- private static final int newLastGoodBuild = 839;
- private static final long transitionTime = 1151103600000L; // 0:00 GMT
24/06/06
+ private static final int newLastGoodBuild = 843;
+ private static final long transitionTime = 1151625600000L; // 0:00 GMT
30/06/06
public static final int buildNumber() {
return buildNumber;
Modified: trunk/freenet/src/freenet/support/math/TimeDecayingRunningAverage.java
===================================================================
--- trunk/freenet/src/freenet/support/math/TimeDecayingRunningAverage.java
2006-06-28 19:10:58 UTC (rev 9397)
+++ trunk/freenet/src/freenet/support/math/TimeDecayingRunningAverage.java
2006-06-28 23:40:09 UTC (rev 9398)
@@ -7,72 +7,27 @@
import freenet.support.Logger;
/**
- * Time based running average.
- * Smoother and less memory usage than an intervalled running average.
- * Does not implement serialization.
- * Uses Math.exp() and a divide on every report so slow if FP is slow.
- * @author amphibian
- * Mathematical basis:
- * We want a weighted average of all reports ever:
- * We have reports r1...rN, which were t1...tN millis ago.
- * Weight of r1 is 0.5^(t1/tHalf)
- * So total is:
- * T =
- * r1*0.5^(t1/tHalf) +
- * r2*0.5^(t2/tHalf) +
- * r3*0.5^(t3/tHalf) +
- * ...
- * Now, if we move forward tDelta, we get:
- * r1*0.5^((t1+tDelta)/tHalf) +
- * r2*0.5^((t2+tDelta)/tHalf) +
- * r3*0.5^((t3+tDelta)/tHalf) +
- * ...
- * =
- * r1*0.5^((t1/tHalf)+(tDelta/tHalf)) +
- * r2*0.5^((t2/tHalf)+(tDelta/tHalf)) +
- * r3*0.5^((t3/tHalf)+(tDelta/tHalf)) +
- * ...
- * =
- * (r1*0.5^(t1/tHalf)) * 0.5 ^ (tDelta/tHalf) + ...
- * = T * 0.5 ^ (tDelta/tHalf)
- *
- * The weighted mean will then be:
- * Tnew = (Tprev * 0.5 ^ (tDelta/tHalf) + r0 * 0.5^0) /
- * (0.5^(t1/tHalf) + 0.5^(t2/tHalf) + 0.5^(t3/tHalf) + ...)
- *
- * So we need to track:
- * T: T -> T * 0.5 ^ (tDelta/tHalf) + R
- * W (total weight) =
- * 0.5^(t1/tHalf) + 0.5^(t2/tHalf) + ...
- * Now, go forward by tDelta millis, we get:
- * W = 0.5^((t1+tDelta)/tHalf) + 0.5^((t2+tDelta)/tHalf) + ...
- * = W * 0.5^tDelta/tHalf
- * Adding a new report, we get: W -> W * 0.5^(tDelta/tHalf) + 1
+ * Time decaying running average.
*
- * So our equasions are:
- * T -> T * 0.5 ^ (tDelta/tHalf) + R
- * W -> W * 0.5 ^ (tDelta/tHalf) + 1
+ * Decay factor = 0.5 ^ (interval / halflife).
*
- * And the overall weighted average is T / W
+ * So if the interval is exactly the half-life then reporting 0 will halve the
value.
*
- * Stability?
- * Lets say tDelta = 0 every time, for maximum increase.
- * Then we get: T -> T + R
- * W -> W + 1
- * Thus both numbers will work fine.
+ * Note that the older version has a half life on the influence of any given
report without taking
+ * into account the fact that reports persist and accumulate. :)
+ *
*/
public class TimeDecayingRunningAverage implements RunningAverage {
private static final long serialVersionUID = -1;
- static final int MAGIC = 0x5ff4ac92;
+ static final int MAGIC = 0x5ff4ac94;
public final Object clone() {
return new TimeDecayingRunningAverage(this);
}
- double weightedTotal;
- double totalWeights;
- double halfLife;
+ double curValue;
+ final double halfLife;
long lastReportTime;
long createdTime;
long totalReports;
@@ -83,8 +38,7 @@
boolean logDEBUG;
public String toString() {
- return super.toString() + ": weightedTotal="+weightedTotal+
- ", totalWeights="+totalWeights+", halfLife="+halfLife+
+ return super.toString() + ": currentValue="+curValue+",
halfLife="+halfLife+
", lastReportTime="+(System.currentTimeMillis()-lastReportTime)+
"ms ago, createdTime="+(System.currentTimeMillis()-createdTime)+
"ms ago, totalReports="+totalReports+", started="+started+
@@ -93,8 +47,7 @@
public TimeDecayingRunningAverage(double defaultValue, long halfLife,
double min, double max) {
- weightedTotal = 0.0;
- totalWeights = 0.0;
+ curValue = defaultValue;
this.defaultValue = defaultValue;
started = false;
this.halfLife = halfLife;
@@ -113,20 +66,12 @@
if(m != MAGIC) throw new IOException("Invalid magic "+m);
int v = dis.readInt();
if(v != 1) throw new IOException("Invalid version "+v);
- weightedTotal = dis.readDouble();
- if(Double.isInfinite(weightedTotal) || Double.isNaN(weightedTotal))
- throw new IOException("Invalid weightedTotal: "+weightedTotal);
- totalWeights = dis.readDouble();
- if(totalWeights < 0.0 || Double.isInfinite(totalWeights) ||
Double.isNaN(totalWeights))
- throw new IOException("Invalid totalWeights: "+totalWeights);
- double avg = weightedTotal / totalWeights;
- if(avg < min || avg > max)
- throw new IOException("Out of range: weightedTotal =
"+weightedTotal+", totalWeights = "+totalWeights);
+ curValue = dis.readDouble();
+ if(Double.isInfinite(curValue) || Double.isNaN(curValue))
+ throw new IOException("Invalid weightedTotal: "+curValue);
+ if(curValue < min || curValue > max)
+ throw new IOException("Out of range: curValue = "+curValue);
started = dis.readBoolean();
- if(!started) {
- totalWeights = 0.0;
- weightedTotal = 0.0;
- }
long priorExperienceTime = dis.readLong();
this.halfLife = halfLife;
this.minReport = min;
@@ -147,14 +92,11 @@
this.minReport = a.minReport;
this.started = a.started;
this.totalReports = a.totalReports;
- this.totalWeights = a.totalWeights;
- this.weightedTotal = a.weightedTotal;
+ this.curValue = a.curValue;
}
public synchronized double currentValue() {
- if(!started)
- return defaultValue;
- else return weightedTotal / totalWeights;
+ return curValue;
}
public synchronized void report(double d) {
@@ -163,8 +105,7 @@
totalReports++;
long now = System.currentTimeMillis();
if(!started) {
- weightedTotal = d;
- totalWeights = 1.0;
+ curValue = d;
started = true;
if(logDEBUG)
Logger.debug(this, "Reported "+d+" on "+this+" when just
started");
@@ -173,17 +114,18 @@
now - lastReportTime;
double thisHalfLife = halfLife;
long uptime = now - createdTime;
- if((uptime / 4) < thisHalfLife) thisHalfLife = (uptime / 4);
+ //if((uptime / 4) < thisHalfLife) thisHalfLife = (uptime / 4);
if(thisHalfLife == 0) thisHalfLife = 1;
double changeFactor =
Math.pow(0.5, ((double)thisInterval) / thisHalfLife);
- weightedTotal = weightedTotal * changeFactor + d;
- totalWeights = totalWeights * changeFactor + 1.0;
+ double oldCurValue = curValue;
+ curValue = curValue * changeFactor /* close to 1.0 if short
interval, close to 0.0 if long interval */
+ + (1.0 - changeFactor) * d;
if(logDEBUG)
Logger.debug(this, "Reported "+d+" on "+this+":
thisInterval="+thisInterval+
", halfLife="+halfLife+", uptime="+uptime+",
thisHalfLife="+thisHalfLife+
- ", changeFactor="+changeFactor+",
weightedTotal="+weightedTotal+
- ",
totalWeights="+totalWeights+", currentValue="+currentValue()+
+ ", changeFactor="+changeFactor+",
oldCurValue="+oldCurValue+
+ ",
currentValue="+currentValue()+
",
thisInterval="+thisInterval+", thisHalfLife="+thisHalfLife+
", uptime="+uptime+",
changeFactor="+changeFactor);
}
@@ -201,8 +143,7 @@
public synchronized void writeDataTo(DataOutputStream out) throws
IOException {
out.writeInt(MAGIC);
out.writeInt(1);
- out.writeDouble(weightedTotal);
- out.writeDouble(totalWeights);
+ out.writeDouble(curValue);
out.writeBoolean(started);
out.writeLong(totalReports);
out.writeLong(System.currentTimeMillis() - createdTime);
