subversion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From stef...@apache.org
Subject svn commit: r1580389 - /subversion/trunk/subversion/libsvn_subr/cache-membuffer.c
Date Sun, 23 Mar 2014 00:18:51 GMT
Author: stefan2
Date: Sun Mar 23 00:18:51 2014
New Revision: 1580389

URL: http://svn.apache.org/r1580389
Log:
Rework the membuffer cache L2 promotion / eviction logic.  The goal is to
allow higher prio data to eventually replace low-prio entries which was not
the case with the prior randomized heuristics.

* subversion/libsvn_subr/cache-membuffer.c
  (ensure_data_insertable_l2): Accept low-prio entries only if they don't
                               encounter higher-prio ones; also remove them
                               quickly again.  Decide the remaining cases
                               solely based on priority and hits.  The aging
                               code will cause unused higher-prio entries
                               to be demoted and evicted eventually.

Modified:
    subversion/trunk/subversion/libsvn_subr/cache-membuffer.c

Modified: subversion/trunk/subversion/libsvn_subr/cache-membuffer.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/cache-membuffer.c?rev=1580389&r1=1580388&r2=1580389&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_subr/cache-membuffer.c (original)
+++ subversion/trunk/subversion/libsvn_subr/cache-membuffer.c Sun Mar 23 00:18:51 2014
@@ -1355,8 +1355,6 @@ ensure_data_insertable_l2(svn_membuffer_
                           entry_t *to_fit_in)
 {
   entry_t *entry;
-  apr_uint64_t average_hit_value;
-  apr_uint64_t threshold;
 
   /* accumulated size of the entries that have been removed to make
    * room for the new one.
@@ -1369,19 +1367,21 @@ ensure_data_insertable_l2(svn_membuffer_
   apr_size_t moved_count = 0;
 
   /* accumulated "worth" of items dropped so far */
-  apr_size_t drop_hits = 0;
+  apr_uint64_t drop_hits = 0;
+
+  /* estimated "worth" of the new entry */
+  apr_uint64_t drop_hits_limit = (to_fit_in->hit_count + 1)
+                               * (apr_uint64_t)to_fit_in->priority;
 
   /* This loop will eventually terminate because every cache entry
    * would get dropped eventually:
-   * - hit counts become 0 after the got kept for 32 full scans
-   * - larger elements get dropped as soon as their hit count is 0
-   * - smaller and smaller elements get removed as the average
-   *   entry size drops (average drops by a factor of 8 per scan)
-   * - after no more than 43 full scans, all elements would be removed
    *
-   * Since size is < 4th of the cache size and about 50% of all
-   * entries get removed by a scan, it is very unlikely that more
-   * than a fractional scan will be necessary.
+   * - the incoming entry is small enough to fit into L2
+   * - every iteration either frees parts of L2 or counts the moved size
+   * - eventually, we either moved too many items with too much total size
+   *   to accept the new entry, or made enough room in L2 for the new entry
+   *
+   * Low-prio items get rejected even sooner.
    */
   while (1)
     {
@@ -1396,17 +1396,18 @@ ensure_data_insertable_l2(svn_membuffer_
       if (end >= to_fit_in->size + cache->l2.current_data)
         return TRUE;
 
-      /* Don't be too eager to cache data.  If a lot of data has been 
-       * moved around, the current item has probably a relatively low
-       * priority.  So, give up after some time.
+      /* Don't be too eager to cache data.  If a lot of data has been moved
+       * around, the current item has probably a relatively low priority.
+       * We must also limit the effort spent here (if even in case of faulty
+       * heuristics).  Therefore, give up after some time.
        */
-      if (moved_size > 8 * to_fit_in->size && moved_count > 3)
+      if (moved_size > 4 * to_fit_in->size && moved_count > 7)
         return FALSE;
 
-      /* if the net worth (in hits) of items removed is already larger
-       * than what we want to insert, reject TO_FIT_IN because it still
-       * does not fit in. */
-      if (drop_hits > to_fit_in->hit_count)
+      /* if the net worth (in weighted hits) of items removed is already
+       * larger than what we want to insert, reject TO_FIT_IN because it
+       * still does not fit in. */
+      if (drop_hits > drop_hits_limit)
         return FALSE;
 
       /* try to enlarge the insertion window
@@ -1426,60 +1427,35 @@ ensure_data_insertable_l2(svn_membuffer_
           svn_boolean_t keep;
           entry = get_entry(cache, cache->l2.next);
 
-          /* Reject insertion for entries with low priority, if the current
-           * entry has seen recent hits. */
-          if (   entry->hit_count
-              && to_fit_in->priority < SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY)
-            return FALSE;
-
-          /* Keep entries that are very small. Those are likely to be data
-           * headers or similar management structures. So, they are probably
-           * important while not occupying much space.
-           * But keep them only as long as they are a minority.
-           */
-          if (   (apr_uint64_t)entry->size * cache->used_entries
-               < cache->data_used / 8)
+          if (to_fit_in->priority < SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY)
             {
-              keep = TRUE;
-            }
-          else if (   entry->priority < SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY
-                   && to_fit_in->priority > entry->priority)
-            {
-              /* Be quick to evict low-priority entries if the one to insert
-               * is of higher priority.
+              /* Low prio items can only be accepted only if the current
+               * entry is of even lower prio and has fewer hits.
                */
-              keep = FALSE;
+              if (   entry->priority > to_fit_in->priority
+                  || entry->hit_count > to_fit_in->hit_count)
+                return FALSE;
             }
-          else if (to_fit_in->priority != entry->priority)
-            {
-              /* Not the same priority but the lower prio side is not a
-               * clear loser either (already checked those cases above).
-               * Keep the current entry if it has seen more hits recently
-               * or is smaller than the one to insert - both relative to
-               * their respective priority.
-               */
-              keep = (apr_uint64_t)to_fit_in->hit_count * to_fit_in->priority
-                   < (apr_uint64_t)entry->hit_count * entry->priority
-                  || (apr_uint64_t)to_fit_in->size * to_fit_in->priority
-                   < (apr_uint64_t)entry->size * entry->priority;
-            }
-          else if (cache->hit_count > cache->used_entries)
+
+          if (entry->priority <= SVN_CACHE__MEMBUFFER_LOW_PRIORITY)
             {
-              /* Roll the dice and determine a threshold somewhere
-               * from 0 up to 2 times the average hit count.
+              /* Be quick to remove low-prio entries - even if the incoming
+               * one is low-prio as well.  This makes room for more important
+               * data and replaces existing data with newly read information.
                */
-              average_hit_value = cache->hit_count / cache->used_entries;
-              threshold = (average_hit_value+1) * (rand() % 4096) / 2048;
-
-              keep = entry->hit_count > threshold;
+              keep = FALSE;
             }
           else
             {
-              /* general hit count is low. Keep everything that got hit
-               * at all and assign some 50% survival chance to everything
-               * else.
+              /* If the existing data is the same prio as the incoming data,
+               * drop the existing entry if it had seen fewer (probably 0)
+               * hits than the entry coming in from L1.  In case of different
+               * priorities, keep the current entry of it has higher prio.
+               * The new entry may still find room by ousting other entries.
                */
-              keep = rand() & 1;
+              keep = to_fit_in->priority == entry->priority
+                   ? entry->hit_count >= to_fit_in->hit_count
+                   : entry->priority > to_fit_in->priority;
             }
 
           /* keepers or destroyers? */
@@ -1493,11 +1469,15 @@ ensure_data_insertable_l2(svn_membuffer_
             }
           else
             {
-              /* Drop the entry from the end of the insertion window, if it
-               * has been hit less than the threshold. Otherwise, keep it and
-               * move the insertion window one entry further.
+              /* Drop the entry from the end of the insertion window.
+               * Count the "hit importance" such that we are not sacrificing
+               * too much of the high-hit contents.  However, don't count
+               * low-priority hits because higher prio entries will often
+               * provide the same data but in a further stage of processing. 
                */
-              drop_hits += entry->hit_count;
+              if (entry->priority > SVN_CACHE__MEMBUFFER_LOW_PRIORITY)
+                drop_hits += entry->hit_count * (apr_uint64_t)entry->priority;
+
               drop_entry(cache, entry);
             }
         }



Mime
View raw message