Brunobkr/llama.cpp_AlgMor24_github

1# lru-cache2 3A cache object that deletes the least-recently-used items.4 5Specify a max number of the most recently used items that you6want to keep, and this cache will keep that many of the most7recently accessed items.8 9This is not primarily a TTL cache, and does not make strong TTL10guarantees. There is no preemptive pruning of expired items by11default, but you _may_ set a TTL on the cache or on a single12`set`. If you do so, it will treat expired items as missing, and13delete them when fetched. If you are more interested in TTL14caching than LRU caching, check out15[@isaacs/ttlcache](http://npm.im/@isaacs/ttlcache).16 17As of version 7, this is one of the most performant LRU18implementations available in JavaScript, and supports a wide19diversity of use cases. However, note that using some of the20features will necessarily impact performance, by causing the21cache to have to do more work. See the "Performance" section22below.23 24## Installation25 26```bash27npm install lru-cache --save28```29 30## Usage31 32```js33// hybrid module, either works34import { LRUCache } from 'lru-cache'35// or:36const { LRUCache } = require('lru-cache')37// or in minified form for web browsers:38import { LRUCache } from 'http://unpkg.com/lru-cache@9/dist/mjs/index.min.mjs'39 40// At least one of 'max', 'ttl', or 'maxSize' is required, to prevent41// unsafe unbounded storage.42//43// In most cases, it's best to specify a max for performance, so all44// the required memory allocation is done up-front.45//46// All the other options are optional, see the sections below for47// documentation on what each one does.  Most of them can be48// overridden for specific items in get()/set()49const options = {50  max: 500,51 52  // for use with tracking overall storage size53  maxSize: 5000,54  sizeCalculation: (value, key) => {55    return 156  },57 58  // for use when you need to clean up something when objects59  // are evicted from the cache60  dispose: (value, key, reason) => {61    freeFromMemoryOrWhatever(value)62  },63 64  // for use when you need to know that an item is being inserted65  // note that this does NOT allow you to prevent the insertion,66  // it just allows you to know about it.67  onInsert: (value, key, reason) => {68    logInsertionOrWhatever(key, value)69  },70 71  // how long to live in ms72  ttl: 1000 * 60 * 5,73 74  // return stale items before removing from cache?75  allowStale: false,76 77  updateAgeOnGet: false,78  updateAgeOnHas: false,79 80  // async method to use for cache.fetch(), for81  // stale-while-revalidate type of behavior82  fetchMethod: async (key, staleValue, { options, signal, context }) => {},83}84 85const cache = new LRUCache(options)86 87cache.set('key', 'value')88cache.get('key') // "value"89 90// non-string keys ARE fully supported91// but note that it must be THE SAME object, not92// just a JSON-equivalent object.93var someObject = { a: 1 }94cache.set(someObject, 'a value')95// Object keys are not toString()-ed96cache.set('[object Object]', 'a different value')97assert.equal(cache.get(someObject), 'a value')98// A similar object with same keys/values won't work,99// because it's a different object identity100assert.equal(cache.get({ a: 1 }), undefined)101 102cache.clear() // empty the cache103```104 105If you put more stuff in the cache, then less recently used items106will fall out. That's what an LRU cache is.107 108For full description of the API and all options, please see [the109LRUCache typedocs](https://isaacs.github.io/node-lru-cache/)110 111## Storage Bounds Safety112 113This implementation aims to be as flexible as possible, within114the limits of safe memory consumption and optimal performance.115 116At initial object creation, storage is allocated for `max` items.117If `max` is set to zero, then some performance is lost, and item118count is unbounded. Either `maxSize` or `ttl` _must_ be set if119`max` is not specified.120 121If `maxSize` is set, then this creates a safe limit on the122maximum storage consumed, but without the performance benefits of123pre-allocation. When `maxSize` is set, every item _must_ provide124a size, either via the `sizeCalculation` method provided to the125constructor, or via a `size` or `sizeCalculation` option provided126to `cache.set()`. The size of every item _must_ be a positive127integer.128 129If neither `max` nor `maxSize` are set, then `ttl` tracking must130be enabled. Note that, even when tracking item `ttl`, items are131_not_ preemptively deleted when they become stale, unless132`ttlAutopurge` is enabled. Instead, they are only purged the133next time the key is requested. Thus, if `ttlAutopurge`, `max`,134and `maxSize` are all not set, then the cache will potentially135grow unbounded.136 137In this case, a warning is printed to standard error. Future138versions may require the use of `ttlAutopurge` if `max` and139`maxSize` are not specified.140 141If you truly wish to use a cache that is bound _only_ by TTL142expiration, consider using a `Map` object, and calling143`setTimeout` to delete entries when they expire. It will perform144much better than an LRU cache.145 146Here is an implementation you may use, under the same147[license](./LICENSE) as this package:148 149```js150// a storage-unbounded ttl cache that is not an lru-cache151const cache = {152  data: new Map(),153  timers: new Map(),154  set: (k, v, ttl) => {155    if (cache.timers.has(k)) {156      clearTimeout(cache.timers.get(k))157    }158    cache.timers.set(159      k,160      setTimeout(() => cache.delete(k), ttl),161    )162    cache.data.set(k, v)163  },164  get: k => cache.data.get(k),165  has: k => cache.data.has(k),166  delete: k => {167    if (cache.timers.has(k)) {168      clearTimeout(cache.timers.get(k))169    }170    cache.timers.delete(k)171    return cache.data.delete(k)172  },173  clear: () => {174    cache.data.clear()175    for (const v of cache.timers.values()) {176      clearTimeout(v)177    }178    cache.timers.clear()179  },180}181```182 183If that isn't to your liking, check out184[@isaacs/ttlcache](http://npm.im/@isaacs/ttlcache).185 186## Storing Undefined Values187 188This cache never stores undefined values, as `undefined` is used189internally in a few places to indicate that a key is not in the190cache.191 192You may call `cache.set(key, undefined)`, but this is just193an alias for `cache.delete(key)`. Note that this has the effect194that `cache.has(key)` will return _false_ after setting it to195undefined.196 197```js198cache.set(myKey, undefined)199cache.has(myKey) // false!200```201 202If you need to track `undefined` values, and still note that the203key is in the cache, an easy workaround is to use a sigil object204of your own.205 206```js207import { LRUCache } from 'lru-cache'208const undefinedValue = Symbol('undefined')209const cache = new LRUCache(...)210const mySet = (key, value) =>211  cache.set(key, value === undefined ? undefinedValue : value)212const myGet = (key, value) => {213  const v = cache.get(key)214  return v === undefinedValue ? undefined : v215}216```217 218## Tracing and Observability219 220Most methods can accept a `status` option, which is an221[`LRUCache.Status`](https://isaacs.github.io/node-lru-cache/interfaces/LRUCache.LRUCache.Status.html)222object that will be decorated along the operation with223indications about what was done and why.224 225Additionally, this library is instrumented using the226[`node:diagnostics_channel`](https://nodejs.org/api/diagnostics_channel.html)227module on Node and other platforms that support it. In order to228get diagnostics metrics, listen on the229`channel('lru-cache:metrics')`. To get Tracing Channel traces,230subscribe to the `tracingChannel('lru-cache')`. The231[`LRUCache.Status`](https://isaacs.github.io/node-lru-cache/interfaces/LRUCache.LRUCache.Status.html)232objects will be provided as the message context to those channel233listeners.234 235For example, you could do the following to get comprehensive236information about every LRUCache instance in your application:237 238```ts239import { tracingChannel, subscribe } from 'node:diagnostics_channel'240 241subscribe('lru-cache:metrics', (message, name) => {242  // name will always be 'lru-cache:metrics'243  // message will be the LRUCache.Status object for whatever244  // synchronous operation was performed.245  console.error('LRUCache Metrics', message)246})247 248tracingChannel('lru-cache').subscribe({249  start: status => {250    // a traced operation is starting251  },252  asyncStart: status => {253    // an async traced operation is starting254  },255  asyncEnd: status => {256    // an async traced operation is ending257  }258  error: status => {259    // a traced operation failed260  },261  end: status => {262    // a traced operation is complete263  },264})265```266 267The async `cache.fetch()` and `cache.forceFetch` methods are268covered by `tracingChannels`. All the other operations are269covered by the `lru-cache:metrics` channel, because they are270strictly synchronous, and thus don't have an asynchronous271lifecycle to track.272 273Note that using `status` objects or using274`node:diagnostics_channel` listeners _will_ impose a modest275performance penalty. Creating data objects is not ever free; do276not believe anyone who tells you otherwise. But it is as small as277possible.278 279### Platform Compatibility Caveat280 281Not all platforms support the `node:diagnostics_channel` module.282Currently, this is only available in Node, Bun, and Deno, and283some edge computing platforms that provide a Node compatibility284layer.285 286To work around this, if you are loading in a non-Node287environment, the package.json exports will direct your module288loader to pull in a version that starts out with a dummy289implementation, then does a conditional dynamic `import` of the290`node:diagnostics_channel` module, and then swaps out those291dummy objects with the real thing if it succeeds. This means that292cache metrics and tracing channels started in the first load-time293tick of your application will _not_ be covered, except in294environments that load using the `require` import295condition, or both the `node` and `esm` import conditions296together.297 298Top-level await _could_ be used to remove this caveat, but that299feature is dead on arrival, unfortunately. See300[#397](https://github.com/isaacs/node-lru-cache/issues/397) and301[#398](https://github.com/isaacs/node-lru-cache/issues/398) for302more details.303 304## Performance305 306As of April 2026, version 11 of this library is one of the most307performant LRU cache implementations in JavaScript.308 309Benchmarks can be extremely difficult to get right. In310particular, the performance of set/get/delete operations on311objects will vary _wildly_ depending on the type of key used. V8312is highly optimized for objects with keys that are short strings,313especially integer numeric strings. Thus any benchmark which314tests _solely_ using numbers as keys will tend to find that an315object-based approach performs the best.316 317Note that coercing _anything_ to strings to use as object keys is318unsafe, unless you can be 100% certain that no other type of319value will be used. For example:320 321```js322const myCache = {}323const set = (k, v) => (myCache[k] = v)324const get = k => myCache[k]325 326set({}, 'please hang onto this for me')327set('[object Object]', 'oopsie')328```329 330Also beware of "Just So" stories regarding performance. Garbage331collection of large (especially: deep) object graphs can be332incredibly costly, with several "tipping points" where it333increases exponentially. As a result, putting that off until334later can make it much worse, and less predictable. If a library335performs well, but only in a scenario where the object graph is336kept shallow, then that won't help you if you are using large337objects as keys.338 339In general, when attempting to use a library to improve340performance (such as a cache like this one), it's best to choose341an option that will perform well in the sorts of scenarios where342you'll actually use it.343 344This library is optimized for repeated gets and minimizing345eviction time, since that is the expected need of a LRU. Set346operations are somewhat slower on average than a few other347options, in part because of that optimization. It is assumed348that you'll be caching some costly operation, ideally as rarely349as possible, so optimizing set over get would be unwise.350 351If performance matters to you:352 3531. If it's at all possible to use small integer values as keys,354   and you can guarantee that no other types of values will be355   used as keys, then do that, and use a cache such as356   [lru-fast](https://npmjs.com/package/lru-fast), or357   [mnemonist's358   LRUCache](https://yomguithereal.github.io/mnemonist/lru-cache)359   which uses an Object as its data store.360 3612. Failing that, if you can use short non-numeric strings (ie,362   less than 256 characters) as your keys, and you do not need363   any of the other features of this library, use [mnemonist's364   LRUCache](https://yomguithereal.github.io/mnemonist/lru-cache).365 3663. If the types of your keys will be anything else, especially367   long strings, strings that look like floats, objects, or some368   mix of types, or if you aren't sure, then this library will369   work well for you.370 371   If you do not need the features that this library provides372   (like asynchronous fetching, a variety of TTL staleness373   options, and so on), then [mnemonist's374   LRUMap](https://yomguithereal.github.io/mnemonist/lru-map) is375   also a very good option, and just slightly faster than this376   module (since it does considerably less).377 3784. Do not use a `dispose` function, size tracking, or especially379   ttl behavior or observability features, unless absolutely380   needed. These features are convenient, and necessary in some381   use cases, and every attempt has been made to make the382   performance impact minimal, but it isn't nothing.383 384## Testing385 386When writing tests that involve TTL-related functionality, note387that this module creates an internal reference to the global388`performance` or `Date` objects at import time. If you import it389statically at the top level, those references cannot be mocked or390overridden in your test environment.391 392To avoid this, dynamically import the package within your tests393so that the references are captured after your mocks are applied.394For example:395 396```ts397// ❌ Not recommended398import { LRUCache } from 'lru-cache'399// mocking timers, e.g. jest.useFakeTimers()400 401// ✅ Recommended for TTL tests402// mocking timers, e.g. jest.useFakeTimers()403const { LRUCache } = await import('lru-cache')404```405 406This ensures that your mocked timers or time sources are407respected when testing TTL behavior.408 409Additionally, you can pass in a `perf` option when creating your410LRUCache instance. This option accepts any object with a `now`411method that returns a number.412 413For example, this would be a very bare-bones time-mocking system414you could use in your tests, without any particular test415framework:416 417```ts418import { LRUCache } from 'lru-cache'419 420let myClockTime = 0421 422const cache = new LRUCache<string>({423  max: 10,424  ttl: 1000,425  perf: {426    now: () => myClockTime,427  },428})429 430// run tests, updating myClockTime as needed431```432 433## Breaking Changes in Version 7434 435This library changed to a different algorithm and internal data436structure in version 7, yielding significantly better437performance, albeit with some subtle changes as a result.438 439If you were relying on the internals of LRUCache in version 6 or440before, it probably will not work in version 7 and above.441 442## Breaking Changes in Version 8443 444- The `fetchContext` option was renamed to `context`, and may no445  longer be set on the cache instance itself.446- Rewritten in TypeScript, so pretty much all the types moved447  around a lot.448- The AbortController/AbortSignal polyfill was removed. For this449  reason, **Node version 16.14.0 or higher is now required**.450- Internal properties were moved to actual private class451  properties.452- Keys and values must not be `null` or `undefined`.453- Minified export available at `'lru-cache/min'`, for both CJS454  and MJS builds.455 456## Breaking Changes in Version 9457 458- Named export only, no default export.459- AbortController polyfill returned, albeit with a warning when460  used.461 462## Breaking Changes in Version 10463 464- `cache.fetch()` return type is now `Promise<V | undefined>`465  instead of `Promise<V | void>`. This is an irrelevant change466  practically speaking, but can require changes for TypeScript467  users.468 469For more info, see the [change log](CHANGELOG.md).470