lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [01/46] lucenenet git commit: Fixed Facet.Taxonomy.LRUHashMap implementation to correctly remove the eldest item from the cache when an item is added (test passing).
Date Tue, 04 Oct 2016 20:01:31 GMT
Repository: lucenenet
Updated Branches:
  refs/heads/master 87d05125b -> ddfb46c10


Fixed Facet.Taxonomy.LRUHashMap implementation to correctly remove the eldest item from the
cache when an item is added (test passing).


Project: http://git-wip-us.apache.org/repos/asf/lucenenet/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucenenet/commit/1ca08dfb
Tree: http://git-wip-us.apache.org/repos/asf/lucenenet/tree/1ca08dfb
Diff: http://git-wip-us.apache.org/repos/asf/lucenenet/diff/1ca08dfb

Branch: refs/heads/master
Commit: 1ca08dfb1609699219da6922138a523b007dff3b
Parents: 87d0512
Author: Shad Storhaug <shad@shadstorhaug.com>
Authored: Fri Sep 23 21:07:16 2016 +0700
Committer: Shad Storhaug <shad@shadstorhaug.com>
Committed: Mon Oct 3 23:30:30 2016 +0700

----------------------------------------------------------------------
 .../Directory/DirectoryTaxonomyReader.cs        |  35 ++--
 src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs     | 162 ++++++++++++-------
 .../Taxonomy/TestLRUHashMap.cs                  |   2 +-
 3 files changed, 118 insertions(+), 81 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucenenet/blob/1ca08dfb/src/Lucene.Net.Facet/Taxonomy/Directory/DirectoryTaxonomyReader.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Facet/Taxonomy/Directory/DirectoryTaxonomyReader.cs b/src/Lucene.Net.Facet/Taxonomy/Directory/DirectoryTaxonomyReader.cs
index a567210..da82cbf 100644
--- a/src/Lucene.Net.Facet/Taxonomy/Directory/DirectoryTaxonomyReader.cs
+++ b/src/Lucene.Net.Facet/Taxonomy/Directory/DirectoryTaxonomyReader.cs
@@ -353,24 +353,21 @@ namespace Lucene.Net.Facet.Taxonomy.Directory
 
             // TODO: can we use an int-based hash impl, such as IntToObjectMap,
             // wrapped as LRU?
-            int catIDInteger = Convert.ToInt32(ordinal);
-            lock (categoryCache)
+
+            // LUCENENET NOTE: We don't need to convert int to int here.
+            // Also, our cache implementation is thread safe, so we can nix the
+            // locks.
+            FacetLabel res;
+            if (categoryCache.TryGetValue(ordinal, out res))
             {
-                var res = categoryCache.Get(catIDInteger,false);
-                if (res != null)
-                {
-                    return res;
-                }
+                return res;
             }
 
             Document doc = indexReader.Document(ordinal);
-            FacetLabel ret = new FacetLabel(FacetsConfig.StringToPath(doc.Get(Consts.FULL)));
-            lock (categoryCache)
-            {
-                categoryCache.Put(catIDInteger, ret);
-            }
+            res = new FacetLabel(FacetsConfig.StringToPath(doc.Get(Consts.FULL)));
+            categoryCache.Put(ordinal, res);
 
-            return ret;
+            return res;
         }
 
         public override int Size
@@ -395,14 +392,10 @@ namespace Lucene.Net.Facet.Taxonomy.Directory
             set
             {
                 EnsureOpen();
-                lock (categoryCache)
-                {
-                    categoryCache.MaxSize = value;
-                }
-                lock (ordinalCache)
-                {
-                    ordinalCache.MaxSize = value;
-                }
+                // LUCENENET NOTE: No locking required here,
+                // since our LRU implementation is thread-safe
+                categoryCache.MaxSize = value;
+                ordinalCache.MaxSize = value;
             }
         }
 

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/1ca08dfb/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs b/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs
index d442992..5d51036 100644
--- a/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs
+++ b/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs
@@ -1,13 +1,9 @@
 ´╗┐using System;
