Итак, ситуация такая: я решал задачу, которая возвращает время в милисекундах, требующееся для заполнения коллекции типа 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 элементов?
перед следующим (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 до миллиарда.
Я не знаю, что такое профайлер, я новичок и в JR я только на 13м уровне.
ссылку смотрю сейчас, но сразу обратил внимание на «out of memory» — так у меня же этого нет. памяти хватает.
однако я пробовал увеличить размер коллекции еще на 1 порядок и мониторил диспетчер задач — и где-то после увеличения используемой памяти на 6 ГБ, счетчик используемой оперативной памяти перестал расти (хотя процессор был загружен), видимо в какое-то ограничение уперся и я мануально завершил работу программы
Это мегакруто, что ты задался таким вопросом, но по-моему рановато.
Думаю, стоит оставить пока этот вопрос. Меня этот вопрос тоже волновал, так что если разберешься и отпишешься — плюсану =)
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];
ну так забивается все объектами. сам подумай, 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");
памяти которой система выделила для работы JVM если у тебя. Она выделяется в оперативке. На жесткий диск ты можешь вылезать только потоками запись/считывания. Могу предположить что, в какой то момент начинает работать GC. попробуй переопределить метод finalize() что бы выводил какой то счетчик. и посмотреть удаляет ли GC объекты.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Для начала удрал все лишние загружаемые библиотеки и прописал строгое название коллекции 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 на
итог
10^6 79ms
10^7 909ms
10^8 117, 901 секунд
Память была заполнена тоже меньше — 5,6 ГБ.
теперь меняем на
Итог
память — 5,9 ГБ
Время работы 118, 966 секунд
Если заменить на char, то итог такой
Память 5,9 ГБ
Время 120, 959 сек (учтите, что процессор меняет тактовую частоту)
Если заменить на boolean, то итог такой
Память 5,9
Время 107, 998 сек.
На boolean'е я рискнул — и увеличил n до миллиарда.
ссылку смотрю сейчас, но сразу обратил внимание на «out of memory» — так у меня же этого нет. памяти хватает.
однако я пробовал увеличить размер коллекции еще на 1 порядок и мониторил диспетчер задач — и где-то после увеличения используемой памяти на 6 ГБ, счетчик используемой оперативной памяти перестал расти (хотя процессор был загружен), видимо в какое-то ограничение уперся и я мануально завершил работу программы
Думаю, стоит оставить пока этот вопрос. Меня этот вопрос тоже волновал, так что если разберешься и отпишешься — плюсану =)
А что такое visualvm?
2^16 -> 64Кбайта
2^20 -> 1Мбайт
2^30 -> 1Гбайт
2^32 -> 4Гбайта
Однако, объекты рассчитываются по-другому см. "Размер Java объектов". Ещё есть тема "Основные принципы настройки Garbage Collection с нуля"
Это либо особенность реализации JVM, либо GC начинает работать — а он тормознутый. Надо спеку смотреть.
Я тоже делал похожий тест, но с заполнением массива
Когда заполняется 2GB система начинает подлагивать, когда 4GB система почти висит. А чтобы не было OutOfMemoryError нужно параметры при запуске прописать см. "Solve java.lang.OutOfMemoryError: Java heap space" там и про профайлер описано. Ещё "Какие бывают типы OutOfMemoryError или из каких частей состоит память java процесса".
Найдешь ответ — отпишись. Буду признателен.
вот маин. что бы посмотрел сколько памяти скушало