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