Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (741)
Games in Android Showcase (225)
games submitted by our members
Games in WIP (823)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  "Better" LinkedList implementation  (Read 3728 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd
« Posted 2017-06-18 01:43:53 »

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:
1  
2  
3  
4  
5  
6  
7  
8  
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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
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;
      }
   }
}

Myomyomyo.
Offline Archive
« Reply #1 - Posted 2017-06-18 04:16:14 »

Wouldn't a circular array with a head and tail pointer suffice?

The tail pointer would point at the index at which the least used object (last added) object is.
The head pointer would point at the next available spot (or a taken spot if it has looped all the way around)

When you remove an element, simply set it to null in the array (make sure all operations have a null check)
To move an element from index N to the front, just save it to a temp var, set index N to null, then put the saved element at the head pointer and increment the head pointer.

Instead of the Element interface containing next and previous pointers, it could contain an index into the array so that lookups are O(1)

Offline abcdef
« Reply #2 - Posted 2017-06-18 11:56:46 »

How is the performance compared to the magic ring buffer used in the disruptor software

http://mechanitis.blogspot.co.uk/2011/06/dissecting-disruptor-whats-so-special.html

Like archive suggests it has a circular buffer, you never remove elements to just overwrite the oldest elements in the list.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #3 - Posted 2017-06-18 13:06:41 »

The problem with a simple ring buffer is that it's essentially a FIFO queue. When an element is accessed, I need to move it to the start of the queue again to make sure it's the most recently used again. I don't think that's doable in an array-based ring buffer. Removing an element would leave a null hole in the array. If you want to fill the hole, you need to shift half the elements to fill the hole (either the ones before or after, so 0 to size/2 elements). If you just leave the hole there, you've essentially reduced the size of the cache until the head reaches that point and can fill the null hole, right? I imagine a pathological (but very common) case where the cache is full of objects, and then two elements are accessed repeatedly, causing them to be moved to the head of the list repeatedly. If each movement leaves a null hole, then one element would be evicted from the cache each time an element is moved to the front of the list. =/ If I've misunderstood or missed something, please let me know.

Myomyomyo.
Offline Archive
« Reply #4 - Posted 2017-06-18 16:23:20 »

Actually, yes I believe you are correct theagentd, there would be a hole in the cache until the pointer reaches that value again.
I suppose the linked list is more suited to this problem.

Offline philfrei
« Reply #5 - Posted 2017-06-18 19:41:01 »

Nice!
Are you thinking about a concurrency-safe version by chance, or is that definitely not an issue in your situation?

Multi-threading is on my mind as I just used a LinkedBlockingDeque for safely managing concurrent calls to an AudioCue class that allows concurrent playback. Am only using offerFirst and pollLast methods. Only a handful of instances per Cue play at one time, so efficiency is less of a concern than reliability.

music and music apps: http://adonax.com
Offline theagentd
« Reply #6 - Posted 2017-06-18 22:15:01 »

Are you thinking about a concurrency-safe version by chance, or is that definitely not an issue in your situation?
Not really, it's not a requirement for my use case. It'd just get messy if I needed to support concurrency in the system I'm working on, really. You can always just synchronize on the whole class if you really wanted to.

Myomyomyo.
Offline CoDi^R
« Reply #7 - Posted 2017-06-19 12:39:59 »

The removeFirst() and removeLast() functions don't check for empty lists yet.  Pointing  Grin

I like your solution, esp. because its an intrusive list - the node pointers are members of the list element.

Robotality - steamworks4j - @code_disaster - codi^r @ #java-gaming
Offline Abuse

JGO Ninja


Medals: 60


falling into the abyss of reality


« Reply #8 - Posted 2017-06-19 14:49:23 »

I'd be inclined to have a reference in the Element, to the List that owns it.

It'd allow fail-fast protection against multiple logic errors (adding an Element to multiple lists/the same list multiple times, removing/moving an element from a List that it's not a member of, etc), making the code far less fragile.
Offline cylab

JGO Kernel


