Repository: maypok86/otter
Pull request #25 (2023-12-15 20:50:58)

Reduce memory footprint
## Description

<!--
Describes the nature of your changes. If they are substantial, you should
further subdivide this into a section describing the problem you are solving and
another describing your solution.
-->

To reduce the memory footprint, we use time from program start instead of Unix time and spinlock instead of mutex to synchronize nodes

## Related issue(s)
#23 
<!--
- Short description of how the PR relates to the issue, including an issue link.
For example
- Fixed #100500 by adding lenses to exported items

Write 'None' if there are no related issues (which is discouraged).
-->

## :white_check_mark: Checklist for your Pull Request

<!--
Ideally a PR has all of the checkmarks set.

If something in this list is irrelevant to your PR, you should still set this
checkmark indicating that you are sure it is dealt with (be that by irrelevance).

If you don't set a checkmark (e. g. don't add a test for new functionality),
you must be able to justify that.
-->

#### Related changes (conditional)

- Tests
    - [x] If I added new functionality, I added tests covering it.
    - [x] If I fixed a bug, I added a regression test to prevent the bug from
      silently reappearing again.

- Documentation
    - [x] I checked whether I should update the docs and did so if necessary:
        - [README](../README.md)

- Public contracts
    - [x] My changes doesn't break project license.

#### Stylistic guide (mandatory)

- [x] My code complies with the [styles guide](https://github.com/uber-go/guide/blob/master/style.md).
- [x] My commit history is clean (only contains changes relating to my
  issue/pull request and no reverted-my-earlier-commit changes) and commit
  messages start with identifiers of related issues in square brackets.

  **Example:** `[#42] Short commit description`

  If necessary both of these can be achieved even after the commits have been
  made/pushed using [rebase and squash](https://git-scm.com/docs/git-rebase).

#### Before merging (mandatory)
- [x] Check __target__  branch of PR is set correctly



Patch:
diff --git a/.golangci.yml b/.golangci.yml
index 784f48a..dbbca8e 100644
--- a/.golangci.yml
+++ b/.golangci.yml
@@ -66,6 +66,10 @@ issues:
     - path: _test\.go
       linters:
         - gosec
+    - path: internal/spinlock/spinlock_test.go
+      linters:
+        - gocritic
+        - staticcheck
 linters-settings:
   gci:
     sections:
diff --git a/cache.go b/cache.go
index 1feb5cb..182db01 100644
--- a/cache.go
+++ b/cache.go
@@ -123,11 +123,11 @@ func (c *Cache[K, V]) Set(key K, value V) {
 
 func (c *Cache[K, V]) SetWithTTL(key K, value V, ttl time.Duration) {
 	ttl = (ttl + time.Second - 1) / time.Second
-	expiration := unixtime.Now() + uint64(ttl)
+	expiration := unixtime.Now() + uint32(ttl)
 	c.set(key, value, expiration)
 }
 
-func (c *Cache[K, V]) set(key K, value V, expiration uint64) {
+func (c *Cache[K, V]) set(key K, value V, expiration uint32) {
 	cost := c.costFunc(key, value)
 	if cost >= c.policy.MaxAvailableCost() {
 		return
diff --git a/internal/expire/policy.go b/internal/expire/policy.go
index 6b8249e..3f76bb0 100644
--- a/internal/expire/policy.go
+++ b/internal/expire/policy.go
@@ -9,8 +9,8 @@ import (
 
 const (
 	numberOfBuckets = 128
-	mask            = uint64(numberOfBuckets - 1)
-	base            = uint64(5)
+	mask            = uint32(numberOfBuckets - 1)
+	base            = uint32(5)
 
 	// eliminate probing.
 	maxProbeCount = 100
@@ -19,11 +19,11 @@ const (
 	mapSize = 100
 )
 
-func bucketTimeToBucketID(bucketTime uint64) int {
+func bucketTimeToBucketID(bucketTime uint32) int {
 	return int(bucketTime & mask)
 }
 
-func timestampToBucketTime(timestamp uint64) uint64 {
+func timestampToBucketTime(timestamp uint32) uint32 {
 	return timestamp / base
 }
 
@@ -33,7 +33,7 @@ func nextBucketID(bucketID int) int {
 
 type bucket[K comparable, V any] struct {
 	m        *swiss.Map[*node.Node[K, V], struct{}]
-	lastTime uint64
+	lastTime uint32
 }
 
 func newBucket[K comparable, V any]() bucket[K, V] {
@@ -43,7 +43,7 @@ func newBucket[K comparable, V any]() bucket[K, V] {
 	}
 }
 
-func (b *bucket[K, V]) add(n *node.Node[K, V], newTime uint64) {
+func (b *bucket[K, V]) add(n *node.Node[K, V], newTime uint32) {
 	if b.isEmpty() {
 		b.m.Put(n, struct{}{})
 		b.lastTime = newTime
@@ -127,7 +127,7 @@ func (p *Policy[K, V]) RemoveExpired(expired []*node.Node[K, V]) []*node.Node[K,
 	return p.probingExpire(expired)
 }
 
-func (p *Policy[K, V]) expireBucket(expired []*node.Node[K, V], bucketID int, now uint64) []*node.Node[K, V] {
+func (p *Policy[K, V]) expireBucket(expired []*node.Node[K, V], bucketID int, now uint32) []*node.Node[K, V] {
 	b := &p.buckets[bucketID]
 	if b.lastTime == 0 {
 		return expired
diff --git a/internal/node/node.go b/internal/node/node.go
index 39b74e4..cedb4ff 100644
--- a/internal/node/node.go
+++ b/internal/node/node.go
@@ -1,9 +1,9 @@
 package node
 
 import (
-	"sync"
 	"sync/atomic"
 
+	"github.com/maypok86/otter/internal/spinlock"
 	"github.com/maypok86/otter/internal/unixtime"
 )
 
@@ -20,15 +20,15 @@ type Node[K comparable, V any] struct {
 	value      V
 	prev       *Node[K, V]
 	next       *Node[K, V]
-	mutex      sync.Mutex
+	lock       spinlock.SpinLock
+	expiration uint32
 	hash       uint64
-	expiration uint64
 	cost       uint32
 	frequency  uint8
 	queueType  uint8
 }
 
-func New[K comparable, V any](key K, value V, expiration uint64, cost uint32) *Node[K, V] {
+func New[K comparable, V any](key K, value V, expiration, cost uint32) *Node[K, V] {
 	return &Node[K, V]{
 		key:        key,
 		value:      value,
@@ -42,16 +42,16 @@ func (n *Node[K, V]) Key() K {
 }
 
 func (n *Node[K, V]) Value() V {
-	n.mutex.Lock()
+	n.lock.Lock()
 	v := n.value
-	n.mutex.Unlock()
+	n.lock.Unlock()
 	return v
 }
 
 func (n *Node[K, V]) SetValue(value V) {
-	n.mutex.Lock()
+	n.lock.Lock()
 	n.value = value
-	n.mutex.Unlock()
+	n.lock.Unlock()
 }
 
 func (n *Node[K, V]) Hash() uint64 {
@@ -66,7 +66,7 @@ func (n *Node[K, V]) IsExpired() bool {
 	return n.expiration > 0 && n.expiration < unixtime.Now()
 }
 
-func (n *Node[K, V]) Expiration() uint64 {
+func (n *Node[K, V]) Expiration() uint32 {
 	return n.expiration
 }
 
diff --git a/internal/spinlock/spinlock.go b/internal/spinlock/spinlock.go
new file mode 100644
index 0000000..b6bcf60
--- /dev/null
+++ b/internal/spinlock/spinlock.go
@@ -0,0 +1,31 @@
+package spinlock
+
+import (
+	"runtime"
+	"sync/atomic"
+)
+
+const maxBackoff = 16
+
+// SpinLock is an implementation of spinlock using exponential backoff algorithm.
+type SpinLock uint32
+
+// Lock locks sl. If the lock is already in use, the calling goroutine blocks until the spinlock is available.
+func (sl *SpinLock) Lock() {
+	backoff := 1
+	for !atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
+		// Leverage the exponential backoff algorithm, see https://en.wikipedia.org/wiki/Exponential_backoff.
+		for i := 0; i < backoff; i++ {
+			runtime.Gosched()
+		}
+		if backoff < maxBackoff {
+			backoff <<= 1
+		}
+	}
+}
+
+// Unlock unlocks sl. A locked SpinLock is not associated with a particular goroutine.
+// It is allowed for one goroutine to lock a SpinLock and then arrange for another goroutine to unlock it.
+func (sl *SpinLock) Unlock() {
+	atomic.StoreUint32((*uint32)(sl), 0)
+}
diff --git a/internal/unixtime/unixtime.go b/internal/unixtime/unixtime.go
index a09d27c..d98fb41 100644
--- a/internal/unixtime/unixtime.go
+++ b/internal/unixtime/unixtime.go
@@ -6,11 +6,11 @@ import (
 	"time"
 )
 
-// We need this package because time.Now() is slower, allocates memory,
-// and we don't need a more precise time for the expiry time (and most other operations).
-var now uint64
-
 var (
+	// We need this package because time.Now() is slower, allocates memory,
+	// and we don't need a more precise time for the expiry time (and most other operations).
+	now uint32
+
 	mutex         sync.Mutex
 	countInstance int
 	done          chan struct{}
@@ -18,7 +18,8 @@ var (
 
 func startTimer() {
 	done = make(chan struct{})
-	atomic.StoreUint64(&now, uint64(time.Now().Unix()))
+	startTime := time.Now().Unix()
+	atomic.StoreUint32(&now, uint32(0))
 
 	go func() {
 		ticker := time.NewTicker(time.Second)
@@ -26,7 +27,7 @@ func startTimer() {
 		for {
 			select {
 			case t := <-ticker.C:
-				atomic.StoreUint64(&now, uint64(t.Unix()))
+				atomic.StoreUint32(&now, uint32(t.Unix()-startTime))
 			case <-done:
 				return
 			}
@@ -58,7 +59,7 @@ func Stop() {
 	}
 }
 
-// Now returns time as a Unix time, the number of seconds elapsed since January 1, 1970 UTC.
-func Now() uint64 {
-	return atomic.LoadUint64(&now)
+// Now returns time as a Unix time, the number of seconds elapsed since program start.
+func Now() uint32 {
+	return atomic.LoadUint32(&now)
 }


Test patch:
diff --git a/internal/spinlock/spinlock_test.go b/internal/spinlock/spinlock_test.go
new file mode 100644
index 0000000..df78698
--- /dev/null
+++ b/internal/spinlock/spinlock_test.go
@@ -0,0 +1,65 @@
+// Copyright notice. Initial version of the following tests was based on
+// the following file from the Go Programming Language core repo:
+// https://github.com/golang/go/blob/831f9376d8d730b16fb33dfd775618dffe13ce7a/src/sync/mutex_test.go
+package spinlock
+
+import (
+	"runtime"
+	"testing"
+	"time"
+)
+
+func HammerSpinLock(sl *SpinLock, loops int, cdone chan bool) {
+	for i := 0; i < loops; i++ {
+		sl.Lock()
+		sl.Unlock()
+	}
+	cdone <- true
+}
+
+func TestSpinLock(t *testing.T) {
+	if n := runtime.SetMutexProfileFraction(1); n != 0 {
+		t.Logf("got mutexrate %d expected 0", n)
+	}
+	defer runtime.SetMutexProfileFraction(0)
+	sl := new(SpinLock)
+	c := make(chan bool)
+	for i := 0; i < 10; i++ {
+		go HammerSpinLock(sl, 1000, c)
+	}
+	for i := 0; i < 10; i++ {
+		<-c
+	}
+}
+
+func TestSpinLockFairness(t *testing.T) {
+	var sl SpinLock
+	stop := make(chan bool)
+	defer close(stop)
+	go func() {
+		for {
+			sl.Lock()
+			time.Sleep(100 * time.Microsecond)
+			sl.Unlock()
+			select {
+			case <-stop:
+				return
+			default:
+			}
+		}
+	}()
+	done := make(chan bool, 1)
+	go func() {
+		for i := 0; i < 10; i++ {
+			time.Sleep(100 * time.Microsecond)
+			sl.Lock()
+			sl.Unlock()
+		}
+		done <- true
+	}()
+	select {
+	case <-done:
+	case <-time.After(10 * time.Second):
+		t.Fatalf("can't acquire SpinLock in 10 seconds")
+	}
+}
diff --git a/internal/unixtime/unixtime_bench_test.go b/internal/unixtime/unixtime_bench_test.go
index 5314212..eaf67db 100644
--- a/internal/unixtime/unixtime_bench_test.go
+++ b/internal/unixtime/unixtime_bench_test.go
@@ -11,11 +11,11 @@ func BenchmarkNow(b *testing.B) {
 
 	b.ReportAllocs()
 	b.RunParallel(func(pb *testing.PB) {
-		var ts uint64
+		var ts uint32
 		for pb.Next() {
 			ts += Now()
 		}
-		atomic.StoreUint64(&sink, ts)
+		atomic.StoreUint64(&sink, uint64(ts))
 	})
 
 	Stop()
diff --git a/internal/unixtime/unixtime_test.go b/internal/unixtime/unixtime_test.go
index c8abf17..dfbe735 100644
--- a/internal/unixtime/unixtime_test.go
+++ b/internal/unixtime/unixtime_test.go
@@ -8,18 +8,16 @@ import (
 func TestNow(t *testing.T) {
 	Start()
 
-	expected := time.Now().Unix()
 	got := Now()
-	if uint64(expected) != got {
-		t.Fatalf("unexpected unix time; got %d; want %d", got, expected)
+	if got != 0 {
+		t.Fatalf("unexpected time since program start; got %d; want %d", got, 0)
 	}
 
 	time.Sleep(3 * time.Second)
 
-	expected = time.Now().Unix()
 	got = Now()
-	if uint64(expected)-got > 1 {
-		t.Fatalf("unexpected unix time; got %d; want %d", got, expected)
+	if got != 2 && got != 3 {
+		t.Fatalf("unexpected time since program start; got %d; want %d", got, 3)
 	}
 
 	Stop()