diff options
| -rw-r--r-- | plumbing/cache/object.go | 73 | ||||
| -rw-r--r-- | plumbing/cache/object_lru.go | 84 | ||||
| -rw-r--r-- | plumbing/cache/object_test.go | 26 | ||||
| -rw-r--r-- | storage/filesystem/object.go | 2 |
4 files changed, 94 insertions, 91 deletions
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 @@ import ( 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 @@ func (s *ObjectSuite) SetUpTest(c *C) { 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) TestAdd_CacheOverflow(c *C) { 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 @@ type ObjectStorage struct { func newObjectStorage(dir *dotgit.DotGit) (ObjectStorage, error) { s := ObjectStorage{ - DeltaBaseCache: cache.NewObjectFIFO(DefaultMaxDeltaBaseCacheSize), + DeltaBaseCache: cache.NewObjectLRU(DefaultMaxDeltaBaseCacheSize), dir: dir, } |