Medals: 173



« Reply #9 - Posted 2017-06-20 06:40:35 »

imagine a pathological (but very common) case where the cache is full of objects, and then two elements are accessed repeatedly, causing them to be moved to the head of the list repeatedly. If each movement leaves a null hole, then one element would be evicted from the cache each time an element is moved to the front of the list.
Actually you could make use of this. Just don't move the object to the top of the list, if it's in the upper half (or some other threshold) already. If anything, just swap it with an object a couple of indicies up in the buffer. This way you would only produce holes for the less used objects. Since you don't need additional references, you can easily make up for the lost cache entries by increasing the array size.

Or you only move the head pointer for adding new objects and just swap existing objects up in the buffer. This would not produce any holes and while it is technically not an LRU list anymore, it might provide good enough heuristics to function as a cache.

Mathias - I Know What [you] Did Last Summer!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #10 - Posted 2017-06-20 13:01:46 »

The removeFirst() and removeLast() functions don't check for empty lists yet.  Pointing  Grin

I like your solution, esp. because its an intrusive list - the node pointers are members of the list element.
NOTHING in this list checks for errors. I should've mentioned that in the original post I guess. xd

>Add already existing element again ---> Corrupt link references.
>Add element from another list ---> Corrupt other list.
>moveToHead() on object not in the list ---> head is set to object not in the list.
>remove() object not in list ---> corrupts size counter and may corrupt link references.
>removeFirst/Last() on empty list ---> nuppo

I keep track of if an element is in the list outside the list for the cache, so such testing wasn't necessary (and IMO not the job of the list in the first place).

I'd be inclined to have a reference in the Element, to the List that owns it.

It'd allow fail-fast protection against multiple logic errors (adding an Element to multiple lists/the same list multiple times, removing/moving an element from a List that it's not a member of, etc), making the code far less fragile.
Yeah, that'd be how you add testing. Add a reference to the list the element currently is on, check this reference in add*(), moveToFirst() and remove(). Null out the reference on removal. Also add an isEmpty() check for the removeFirst/Last() functions.

Actually you could make use of this. Just don't move the object to the top of the list, if it's in the upper half (or some other threshold) already. If anything, just swap it with an object a couple of indicies up in the buffer. This way you would only produce holes for the less used objects. Since you don't need additional references, you can easily make up for the lost cache entries by increasing the array size.

Or you only move the head pointer for adding new objects and just swap existing objects up in the buffer. This would not produce any holes and while it is technically not an LRU list anymore, it might provide good enough heuristics to function as a cache.
I'm worried about experimenting too much with my use case. The cache is critical for performance, and if I were to start thrashing, the game will essentially freeze up. I could try some kind of system where you don't move an accessed element to the head of the list, but just "upgrade" it a couple of elements up by swapping it with an element x indices up in the list. If x is randomly chosen for each swap, then the risk of getting to a pathological case would be low. Like you said, this wouldn't be an LRU cache anymore, but some kind of heuristic priority cache I guess. It's an interesting idea, but I'm afraid I don't have much more time to spend on this right now. =/

Myomyomyo.
Offline Icecore
« Reply #11 - Posted 2017-06-20 14:00:05 »

>Add already existing element again ---> Corrupt link references.
>Add element from another list ---> Corrupt other list.
>moveToHead() on object not in the list ---> head is set to object not in the list.
>remove() object not in list ---> corrupts size counter and may corrupt link references.

That’s why linked list elements remember own holder Wink
1  
2  
3  
4  
   public static class SimpleElement<E extends SimpleElement> implements Element<E>{
+      private FastLinkedList<E> Holder;
       private E next, previous;
   }

Or
1  
2  
3  
4  
5  
   public static class LinkedListElement<E>{
      private FastLinkedList<E> Holder;
      private LinkedListElement<E> next, previous;
      public E ElementData;
   }

Last known State: Reassembled in Cyberspace
End Transmission....
..
.
Offline SHC
« Reply #12 - Posted 2017-06-20 14:57:04 »

