1# -*- coding: utf-8 -*-
2
3########################################################################
4#
5# License: BSD
6# Created: Aug 13, 2006
7# Author:  Francesc Alted - faltet@pytables.com
8#
9# $Id: $
10#
11########################################################################
12
13"""Cython interface for several LRU cache systems.
14
15Classes (type extensions):
16
17    NodeCache
18    ObjectCache
19    NumCache
20
21Functions:
22
23Misc variables:
24
25"""
26
27cdef extern from "Python.h":
28    int PyUnicode_Compare(object, object)
29
30import sys
31
32import numpy
33from libc.string cimport memcpy, strcmp
34from cpython.unicode cimport PyUnicode_Check
35from numpy cimport import_array, ndarray
36
37from .parameters import (DISABLE_EVERY_CYCLES, ENABLE_EVERY_CYCLES,
38  LOWEST_HIT_RATIO)
39
40
41
42#----------------------------------------------------------------------------
43# Initialization code.
44# The numpy API requires this function to be called before
45# using any numpy facilities in an extension module.
46import_array()
47#----------------------------------------------------------------------------
48
49
50# ------- Minimalist NodeCache for nodes in PyTables ---------
51
52# The next NodeCache code relies on the fact that a node that is
53# fetched from the cache will be removed from it. Said in other words:
54# "A node cannot be alive and dead at the same time."
55
56# Thanks to the above behaviour, the next code has been stripped down
57# to a bare minimum (the info in cache is kept in just 2 lists).
58
59#*********************** Important note! *****************************
60# The code behind has been carefully tuned to serve the needs of
61# PyTables cache for nodes. As a consequence, it is no longer
62# appropriate as a general LRU cache implementation. You have been
63# warned!.  F. Alted 2006-08-08
64#*********************************************************************
65
66
67cdef class NodeCache:
68  """Least-Recently-Used (LRU) cache for PyTables nodes."""
69
70  def __init__(self, nslots):
71    """Maximum nslots of the cache.
72
73    If more than 'nslots' elements are added to the cache,
74    the least-recently-used ones will be discarded.
75
76    """
77
78    if nslots < 0:
79      raise ValueError("Negative number (%s) of slots!" % nslots)
80    self.nslots = nslots
81    self.nextslot = 0
82    self.nodes = []
83    self.paths = []
84
85  def __len__(self):
86    return len(self.nodes)
87
88  def __setitem__(self, path, node):
89    self.setitem(path, node)
90
91  cdef setitem(self, object path, object node):
92    """Puts a new node in the node list."""
93
94    if self.nslots == 0:   # Oops, the cache is set to empty
95      return
96    # Check if we are growing out of space
97    if self.nextslot == self.nslots:
98      # It is critical to reduce nextslot *before* the preemption of
99      # the LRU node.  If not, this can lead with problems in situations
100      # with very small caches (length 1 or so).
101      # F. Alted 2008-10-22
102      self.nextslot = self.nextslot - 1
103      # Remove the LRU node and path (the start of the lists)
104      del self.nodes[0]
105      del self.paths[0]
106    # The equality protection has been put for situations in which a
107    # node is being preempted and added simultaneously (with very small
108    # caches).
109    if len(self.nodes) == len(self.paths):
110      # Add the node and path to the end of its lists
111      self.nodes.append(node)
112      self.paths.append(path)
113      self.nextslot = self.nextslot + 1
114
115  def __contains__(self, path):
116    if self.getslot(path) == -1:
117      return 0
118    else:
119      return 1
120
121  cdef long getslot(self, object path):
122    """Checks whether path is in this cache or not."""
123
124    cdef long i, nslot, compare
125
126    nslot = -1  # -1 means not found
127    if PyUnicode_Check(path):
128        # Start looking from the trailing values (most recently used)
129        for i from self.nextslot > i >= 0:
130          #if strcmp(<char *>encoded_path, <char *>self.paths[i]) == 0:
131          if PyUnicode_Compare(path, self.paths[i]) == 0:
132            nslot = i
133            break
134    else:
135        # Start looking from the trailing values (most recently used)
136        for i from self.nextslot > i >= 0:
137          #if strcmp(<char *>path, <char *>self.paths[i]) == 0:
138          if PyUnicode_Check(self.paths[i]):
139            compare = PyUnicode_Compare(path, self.paths[i])
140          else:
141            compare = strcmp(<char *>path, <char *>self.paths[i])
142          if compare == 0:
143            nslot = i
144            break
145
146    return nslot
147
148  __marker = object()
149
150  def pop(self, path, d=__marker):
151    try:
152      node = self.cpop(path)
153    except KeyError:
154      if d is not self.__marker:
155        return d
156      else:
157        raise
158    else:
159      return node
160
161  cdef object cpop(self, object path):
162    cdef long nslot
163
164    nslot = self.getslot(path)
165    if nslot == -1:
166        raise KeyError(path)
167    else:
168        node = self.nodes[nslot]
169        del self.nodes[nslot]
170        del self.paths[nslot]
171        self.nextslot = self.nextslot - 1
172    return node
173
174  def __iter__(self):
175    # Do a copy of the paths list because it can be modified in the middle of
176    # the iterator!
177    copy = self.paths[:]
178    return iter(copy)
179
180  def __repr__(self):
181    return "<%s (%d elements)>" % (str(self.__class__), len(self.paths))
182
183
184########################################################################
185# Common code for other LRU cache classes
186########################################################################
187
188cdef class BaseCache:
189  """Base class that implements automatic probing/disabling of the cache."""
190
191  def __init__(self, long nslots, object name):
192
193    if nslots < 0:
194      raise ValueError("Negative number (%s) of slots!" % nslots)
195    self.setcount = 0;  self.getcount = 0;  self.containscount = 0
196    self.enablecyclecount = 0;  self.disablecyclecount = 0
197    self.iscachedisabled = False  # Cache is enabled by default
198    self.disableeverycycles = DISABLE_EVERY_CYCLES
199    self.enableeverycycles = ENABLE_EVERY_CYCLES
200    self.lowesthr = LOWEST_HIT_RATIO
201    self.nprobes = 0.0;  self.hitratio = 0.0
202    self.nslots = nslots
203    self.seqn_ = 0;  self.nextslot = 0
204    self.name = name
205    self.incsetcount = False
206    # The array for keeping the access times (using long ints here)
207    self.atimes = <ndarray>numpy.zeros(shape=nslots, dtype=numpy.int_)
208    self.ratimes = <long *>self.atimes.data
209
210  def __len__(self):
211    return self.nslots
212
213  # Machinery for determining whether the hit ratio is being effective
214  # or not.  If not, the cache will be disabled. The efficency will be
215  # checked every cycle (the time that the cache would be refilled
216  # completely).  In situations where the cache is not being re-filled
217  # (i.e. it is not enabled) for a long time, it is forced to be
218  # re-enabled when a certain number of cycles has passed so as to
219  # check whether a new scenario where the cache can be useful again
220  # has come.
221  # F. Alted 2006-08-09
222  cdef int checkhitratio(self):
223    cdef double hitratio
224    cdef long nslot
225
226    if self.setcount > self.nslots:
227      self.disablecyclecount = self.disablecyclecount + 1
228      self.enablecyclecount = self.enablecyclecount + 1
229      self.nprobes = self.nprobes + 1
230      hitratio = <double>self.getcount / self.containscount
231      self.hitratio = self.hitratio + hitratio
232      # Reset the hit counters
233      self.setcount = 0;  self.getcount = 0;  self.containscount = 0
234      if (not self.iscachedisabled and
235          self.disablecyclecount >= self.disableeverycycles):
236        # Check whether the cache is being effective or not
237        if hitratio < self.lowesthr:
238          # Hit ratio is low. Disable the cache.
239          self.iscachedisabled = True
240        else:
241          # Hit ratio is acceptable. (Re-)Enable the cache.
242          self.iscachedisabled = False
243        self.disablecyclecount = 0
244      if self.enablecyclecount >= self.enableeverycycles:
245        # We have reached the time for forcing the cache to act again
246        self.iscachedisabled = False
247        self.enablecyclecount = 0
248    return not self.iscachedisabled
249
250  def couldenablecache(self):
251    return self.couldenablecache_()
252
253  # Check whether the cache is enabled or *could* be enabled in the next
254  # setitem operation. This method can be used in order to probe whether
255  # an (expensive) operation to be done before a .setitem() is worth the
256  # effort or not.
257  cdef int couldenablecache_(self):
258
259    if self.nslots == 0:
260      return False
261    # Increment setitem because it can be that .setitem() doesn't
262    # get called after calling this.
263    self.setcount = self.setcount + 1;  self.incsetcount = True
264    if self.iscachedisabled:
265      if self.setcount == self.nslots:
266        # The cache *could* be enabled in the next setitem operation
267        return True
268      else:
269        return False
270    else:
271      return True
272
273  # Increase the access time (implemented as a C long sequence)
274  cdef long incseqn(self):
275
276    self.seqn_ = self.seqn_ + 1
277    if self.seqn_ < 0:
278      # Ooops, the counter has run out of range! Reset all the access times.
279      self.atimes[:] = sys.maxint
280      # Set the counter to 1 (to indicate that it is newer than existing ones)
281      self.seqn_ = 1
282    return self.seqn_
283
284  def __repr__(self):
285    return "<%s(%s) (%d elements)>" % (self.name, str(self.__class__),
286                                       self.nslots)
287
288
289########################################################################
290#  Helper class for ObjectCache
291########################################################################
292
293cdef class ObjectNode:
294  """Record of a cached value. Not for public consumption."""
295
296  def __init__(self, object key, object obj, long nslot):
297    object.__init__(self)
298    self.key = key
299    self.obj = obj
300    self.nslot = nslot
301
302  def __repr__(self):
303    return "<%s %s (slot #%s) => %s>" % (self.__class__, self.key, self.nslot,
304                                         self.object)
305
306
307########################################################################
308#  Minimalistic LRU cache implementation for general python objects
309#        This is a *true* general lru cache for python objects
310########################################################################
311
312cdef class ObjectCache(BaseCache):
313  """Least-Recently-Used (LRU) cache specific for python objects."""
314
315  def __init__(self, long nslots, long maxcachesize, object name):
316    """Maximum size of the cache.
317
318    If more than 'nslots' elements are added to the cache,
319    the least-recently-used ones will be discarded.
320
321    Parameters:
322    nslots - The number of slots in cache
323    name - A descriptive name for this cache
324
325    """
326
327    super(ObjectCache, self).__init__(nslots, name)
328    self.cachesize = 0
329    self.maxcachesize = maxcachesize
330    # maxobjsize will be the same as the maximum cache size
331    self.maxobjsize = maxcachesize
332    self.__list = [None]*nslots
333    self.__dict = {}
334    self.mrunode = <ObjectNode>None   # Most Recent Used node
335    # The array for keeping the object size (using long ints here)
336    self.sizes = <ndarray>numpy.zeros(shape=nslots, dtype=numpy.int_)
337    self.rsizes = <long *>self.sizes.data
338
339  # Clear cache
340  cdef clearcache_(self):
341    self.__list = [None]*self.nslots
342    self.__dict = {}
343    self.mrunode = <ObjectNode>None
344    self.cachesize = 0
345    self.nextslot = 0
346    self.seqn_ = 0
347
348  # Remove a slot (if it exists in cache)
349  cdef removeslot_(self, long nslot):
350    cdef ObjectNode node
351
352    assert nslot < self.nslots, "Attempting to remove beyond cache capacity."
353    node = self.__list[nslot]
354    if node is not None:
355      self.__list[nslot] = None
356      del self.__dict[node.key]
357      self.cachesize = self.cachesize - self.rsizes[nslot]
358      self.rsizes[nslot] = 0
359      if self.mrunode and self.mrunode.nslot == nslot:
360        self.mrunode = <ObjectNode>None
361    # The next slot to be updated will be this one
362    self.nextslot = nslot
363
364  # Update a slot
365  cdef updateslot_(self, long nslot, long size, object key, object value):
366    cdef ObjectNode node, oldnode
367    cdef long nslot1, nslot2
368    cdef object lruidx
369
370    assert nslot < self.nslots, "Number of nodes exceeding cache capacity."
371    # Remove the previous nslot
372    self.removeslot_(nslot)
373    # Protection against too large data cache size
374    while size + self.cachesize > self.maxcachesize:
375      # Remove the LRU node among the 10 largest ones
376      largidx = self.sizes.argsort()[-10:]
377      nslot1 = self.atimes[largidx].argmin()
378      nslot2 = largidx[nslot1]
379      self.removeslot_(nslot2)
380    # Insert the new one
381    node = ObjectNode(key, value, nslot)
382    self.ratimes[nslot] = self.incseqn()
383    self.rsizes[nslot] = size
384    self.__list[nslot] = node
385    self.__dict[key] = node
386    self.mrunode = node
387    self.cachesize = self.cachesize + size
388    # The next slot to update will be the LRU
389    self.nextslot = self.atimes.argmin()
390
391  # Put the object to the data in cache (for Python calls)
392  def setitem(self, object key, object value, object size):
393    return self.setitem_(key, value, size)
394
395  # Put the object in cache (for cython calls)
396  # size can be the exact size of the value object or an estimation.
397  cdef long setitem_(self, object key, object value, long size):
398    cdef long nslot
399
400    if self.nslots == 0:   # The cache has been set to empty
401      return -1
402    nslot = -1
403    # Perhaps setcount has been already incremented in couldenablecache()
404    if not self.incsetcount:
405      self.setcount = self.setcount + 1
406    else:
407      self.incsetcount = False
408    if size > self.maxobjsize:  # Check if the object is too large
409      return -1
410    if self.checkhitratio():
411      nslot = self.nextslot
412      self.updateslot_(nslot, size, key, value)
413    else:
414      # Empty the cache because it is not effective and it is taking space
415      self.clearcache_()
416    return nslot
417
418  # Tells whether the key is in cache or not
419  def __contains__(self, object key):
420    return self.__dict.has_key(key)
421
422  # Tells in which slot the key is. If not found, -1 is returned.
423  def getslot(self, object key):
424    return self.getslot_(key)
425
426  # Tells in which slot the key is. If not found, -1 is returned.
427  cdef long getslot_(self, object key):
428    cdef ObjectNode node
429
430    if self.nslots == 0:   # The cache has been set to empty
431      return -1
432    self.containscount = self.containscount + 1
433    # Give a chance to the MRU node
434    node = self.mrunode
435    if node and node.key == key:
436      return node.nslot
437    # No luck. Look in the dictionary.
438    node = self.__dict.get(key)
439    if node is <ObjectNode>None:
440      return -1
441    return node.nslot
442
443  # Return the object to the data in cache (for Python calls)
444  def getitem(self, object nslot):
445    return self.getitem_(nslot)
446
447  # Return the object to the data in cache (for cython calls)
448  cdef object getitem_(self, long nslot):
449    cdef ObjectNode node
450
451    self.getcount = self.getcount + 1
452    node = self.__list[nslot]
453    self.ratimes[nslot] = self.incseqn()
454    self.mrunode = node
455    return node.obj
456
457  def __repr__(self):
458    if self.nprobes > 0:
459      hitratio = self.hitratio / self.nprobes
460    else:
461      hitratio = <double>self.getcount / self.containscount
462    return """<%s(%s)
463  (%d maxslots, %d slots used, %.3f KB cachesize,
464  hit ratio: %.3f, disabled? %s)>
465  """ % (self.name, str(self.__class__), self.nslots, self.nextslot,
466         self.cachesize / 1024., hitratio, self.iscachedisabled)
467
468
469###################################################################
470#  Minimalistic LRU cache implementation for numerical data
471###################################################################
472# The next code is more efficient in situations where efficiency is low.
473###################################################################
474
475#*********************** Important note! ****************************
476# The code behind has been carefully tuned to serve the needs of
477# caching numerical data. As a consequence, it is no longer appropriate
478# as a general LRU cache implementation. You have been warned!.
479# F. Alted 2006-08-09
480#********************************************************************
481
482cdef class NumCache(BaseCache):
483  """Least-Recently-Used (LRU) cache specific for Numerical data."""
484
485  def __init__(self, object shape, object dtype, object name):
486    """Maximum size of the cache.
487
488    If more than 'nslots' elements are added to the cache,
489    the least-recently-used ones will be discarded.
490
491    Parameters:
492    shape - The rectangular shape of the cache (nslots, nelemsperslot)
493    itemsize - The size of the element base in cache
494    name - A descriptive name for this cache
495
496    """
497
498    cdef long nslots
499
500    nslots = shape[0];  self.slotsize = shape[1]
501    if nslots >= 1<<16:
502      # nslots can't be higher than 2**16. Will silently trunk the number.
503      nslots = <long>((1<<16)-1)  # Cast makes cython happy here
504    super(NumCache, self).__init__(nslots, name)
505    self.itemsize = dtype.itemsize
506    self.__dict = {}
507    # The cache object where all data will go
508    # The last slot is to allow the setitem1_ method to still return
509    # a valid scratch area for writing purposes
510    self.cacheobj = <ndarray>numpy.empty(shape=(nslots+1, self.slotsize),
511                                         dtype=dtype)
512    self.rcache = <void *>self.cacheobj.data
513    # The array for keeping the keys of slots
514    self.keys = <ndarray>(-numpy.ones(shape=nslots, dtype=numpy.int64))
515    self.rkeys = <long long *>self.keys.data
516
517  # Returns the address of nslot
518  cdef void *getaddrslot_(self, long nslot):
519    if nslot >= 0:
520      return <char *>self.rcache + nslot * self.slotsize * self.itemsize
521    else:
522      return <char *>self.rcache + self.nslots * self.slotsize * self.itemsize
523
524  def setitem(self, long long key, ndarray nparr, long start):
525    return self.setitem_(key, nparr.data, start)
526
527  # Copy the new data into a cache slot
528  cdef long setitem_(self, long long key, void *data, long start):
529    cdef long nslot
530
531    nslot = self.setitem1_(key)
532    if nslot >= 0:
533      # Copy the data to cache
534      memcpy(<char *>self.rcache + nslot * self.slotsize * self.itemsize,
535             <char *>data + start * self.itemsize,
536             self.slotsize * self.itemsize)
537    return nslot
538
539  # Return a cache data pointer appropriate to save data.
540  # Even if the cache is disabled, this will return a -1, which is
541  # the last element in the cache.
542  # This version avoids a memcpy of data, but the user should be
543  # aware that data in nslot cannot be overwritten!
544  cdef long setitem1_(self, long long key):
545    cdef long nslot
546    cdef object key2
547
548    if self.nslots == 0:   # Oops, the cache is set to empty
549      return -1
550    # Perhaps setcount has been already incremented in couldenablecache()
551    if not self.incsetcount:
552      self.setcount = self.setcount + 1
553    else:
554      self.incsetcount = False
555    nslot = -1
556    if self.checkhitratio():
557      # Check if we are growing out of space
558      if self.nextslot == self.nslots:
559        # Get the least recently used slot
560        nslot = self.atimes.argmin()
561        # Remove the slot from the dict
562        key2 = self.keys[nslot]
563        del self.__dict[key2]
564        self.nextslot = self.nextslot - 1
565      else:
566        # Get the next slot available
567        nslot = self.nextslot
568      # Insert the slot in the dictionary
569      self.__dict[key] = nslot
570      self.keys[nslot] = key
571      self.ratimes[nslot] = self.incseqn()
572      self.nextslot = self.nextslot + 1
573      # The next reduces the performance of the cache in scenarios where
574      # the efficicency is near to zero.  I don't understand exactly why.
575      # F. Alted 24-03-2008
576    elif self.nextslot > 0:
577      # Empty the cache if needed
578      self.__dict.clear()
579      self.nextslot = 0
580    return nslot
581
582  def getslot(self, long long key):
583    return self.getslot_(key)
584
585  # Tells in which slot key is. If not found, -1 is returned.
586  cdef long getslot_(self, long long key):
587    cdef object nslot
588
589    self.containscount = self.containscount + 1
590    if self.nextslot == 0:   # No chances for finding a slot
591      return -1
592    try:
593      nslot = self.__dict[key]
594    except KeyError:
595      return -1
596    return nslot
597
598  def getitem(self, long nslot, ndarray nparr, long start):
599    self.getitem_(nslot, nparr.data, start)
600
601  # This version copies data in cache to data+start.
602  # The user should be responsible to provide a large enough data buffer
603  # to keep all the data.
604  cdef getitem_(self, long nslot, void *data, long start):
605    cdef void *cachedata
606
607    cachedata = self.getitem1_(nslot)
608    # Copy the data in cache to destination
609    memcpy(<char *>data + start * self.itemsize, cachedata,
610           self.slotsize * self.itemsize)
611
612  # Return the pointer to the data in cache
613  # This version avoids a memcpy of data, but the user should be
614  # aware that data in nslot cannot be overwritten!
615  cdef void *getitem1_(self, long nslot):
616
617    self.getcount = self.getcount + 1
618    self.ratimes[nslot] = self.incseqn()
619    return <char *>self.rcache + nslot * self.slotsize * self.itemsize
620
621  def __repr__(self):
622    cachesize = (self.nslots * self.slotsize * self.itemsize) / 1024.
623    if self.nprobes > 0:
624      hitratio = self.hitratio / self.nprobes
625    elif self.containscount > 0:
626      hitratio = <double>self.getcount / self.containscount
627    else:
628      hitratio = numpy.nan
629    return """<%s(%s)
630  (%d maxslots, %d slots used, %.3f KB cachesize,
631  hit ratio: %.3f, disabled? %s)>
632  """ % (self.name, str(self.__class__), self.nslots, self.nextslot,
633         cachesize, hitratio, self.iscachedisabled)
634
635
636## Local Variables:
637## mode: python
638## py-indent-offset: 2
639## tab-width: 2
640## fill-column: 78
641## End:
642