add element to limited size list

Question

I have the following method which adds an element to a size limited ArrayList. If the size of the ArrayList exceeds, previous elements are removed (like FIFO = "first in first out") (version 1):

// adds the "item" into "list" and satisfies the "limit" of the list
public static <T> void add(List<T> list, final T item, int limit) {
        var size = list.size() + 1;
        if (size > limit) {
            var exeeded = size - limit;
            for (var i = 0; i < exeeded; i++) {
                list.remove(0);
            }
        }
        list.add(item);
    }

The "version 1"-method works. However, I wanted to improve this method by using subList (version 2):

public static <T> void add(List<T> list, final T item, int limit) {
    var size = list.size() + 1;
    if (size > limit) {
        var exeeded = size - limit;
        list.subList(0, exeeded).clear();
    }
    list.add(item);
}

Both methods works. However, I want to know if "version 2" is also more performant than "version 1".

EDIT: improved "Version 3":

public static <T> void add(List<T> list, final T item, int limit) {
        var size = list.size() + 1;
        if (size > limit) {
            var exeeded = size - limit;
            if (exeeded > 1) {
                list.subList(0, exeeded).clear();
            } else {
                list.remove(0);
            }
        }
        list.add(item);
    }

But you can change the parameter `limit` and the `exceeded`-parts has the aim to remove all exceeding items (which may be 1 or higher). If you have a better version, please share as an answer. I need the most performant solution for this use case. — nimo23, May 17 '21 at 11:48
Yes, it will be filled if limit is reached. You can try it out. — nimo23, May 17 '21 at 11:51
Ok, got it. So you alter the limit dynamically? Then I removed my comment, because it no longer makes sense now that I understood your requirements. — maloomeister, May 17 '21 at 11:51
If you don't consider alternative approaches (which are probably superior and explained in the existing answers), then the second version is the better of the two. In many list implementations, there will be no difference, but some (such as `ArrayList`) can avoid a lot of unnecessary work if they get told a whole chunk of the list to remove at once as opposed to calling remove multiple times. — Joachim Sauer, May 17 '21 at 12:02
@JoachimSauer is this also valid if the "whole chunk" only contains of only one element? For example, if `exceeded = 1`, then is `list.subList(0, 1).clear();` worser than `list.remove(0);` Or does it not make any difference if `exceeded = 1`? Most of the time, `exceeded = 1` but in rare cases it can be higher.. — nimo23, May 17 '21 at 12:09
@nimo23: That sounds like a micro-optimization that makes the code much less clear and has only limited benefit. Before I'd even consider implementing this as a potential performance improvement, I'd have to be pretty convinced that this is an actual bottleneck. That being said: if the sublist is only one element, then theoretically the cost of creating the view object could increase the cost over that of a simple remove() call. — Joachim Sauer, May 17 '21 at 12:13
Since you are using the `List` interface and didn’t name an actual implementation class, no statement about the performance can be made. Apparently, you are considering `ArrayList`. Then, the simple answer is, use none of these variants, but an `ArrayDeque` instead. — Holger, May 18 '21 at 07:51
*1.* With an `ArrayDeque`, I cannot change the limit dynamically - with my implementation, I can. *2.* Is anything wrong with my implementation to consider to use `ArrayDeque`? — nimo23, May 18 '21 at 08:01
1. What do you mean with “With an `ArrayDeque`, I cannot change the limit dynamically”? Of course you can. The same way as with `ArrayList`. 2. Why do you suddenly ask whether there is “anything wrong”? You asked a *performance* question and `ArrayDeque` doesn’t have the performance issue that you attempt to solve. You can remove from the head without causing copying of any elements in the underlying array. — Holger, May 18 '21 at 12:13
@Holger yes, right. `ArrayDeque` seems better for such a dynamically circular buffer. If you want, you can post an answer which I will accept. — nimo23, May 18 '21 at 12:21

score 4 · Accepted Answer · answered May 18 '21 at 16:21

It seems you have the ArrayList implementation in mind where remove(0) imposes the cost of copying all remaining elements in the backing array, repeatedly if you invoke remove(0) repeatedly.

In this case, using subList(0, number).clear() is a significant improvement, as you’re paying the cost of copying elements only once instead of number times.

Since the copying costs of remove(0) and subList(0, number).clear() are identical when number is one, the 3rd variant would save the cost of creating a temporary object for the sub list in that case. This, however is a tiny impact that doesn’t depend on the size of the list (or any other aspect of the input) and usually isn’t worth the more complex code. See also this answer for a discussion of the costs of a single temporary object. It’s even possible that the costs of the sub list construction get removed by the JVM’s runtime optimizer. Hence, such a conditional should only be used when you experience an actual performance problem, the profiler traces the problem back to this point, and benchmarks prove that the more complicated code has a positive effect.

But this is all moot when you use an ArrayDeque instead. This class has no copying costs when removing its head element, hence you can simply remove excess elements in a loop.

score 0 · Answer 2 · answered May 17 '21 at 11:41

Question 1: The problem is this line:

list = list.subList(exeeded, list.size());

You're reassigning the variable list which will not change to object passed as an argument but only its local counterpart.

Question 2: The sublist will (on an array list) still need to recreate the array at some point. If you don't want that you could use a LinkedList. But as a general rule the ArrayList will still perform better on the whole. Since the underlying array only has to be recreated when exceeding the maximum capacity it usually doesn't matter a lot. You could also try to actually shift the array, move every element to the next slot in the array. That way you would have to move all elements when a new one is added but don't need to recreate the array. So you avoid the trip to the heap which is usually the biggest impact on performance.

add element to limited size list

2 Answers2