Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Memory leak when using method Remove() #4

Open
Vykstorm opened this issue Apr 20, 2023 · 0 comments
Open

Memory leak when using method Remove() #4

Vykstorm opened this issue Apr 20, 2023 · 0 comments

Comments

@Vykstorm
Copy link

While using this queue implementation in one of my projects, i noticed that the memory consumption of my process was growing indefinitely.
While doing some research by profilling my application, i realized that a call to Remove() only deletes the entries of the maps Queue.items, Queue.ids for the removed element , but Queue.count value is not decreased.
The effect of this is that when the Append() function is called again, Queue.count is increased, and if Queue.count >= len(Queue.buf), the buffer is increased by twice it's size.

In other words, the next code will indefinitely grow the internal buffer and consume uneeded heap memory```

q := queue.New()
for {
   q.Append(0)
   q.Remove(0)
}

I suggest an alternative implementation which fix this problem and updates Queue.buf and Queue.count properly (but with O(n) complexity).

func (q *Queue) Remove(elem interface{}) bool {
	q.mutex.Lock()
	defer q.mutex.Unlock()

	id, ok := q.ids[elem]
	if !ok {
		return false
	}
	q.moveToFront(id)

	for {
		id := q.pop()

		item, ok := q.items[id]

		if ok {
			delete(q.ids, item)
			delete(q.items, id)
			q.onChanged()
			return true
		}
	}
}

func (q *Queue) moveToFront(id int64) {
	// Precondition: id is the id of an item in the queue. 
	// Find position in buf where item with id is located
	i := q.head
	for {
		if q.buf[i] == id {
			break
		}
		i += 1
	}
	// Move elements from J=head .. i-1 to j+1
	if i == q.head {
		// Already in the front of the queue
		return
	}

	for j := i; j > q.head; j-- {
			q.buf[j] = q.buf[j-1]
	}
	
	// Place ith element into head
	q.buf[q.head] = id
}

Wrote also a unit test:


func TestRemove(t *testing.T) {
	q := New()
	k := 500
	for  i := 0; i < k; i++ {
		q.Append(i)
	}
	for i := 0; i < k; i++ {
		value := k-i-1
		q.Remove(value)

		// q.count remains consistent
		require.Equal(t, q.count, k-i-1)

		// The rest of values remains in the queue
		for j := 0; j < value; j++ {
			require.True(t, q.Contains(j))
		}
		// Queue does not contain deleted values anymore
		for j := value; j < k; j ++ {
			require.False(t, q.Contains(j))
		}
	}

	// Queue is now empty
	require.True(t, q.Empty())
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant