<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[179402] trunk/Source/WebCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/179402">179402</a></dd>
<dt>Author</dt> <dd>cdumez@apple.com</dd>
<dt>Date</dt> <dd>2015-01-30 09:40:51 -0800 (Fri, 30 Jan 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Store MemoryCache's live decoded resources in a ListHashSet
https://bugs.webkit.org/show_bug.cgi?id=141051
Reviewed by Antti Koivisto.
Store MemoryCache's live decoded resources in a ListHashSet instead of
a linked list. The frequent operations are:
1. Add items to one end
2. Remove items from the other end or anywhere in the container by value
Using a ListHashSet instead of a manual linked list results in *much*
simpler / shorter code and is fast for all operations (faster than
linked list even for removing an given element from the container given
its value). The previous implementation required us to keep a lot of
pointers up-to-date, which was error prone.
This is a first step towards simplifying the MemoryCache implementation.
* loader/cache/CachedResource.cpp:
(WebCore::CachedResource::CachedResource):
(WebCore::CachedResource::setDecodedSize):
(WebCore::CachedResource::didAccessDecodedData):
* loader/cache/CachedResource.h:
(WebCore::CachedResource::inLiveDecodedResourcesList): Deleted.
* loader/cache/MemoryCache.cpp:
(WebCore::MemoryCache::pruneLiveResourcesToSize):
(WebCore::MemoryCache::removeFromLiveDecodedResourcesList):
(WebCore::MemoryCache::insertInLiveDecodedResourcesList):
* loader/cache/MemoryCache.h:
(WebCore::MemoryCache::inLiveDecodedResourcesList):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreloadercacheCachedResourcecpp">trunk/Source/WebCore/loader/cache/CachedResource.cpp</a></li>
<li><a href="#trunkSourceWebCoreloadercacheCachedResourceh">trunk/Source/WebCore/loader/cache/CachedResource.h</a></li>
<li><a href="#trunkSourceWebCoreloadercacheMemoryCachecpp">trunk/Source/WebCore/loader/cache/MemoryCache.cpp</a></li>
<li><a href="#trunkSourceWebCoreloadercacheMemoryCacheh">trunk/Source/WebCore/loader/cache/MemoryCache.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (179401 => 179402)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-01-30 17:38:39 UTC (rev 179401)
+++ trunk/Source/WebCore/ChangeLog 2015-01-30 17:40:51 UTC (rev 179402)
</span><span class="lines">@@ -1,3 +1,36 @@
</span><ins>+2015-01-30 Chris Dumez <cdumez@apple.com>
+
+ Store MemoryCache's live decoded resources in a ListHashSet
+ https://bugs.webkit.org/show_bug.cgi?id=141051
+
+ Reviewed by Antti Koivisto.
+
+ Store MemoryCache's live decoded resources in a ListHashSet instead of
+ a linked list. The frequent operations are:
+ 1. Add items to one end
+ 2. Remove items from the other end or anywhere in the container by value
+
+ Using a ListHashSet instead of a manual linked list results in *much*
+ simpler / shorter code and is fast for all operations (faster than
+ linked list even for removing an given element from the container given
+ its value). The previous implementation required us to keep a lot of
+ pointers up-to-date, which was error prone.
+
+ This is a first step towards simplifying the MemoryCache implementation.
+
+ * loader/cache/CachedResource.cpp:
+ (WebCore::CachedResource::CachedResource):
+ (WebCore::CachedResource::setDecodedSize):
+ (WebCore::CachedResource::didAccessDecodedData):
+ * loader/cache/CachedResource.h:
+ (WebCore::CachedResource::inLiveDecodedResourcesList): Deleted.
+ * loader/cache/MemoryCache.cpp:
+ (WebCore::MemoryCache::pruneLiveResourcesToSize):
+ (WebCore::MemoryCache::removeFromLiveDecodedResourcesList):
+ (WebCore::MemoryCache::insertInLiveDecodedResourcesList):
+ * loader/cache/MemoryCache.h:
+ (WebCore::MemoryCache::inLiveDecodedResourcesList):
+
</ins><span class="cx"> 2015-01-30 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> [cairo] Fix #if guards in platform/graphics/cairo directory
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheCachedResourcecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/CachedResource.cpp (179401 => 179402)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/CachedResource.cpp 2015-01-30 17:38:39 UTC (rev 179401)
+++ trunk/Source/WebCore/loader/cache/CachedResource.cpp 2015-01-30 17:40:51 UTC (rev 179402)
</span><span class="lines">@@ -125,7 +125,6 @@
</span><span class="cx"> , m_handleCount(0)
</span><span class="cx"> , m_preloadCount(0)
</span><span class="cx"> , m_preloadResult(PreloadNotReferenced)
</span><del>- , m_inLiveDecodedResourcesList(false)
</del><span class="cx"> , m_requestedFromNetworkingLayer(false)
</span><span class="cx"> , m_inCache(false)
</span><span class="cx"> , m_loading(false)
</span><span class="lines">@@ -138,8 +137,6 @@
</span><span class="cx"> #endif
</span><span class="cx"> , m_nextInAllResourcesList(0)
</span><span class="cx"> , m_prevInAllResourcesList(0)
</span><del>- , m_nextInLiveResourcesList(0)
- , m_prevInLiveResourcesList(0)
</del><span class="cx"> , m_owningCachedResourceLoader(0)
</span><span class="cx"> , m_resourceToRevalidate(0)
</span><span class="cx"> , m_proxyResource(0)
</span><span class="lines">@@ -517,9 +514,10 @@
</span><span class="cx"> // violation of the invariant that the list is to be kept sorted
</span><span class="cx"> // by access time. The weakening of the invariant does not pose
</span><span class="cx"> // a problem. For more details please see: https://bugs.webkit.org/show_bug.cgi?id=30209
</span><del>- if (m_decodedSize && !m_inLiveDecodedResourcesList && hasClients())
</del><ins>+ bool inLiveDecodedResourcesList = memoryCache().inLiveDecodedResourcesList(*this);
+ if (m_decodedSize && !inLiveDecodedResourcesList && hasClients())
</ins><span class="cx"> memoryCache().insertInLiveDecodedResourcesList(this);
</span><del>- else if (!m_decodedSize && m_inLiveDecodedResourcesList)
</del><ins>+ else if (!m_decodedSize && inLiveDecodedResourcesList)
</ins><span class="cx"> memoryCache().removeFromLiveDecodedResourcesList(this);
</span><span class="cx">
</span><span class="cx"> // Update the cache's size totals.
</span><span class="lines">@@ -552,7 +550,7 @@
</span><span class="cx"> m_lastDecodedAccessTime = timeStamp;
</span><span class="cx">
</span><span class="cx"> if (inCache()) {
</span><del>- if (m_inLiveDecodedResourcesList) {
</del><ins>+ if (memoryCache().inLiveDecodedResourcesList(*this)) {
</ins><span class="cx"> memoryCache().removeFromLiveDecodedResourcesList(this);
</span><span class="cx"> memoryCache().insertInLiveDecodedResourcesList(this);
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheCachedResourceh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/CachedResource.h (179401 => 179402)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/CachedResource.h 2015-01-30 17:38:39 UTC (rev 179401)
+++ trunk/Source/WebCore/loader/cache/CachedResource.h 2015-01-30 17:40:51 UTC (rev 179402)
</span><span class="lines">@@ -187,8 +187,6 @@
</span><span class="cx"> void setInCache(bool inCache) { m_inCache = inCache; }
</span><span class="cx"> bool inCache() const { return m_inCache; }
</span><span class="cx">
</span><del>- bool inLiveDecodedResourcesList() { return m_inLiveDecodedResourcesList; }
-
</del><span class="cx"> void clearLoader();
</span><span class="cx">
</span><span class="cx"> SharedBuffer* resourceBuffer() const { return m_data.get(); }
</span><span class="lines">@@ -306,7 +304,6 @@
</span><span class="cx">
</span><span class="cx"> unsigned m_preloadResult : 2; // PreloadResult
</span><span class="cx">
</span><del>- bool m_inLiveDecodedResourcesList : 1;
</del><span class="cx"> bool m_requestedFromNetworkingLayer : 1;
</span><span class="cx">
</span><span class="cx"> bool m_inCache : 1;
</span><span class="lines">@@ -324,9 +321,6 @@
</span><span class="cx">
</span><span class="cx"> CachedResource* m_nextInAllResourcesList;
</span><span class="cx"> CachedResource* m_prevInAllResourcesList;
</span><del>-
- CachedResource* m_nextInLiveResourcesList;
- CachedResource* m_prevInLiveResourcesList;
</del><span class="cx">
</span><span class="cx"> CachedResourceLoader* m_owningCachedResourceLoader; // only non-null for resources that are not in the cache
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheMemoryCachecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/MemoryCache.cpp (179401 => 179402)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/MemoryCache.cpp 2015-01-30 17:38:39 UTC (rev 179401)
+++ trunk/Source/WebCore/loader/cache/MemoryCache.cpp 2015-01-30 17:40:51 UTC (rev 179402)
</span><span class="lines">@@ -301,16 +301,14 @@
</span><span class="cx"> currentTime = monotonicallyIncreasingTime();
</span><span class="cx">
</span><span class="cx"> // Destroy any decoded data in live objects that we can.
</span><del>- // Start from the tail, since this is the least recently accessed of the objects.
</del><ins>+ // Start from the head, since this is the least recently accessed of the objects.
</ins><span class="cx">
</span><span class="cx"> // The list might not be sorted by the m_lastDecodedAccessTime. The impact
</span><span class="cx"> // of this weaker invariant is minor as the below if statement to check the
</span><span class="cx"> // elapsedTime will evaluate to false as the currentTime will be a lot
</span><span class="cx"> // greater than the current->m_lastDecodedAccessTime.
</span><span class="cx"> // For more details see: https://bugs.webkit.org/show_bug.cgi?id=30209
</span><del>- CachedResource* current = m_liveDecodedResources.m_tail;
- while (current) {
- CachedResource* prev = current->m_prevInLiveResourcesList;
</del><ins>+ for (auto* current : m_liveDecodedResources) {
</ins><span class="cx"> ASSERT(current->hasClients());
</span><span class="cx"> if (current->isLoaded() && current->decodedSize()) {
</span><span class="cx"> // Check to see if the remaining resources are too new to prune.
</span><span class="lines">@@ -318,10 +316,8 @@
</span><span class="cx"> if (!shouldDestroyDecodedDataForAllLiveResources && elapsedTime < cMinDelayBeforeLiveDecodedPrune)
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- if (current->decodedDataIsPurgeable()) {
- current = prev;
</del><ins>+ if (current->decodedDataIsPurgeable())
</ins><span class="cx"> continue;
</span><del>- }
</del><span class="cx">
</span><span class="cx"> // Destroy our decoded data. This will remove us from
</span><span class="cx"> // m_liveDecodedResources, and possibly move us to a different LRU
</span><span class="lines">@@ -331,7 +327,6 @@
</span><span class="cx"> if (targetSize && m_liveSize <= targetSize)
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>- current = prev;
</del><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -620,69 +615,14 @@
</span><span class="cx">
</span><span class="cx"> void MemoryCache::removeFromLiveDecodedResourcesList(CachedResource* resource)
</span><span class="cx"> {
</span><del>- // If we've never been accessed, then we're brand new and not in any list.
- if (!resource->m_inLiveDecodedResourcesList)
- return;
- resource->m_inLiveDecodedResourcesList = false;
-
-#if !ASSERT_DISABLED
- // Verify that we are in fact in this list.
- bool found = false;
- for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
- if (current == resource) {
- found = true;
- break;
- }
- }
- ASSERT(found);
-#endif
-
- CachedResource* next = resource->m_nextInLiveResourcesList;
- CachedResource* prev = resource->m_prevInLiveResourcesList;
-
- if (next == 0 && prev == 0 && m_liveDecodedResources.m_head != resource)
- return;
-
- resource->m_nextInLiveResourcesList = 0;
- resource->m_prevInLiveResourcesList = 0;
-
- if (next)
- next->m_prevInLiveResourcesList = prev;
- else if (m_liveDecodedResources.m_tail == resource)
- m_liveDecodedResources.m_tail = prev;
-
- if (prev)
- prev->m_nextInLiveResourcesList = next;
- else if (m_liveDecodedResources.m_head == resource)
- m_liveDecodedResources.m_head = next;
</del><ins>+ m_liveDecodedResources.remove(resource);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void MemoryCache::insertInLiveDecodedResourcesList(CachedResource* resource)
</span><span class="cx"> {
</span><span class="cx"> // Make sure we aren't in the list already.
</span><del>- ASSERT(!resource->m_nextInLiveResourcesList && !resource->m_prevInLiveResourcesList && !resource->m_inLiveDecodedResourcesList);
- resource->m_inLiveDecodedResourcesList = true;
-
- resource->m_nextInLiveResourcesList = m_liveDecodedResources.m_head;
- if (m_liveDecodedResources.m_head)
- m_liveDecodedResources.m_head->m_prevInLiveResourcesList = resource;
- m_liveDecodedResources.m_head = resource;
-
- if (!resource->m_nextInLiveResourcesList)
- m_liveDecodedResources.m_tail = resource;
-
-#if !ASSERT_DISABLED
- // Verify that we are in now in the list like we should be.
- bool found = false;
- for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
- if (current == resource) {
- found = true;
- break;
- }
- }
- ASSERT(found);
-#endif
-
</del><ins>+ ASSERT(!m_liveDecodedResources.contains(resource));
+ m_liveDecodedResources.add(resource);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void MemoryCache::addToLiveResourcesSize(CachedResource* resource)
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheMemoryCacheh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/MemoryCache.h (179401 => 179402)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/MemoryCache.h 2015-01-30 17:38:39 UTC (rev 179401)
+++ trunk/Source/WebCore/loader/cache/MemoryCache.h 2015-01-30 17:40:51 UTC (rev 179402)
</span><span class="lines">@@ -31,6 +31,7 @@
</span><span class="cx"> #include <wtf/Forward.h>
</span><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><ins>+#include <wtf/ListHashSet.h>
</ins><span class="cx"> #include <wtf/Noncopyable.h>
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx"> #include <wtf/text/StringHash.h>
</span><span class="lines">@@ -138,6 +139,7 @@
</span><span class="cx"> WEBCORE_EXPORT Statistics getStatistics();
</span><span class="cx">
</span><span class="cx"> void resourceAccessed(CachedResource*);
</span><ins>+ bool inLiveDecodedResourcesList(CachedResource& resource) const { return m_liveDecodedResources.contains(&resource); }
</ins><span class="cx">
</span><span class="cx"> typedef HashSet<RefPtr<SecurityOrigin>> SecurityOriginSet;
</span><span class="cx"> WEBCORE_EXPORT void removeResourcesWithOrigin(SecurityOrigin*);
</span><span class="lines">@@ -203,7 +205,7 @@
</span><span class="cx"> Vector<LRUList, 32> m_allResources;
</span><span class="cx">
</span><span class="cx"> // List just for live resources with decoded data. Access to this list is based off of painting the resource.
</span><del>- LRUList m_liveDecodedResources;
</del><ins>+ ListHashSet<CachedResource*> m_liveDecodedResources;
</ins><span class="cx">
</span><span class="cx"> // A URL-based map of all resources that are in the cache (including the freshest version of objects that are currently being
</span><span class="cx"> // referenced by a Web page).
</span></span></pre>
</div>
</div>
</body>
</html>