We should cap the size of stored statistics and prune the store in order of importance, less to more.
<rdar://problem/33164403>
Created attachment 314750 [details] Patch
I know there are a couple of whitespace changes that shouldn't be there but I just can't get Xcode to not add them back in so I'll have to fix the files in some other editor before landing.
Oh, patch doesn't seem to apply to trunk. Will merge.
Created attachment 314767 [details] Patch
Created attachment 314776 [details] Patch
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:47 > +static size_t maxStatisticsEntries = 1000; All those overridable statics are wrong and should be data members. There can be several ResourceLoadStatisticsStore per process at least in theory since there is one store per WebSiteDataStore. I believe those should be data members.
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review > Source/WebCore/loader/ResourceLoadStatistics.h:65 > + WallTime lastSeen { WallTime::fromRawSeconds(-1) }; Do we really need this magic -1 value here? Do we really need to distinguish default value from reset? > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:295 > +void ResourceLoadStatisticsStore::setMaxStatisticsEntries(size_t entries) entries is a bad name > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:300 > +void ResourceLoadStatisticsStore::setPruneEntriesDownTo(size_t entries) entries is a bad name > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:454 > + size_t numberOfEntriesLeftToPrune = m_resourceStatisticsMap.size() - pruneEntriesDownTo; If this is 0, we're in trouble, based on your implementation of sortAndPrune()
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:435 > + std::sort(statisticsToPrune.begin(), statisticsToPrune.end(), [](const StatisticsLastSeen& a, const StatisticsLastSeen& b) { If statisticsToPrune.size() <= numberOfEntriesToPrune, then sorting is useless, right? We are going to remove ALL the entries in statisticsToPrune in this case, and it does not matter in which order they are removed. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:448 > +void ResourceLoadStatisticsStore::pruneStatisticsIfNeeded() How often is this called?
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:441 > + if (!--numberOfEntriesToPrune) This is bad if numberOfEntriesToPrune is 0. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:456 > + Vector<StatisticsLastSeen> nonPrevalentResourcesWithoutUserInteraction; Feels like this could be an array of Vectors, then the pruning code could be written as a loop. e.g. roughly Vector<StatisticsLastSeen> resourcesToPrunePerImportance[maxImportance + 1]; for (auto& resourceStatistic : m_resourceStatisticsMap.values()) resourcesToPruneInPriority[computeImportance(resourceStatistic)].append({ resourceStatistic.highLevelDomain, resourceStatistic.lastSeen }); unsigned importance = 0; while (numberOfEntriesLeftToPrune) { ASSERT(importance <= maxImportance); numberOfEntriesLeftToPrune = pruneResources(m_resourceStatisticsMap, resourcesToPrunePerImportance[importance++], numberOfEntriesLeftToPrune); }
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review > Source/WebCore/loader/ResourceLoadObserver.cpp:82 > +static WallTime reduceTimeResolution(WallTime time) What's the reason we need to reduce the resolution of the lastSeen timestamp?
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:47 >> +static size_t maxStatisticsEntries = 1000; > > All those overridable statics are wrong and should be data members. There can be several ResourceLoadStatisticsStore per process at least in theory since there is one store per WebSiteDataStore. > I believe those should be data members. Will fix. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:295 >> +void ResourceLoadStatisticsStore::setMaxStatisticsEntries(size_t entries) > > entries is a bad name Will fix. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:300 >> +void ResourceLoadStatisticsStore::setPruneEntriesDownTo(size_t entries) > > entries is a bad name Will fix. I also think we should assert if we set "pruneEntriesDownTo" some value that is greater than the maximum number of allowable entries. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:435 >> + std::sort(statisticsToPrune.begin(), statisticsToPrune.end(), [](const StatisticsLastSeen& a, const StatisticsLastSeen& b) { > > If statisticsToPrune.size() <= numberOfEntriesToPrune, then sorting is useless, right? We are going to remove ALL the entries in statisticsToPrune in this case, and it does not matter in which order they are removed. Good point -- since at each pruning step we are seeking to remove a smaller number of records, we may hit this routine at a point where we need to remove all, and a later point where we only remove some. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:441 >> + if (!--numberOfEntriesToPrune) > > This is bad if numberOfEntriesToPrune is 0. Again, I'm pretty sure we can't enter this function with a non-zero 'numberOfEntriesToPrune', but I added an ASSERT in this loop just to prove we don't do so. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:448 >> +void ResourceLoadStatisticsStore::pruneStatisticsIfNeeded() > > How often is this called? It looks like this is triggered when the WebProcess completes a load and thinks its found new data to share. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:454 >> + size_t numberOfEntriesLeftToPrune = m_resourceStatisticsMap.size() - pruneEntriesDownTo; > > If this is 0, we're in trouble, based on your implementation of sortAndPrune() We only hit this if m_resourceStatisticsMap.size() > the max count, and the pruning target count should always be less than the overall max (by default, by around 200 or so). I don't think we can hit this, but I'll add an assert. Would you prefer a test and early return? >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:456 >> + Vector<StatisticsLastSeen> nonPrevalentResourcesWithoutUserInteraction; > > Feels like this could be an array of Vectors, then the pruning code could be written as a loop. e.g. roughly > > Vector<StatisticsLastSeen> resourcesToPrunePerImportance[maxImportance + 1]; > for (auto& resourceStatistic : m_resourceStatisticsMap.values()) > resourcesToPruneInPriority[computeImportance(resourceStatistic)].append({ resourceStatistic.highLevelDomain, resourceStatistic.lastSeen }); > > unsigned importance = 0; > while (numberOfEntriesLeftToPrune) { > ASSERT(importance <= maxImportance); > numberOfEntriesLeftToPrune = pruneResources(m_resourceStatisticsMap, resourcesToPrunePerImportance[importance++], numberOfEntriesLeftToPrune); > } Seems reasonable.
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review >> Source/WebCore/loader/ResourceLoadObserver.cpp:82 >> +static WallTime reduceTimeResolution(WallTime time) > > What's the reason we need to reduce the resolution of the lastSeen timestamp? I'm not sure, either. I left it in for now, but it seems like this could be omitted if we found it was a hotspot.
Comment on attachment 314776 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=314776&action=review >>> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:454 >>> + size_t numberOfEntriesLeftToPrune = m_resourceStatisticsMap.size() - pruneEntriesDownTo; >> >> If this is 0, we're in trouble, based on your implementation of sortAndPrune() > > We only hit this if m_resourceStatisticsMap.size() > the max count, and the pruning target count should always be less than the overall max (by default, by around 200 or so). I don't think we can hit this, but I'll add an assert. > > Would you prefer a test and early return? ?? The check 3 lines above is: if (m_resourceStatisticsMap.size() < maxStatisticsEntries) return; So if m_resourceStatisticsMap.size() == maxStatisticsEntries then you can end up with 0 here, no?
(In reply to Chris Dumez from comment #14) > Comment on attachment 314776 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=314776&action=review > > >>> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:454 > >>> + size_t numberOfEntriesLeftToPrune = m_resourceStatisticsMap.size() - pruneEntriesDownTo; > > The check 3 lines above is: > if (m_resourceStatisticsMap.size() < maxStatisticsEntries) > return; > > So if m_resourceStatisticsMap.size() == maxStatisticsEntries then you can > end up with 0 here, no? If m_resourceStatisticsMap.size() == maxStatisticsEntries, we can only get zero if maxStatisticsEntries also equals "pruneEntriesDownTo", right? It's all academic now, since your revised algorithm protects against it.
Created attachment 315014 [details] Patch
Created attachment 315029 [details] Patch (Rebaselined)
Created attachment 315042 [details] Patch
Comment on attachment 315029 [details] Patch (Rebaselined) View in context: https://bugs.webkit.org/attachment.cgi?id=315029&action=review > Source/WebCore/loader/ResourceLoadStatistics.h:65 > + WallTime lastSeen { WallTime::fromRawSeconds(-1) }; As I commented on the earlier iteration. I do not think we need this magic -1 value. Why do we need to distinguish reset from default value here? I think this was just a bad copy/paste from the other WallTime member in statistics. > Source/WebKit2/UIProcess/WebResourceLoadStatisticsStore.cpp:150 > + coreStore().pruneStatisticsIfNeeded(); Will need some rebaselining now that I merged the 2 stores. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:257 > + ASSERT(pruneTargetCount <= m_maxStatisticsEntries); It is best to check this when pruning than here since you could imagine someone calling setPruneEntriesDownTo() then setMaxStatisticsEntries(), in this order, and yet leading to something valid. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:367 > +static size_t pruneResources(HashMap<String, WebCore::ResourceLoadStatistics>& statisticsMap, Vector<StatisticsLastSeen>& statisticsToPrune, size_t numberOfEntriesToPrune) Looks like the Vector should be const. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:375 > + for (auto& statistic : statisticsToPrune) { I think it would be better as: for (size_t i = 0, end = std::min(numberOfEntriesToPrune, statisticsToPrune.size()); i != end; ++i) statisticsMap.remove(statisticsToPrune[i].topPrivatelyOwnedDomain); > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:382 > + return numberOfEntriesToPrune; Could we just pass numberOfEntriesToPrune by reference instead of returning it. It would seem better to me. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:385 > +constexpr size_t maxImportance { 3 }; I think global constants should go to the top of the cpp file. I think using unsigned should be enough for importance, both here and below. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:389 > + if (!resourceStatistic.isPrevalentResource) I think this may be a bit more readable: unsigned importance = maxImportance; if (!resourceStatistic.isPrevalentResource) importance -= 1; if (!resourceStatistic.hadUserInteraction) importance -= 2; return importance; > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:398 > + if (m_resourceStatisticsMap.size() < m_maxStatisticsEntries) Shouldn't this be <= ? If we have max entries, it sounds like we don't need pruning yet. > Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:409 > + while (numberOfEntriesLeftToPrune) { I think this would look better as: for (unsigned importance = 0; numberOfEntriesLeftToPrune && importance <= maxImportance; ++importance) numberOfEntriesLeftToPrune = pruneResources(m_resourceStatisticsMap, resourcesToPrunePerImportance[importance], numberOfEntriesLeftToPrune);
Comment on attachment 315029 [details] Patch (Rebaselined) View in context: https://bugs.webkit.org/attachment.cgi?id=315029&action=review > Source/WebKit2/UIProcess/WebResourceLoadStatisticsStore.cpp:510 > +void WebResourceLoadStatisticsStore::setLastSeen(Seconds seconds, const URL& url) The parameters look backward to me.
Comment on attachment 315029 [details] Patch (Rebaselined) View in context: https://bugs.webkit.org/attachment.cgi?id=315029&action=review >> Source/WebCore/loader/ResourceLoadStatistics.h:65 >> + WallTime lastSeen { WallTime::fromRawSeconds(-1) }; > > As I commented on the earlier iteration. I do not think we need this magic -1 value. Why do we need to distinguish reset from default value here? I think this was just a bad copy/paste from the other WallTime member in statistics. Ok. I'll get rid of it. >> Source/WebKit2/UIProcess/WebResourceLoadStatisticsStore.cpp:150 >> + coreStore().pruneStatisticsIfNeeded(); > > Will need some rebaselining now that I merged the 2 stores. No kidding! It wasn't too bad, but a new patch is up (missing some of your comments, so don't review it yet). >> Source/WebKit2/UIProcess/WebResourceLoadStatisticsStore.cpp:510 >> +void WebResourceLoadStatisticsStore::setLastSeen(Seconds seconds, const URL& url) > > The parameters look backward to me. Switched. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:257 >> + ASSERT(pruneTargetCount <= m_maxStatisticsEntries); > > It is best to check this when pruning than here since you could imagine someone calling setPruneEntriesDownTo() then setMaxStatisticsEntries(), in this order, and yet leading to something valid. Will do. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:367 >> +static size_t pruneResources(HashMap<String, WebCore::ResourceLoadStatistics>& statisticsMap, Vector<StatisticsLastSeen>& statisticsToPrune, size_t numberOfEntriesToPrune) > > Looks like the Vector should be const. Will do. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:375 >> + for (auto& statistic : statisticsToPrune) { > > I think it would be better as: > for (size_t i = 0, end = std::min(numberOfEntriesToPrune, statisticsToPrune.size()); i != end; ++i) > statisticsMap.remove(statisticsToPrune[i].topPrivatelyOwnedDomain); Eh. Ok. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:382 >> + return numberOfEntriesToPrune; > > Could we just pass numberOfEntriesToPrune by reference instead of returning it. It would seem better to me. Yes. Good idea. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:385 >> +constexpr size_t maxImportance { 3 }; > > I think global constants should go to the top of the cpp file. > I think using unsigned should be enough for importance, both here and below. OK. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:389 >> + if (!resourceStatistic.isPrevalentResource) > > I think this may be a bit more readable: > unsigned importance = maxImportance; > if (!resourceStatistic.isPrevalentResource) > importance -= 1; > if (!resourceStatistic.hadUserInteraction) > importance -= 2; > return importance; Sure! >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:398 >> + if (m_resourceStatisticsMap.size() < m_maxStatisticsEntries) > > Shouldn't this be <= ? > If we have max entries, it sounds like we don't need pruning yet. Reasonable. I'll change it. >> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:409 >> + while (numberOfEntriesLeftToPrune) { > > I think this would look better as: > for (unsigned importance = 0; numberOfEntriesLeftToPrune && importance <= maxImportance; ++importance) > numberOfEntriesLeftToPrune = pruneResources(m_resourceStatisticsMap, resourcesToPrunePerImportance[importance], numberOfEntriesLeftToPrune); Okay!
Created attachment 315043 [details] Patch
Comment on attachment 315043 [details] Patch r=me if the bots are happy.
Created attachment 315048 [details] Patch
Comment on attachment 315029 [details] Patch (Rebaselined) View in context: https://bugs.webkit.org/attachment.cgi?id=315029&action=review >>> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:367 >>> +static size_t pruneResources(HashMap<String, WebCore::ResourceLoadStatistics>& statisticsMap, Vector<StatisticsLastSeen>& statisticsToPrune, size_t numberOfEntriesToPrune) >> >> Looks like the Vector should be const. > > Will do. Bah -- it can't be -- the sort operation needs to modify the statisticsToPrune Vector.
Created attachment 315053 [details] Patch
(In reply to Brent Fulgham from comment #25) > Comment on attachment 315029 [details] > Patch (Rebaselined) > > View in context: > https://bugs.webkit.org/attachment.cgi?id=315029&action=review > > >>> Source/WebKit2/UIProcess/Storage/ResourceLoadStatisticsStore.cpp:367 > >>> +static size_t pruneResources(HashMap<String, WebCore::ResourceLoadStatistics>& statisticsMap, Vector<StatisticsLastSeen>& statisticsToPrune, size_t numberOfEntriesToPrune) > >> > >> Looks like the Vector should be const. > > > > Will do. > > Bah -- it can't be -- the sort operation needs to modify the > statisticsToPrune Vector. oh, duh :) sorry.
Your latest patch only seems to include the changes to TestRunner?
Created attachment 315061 [details] Patch
(In reply to Chris Dumez from comment #28) > Your latest patch only seems to include the changes to TestRunner? Oh, rats. I must have uploaded from the Tools directory (which was the last place I was manually patching the changes). Grrr! Uploaded the hopefully final version!
Committed r219319: <http://trac.webkit.org/changeset/219319>
Reopening to attach new patch.
Created attachment 315069 [details] Patch
Comment on attachment 315069 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=315069&action=review > Source/WebKit2/UIProcess/WebResourceLoadStatisticsStore.cpp:947 > + ++removed; Why not directly --numberOfEntriesToPrune; ? instead of having an extra variable?
Comment on attachment 315069 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=315069&action=review >> Source/WebKit2/UIProcess/WebResourceLoadStatisticsStore.cpp:947 >> + ++removed; > > Why not directly --numberOfEntriesToPrune; ? instead of having an extra variable? I was worried that std::min would be evaluated at each iteration loop, but now I see that it was being assigned to 'end', so would not. I'll land a correction to tidy that up.
Second patch: Committed r219323: <http://trac.webkit.org/changeset/219323>
Final cleanup: Committed r219337: <http://trac.webkit.org/changeset/219337>