Hey, everyone.
Today I found myself in a need of a least-recently-used (LRU) cache system. Essentially, I wanted a cache of the last 10 000 used objects. When a new object was to be loaded, I wanted to unload the oldest element in the cache. Before, the cache was only 96 elements, at which point looping through the list to find the least recently used element was perfectly fine for the load I had, but with 10 000 objects, that situation changed. I found that LinkedHashMap could be used as a makeshift cache, as it can be set to update the internal order of elements when they are accessed, but it just seemed inefficient and weird for what I actually wanted to accomplish here. Some research made me realize that a simple linked list was a good fit for this, as a double linked list can easily be maintained in LRU order. Basically, whenever an element in the cache is used, it is moved to the beginning of the list (an O(1) operation on linked list), meaning that the cache stores objects sorted from most recently used to least recently used. Then to remove the most least recently used object, I just remove the tail of the list, again an O(1) operation.
Now, I hope we all know how bad Java’s LinkedList class is. Not only does it generate garbage every time an object is added to it, but moving an object to the beginning of a list is an O(n) operation as I’d need to use list.remove(object), which would need to scan through the list until it finds the object in question and can remove it. A proper linked list implementation would store the previous and next references in the object itself, meaning that finding the previous and next objects become O(1) operations, and the element can be removed without going through the entire list. So… I wrote a minimal linked list that could do what I needed and not much more.
As mentioned, the main difference is that my linked list class does not allocate Node objects to store the next and previous references, but instead stores those references in the elements themselves. This leads to a couple of peculiarities.
- All elements must implement an interface that allows the list to set the previous and next pointers (or alternatively extend a class which implements those functions for it).
- You can’t place the same element in a linked list twice, as each element can only track one previous and next neighbor.
- For the same reason, you can’t even use the same element in two DIFFERENT lists at the same time.
In my case, none of these were an issue, so I went ahead and implemented it. I even added a special method for moving an element in the list to the start of the list for maximum performance in that sense. The class provides the following functions, all of which are O(1):
- addFirst(e)
- addLast(e)
- moveToFirst(e)
- remove(e)
- removeFirst()
- removeLast()
There is no random access function. The correct way of looping through the list is to simply call element.getNext() until it returns null (the current size of the list is tracked though). The somewhat complicated usage of generics is there to allow for type safety, both when extending the Element class and when working with FastLinkedList.
Usage example:
private class MyElement extends FastLinkedList.SimpleElement<MyElement>{ //Note this definition here, it's particularly clever =P
...
}
FastLinkedList<MyElement> list = new FastLinkedList<>();
list.addFirst(...);
...
Performance test on 100 000 randomly shuffled elements:
Adding 100 000 objects to the list:
LinkedList: 1.617 ms
FastLinkedList: 0.627 ms
~3x faster
Move 2000 random elements from their current position to the start of the list:
LinkedList: 203.315 ms
FastLinkedList: 0.118 ms
Insanely much faster (O(n)—>O(1))
Remove 2000 random elements from the list:
LinkedList: 175.541 ms
FastLinkedList: 0.094 ms
Insanely much faster (O(n)—>O(1))
Remove remaining 98 000 objects using removeFirst():
LinkedList: 0.298 ms
FastLinkedList: 2.78 ms
Noticeably slower in this test due to worse cache coherency. FastLinkedList needs to access each element’s data to find the next and previous node in the list. As the elements are shuffled, this ends up jumping around randomly in memory. Java’s LinkedList instead creates Node objects for each element, which end up sequentially in memory as they’re recreated each iteration. This is not an issue with real-life data, and is the cost of going garbage-less.
Code:
package engine.util;
import engine.util.FastLinkedList.Element; //this import is required
public class FastLinkedList<E extends Element<E>> {
private E head, tail;
private int size;
public FastLinkedList() {}
public void addFirst(E element){
if(size == 0){
head = element;
tail = element;
}else{
head.setPrevious(element);
element.setNext(head);
head = element;
}
size++;
}
public void addLast(E element){
if(size == 0){
head = element;
tail = element;
}else{
tail.setNext(element);
element.setPrevious(tail);
tail = element;
}
size++;
}
public void moveToFirst(E element){
if(element == head){
return;
}
E prev = element.getPrevious();
E next = element.getNext();
prev.setNext(next); //prev cannot be null thanks to if-statement above
if(next != null){
next.setPrevious(prev);
}else{
//element was tail, update the tail.
tail = prev;
}
element.setPrevious(null);
element.setNext(head);
head.setPrevious(element);
head = element;
}
public void remove(E element){
E prev = element.getPrevious();
E next = element.getNext();
if(prev != null){
prev.setNext(next);
}else{
//prev == null means element was head.
head = next;
}
if(next != null){
next.setPrevious(prev);
}else{
//next == null means element was tail.
tail = prev;
}
element.setPrevious(null);
element.setNext(null);
size--;
}
public E removeFirst(){
E h = head;
E next = h.getNext();
if(next != null){
next.setPrevious(null);
}else{
//next and prev are null, list is now empty
tail = null;
}
h.setNext(null);
head = next;
size--;
return h;
}
public E removeLast(){
E t = tail;
E prev = t.getPrevious();
if(prev != null){
prev.setNext(null);
}else{
//next and prev are null, list is now empty
head = null;
}
t.setPrevious(null);
tail = prev;
size--;
return t;
}
public E getFirst(){
return head;
}
public E getLast(){
return tail;
}
public int size() {
return size;
}
public boolean isEmpty(){
return size == 0;
}
public String toString() {
StringBuilder b = new StringBuilder("[");
E e = head;
for(int i = 0; i < size; i++){
b.append(e.toString());
if(i != size-1){
b.append(", ");
}
e = e.getNext();
}
return b.append(']').toString();
}
public static interface Element<E extends Element>{
public void setNext(E next);
public void setPrevious(E previous);
public E getNext();
public E getPrevious();
}
public static class SimpleElement<E extends SimpleElement> implements Element<E>{
private E next, previous;
@Override
public void setNext(E next) {
this.next = next;
}
@Override
public void setPrevious(E previous) {
this.previous = previous;
}
@Override
public E getNext() {
return next;
}
@Override
public E getPrevious() {
return previous;
}
}
}
