plumbing/cache: change FIFO to LRU cache
diff --git a/plumbing/cache/object.go b/plumbing/cache/object.go
deleted file mode 100644
index 44e0d32..0000000
--- a/plumbing/cache/object.go
+++ /dev/null
@@ -1,73 +0,0 @@
-package cache
-
-import (
- "gopkg.in/src-d/go-git.v4/plumbing"
-)
-
-const (
- initialQueueSize = 20
- MaxSize = 10 * MiByte
-)
-
-type ObjectFIFO struct {
- objects map[plumbing.Hash]plumbing.EncodedObject
- order *queue
-
- maxSize FileSize
- actualSize FileSize
-}
-
-// NewObjectFIFO returns an Object cache that keeps the newest objects that fit
-// into the specific memory size
-func NewObjectFIFO(size FileSize) *ObjectFIFO {
- return &ObjectFIFO{
- objects: make(map[plumbing.Hash]plumbing.EncodedObject),
- order: newQueue(initialQueueSize),
- maxSize: size,
- }
-}
-
-// Put puts a new object to the cache. If the object size is greater than the
-// cache size, the object is not added.
-func (c *ObjectFIFO) Put(o plumbing.EncodedObject) {
- objSize := FileSize(o.Size())
-
- // if the size of the object is bigger or equal than the cache size,
- // skip it
- if objSize >= c.maxSize {
- return
- }
-
- // if the object is into the cache, do not add it again
- if _, ok := c.objects[o.Hash()]; ok {
- return
- }
-
- // delete the oldest object if cache is full
- if c.actualSize >= c.maxSize {
- h := c.order.Pop()
- o := c.objects[h]
- if o != nil {
- c.actualSize -= FileSize(o.Size())
- delete(c.objects, h)
- }
- }
-
- c.objects[o.Hash()] = o
- c.order.Push(o.Hash())
- c.actualSize += FileSize(o.Size())
-}
-
-// Get returns an object by his hash. If the object is not found in the cache, it
-// returns nil
-func (c *ObjectFIFO) Get(k plumbing.Hash) (plumbing.EncodedObject, bool) {
- obj, ok := c.objects[k]
- return obj, ok
-}
-
-// Clear the content of this object cache
-func (c *ObjectFIFO) Clear() {
- c.objects = make(map[plumbing.Hash]plumbing.EncodedObject)
- c.order = newQueue(initialQueueSize)
- c.actualSize = 0
-}
diff --git a/plumbing/cache/object_lru.go b/plumbing/cache/object_lru.go
new file mode 100644
index 0000000..e4c3160
--- /dev/null
+++ b/plumbing/cache/object_lru.go
@@ -0,0 +1,84 @@
+package cache
+
+import (
+ "container/list"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+)
+
+// ObjectLRU implements an object cache with an LRU eviction policy and a
+// maximum size (measured in object size).
+type ObjectLRU struct {
+ MaxSize FileSize
+
+ actualSize FileSize
+ ll *list.List
+ cache map[interface{}]*list.Element
+}
+
+// NewObjectLRU creates a new ObjectLRU with the given maximum size. The maximum
+// size will never be exceeded.
+func NewObjectLRU(maxSize FileSize) *ObjectLRU {
+ return &ObjectLRU{MaxSize: maxSize}
+}
+
+// Put puts an object into the cache. If the object is already in the cache, it
+// will be marked as used. Otherwise, it will be inserted. A single object might
+// be evicted to make room for the new object.
+func (c *ObjectLRU) Put(obj plumbing.EncodedObject) {
+ if c.cache == nil {
+ c.actualSize = 0
+ c.cache = make(map[interface{}]*list.Element, 1000)
+ c.ll = list.New()
+ }
+
+ key := obj.Hash()
+ if ee, ok := c.cache[key]; ok {
+ c.ll.MoveToFront(ee)
+ ee.Value = obj
+ return
+ }
+
+ objSize := FileSize(obj.Size())
+
+ if objSize >= c.MaxSize {
+ return
+ }
+
+ if c.actualSize+objSize > c.MaxSize {
+ last := c.ll.Back()
+ lastObj := last.Value.(plumbing.EncodedObject)
+ lastSize := FileSize(lastObj.Size())
+
+ c.ll.Remove(last)
+ delete(c.cache, lastObj.Hash())
+ c.actualSize -= lastSize
+
+ if c.actualSize+objSize > c.MaxSize {
+ return
+ }
+ }
+
+ ee := c.ll.PushFront(obj)
+ c.cache[key] = ee
+ c.actualSize += objSize
+}
+
+// Get returns an object by its hash. It marks the object as used. If the object
+// is not in the cache, (nil, false) will be returned.
+func (c *ObjectLRU) Get(k plumbing.Hash) (plumbing.EncodedObject, bool) {
+ ee, ok := c.cache[k]
+ if !ok {
+ return nil, false
+ }
+
+ c.ll.MoveToFront(ee)
+ return ee.Value.(plumbing.EncodedObject), true
+}
+
+// Clear the content of this object cache.
+func (c *ObjectLRU) Clear() {
+ c.ll = nil
+ c.cache = nil
+ c.actualSize = 0
+}
diff --git a/plumbing/cache/object_test.go b/plumbing/cache/object_test.go
index 2a55acf..9359455 100644
--- a/plumbing/cache/object_test.go
+++ b/plumbing/cache/object_test.go
@@ -12,7 +12,7 @@
func Test(t *testing.T) { TestingT(t) }
type ObjectSuite struct {
- c *ObjectFIFO
+ c Object
aObject plumbing.EncodedObject
bObject plumbing.EncodedObject
cObject plumbing.EncodedObject
@@ -27,32 +27,26 @@
s.cObject = newObject("cccccccccccccccccccccccccccccccccccccccc", 1*Byte)
s.dObject = newObject("dddddddddddddddddddddddddddddddddddddddd", 1*Byte)
- s.c = NewObjectFIFO(2 * Byte)
+ s.c = NewObjectLRU(2 * Byte)
}
-func (s *ObjectSuite) TestAdd_SameObject(c *C) {
+func (s *ObjectSuite) TestPutSameObject(c *C) {
s.c.Put(s.aObject)
- c.Assert(s.c.actualSize, Equals, 1*Byte)
s.c.Put(s.aObject)
- c.Assert(s.c.actualSize, Equals, 1*Byte)
+ _, ok := s.c.Get(s.aObject.Hash())
+ c.Assert(ok, Equals, true)
}
-func (s *ObjectSuite) TestAdd_BigObject(c *C) {
+func (s *ObjectSuite) TestPutBigObject(c *C) {
s.c.Put(s.bObject)
- c.Assert(s.c.actualSize, Equals, 0*Byte)
- c.Assert(s.c.actualSize, Equals, 0*KiByte)
- c.Assert(s.c.actualSize, Equals, 0*MiByte)
- c.Assert(s.c.actualSize, Equals, 0*GiByte)
- c.Assert(len(s.c.objects), Equals, 0)
+ _, ok := s.c.Get(s.aObject.Hash())
+ c.Assert(ok, Equals, false)
}
-func (s *ObjectSuite) TestAdd_CacheOverflow(c *C) {
+func (s *ObjectSuite) TestPutCacheOverflow(c *C) {
s.c.Put(s.aObject)
- c.Assert(s.c.actualSize, Equals, 1*Byte)
s.c.Put(s.cObject)
- c.Assert(len(s.c.objects), Equals, 2)
s.c.Put(s.dObject)
- c.Assert(len(s.c.objects), Equals, 2)
obj, ok := s.c.Get(s.aObject.Hash())
c.Assert(ok, Equals, false)
@@ -67,9 +61,7 @@
func (s *ObjectSuite) TestClear(c *C) {
s.c.Put(s.aObject)
- c.Assert(s.c.actualSize, Equals, 1*Byte)
s.c.Clear()
- c.Assert(s.c.actualSize, Equals, 0*Byte)
obj, ok := s.c.Get(s.aObject.Hash())
c.Assert(ok, Equals, false)
c.Assert(obj, IsNil)
diff --git a/storage/filesystem/object.go b/storage/filesystem/object.go
index 4a67a00..6dd910b 100644
--- a/storage/filesystem/object.go
+++ b/storage/filesystem/object.go
@@ -29,7 +29,7 @@
func newObjectStorage(dir *dotgit.DotGit) (ObjectStorage, error) {
s := ObjectStorage{
- DeltaBaseCache: cache.NewObjectFIFO(DefaultMaxDeltaBaseCacheSize),
+ DeltaBaseCache: cache.NewObjectLRU(DefaultMaxDeltaBaseCacheSize),
dir: dir,
}
