[Neo-report] r2710 jm - in /trunk/neo/client: cache.py mq.py
nobody at svn.erp5.org
nobody at svn.erp5.org
Tue Apr 12 18:15:48 CEST 2011
Author: jm
Date: Tue Apr 12 18:15:48 2011
New Revision: 2710
Log:
client: rename mq.py to cache.py before rewriting it
Added:
trunk/neo/client/cache.py
- copied, changed from r2709, trunk/neo/client/mq.py
Removed:
trunk/neo/client/mq.py
Copied: trunk/neo/client/cache.py (from r2709, trunk/neo/client/mq.py)
==============================================================================
(empty)
Removed: trunk/neo/client/mq.py
==============================================================================
--- trunk/neo/client/mq.py [iso-8859-1] (original)
+++ trunk/neo/client/mq.py (removed)
@@ -1,382 +0,0 @@
-##############################################################################
-#
-# Copyright (c) 2005 Nexedi SARL and Contributors. All Rights Reserved.
-# Yoshinori Okuji <yo at nexedi.com>
-#
-# WARNING: This program as such is intended to be used by professional
-# programmers who take the whole responsability of assessing all potential
-# consequences resulting from its eventual inadequacies and bugs
-# End users who are looking for a ready-to-use solution with commercial
-# garantees and support are strongly adviced to contract a Free Software
-# Service Company
-#
-# This program is Free Software; you can redistribute it and/or
-# modify it under the terms of the GNU General Public License
-# as published by the Free Software Foundation; either version 2
-# of the License, or (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-#
-##############################################################################
-
-"""
-Multi-Queue Cache Algorithm.
-"""
-
-from math import log
-
-class MQIndex(object):
- """
- Virtual base class for MQ cache external indexes.
- """
- def clear(self):
- """
- Called when MQ is cleared.
- """
- raise NotImplementedError
-
- def remove(self, key):
- """
- Called when key's value is removed from cache, and key is pushed to
- history buffer.
- """
- raise NotImplementedError
-
- def add(self, key):
- """
- Called when key is added into cache.
- It is either a new key, or a know key comming back from history
- buffer.
- """
- raise NotImplementedError
-
-class Element(object):
- """
- This class defines an element of a FIFO buffer.
- """
- pass
-
-class FIFO(object):
- """
- This class implements a FIFO buffer.
- """
-
- def __init__(self):
- self.head = None
- self.tail = None
- self._len = 0
- self.prev = None
- self.data = None
- self.next = None
- self.level = None
- self.counter = None
- self.value = None
- self.element = None
- self.key = None
- self.expire_time = None
-
- def __len__(self):
- return self._len
-
- def append(self):
- element = Element()
- element.next = None
- element.prev = self.tail
- if self.tail is not None:
- self.tail.next = element
- self.tail = element
- if self.head is None:
- self.head = element
- self._len += 1
- return element
-
- def shift(self):
- element = self.head
- if element is None:
- return None
- del self[element]
- del element.next
- del element.prev
- return element
-
- def __delitem__(self, element):
- if element.next is None:
- self.tail = element.prev
- else:
- element.next.prev = element.prev
-
- if element.prev is None:
- self.head = element.next
- else:
- element.prev.next = element.next
-
- self._len -= 1
-
-class Data(object):
- """
- Data for each element in a FIFO buffer.
- """
- pass
-
-def sizeof(o):
- """This function returns the estimated size of an object."""
- if isinstance(o, tuple):
- return sum((sizeof(s) for s in o))
- elif o is None:
- # XXX: unknown size (arch pointer ?)
- return 0
- else:
- return len(o)+16
-
-class MQ(object):
- """
- This class manages cached data by a variant of Multi-Queue.
-
- This class caches various sizes of objects. Here are some considerations:
-
- - Expired objects are not really deleted immediately. But if GC is invoked too often,
- it degrades the performance significantly.
-
- - If large objects are cached, the number of cached objects decreases. This might affect
- the cache hit ratio. It might be better to tweak a buffer level according to the size of
- an object.
-
- - Stored values must be strings.
-
- - The size calculation is not accurate.
-
- Quick description of Multi-Queue algorithm:
- - There are multiple "regular" queues, plus a history queue
- - The queue to store an object in depends on its access frequency
- - The queue an object is in defines its lifespan (higher-index queue eq.
- longer lifespan)
- -> The more often an object is accessed, the higher lifespan it will
- have
- - Upon a cache miss, the oldest entry of first non-empty queue is
- transfered to history queue
- - Upon cache or history hit, object frequency is increased and object
- might get moved to longer-lived queue
- - Each access "ages" objects in cache, and an aging object is moved to
- shorter-lived queue as it ages without being accessed
- """
-
- def __init__(self, life_time=10000, buffer_levels=9,
- max_history_size=100000, max_size=20*1024*1024):
- self._index_list = []
- self._life_time = life_time
- self._buffer_levels = buffer_levels
- self._max_history_size = max_history_size
- self._max_size = max_size
- self.clear()
-
- def addIndex(self, index, reindex=True):
- """
- Add an index ot this cache.
- index
- Object implementing methods from MQIndex class.
- reindex (True)
- If True, give all existing keys as new to index.
- """
- if reindex:
- # Index existing entries
- add = index.add
- for key in self._data:
- add(key)
- self._index_list.append(index)
-
- def _mapIndexes(self, method_id, args=(), kw={}):
- for index in self._index_list:
- getattr(index, method_id)(*args, **kw)
-
- def clear(self):
- self._history_buffer = FIFO()
- self._cache_buffers = []
- for level in range(self._buffer_levels):
- self._cache_buffers.append(FIFO())
- self._data = {}
- self._time = 0
- self._size = 0
- self._mapIndexes('clear')
-
- def has_key(self, key):
- if key in self._data:
- data = self._data[key]
- if data.level >= 0:
- return 1
- return 0
-
- __contains__ = has_key
-
- def fetch(self, key):
- """
- Fetch a value associated with the key.
- """
- data = self._data[key]
- if data.level >= 0:
- value = data.value
- self._size -= sizeof(value)
- self.store(key, value)
- return value
- raise KeyError(key)
-
- __getitem__ = fetch
-
- def get(self, key, d=None):
- try:
- return self.fetch(key)
- except KeyError:
- return d
-
- def _evict(self, key):
- """
- Evict an element to the history buffer.
- """
- self._mapIndexes('remove', (key, ))
- data = self._data[key]
- self._size -= sizeof(data.value)
- del self._cache_buffers[data.level][data.element]
- element = self._history_buffer.append()
- data.level = -1
- data.element = element
- del data.value
- del data.expire_time
- element.data = data
- if len(self._history_buffer) > self._max_history_size:
- element = self._history_buffer.shift()
- del self._data[element.data.key]
-
- def store(self, key, value):
- cache_buffers = self._cache_buffers
-
- try:
- data = self._data[key]
- except KeyError:
- counter = 1
- self._mapIndexes('add', (key, ))
- else:
- level, element, counter = data.level, data.element, data.counter + 1
- if level >= 0:
- del cache_buffers[level][element]
- else:
- del self._history_buffer[element]
- self._mapIndexes('add', (key, ))
-
- # XXX It might be better to adjust the level according to the object
- # size.
- level = min(int(log(counter, 2)), self._buffer_levels - 1)
- element = cache_buffers[level].append()
- data = Data()
- data.key = key
- data.expire_time = self._time + self._life_time
- data.level = level
- data.element = element
- data.value = value
- data.counter = counter
- element.data = data
- self._data[key] = data
- self._size += sizeof(value)
- del value
-
- self._time += 1
-
- # Expire old elements.
- time = self._time
- for level, cache_buffer in enumerate(cache_buffers):
- head = cache_buffer.head
- if head is not None and head.data.expire_time < time:
- del cache_buffer[head]
- data = head.data
- if level > 0:
- new_level = level - 1
- element = cache_buffers[new_level].append()
- element.data = data
- data.expire_time = time + self._life_time
- data.level = new_level
- data.element = element
- else:
- self._evict(data.key)
-
- # Limit the size.
- max_size = self._max_size
- if self._size > max_size:
- for cache_buffer in cache_buffers:
- while self._size > max_size:
- element = cache_buffer.head
- if element is None:
- break
- self._evict(element.data.key)
- if self._size <= max_size:
- break
-
- __setitem__ = store
-
- def invalidate(self, key):
- if key in self._data:
- data = self._data[key]
- if data.level >= 0:
- del self._cache_buffers[data.level][data.element]
- self._evict(key)
- return
- raise KeyError, "%s was not found in the cache" % (key, )
-
- __delitem__ = invalidate
-
- def update(self, key, callback):
- """
- Update entry without changing its level.
- """
- data = self._data[key]
- if data.level < 0:
- raise KeyError(key)
- data.value = callback(data.value)
-
-# Here is a test.
-if __name__ == '__main__':
- import hotshot, hotshot.stats
-
- def test():
- cache = MQ(life_time=100, buffer_levels=9, max_history_size=10000,
- max_size=2*1024*1024)
-
- cache[0] = 'foo'
- assert cache[0] == 'foo', '0 should be present'
- del cache[0]
- assert cache.get(0) is None, '0 should not be present'
-
- for i in xrange(10000):
- assert cache.get(i) is None, '%d should not be present' % i
-
- for i in xrange(10000):
- cache[i] = str(i)
- assert cache.get(i) == str(i), '%d does not exist' % i
-
- for i in xrange(10000 - 100 - 1):
- assert cache.get(i) is None, '%d should not be present' % i
-
- for i in xrange(10):
- cache[i] = str(i)
-
- for _ in xrange(1000):
- for i in xrange(10):
- assert cache.get(i) == str(i), '%d does not exist' % i
-
- for i in xrange(10, 500):
- cache[i] = str(i)
-
- for i in xrange(10):
- assert cache.get(i) == str(i), '%d does not exist' % i
-
- prof = hotshot.Profile("mq.prof")
- prof.runcall(test)
- prof.close()
- stats = hotshot.stats.load("mq.prof")
- stats.strip_dirs()
- stats.sort_stats('time', 'calls')
- stats.print_stats(20)
More information about the Neo-report
mailing list