-using System.Collections.Concurrent;
 using System.Collections.Generic;
 using System.Linq;
-using System.Threading;
-using Lucene.Net.Support;
 
 namespace Lucene.Net.Facet.Taxonomy
 {
-
     /*
      * Licensed to the Apache Software Foundation (ASF) under one or more
      * contributor license agreements.  See the NOTICE file distributed with
@@ -25,7 +21,6 @@ namespace Lucene.Net.Facet.Taxonomy
      * limitations under the License.
      */
 
-
     /// <summary>
     /// LRUHashMap is an extension of Java's HashMap, which has a bounded size();
     /// When it reaches that size, each time a new element is added, the least
@@ -58,97 +53,146 @@ namespace Lucene.Net.Facet.Taxonomy
     /// @lucene.experimental
     /// </para>
     /// </summary>
-    public class LRUHashMap<TV, TU> where TU : class //this is implementation of LRU
Cache
+    public class LRUHashMap<TKey, TValue> where TValue : class //this is implementation
of LRU Cache
     {
-
-        public int MaxSize { get; set; }
-        private int CleanSize;
-        private TimeSpan MaxDuration;
-
-
-        private readonly ConcurrentDictionary<TV, CacheDataObject<TU>> _cache
= new ConcurrentDictionary<TV, CacheDataObject<TU>>();
-
-        public LRUHashMap(int maxSize = 50000, int cleanPercentage = 30, TimeSpan maxDuration
= default(TimeSpan))
+        private readonly Dictionary<TKey, CacheDataObject> cache;
+        // We can't use a ReaderWriterLockSlim because every read is also a 
+        // write, so we gain nothing by doing so
+        private readonly object syncLock = new object();
+        // Record last access so we can tie break if 2 calls make it in within
+        // the same millisecond.
+        private long lastAccess;
+        private int maxSize;
+
+        public LRUHashMap(int maxSize)
         {
-            MaxSize = maxSize;
-            CleanSize = (int)Math.Max(MaxSize * (1.0 * cleanPercentage / 100), 1);
-            if (maxDuration == default(TimeSpan))
+            if (maxSize < 1)
             {
-                MaxDuration = TimeSpan.FromDays(1);
+                throw new ArgumentOutOfRangeException("maxSize must be at least 1");
             }
-            else
+            this.maxSize = maxSize;
+            this.cache = new Dictionary<TKey, CacheDataObject>(maxSize);
+        }
+
+        public virtual int MaxSize
+        {
+            get { return maxSize; }
+            set
             {
-                MaxDuration = maxDuration;
+                if (value < 1)
+                {
+                    throw new ArgumentOutOfRangeException("MaxSize must be at least 1");
+                }
+                maxSize = value;
             }
         }
 
-        
-        public bool Put(TV cacheKey, TU value)
+        public bool Put(TKey key, TValue value)
         {
-            return AddToCache(cacheKey, value);
+            lock (syncLock)
+            { 
+                CacheDataObject cdo;
+                if (cache.TryGetValue(key, out cdo))
+                {
+                    // Item already exists, update our last access time
+                    cdo.Timestamp = GetTimestamp();
+                }
+                else
+                {
+                    cache[key] = new CacheDataObject
+                    {
+                        Value = value,
+                        Timestamp = GetTimestamp()
+                    };
+                    // We have added a new item, so we may need to remove the eldest
+                    if (cache.Count > MaxSize)
+                    {
+                        // Remove the eldest item (lowest timestamp) from the cache
+                        cache.Remove(cache.OrderBy(x => x.Value.Timestamp).First().Key);
+                    }
+                }
+            }
+            return true;
         }
 
-        public bool AddToCache(TV cacheKey, TU value)
+        public TValue Get(TKey key)
         {
-            var cachedResult = new CacheDataObject<TU>
-            {
-                Usage = 1, //value == null ? 1 : value.Usage + 1,
-                Value = value,
-                Timestamp = DateTime.UtcNow
-            };
-
-            _cache.AddOrUpdate(cacheKey, cachedResult, (_, __) => cachedResult);
-            if (_cache.Count > MaxSize)
+            lock (syncLock)
             {
-                foreach (var source in _cache
-                    .OrderByDescending(x => x.Value.Usage)
-                    .ThenBy(x => x.Value.Timestamp)
-                    .Skip(MaxSize - CleanSize))
+                CacheDataObject cdo;
+                if (cache.TryGetValue(key, out cdo))
                 {
-                    if (EqualityComparer<TV>.Default.Equals(source.Key, cacheKey))
-                        continue; // we don't want to remove the one we just added
-                    CacheDataObject<TU> ignored;
-                    _cache.TryRemove(source.Key, out ignored);
+                    // Write our last access time
+                    cdo.Timestamp = GetTimestamp();
+
+                    return cdo.Value;
                 }
             }
-            return true;
+            return null;
         }
 
-        public TU Get(TV cacheKey, bool increment = false)
+        public bool TryGetValue(TKey key, out TValue value)
         {
-            CacheDataObject<TU> value;
-            if (_cache.TryGetValue(cacheKey, out value) && (DateTime.UtcNow - value.Timestamp)
<= MaxDuration)
+            lock (syncLock)
             {
-                if (increment)
+                CacheDataObject cdo;
+                if (cache.TryGetValue(key, out cdo))
                 {
-                    Interlocked.Increment(ref value.Usage);
+                    // Write our last access time
+                    cdo.Timestamp = GetTimestamp();
+                    value = cdo.Value;
+
+                    return true;
                 }
-                return value.Value;
+
+                value = null;
+                return false;
             }
-            return null;
         }
 
-        public bool IsExistInCache(TV cacheKey)
+        public bool ContainsKey(TKey key)
         {
-            return (_cache.ContainsKey(cacheKey));
+            return cache.ContainsKey(key);
         }
 
+        // LUCENENET TODO: Rename to Count (.NETify)
         public int Size()
         {
-            return _cache.Count;
+            return cache.Count;
+        }
+
+        private long GetTimestamp()
+        {
+            long ticks = DateTime.UtcNow.Ticks;
+            if (ticks <= lastAccess)
+            {
+                // Tie break by incrementing
+                // when 2 calls happen within the
+                // same millisecond
+                ticks = ++lastAccess;
+            }
+            else
+            {
+                lastAccess = ticks;
+            }
+            return ticks;
         }
+        
 
         #region Nested type: CacheDataObject
 
-        private class CacheDataObject<T> where T : class
+        private class CacheDataObject
         {
-            public DateTime Timestamp;
-            public int Usage;
-            public T Value;
+            // Ticks representing the last access time
+            public long Timestamp;
+            public TValue Value;
+
+            public override string ToString()
+            {
+                return "Last Access: " + Timestamp.ToString() + " - " + Value.ToString();
+            }
         }
 
         #endregion
-
     }
-
 }
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/1ca08dfb/src/Lucene.Net.Tests.Facet/Taxonomy/TestLRUHashMap.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Tests.Facet/Taxonomy/TestLRUHashMap.cs b/src/Lucene.Net.Tests.Facet/Taxonomy/TestLRUHashMap.cs
index 71b62c5..c08bca8 100644
--- a/src/Lucene.Net.Tests.Facet/Taxonomy/TestLRUHashMap.cs
+++ b/src/Lucene.Net.Tests.Facet/Taxonomy/TestLRUHashMap.cs
@@ -30,7 +30,7 @@ namespace Lucene.Net.Facet.Taxonomy
         [Test]
         public virtual void TestLru()
         {
-            LRUHashMap<string, string> lru = new LRUHashMap<string, string>(3,1);
+            LRUHashMap<string, string> lru = new LRUHashMap<string, string>(3);
             Assert.AreEqual(0, lru.Size());
             lru.Put("one", "Hello world");
             Assert.AreEqual(1, lru.Size());


Mime
View raw message