Instead of exposing the internal element class, won't it be better to keep a static pool of element objects in the linked list class? That's better for the API and easily fixes the corruption problems. I'd like to see how that performs over the standard list.

Offline Jono
« Reply #13 - Posted 2017-06-21 10:00:17 »

A long time ago I did a linked list pool (but only for int values).
http://www.java-gaming.org/topics/linked-list-without-objects/20891/view.html

This was much quicker than object-based linked lists, though I was using it for multiple lists that were often merged/appended. That's a bit different from the use-case here.
Offline Riven
Administrator

« JGO Overlord »


Medals: 1324
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2017-06-22 07:52:33 »

Does your LRU cache need to be perfect? If not, I'd just create buckets of items, and transfer items among buckets, which is cache friendly.

List<List<Item>>
where the inner list is an ArrayList, and the outer list... probably too (as that is still bound to be faster than the LinkedList, even on random insert/remove) given that you probably won't have more than 100 buckets for 10.000 items.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline Icecore
« Reply #15 - Posted 2017-06-22 16:40:18 »

I'd just create buckets of items, and transfer items among buckets, which is cache friendly.

Its good concept – but its not so easy to implement as basic List
And about LRU cache
It sad, but it not help much – because Java hold pointer to object
And objects scattered all around random places on memory
So on iteration of array objects – it jumps around memory - its not cache friendly)

Remove remaining 98 000 objects using removeFirst():
    LinkedList: 0.298 ms
    FastLinkedList: 2.78 ms
and this result most likely because you use Call function - not direct element change like in LinkedList
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
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;
}


LinkedList
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
}

Last known State: Reassembled in Cyberspace
End Transmission....
..
.
Offline theagentd
« Reply #16 - Posted 2017-06-23 17:46:11 »

@SHC
A pooled Node version would probably be slightly worse performance-wise when looping over the list due to the Node object and the element object being in two different places in memory. Also, without exposing the pointers, it becomes a bit annoying to loop through the list, but that's no real concern I guess.

@jono
Interesting, it'd be cool to see a.comparison between that and my implementation.

@Riven
Hmm, how exactly would that work?

Myomyomyo.
Offline Icecore
« Reply #17 - Posted 2017-06-27 11:27:07 »

I think I understand for what you need List – for pathfind
I use for this Binary Heap
My 5 years old code of Binary Heap is not best quality
So I find in google link - it looks nice and clean (better than mine ^^)
https://stackoverflow.com/questions/18241192/implement-heap-using-a-binary-tree

Last known State: Reassembled in Cyberspace
End Transmission....
..
.
Offline Jono
« Reply #18 - Posted 2017-06-27 15:01:18 »

@jono
Interesting, it'd be cool to see a.comparison between that and my implementation.

To make it comparable it has to be turned into a doubly-linked list and be generalised to hold objects instead of just ints.

I tried this out, using elements with a "getID" method to enable the random access. It loses the cache coherency from storing data+references in one array, as well as having more overhead from the extra book-keeping of the previous links. In the end approximately 500x faster than java.util.LinkedList on the random access operations but roughly the same on the removeFirsts -- there is a lot of variance between tests on this though.

In short, no good reason to move from your implementation. It moves the next/prev links out of the elements and into the single pool class, but at the cost of some efficiency.
Pages: [1]
  ignore  |  Print  
 
 

 
Ecumene (106 views)
2017-09-30 02:57:34

theagentd (132 views)
2017-09-26 18:23:31

cybrmynd (243 views)
2017-08-02 12:28:51

cybrmynd (235 views)
2017-08-02 12:19:43

cybrmynd (236 views)
2017-08-02 12:18:09

Sralse (250 views)
2017-07-25 17:13:48

Archive (861 views)
2017-04-27 17:45:51

buddyBro (1005 views)
2017-04-05 03:38:00

CopyableCougar4 (1563 views)
2017-03-24 15:39:42

theagentd (1372 views)
2017-03-24 15:32:08
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-03-02 06:37:51
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!