Java - Best Strategy For Appending and Deleting In Giant Lists?

java, list, performance

Solution

A solution

... If you need a constant amount of last elements, just use an array as a base for a ring buffer.

single allocation

no get/put/etc. method overhead if inlined

simple

A sample (may not compile, written on the fly) implementation:

class LastElementsStore<T> {
  Object[] arr;
  int size;
  int nextPutIndex;

  LastElementsStore(int size ) {
    arr = new Object[size];
    this.size = size;
  }

  void put(T elt) {
    arr[nextPutIndex] = elt;
    nextPutIndex++;
    if (nextPutIndex == size) {
      nextPutIndex = 0;
    }
  }

  // getters of your choice

}

If there are not enough elements, nulls will be returned.

If you need them ordered, you start from nextPutIndex, read till the end, then go to 0 and continue reading.

You have full control of the memory, no additional node allocations will be made as in LinkedList, no resizing as in ArrayList.

Old objects are released automatically as soon as your reach the limit.

Your requirements

no DB -- done, just an array used

objects are the same type -- simple template

up to 50,000 objects per second -- if an array can't handle it, nothing in Java can

performance important -- as above, no additional overhead in accessing an array quick iteration through the whole list is important -- as fast an iteration as possible

random access is also important -- the data is ordered, and the first not-null element at/after `nextPutIndex` is the first available

Problem

Using Java. I record small objects for some calculation etc. and I need only the last x thousand of them. So I'd like to release the first to the garbage collector. But since deleting from ArrayLists is expensive ... The following is important (can't change) - no DB - objects are the same type - up to 50,000 objects per second - performance important - quick iteration through the whole list is important - random access is also important This can be changed: - right now using `ArrayList<MyObject>` - limit: 100,000 objects (stops recording, but must continue) My guesses: - LinkedList - RingBuffer - ??? What can I do to iterate very quick and release old objects also quick at the same time ?

Original source