[Zodb-checkins] CVS: ZODB3/ZEO - simul.py:1.10
Guido van Rossum
guido@python.org
Mon, 9 Sep 2002 21:51:20 -0400
Update of /cvs-repository/ZODB3/ZEO
In directory cvs.zope.org:/tmp/cvs-serv31300
Modified Files:
simul.py
Log Message:
Rewrite the simple free list allocator using Tim's suggestion of
keeping track of the beginning and end address of all free blocks, to
make merging of adjacent blocks a breeze. The free list is no longer
kept sorted order.
Unfortunately, this still performs poorly. It has a higher hit rate
(with the 38 minute trace I'm using; the longer traces take too long)
than the buddy system allocator with the same arena size, it is *much*
slower, the memory usage is under 20% (!!!), and despite a roving
pointer, the allocation loop is taken an average of 692 times per
allocation. At the end of the simulation the free list contains 1039
blocks; I presume this is a steady state approximating the average
behavior. (There are 2280 allocated blocks at that point, roughly
confirming Knuth's "50% rule" and suggesting that the block merge code
works properly.)
I guess the next idea is separate free lists per size.
=== ZODB3/ZEO/simul.py 1.9 => 1.10 ===
--- ZODB3/ZEO/simul.py:1.9 Mon Sep 9 20:34:32 2002
+++ ZODB3/ZEO/simul.py Mon Sep 9 21:51:20 2002
@@ -539,20 +539,21 @@
self.rover = self.avail
node = BlockNode(None, arenasize, 0)
node.linkbefore(self.avail)
+ self.taglo = {0: node}
+ self.taghi = {arenasize: node}
# Allocator statistics
self.nallocs = 0
self.nfrees = 0
self.allocloops = 0
- self.freeloops = 0
self.freebytes = arenasize
self.freeblocks = 1
self.allocbytes = 0
self.allocblocks = 0
def report(self):
- print ("NA=%d AL=%d NF=%d FL=%d ABy=%d ABl=%d FBy=%d FBl=%d" %
+ print ("NA=%d AL=%d NF=%d ABy=%d ABl=%d FBy=%d FBl=%d" %
(self.nallocs, self.allocloops,
- self.nfrees, self.freeloops,
+ self.nfrees,
self.allocbytes, self.allocblocks,
self.freebytes, self.freeblocks))
@@ -560,29 +561,30 @@
self.nallocs += 1
# First fit algorithm
rover = stop = self.rover
- free = None
while 1:
self.allocloops += 1
if rover.size >= size:
- if rover.size == size:
- self.rover = rover.next
- rover.unlink()
- self.freeblocks -= 1
- self.allocblocks += 1
- self.freebytes -= size
- self.allocbytes += size
- return rover
- free = rover
break
rover = rover.next
if rover is stop:
- break
- if free is None: # We ran out of space
- return None
- # Take space from the end of the roving pointer
- assert free.size > size
- node = BlockNode(None, size, free.addr + free.size - size)
- free.size -= size
+ return None # We went round the list without finding space
+ if rover.size == size:
+ self.rover = rover.next
+ rover.unlink()
+ del self.taglo[rover.addr]
+ del self.taghi[rover.addr + size]
+ self.freeblocks -= 1
+ self.allocblocks += 1
+ self.freebytes -= size
+ self.allocbytes += size
+ return rover
+ # Take space from the beginning of the roving pointer
+ assert rover.size > size
+ node = BlockNode(None, size, rover.addr)
+ del self.taglo[rover.addr]
+ rover.size -= size
+ rover.addr += size
+ self.taglo[rover.addr] = rover
#self.freeblocks += 0 # No change here
self.allocblocks += 1
self.freebytes -= size
@@ -591,32 +593,37 @@
def free(self, node):
self.nfrees += 1
+ self.freeblocks += 1
+ self.allocblocks -= 1
self.freebytes += node.size
self.allocbytes -= node.size
- self.allocblocks -= 1
- x = self.avail.next
- while x is not self.avail and x.addr < node.addr:
- self.freeloops += 1
- x = x.next
- if node.addr + node.size == x.addr: # Merge with next
- x.addr -= node.size
- x.size += node.size
- node = x
- else: # Insert new node into free list
- node.linkbefore(x)
- self.freeblocks += 1
- x = node.prev
- if node.addr == x.addr + x.size and x is not self.avail:
- # Merge with previous node in free list
- node.unlink()
- x.size += node.size
- node = x
+ node.linkbefore(self.avail)
+ self.taglo[node.addr] = node
+ self.taghi[node.addr + node.size] = node
+ x = self.taghi.get(node.addr)
+ if x is not None:
+ # Merge x into node
+ x.unlink()
+ self.freeblocks -= 1
+ del self.taglo[x.addr]
+ del self.taghi[x.addr + x.size]
+ del self.taglo[node.addr]
+ node.addr = x.addr
+ node.size += x.size
+ self.taglo[node.addr] = node
+ x = self.taglo.get(node.addr + node.size)
+ if x is not None:
+ # Merge x into node
+ x.unlink()
self.freeblocks -= 1
+ del self.taglo[x.addr]
+ del self.taghi[x.addr + x.size]
+ del self.taghi[node.addr + node.size]
+ node.size += x.size
+ self.taghi[node.addr + node.size] = node
# It's possible that either one of the merges above invalidated
# the rover.
# It's simplest to simply reset the rover to the newly freed block.
- # It also seems optimal; if I only move the rover when it's
- # become invalid, there performance goes way down.
self.rover = node
def dump(self, msg=""):
@@ -654,6 +661,7 @@
while queue and queue[0][0] <= T:
time, node = heapq.heappop(queue)
assert time == T
+ ##print "free addr=%d, size=%d" % (node.addr, node.size)
cache.free(node)
blocks -= 1
size = random.randint(100, 2000)
@@ -664,6 +672,7 @@
cache.dump("T=%4d: %d blocks;" % (T, blocks))
break
else:
+ ##print "alloc addr=%d, size=%d" % (node.addr, node.size)
blocks += 1
heapq.heappush(queue, (T + lifetime, node))
T = T+1