JavaRush /Java блог /Архив info.javarush /Резкое увеличение времени, при list.add(0, new Object());...
turboblufer
15 уровень

Резкое увеличение времени, при list.add(0, new Object()); для LinkedList

Статья из группы Архив info.javarush
Итак, ситуация такая: я решал задачу, которая возвращает время в милисекундах, требующееся для заполнения коллекции типа LinkedList (в нулевой сегмент). Кстати, да, это на порядок быстрее происходит, чем для ArrayList, но речь идет не об этом.

Я стал исследовать, как меняется время работы программы, например, для 1000 элементов, для 10000 элементов, итд.
public static void main(String[] args) { System.out.println(getTimeMsOfInsert(new LinkedList())); } public static long getTimeMsOfInsert(List list) { long currentTime = new Date().getTime(); insert10000( list ); return new Date().getTime() - currentTime; } public static void insert10000(List list) { for (long i=0;i<10000000;i++) { list.add(0, new Object()); } } И получил такой результат 10^4 элементов работал 2 ms 10^5 элементов работал 15ms 10^6 элементов работал 187ms 10^7 элементов работал 2,327 секунд И теперь, внимание - я ожидал, что для 10^8 элементов алгоритм будет работать примерно 20 секунд... однако на деле: 10^8 элементов работал 202,215 секунд Дополнительная информация: процессор core i7 4810MQ (2,8 GHz) 6 MB кэш памяти 32 GB оперативной памяти Win8 64 Во время выполнения программы с 10^8 элементами я запустил диспетчер задач - процессор пахал на 100%, несколько сотен Мегабайт оперативной памяти заполнялись. Вопросы: 1 - почему при переходе от 10^7 к 10^8 элементам алгоритм увеличивает время работы не на 1, а на 2 порядка? Моя гипотеза такова: закончился кэш процессора и массив пошел в оперативную память. Но неужели в моем распоряжении несколько МБ кэша процессора, при условии, что помимо IDEA ничего не запущено? 2 - есть ли возможность сократить время работы алгоритма до примерно 20 секунд? 3 - сколько примерно будет программа вычислять 10^9 элементов?
Комментарии (15)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
turboblufer Уровень 15
9 августа 2014
Попробовал сделать некоторую оптимизацию.
Для начала удрал все лишние загружаемые библиотеки и прописал строгое название коллекции LinkedList.

Результаты
10^5 16ms
10^6 230ms
10^7 2259ms
10^8 211, 045 секунд

перед следующим (10 в 8й степени) я проверил диспетчер задач

Процессор 2%
Память оперативная 3,4 из 32 ГБ
Я отслеживал во время вычисления 10^ диспетчер задач — перед концом вычислений было 7,7 ГБ оперативки занято. То есть а нужды программы жралось примерно 4,3 ГБ.
Время работы программы было выше, чем в первый прогон, однако я спишу это на плавающую тактовую частоту процессора. Не совсем чистый эксперимент.

Теперь я меняю Object на
list.add(0, 0);


итог
10^6 79ms
10^7 909ms
10^8 117, 901 секунд
Память была заполнена тоже меньше — 5,6 ГБ.

теперь меняем на
byte a =0;
        for (long i=0;i<100000000;i++)
        {
            list.add(0, a);
        }


Итог
память — 5,9 ГБ
Время работы 118, 966 секунд

Если заменить на char, то итог такой
Память 5,9 ГБ
Время 120, 959 сек (учтите, что процессор меняет тактовую частоту)

Если заменить на boolean, то итог такой
Память 5,9
Время 107, 998 сек.

На boolean'е я рискнул — и увеличил n до миллиарда.
blacky Уровень 23
9 августа 2014
2^10 -> 1Кбайт
2^16 -> 64Кбайта
2^20 -> 1Мбайт
2^30 -> 1Гбайт
2^32 -> 4Гбайта
Однако, объекты рассчитываются по-другому см. "Размер Java объектов". Ещё есть тема "Основные принципы настройки Garbage Collection с нуля"
Это либо особенность реализации JVM, либо GC начинает работать — а он тормознутый. Надо спеку смотреть.
Я тоже делал похожий тест, но с заполнением массива
final int SIZE = Integer.MAX_VALUE - 2;
int[] a = new int[SIZE]; 

Когда заполняется 2GB система начинает подлагивать, когда 4GB система почти висит. А чтобы не было OutOfMemoryError нужно параметры при запуске прописать см. "Solve java.lang.OutOfMemoryError: Java heap space" там и про профайлер описано. Ещё "Какие бывают типы OutOfMemoryError или из каких частей состоит память java процесса".
Найдешь ответ — отпишись. Буду признателен.
Sant9Iga Уровень 41
9 августа 2014
ну так забивается все объектами. сам подумай, 10^7 объектов созданных + еще для каждого объекта по 2 ссылки. памяти кушает очень много. а GC не может ничего сделать, потому что на объекты есть ссылка
Long t0 = System.currentTimeMillis();
        int n = 100000000;
        insert10000(new LinkedList());
        Long t1 = System.currentTimeMillis();
        System.out.println("time: " + (t1 - t0) / 1000d + " sec");
        System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024) + " mb");

вот маин. что бы посмотрел сколько памяти скушало