Just a few words

Don’t be dissuaded by this LRU. It’s actually very simple. LRU stands for “Lastest Recently Used”, or “least Recently Used”. In human terms, LRU refers to data. If data has been accessed Recently, it is more likely to be accessed in the future, and the data that has not been accessed Recently will be eliminated first.

Put the picture:

  1. At the beginning, the memory is empty, let’s say 3, stored in A, B, and C
  2. The problem occurs when D is saved, because there is not enough memory, so the longest unaccessed A is eliminated
  3. When B is rereferenced, its order is reordered, that is, it is placed first.
  4. When the data was stored again, it faced the problem of insufficient memory space. Since B was used recently, C became the longest unused data and was eliminated.

Caching mechanisms in browsers

When you use a browser to access a web page, the browser first checks to see if there is a local copy of the resource. If there is, the browser does not bother to request it, and directly ends the request and returns the cached file. This saves traffic requests and improves access speed.

Since this is a local cache, the cache size must be finite. When we have too many requests, we use this LRU cache flushing policy to determine which data will be retained and which data will be removed. In addition to LRU(least recently used), there are FIFO(first in, first out) and LFU(least used).

Implementation of LRU algorithm in Vue keep-alive

Those familiar with Vue should know the purpose of keep-alive — to keep dynamic components in state to avoid losing performance during repeated rendering. A brief description of Keep-alive from the VUE documentation. Also, since it is a local cache, there must be a limit to the cache capacity. Similar to the browser caching mechanism, the LRU elimination caching algorithm is used here. The longer you leave a component unactivated, the more likely it is to be deprecated and deleted.

keep-alive

  • props
    • includeString or regular expression. Only components with matching names are cached.
    • excludeString or regular expression. Only components whose names match are not cached.
    • maxNumbers. Maximum number of component instances can be cached. Added in version 2.5.0.
  • usage
<keep-alive>
  <component :is="view"></component>
</keep-alive>
Copy the code

Implementation of keep-alive in Vue

  const patternTypes: Array<Function> = [String.RegExp.Array];

  export default {
    name: 'keep-alive'.// Marked as an abstract component, it is not rendered as a DOM element and does not appear in the parent component chain
    abstract: true,

    props: {
      // Meet the conditions of the cache
      include: patternTypes,
      // Meet the condition of no cache
      exclude: patternTypes,
      // Limit the size of the cache component
      max: [String.Number]
    },

    created () {
      // Initialize the cache object used to store the cache
      this.cache = Object.create(null);
      // Initializes the array of keys used to store VNode keys
      this.keys = [];
    },

    destroyed () {
      // When the keep-alive component is destroyed, all cached components are deleted
      for (const key in this.cache) {
        pruneCacheEntry(this.cache, key, this.keys)
      }
    },

    mounted () {
      /** * listen for caches, include, caches that meet the criteria; Exclude a method that does not cache * purneCache incoming instances and filters the cache * matches in the instance to determine whether the component name matches the specified */
      this.$watch('include'.val= > {
        pruneCache(this.name= > matches(val, name))
      })
      this.$watch('exclude'.val= > {
        pruneCache(this.name= >! matches(val, name)) }) }, render () {// Get the slot of the first child element
      const slot = this.$slots.default
      const vnode: VNode = getFirstComponentChild(slot)
      constcomponentOptions: ? VNodeComponentOptions = vnode && vnode.componentOptionsif (componentOptions) {
        // check pattern
        const name: ?string = getComponentName(componentOptions)
        const { include, exclude } = this
        if ( // Check that the component name is not included in include or exclude, and return VNode directly
          // Not included(include && (! name || ! matches(include, name))) ||/ / in the exclude
          (exclude && name && matches(exclude, name))
        ) {
          return vnode
        }

        // The cache condition is met
        const { cache, keys } = this
        // Define the key name
        const key: ?string = vnode.key == null
          // same constructor may get registered as different local components
          // so cid alone is not enough (#3269)
          ? componentOptions.Ctor.cid + (componentOptions.tag ? ` : :${componentOptions.tag}` : ' ')
          : vnode.key

        // Here is the LRU algorithm implementation
        if (cache[key]) { // The component is already cached in the cache
          vnode.componentInstance = cache[key].componentInstance
          // make current key freshest
          // Place the current component's key in the latest position (delete the original and push it to the end of the queue)
          remove(keys, key)
          keys.push(key)
        } else { // If the component has not been cached
          // Add the component to the cache and append the key to the end of the keys queue
          cache[key] = vnode
          keys.push(key)
          // prune oldest entry
          // Determine whether the current cache size exceeds the limit
          if (this.max && keys.length > parseInt(this.max)) {
            // Delete the longest unused component when the limit is exceeded.
            pruneCacheEntry(cache, keys[0], keys, this._vnode)
          }
        }

        vnode.data.keepAlive = true
      }
      return vnode || (slot && slot[0])}}// Add the implementation of pruneCacheEntry
  function pruneCacheEntry (
    cache: VNodeCache,
    key: string,
    keys: Array<string>, current? : VNode) {
    const cached = cache[key]
    if(cached && (! current || cached.tag ! == current.tag)) {// Uninstall the component
      cached.componentInstance.$destroy()
    }
    // Clear the component cache in the cache
    cache[key] = null
    / / delete key
    remove(keys, key)
  }

  // remove method (in shared/util.js)
  /** * Remove an item from an array. */
  export function remove (arr: Array<any>, item: any) :Array<any> | void {
    if (arr.length) {
      const index = arr.indexOf(item)
      if (index > - 1) {
        return arr.splice(index, 1)}}}Copy the code

Vue keep-alive source code

The keep-alive component caches includes. Components of the exclinflation condition, rather than destroying them. When the number of components in the keep-alive cache exceeds Max, the LRU elimination algorithm is adopted to delete the components that have not been used for the longest time from the cache.

Let’s try to implement an LRU algorithm

Design and build a least-recently used cache that removes the least-recently used items. The cache should map from key to value (allowing you to insert and retrieve values for specific keys) and specify the maximum capacity at initialization. When the cache is full, it should remove the least recently used items.

It should support the following operations: get for data and PUT for writing data.

Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned. Write data PUT (key, value) – Writes the data value of the key if it does not exist. When the cache reaches its maximum capacity, it should remove the least-recently used data values before writing new data to make room for new data values.

Source: LeetCode

My leetcode problem solving

Pay attention to my public account