Повышение производительности при переходе на пользовательский односвязный список

Question

Я создал односвязный список в Java.Этот список обладает свойством, что первый нажатый элемент является последним элементом, который будет извлечен.

Потрясающая производительность по сравнению с очередью.Мне нравится улучшать производительность пуша.Вместо добавления я также попытался добавить метод push, это не улучшило производительность.

У вас есть идеи, как улучшить этот список?

Производительность Push-Pop (стек, ArrayList и Queue являются реализациями java.util):

10 миллионов целых чисел, усредненных за 10 прогонов

• Заполнение стека: 776,3 мс
• Поппинг стека: 207,2 мс
• Заполнение ArrayList: 574,0 мс
• Отображение ArrayList: 35,3 мс
• Заполнение очереди: 2642,2 мс
• Оформление очереди: 96,9 мс
• Заполнение MyList: 4811,2 мс
• Отображение MyList: 50,5 мс

public class MyList<T> {
    T head = null;
    MyList<T> tail = null;
    boolean isNil = true;

    public T pop() {
        if(isNil) {
            return null;
        }
        else if(this.tail.isNil) {
            this.isNil = true;
            return head;
        }
        else {
            T head = this.head;
            this.head = this.tail.head;
            this.tail = this.tail.tail;
            return head;
        }
    }

    public void push(T element) {
        MyList<T> item = new MyList<T>();
        item.head = this.head;
        item.tail = this.tail;
        item.isNil = this.isNil;
        this.head = element;
        this.tail = item;
        this.isNil = false;
    }
}

Answer 1

Я думаю, что причина того, что производительность вашего списка отстает от ArrayList, заключается в том, что вы выделяете много мелких объектов, тогда как ArrayList (и Stack, , основанные на Vector) выделять в гораздо больших блоках.

Если вы настроены на повышение производительности этого конкретного фрагмента кода, вы можете свернуть свой собственный список сторонних ресурсов, предварительно выделив память в больших блоках, а затем разделив еев MyList<T> по мере необходимости.Помните, однако, что последствия этого для управления памятью могут быть серьезными: вам нужно избегать создания блоков, которые задерживаются в памяти гораздо дольше, чем это требуется, вызывая фактическую утечку памяти.

Answer 2

На самом деле не все так много возможностей для улучшения, но я бы избавился от переменной isNil. Вы можете также легко использовать сравнение tail == null. Это сэкономит вам пару заданий в каждой итерации.

Вы не сможете уйти от создания объекта (если вам требуется, чтобы он был односвязным, а не на основе массива), но вы можете уменьшить количество назначений.

Answer 3

Изменение теста ниже для использования ArrayList Я получаю следующее, когда использую большой размер молодого поколения.-XX:NewSize=1g Это помогает, потому что GC - это большие накладные расходы, а большой размер Eden уменьшает количество GC.

ArrayList push&pop 10000000 repeated 10 times took 1183 ms.

Примечание: чтобы ArrayList был эффективным, вы хотите добавить его в конец (и удалитьс конца)

---

Вы можете попробовать TIntArrayList или сделать то же самое

TIntArrayList list = new TIntArrayList();
long start = System.nanoTime();
int values = 10 * 1000 * 1000;
int runs = 10;
for (int r = 0; r < runs; r++) {
    for (int i = 0; i < values; i++) {
        list.add(i);
    }
    for (int i = 0; i < values; i++) {
        int last = list.remove(list.size() - 1); // get the last
    }
}
long time = System.nanoTime() - start;
System.out.println("TIntArrayList push&pop " + values + " repeated "+runs+" times took " + time / 1000000 + " ms.");

print

TIntArrayList push&pop 10000000 repeated 10 times took 577 ms.

Самыми большими издержками, вероятно, будет распределение объектов.Чтобы ускорить это, я предлагаю вам взглянуть на способы минимизировать это.Кстати: вы должны проверить, сколько времени это займет с различными целыми числами.