JavaRush/Блог/Архив 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, 11:34
Попробовал сделать некоторую оптимизацию.
Для начала удрал все лишние загружаемые библиотеки и прописал строгое название коллекции 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, 11:47
Извини, но это не назвать оптимизацией. Воспользуйся профайлером, например, VisualVM. Ты думаешь, я тебе ссылки кидал наобум что ли?
turboblufer
Уровень 15
9 августа 2014, 13:16
Я не знаю, что такое профайлер, я новичок и в JR я только на 13м уровне.
ссылку смотрю сейчас, но сразу обратил внимание на «out of memory» — так у меня же этого нет. памяти хватает.

однако я пробовал увеличить размер коллекции еще на 1 порядок и мониторил диспетчер задач — и где-то после увеличения используемой памяти на 6 ГБ, счетчик используемой оперативной памяти перестал расти (хотя процессор был загружен), видимо в какое-то ограничение уперся и я мануально завершил работу программы
blacky
Уровень 23
9 августа 2014, 13:43
Это мегакруто, что ты задался таким вопросом, но по-моему рановато.
Думаю, стоит оставить пока этот вопрос. Меня этот вопрос тоже волновал, так что если разберешься и отпишешься — плюсану =)
turboblufer
Уровень 15
9 августа 2014, 14:05
Рановато — наверное ты прав. А когда будет не рано?

А что такое visualvm?
blacky
Уровень 23
9 августа 2014, 14:20
Не рано, кому дáно, а не дáно, и век рано
blacky
Уровень 23
9 августа 2014, 01:04
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 процесса".
Найдешь ответ — отпишись. Буду признателен.
turboblufer
Уровень 15
9 августа 2014, 02:16
У меня проблема не в out of memory, проблема в резком падении производительности. И при определенном n
blacky
Уровень 23
18 августа 2014, 20:10
Расчёт памяти
// Integer.MAX_VALUE = 2147483647
int[] m = new int[Integer.MAX_VALUE - 2];
// массив будет содержать 2 147 483 647 элемента по 4 байта
// расчет памяти:
// (2 147 483 647 * 32) / (8 бит * 1024 бит * 1024 бит) = 
// (68 719 476 704 / 8 388 608) = 8 191.99999619 MiB
Sant9Iga
Уровень 41
9 августа 2014, 00:15
ну так забивается все объектами. сам подумай, 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");

вот маин. что бы посмотрел сколько памяти скушало
Sant9Iga
Уровень 41
9 августа 2014, 00:32
у меня например упал по OutOfMemoryError: Java heap space) это на 10^8)
turboblufer
Уровень 15
9 августа 2014, 02:13
Какой памяти? Повторяю, у меня 32ГБ оперативки и просмотр диспетчера задач показало, что лишь несколько сотен забилось.
turboblufer
Уровень 15
9 августа 2014, 02:14
Это означает конец оперативки? На винт не переходило?
Sant9Iga
Уровень 41
13 августа 2014, 13:20
памяти которой система выделила для работы JVM если у тебя. Она выделяется в оперативке. На жесткий диск ты можешь вылезать только потоками запись/считывания. Могу предположить что, в какой то момент начинает работать GC. попробуй переопределить метод finalize() что бы выводил какой то счетчик. и посмотреть удаляет ли GC объекты.
Sant9Iga
Уровень 41
13 августа 2014, 13:24
блин туплю. GC не будет собирать ничего, потому что на все объекты есть ссылки