Merge lp:~sidnei/txstatsd/faster-exponentially-decaying-sample into lp:txstatsd

[Sidnei da Silva]

Speed up update() by avoiding attribute access where possible

Speed up update() by avoiding attribute access where possible

[Lucio Torre (lucio.torre)]

we can also remove the inner call to time.time() and use now = timestamp

review: Approve

[lp:~sidnei/txstatsd/faster-exponentially-decaying-sample]

90. By Sidnei da Silva on 2012-05-11

- Use timestamp as tick if provided

=== modified file 'txstatsd/stats/exponentiallydecayingsample.py'
--- txstatsd/stats/exponentiallydecayingsample.py	2012-03-07 20:20:52 +0000
+++ txstatsd/stats/exponentiallydecayingsample.py	2012-05-11 06:12:19 +0000
@@ -1,7 +1,7 @@
-import bisect
-import math
-import random
-import time
+from time import time
+from random import random
+from math import exp
+from bisect import insort
 
 
 class ExponentiallyDecayingSample(object):
@@ -30,17 +30,12 @@
         @parama alpha: The exponential decay factor; the higher this is,
             the more biased the sample will be towards newer values.
         """
-        self._values = []
         self.alpha = alpha
         self.reservoir_size = reservoir_size
 
-        self.count = 0
-        self.start_time = 0
-        self.next_scale_time = 0
-
         if wall_time is None:
-            wall_time = time.time
-        self._wall_time = wall_time
+            wall_time = time
+        self.tick = wall_time
         self.clear()
 
     def clear(self):
@@ -48,7 +43,7 @@
         self.count = 0
         self.start_time = self.tick()
         self.next_scale_time = (
-            self._wall_time() + self.RESCALE_THRESHOLD)
+            self.tick() + self.RESCALE_THRESHOLD)
 
     def size(self):
         return min(self.reservoir_size, self.count)
@@ -60,35 +55,27 @@
         @param timestamp: The epoch timestamp of *value* in seconds.
         """
 
-        now = self._wall_time()
-        next = self.next_scale_time
-        if now >= next:
-            self.rescale(now, next)
-
         if timestamp is None:
             timestamp = self.tick()
-
-        priority = self.weight(timestamp - self.start_time) / random.random()
-        self.count += 1
-        new_count = self.count
-        if new_count <= self.reservoir_size:
-            bisect.insort(self._values, (priority, value))
+        now = timestamp
+            
+        if now >= self.next_scale_time:
+            self.rescale(now, self.next_scale_time)
+
+        priority = exp(self.alpha * (timestamp - self.start_time)) / random()
+        values = self._values
+
+        if self.count < self.reservoir_size:
+            self.count += 1
+            insort(values, (priority, value))
         else:
-            first = self._values[0][0]
-
-            if first < priority:
-                bisect.insort(self._values, (priority, value))
-                self._values = self._values[1:]
-
+            if values[0][0] < priority:
+                insort(values, (priority, value))
+                values.pop(0)
+            
     def get_values(self):
         return [v for (k, v) in self._values]
 
-    def tick(self):
-        return self._wall_time()
-
-    def weight(self, t):
-        return math.exp(self.alpha * t)
-
     def rescale(self, now, next):
         """
         A common feature of the above techniques - indeed, the key technique
@@ -112,13 +99,12 @@
         pass over whatever data structure is being used.
         """
 
-        self.next_scale_time = (
-            now + self.RESCALE_THRESHOLD)
+        self.next_scale_time = (now + self.RESCALE_THRESHOLD)
         old_start_time = self.start_time
-        self.start_time = self.tick()
+        self.start_time = now
 
         new_values = []
         for k, v in self._values:
-            nk = k * math.exp(-self.alpha * (self.start_time - old_start_time))
-            new_values.append((nk, v))
+            nk = k * exp(-self.alpha * (self.start_time - old_start_time))
+            insort(new_values, (nk, v))
         self._values = new_values