53
edits
DocShell/Fastback: Difference between revisions
→Eviction from history
| Line 20: | Line 20: | ||
Once a new content viewer has been placed into session history through a call to <code>DocumentViewerImpl::Destroy()</code>, <code>nsSHistory::EvictContentViewers()</code> is called. It first checks the limit for the current nsSHistory object, by determining a sliding window of SHEntrry indices which are allowed to have cached viewers. The sliding window has an endpoint at the new current index, and the other endpoint is 3 back (if we're going forward) or 3 in front (if we're going backward). Any viewers outside of this range are evicted. Next, it checks against the global limit, by computing the sliding window for each nsSHistory. The viewer which is the furthest away from its SHistory's current index is considered the best eviction candidate, because it's the least recently used across the app. At the end of this process, we have a count of all cached content viewers. If it's more than the fixed limit, we evict the one that was furthest away. If we still need to evict viewers to reach the limit, we start the entire process again. | Once a new content viewer has been placed into session history through a call to <code>DocumentViewerImpl::Destroy()</code>, <code>nsSHistory::EvictContentViewers()</code> is called. It first checks the limit for the current nsSHistory object, by determining a sliding window of SHEntrry indices which are allowed to have cached viewers. The sliding window has an endpoint at the new current index, and the other endpoint is 3 back (if we're going forward) or 3 in front (if we're going backward). Any viewers outside of this range are evicted. Next, it checks against the global limit, by computing the sliding window for each nsSHistory. The viewer which is the furthest away from its SHistory's current index is considered the best eviction candidate, because it's the least recently used across the app. At the end of this process, we have a count of all cached content viewers. If it's more than the fixed limit, we evict the one that was furthest away. If we still need to evict viewers to reach the limit, we start the entire process again. | ||
This algorithm is inefficient (O(n | This algorithm is inefficient (O(n²)) in the worst case, but O(n) in the common case, since we'll rarely need to evict more than one viewer -- only if the user manually changes the pref that controls the limit. There is a fast path for "clear history" which evicts all cached viewers in O(n) time. | ||