Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Был тут на одном собеседовании, задали вопрос

Автор: Royan 19.5.2008, 15:38

Вот я снова начал ходить по собеседованиям и ... узнавать новые вещи из сферы высоких технологий. В общем хочу поделиться. Был такой вопрос, - Почему ещё ArrayList, работает быстрее, чем LinkedList? Поясню вопрос, всем известно, что пройти по списку медленнее, чем прочесть элемент по индексу, попытайтесь объяснить где еще кроются тормоза. Поскольку ответ мне показался спорным, я сразу даю направление в котором следует его искать. Нужно разобрать самый низкий уровень, а именно принципы работы CPU. Если ответ совпадающий с тем, который я услышал на собеседовании не будет найден, я его озвучу, а заодно сам, вместе с вами попытаюсь разобраться насколько такие вещи имеют место быть.

Автор: Sartorius 19.5.2008, 16:03

Хоть с джавой и мало работал решу предположить, что элементы ArrayList находятся рядом в памяти, что позволяет эффективно испльзовать кэширование

Автор: Royan 19.5.2008, 16:12

Цитата(Sartorius @  19.5.2008,  13:03 ) Хоть с джавой и мало работал решу предположить, что элементы ArrayList находятся рядом в памяти, что позволяет эффективно испльзовать кэширование   Хотелось бы услышать ответ поподробнее

Автор: Platon 19.5.2008, 16:30

Интересно. может быть что-то из курса ассемблера? типа доступ к элементу массива e[off] а к следующему элементу памяти в LL e[e[off]]

Автор: Sartorius 19.5.2008, 16:51

http://tesis.infotecstt.ru/docs/intel.486/html/ch12.htm

Автор: LSD 19.5.2008, 17:18

Ну во первых неплохо бы указывать, что там было до "еще", чтобы не перебирать все варианты   А по сабжу, если речь идет об простой итерации, то: - меньше обращений к памяти - обращения к памяти идут в одной области памяти (значит эффективно работает кеш процессора)

Автор: COVD 19.5.2008, 17:23

Интересно, это хоть сколько-нибудь существенное знание для java программиста? Разве не достаточно знания первой причины для разработки? Т.е. вширь уже некуда, поэтому давайте вглубь? На мой взгляд задающие такие вопросы занимаются не бизнесом, а искусством ради искусства.

Автор: unkis 19.5.2008, 17:44

Я не уверен но можеть быть так: LinkedList содержит в памяти ссылки на элементы и возможно для ЦП нужно две операции: прочитать адрес и перейти по адресу, а в ArrayList каждый элемент идёт друг за другом и поэтому достаточно одной операции просто перейти на следующий элемент. вообщем как-то так, не знаю понял ли меня кто-то и правильно ли я размышляю, очень хотеться услышать правильный ответ.

Автор: AntonSaburov 19.5.2008, 17:47

Я думаю, что вопрос задавался по принципу: ArrayList основан на массиве и поэтому обращение к элементу [i] будет в один шаг. LinkedList основан на связанном списке, т.е. есть указатель на первый элемент, а остальные прилинкованы. И доступ к элементу [i] будет конечно же медленнее. С другой стороны - добавление в LinkedList не зависит от количества элементов - хоть 200, зоть 100 тыс. Время добавления не меняется. А вот в ArrayList (если массив уже почти заполнен) - там будет создаваться новый массив большего размера. А значит в какой-то ситуации добавление может выйти боком. Дальше думайте, где лучше использовать одну коллекцию, а где - другую. На самом деле достаточно здравый вопрос.

Автор: Platon 19.5.2008, 17:48

unkis, лично я тебя очень хорошо понял: Цитата(Platon @  19.5.2008,  17:30 ) типа доступ к элементу массива e[off] а к следующему элементу памяти в LL e[e[off]] Добавлено через 2 минуты и 44 секунды AntonSaburov, учитывая, что Royan сделал оговорку на ЦПУ, то думаю, тут скорость не в том, чтобы определить массовость операций извлечения / добавления.

Автор: AntonSaburov 19.5.2008, 18:05

Цитата(Platon @  19.5.2008,  17:48 ) AntonSaburov, учитывая, что Royan сделал оговорку на ЦПУ, то думаю, тут скорость не в том, чтобы определить массовость операций извлечения / добавления.  Странный вопрос тогда для собеседования по JAVA - по-моему им просто хотелось показать свою крутость. Достаточно посмотреть исходники этих двух классов - а лезть в CPU уже бессмысленно. Тем более если учесть. что JAVA кросс-платформенная.

Автор: Krivoy 20.5.2008, 12:38

С позиции CPU ArrayList скорей всего реализован как стек - ESP+индекс - вот тебе и значение(это ИМХО - то есть догадка - ни чего более - не вскрывал), LinkedList же можно нагородить с три короба и соответственно операций там не одна......а если учесть что ОС может сегмент данных выгрузить(!) -  то время поиска может существенно увеличится.

Автор: FlasH 20.5.2008, 13:22

Если речь о скорости обхода - она одинаковая. LinkedList при этом нужно обходить с помощью итератора, а ArrayList как массив через get(index).  Я не знаю, как написать корректный тест (списки в 1млн элементов обходятся за 16мс, а минимальный инкремент моего таймера - 15мс), видимо где-то что-то оптимизируется. По скорости добавления элементов в список - ArrayList медленнее известно почему. А по поводу инструкций процессора - они ж разные бывают, большая нагрузка часто на SPARCах и POWERах обрабатывается, а ещё бывают S390 и java-процессоры. Интересно, чем же объяснили разницу в скорости интервьюверы?

Автор: Kangaroo 20.5.2008, 14:23

Вот из-за таких вопросов я и не люблю интервью   Что-то рассказать, конечно, можно, но это не обязательно понравится интервьюверам.

Автор: FlasH 20.5.2008, 15:09

Цитата(Kangaroo @  20.5.2008,  14:23 )  Что-то рассказать, конечно, можно, но это не обязательно понравится интервьюверам.  зато такие интервьюверы ждут шаблонных ответов и особо в суть этих ответов не вникают. Можно ещё встречные вопросы задавать - уточняющие, в конце концов интервьювер сам ответит на свой вопрос, либо согласится с тем, что этот вопрос вы хорошо знаете

Автор: LSD 20.5.2008, 15:31

Цитата(FlasH @  20.5.2008,  14:22 ) Если речь о скорости обхода - она одинаковая. LinkedList при этом нужно обходить с помощью итератора, а ArrayList как массив через get(index).  Я не знаю, как написать корректный тест (списки в 1млн элементов обходятся за 16мс, а минимальный инкремент моего таймера - 15мс), видимо где-то что-то оптимизируется. Нет итерация у ArrayList быстрее: Код     final int size = 1000 * 1000;     long time;     ArrayList<String> arrayList = new ArrayList<String>();     LinkedList<String> linkedList = new LinkedList<String>();     time = System.nanoTime();     for(int i=0; i < size; i++)     {       arrayList.add("ABC");     }     time = System.nanoTime() - time;     System.out.println("ArrayList add time  = " + time);     time = System.nanoTime();     for(int i=0; i < size; i++)     {       linkedList.add("ABC");     }     time = System.nanoTime() - time;     System.out.println("LinkedList add time = " + time);     time = System.nanoTime();     for(int i = 0; i < arrayList.size(); i++)     {       String s = arrayList.get(i);     }     time = System.nanoTime() - time;     System.out.println("ArrayList iterate time  = " + time);     time = System.nanoTime();     for(Iterator<String> it = linkedList.iterator(); it.hasNext();)     {       String s = it.next();     }     time = System.nanoTime() - time;     System.out.println("linkedList iterate time = " + time); Цитата(FlasH @  20.5.2008,  14:22 ) По скорости добавления элементов в список - ArrayList медленнее известно почему. Только если добавлять не в конец списка, если добавлять элементы в конец списка ArrayList быстрее. Даже если ему придется переодически увеличивать размер массива. Если же сразу задать нужный размер, то скорость выше на порядок. LinkedList на добавление любого объекта приходится создавать новый объект в куче, а это весьма не быстрая операция.

Автор: FlasH 26.5.2008, 14:53

Действительно, LinkedList хорош, только если интенсивно изменять не конец списка.  Очень познавательный тест оказался. Кроме того, ArrayList сделает toArray() на порядок быстрее; Результаты на 5 млн. элементов в нс: Код ArrayList add time      = 207997222 LinkedList add time     = 607200983 ArrayList iterate time  = 52000115 LinkedList iterate time = 115023920 ArrayList toArray time  = 33585056 LinkedList toArray time = 153486128

Автор: Platon 26.5.2008, 15:07

Цитата(FlasH @  26.5.2008,  15:53 ) Действительно, LinkedList хорош, только если интенсивно изменять среднюю его часть.  Точно ли только середину? По-моему, хорош когда добавляем данные не в конец списка. К примеру, очередь на ArrayList - сомнительное развлечение. (?)

Автор: w1nd 28.5.2008, 00:03

Цитата(unkis @  19.5.2008,  17:44 ) LinkedList содержит в памяти ссылки на элементы и возможно для ЦП нужно две операции: прочитать адрес и перейти по адресу, а в ArrayList каждый элемент идёт друг за другом и поэтому достаточно одной операции просто перейти на следующий элемент. Цитата(Platon @  19.5.2008,  17:48 ) типа доступ к элементу массива e[off] а к следующему элементу памяти в LL e[e[off]] Строго говоря - ересь. Доступ к элементу массива или списка - это много больше, чем даже десяток инструкций - на уровне процессора не будет прохода в цикле по массиву даже близко. Эффективный адрес элемента массива всякий раз будет вычисляться заново и никаких операций вроде инкремента смещения не будет. С другой стороны - близко к истине, потому что при работе со списком в любом случае производится больше операций с памятью, чем при работе с массивом. Цитата(FlasH @  20.5.2008,  13:22 ) Если речь о скорости обхода - она одинаковая. LinkedList при этом нужно обходить с помощью итератора, а ArrayList как массив через get(index).  Одинаковая ТОЛЬКО в том случае, если для обхода обоих типов списков использовать итератор. Если ArrayList "как массив через get(index)" обходить, то это будет значительно быстрее, чем LinkedList с итератором.

Автор: Stampede 28.5.2008, 00:41

Цитата(w1nd @  27.5.2008,  15:03 ) Строго говоря - ересь. Прямо так уж и ересь? Дело-то на самом деле не в том, сколько инструкций занимает перейти от одного элемента к другому: одну, две или тысячу, а в том, что если в ArrayList адрес n-го элемента пересчитывается впрямую из индекса (на основании достаточно простой арифметики, то в LinkedList у тебя нет для этого  никакой другой возможности кроме как пройтись по этому списку от самой головы. И хорошо если у тебя этих элементов 10, а ведь может быть и миллион. Это, собственно, и имел в виду unkis, просто выразился не совсем четко. Но разве до такой степени, чтобы нельзя было понять, о чем идет речь, и объявлять его слова ересью?

Автор: w1nd 28.5.2008, 00:55

Цитата(Stampede @  28.5.2008,  00:41 ) Дело-то на самом деле не в том, сколько инструкций занимает перейти от одного элемента к другому: одну, две или тысячу, а в том, что если в ArrayList адрес n-го элемента пересчитывается впрямую из индекса (на основании достаточно простой арифметики, то в LinkedList у тебя нет для этого  никакой другой возможности кроме как пройтись по этому списку от самой головы. И хорошо если у тебя этих элементов 10, а ведь может быть и миллион. Дело не в этом. При обходе итератором нет никаких проходов от головы. В случае с массивом для получения следующего элемента мы выбираем memory[offset+(typesize*index)], а в случае со списком - memory[offset], memory[offset].  Цитата(Stampede @  28.5.2008,  00:41 ) Но разве до такой степени, чтобы нельзя было понять, о чем идет речь, и объявлять его слова ересью? Да, ведь unkis пытался привязать разницу именно к результатам компиляции.

Автор: Platon 28.5.2008, 04:58

w1nd, а в чем же тут моя ересь? Цитата(Platon @  19.5.2008,  17:30 ) типа доступ к элементу массива e[off] а к следующему элементу памяти в LL e[e[off]]  Цитата(w1nd @  28.5.2008,  01:55 ) В случае с массивом для получения следующего элемента мы выбираем memory[offset+(typesize*index)], а в случае со списком - memory[offset], memory[offset].  вижу одно и тоже.

Автор: w1nd 28.5.2008, 08:05

Цитата(Platon @  28.5.2008,  04:58 ) вижу одно и тоже. Цитата(w1nd @  28.5.2008,  00:03 ) Доступ к элементу массива или списка - это много больше, чем даже десяток инструкций - на уровне процессора не будет прохода в цикле по массиву даже близко. Эффективный адрес элемента массива всякий раз будет вычисляться заново и никаких операций вроде инкремента смещения не будет.

Автор: fixxer 28.5.2008, 11:18

О чем тут спорить? Доступ к произвольному элементу ArrayList - O(1), с точностью до множителя, до LinkedList - O(n), опять таки с точностью до множителя. Все погрешности и детали уходят в тот самый множитель, нас интересует только порядок роста.

Автор: Royan 12.6.2008, 16:35

Сорри что застрял с ответом. Дел было невпроворот, в общем, на собеседовании ответ был таков. Приведу сразу картинку, чтобы было удобнее смотреть, вот возьмем к примеру схематичное изображение нового 4-х ядерного процессора от AMD  (источник: http://www.hwupgrade.com/articles/print/cpu/10) Как видно у каждого ядра есть по три кеша. Так вот в случае, когда мы идем по ArrayList мы кешируем индексы в каком-то из трех кэшей (сейчас даже не важно в каком именно) соответственно обход ArrayList'а будет выглядеть вот так (я думаю понятно что я утрирую и делаю описываю все очень схематично): get(0) -> CPU -> Обновлям кэши из опертивки и возвращаем значение get(1) -> CPU -> Достаем offset из кэша и возвращаем значение get(n - 1) -> CPU -> Достаем offset из кэша и возвращаем значение  get(n) -> CPU -> Обновлям кэши из опертивки и возвращаем значение и т.д. В случае же LinkedList поскольку все элементы разбросаны, обновление кэшей происходит постоянно.  Под обновлением кеша я имею ввиду передачу какого-либо объема информации через шину, соединяющую кеши.

Автор: Kangaroo 12.6.2008, 17:38

М-да..  Вывод: "Какой же из тебя Java-девелопер, если ты не знаешь новый 4-х ядерного процессор от AMD". Даже не смешно.

Автор: LSD 12.6.2008, 21:15

Цитата(Kangaroo @  12.6.2008,  18:38 ) Вывод: "Какой же из тебя Java-девелопер, если ты не знаешь новый 4-х ядерного процессор от AMD". Даже не смешно.  Не скажи, знать как работает железо и JVM - нужно, иначе как ты будешь оптимизировать код. Я вообще-то не люблю Спольски, но с http://local.joelonsoftware.com/mediawiki/index.php/%D0%9D%D0%B0%D0%B7%D0%B0%D0%B4,_%D0%BA_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B0%D0%BC его статьей полностью согласен. Добавлено через 3 минуты и 57 секунд Да и знать особенности работы нового 4-х ядерного процессор от AMD, совсем не нужно. Достаточно базовых знаний о том как устроен и работает процессор.

Автор: Royan 12.6.2008, 22:04

LSD, Ты знаешь первым делом, когда я услышал этот вопрос, я подумал про эту статью Спольски. Но, во-первых, согласись, статья клево написана и в ней разобран некий классический пример.  Во-вторых,  когда я отвечал на вопрос (а правильный ответ я не дал), я подумал, поскольку я не "в теме", то даже узнав доводы я усомнюсь в их справедливости, ибо внутренняя архитектура и устройство современных процессоров это настолько сложная задача, что спрашивать, а уж тем более отвечать по этой тематике, даже будучи инженером, но без погружения в проблему просто преступно. Всякие там оптимизации, какие-то внутренние особенности и т.д. Честно говоря, мне показалось что интервьюер оперирует знаниями о 8086 покуда во всех инженерных вузах страны этот процессор преподы знают вдоль и поперек, а потому очень любят про него рассказывать на лекциях (собственно поэтому и многие студенты черпают свои знания о процессорах только с таких лекций), хотя эта интеловская бодяга 30 летний давности по сложности и архитектуре также похожа на современное устройство процессора как дачное ведро на японский унитаз. Именно поэтому меня крайне удивило, что меня спрашивают о том, о чем я могу быть и не в курсе. Разумеется под этим вопросом меня хотели "прощупать" на знание кэшей и того как они могут быть использованы... Хотя, опять же, по-моему, такую вещь как кеш я знаю как и когда мне использовать и умею ее реализовать, но понять что от меня хотят в этом случае (сравнивая ArrayList и LinkedList) я не смог.

Автор: serger 13.6.2008, 08:20

По моему - всё это бред. Правильный ответ на принципе аллокации памяти будет... ИМХО кэш - это private в процессоре, и его реализация не должна влиять на программу - тем более java... а если братть процессор с объединённым кешем для ядер?!.. Тот же интел? Да и сколько всяких "процов" существует?!.. А если ещё учитывать тонкости контроллера памяти. И паралельные программы и расположение звёзд и луны...   Они б ещё к электронам привязывались.. Добавлено через 1 минуту и 47 секунд По поводу статьи.. Напоминает спор политиков, когда не просто рассматриваются крайние случаи, а берутся за основу. Однобоко. Но интересно.

Автор: slava 13.6.2008, 10:09

Цитата Именно поэтому меня крайне удивило, что меня спрашивают о том, о чем я могу быть и не в курсе это они специально такие вопросы задают чтобы посмотреть как ты будеш себя вести в такой ситуации. У меня тоже такие вопросы были, что порой сидел и думал это они  серьёзно спрашивают или... главное не паниковать и вести себя уверенно.

Автор: w1nd 13.6.2008, 20:18

Цитата(Royan @  12.6.2008,  16:35 ) В случае же LinkedList поскольку все элементы разбросаны, обновление кэшей происходит постоянно.  Это точно не так. Вы забываете, что итерирование ArrayList (как и любой другой коллекции) - это не низкоуровневый проход по массиву данных. Так что неупорядоченные обращения к памяти происходят в любом случае, а вышеприведённая аргументация... ну вы понимаете  Добавлено через 10 минут и 37 секунд Вообще, прогнозировать попадания в кэш можно только при отсутствии прерываний, переключения задач и только если вы пишете на ассемблере.

Автор: Platon 13.6.2008, 20:59

Так я и знал!!! w1nd прийдет - всех разнесет за такую чушь.

Автор: Kangaroo 14.6.2008, 00:03

Цитата(Platon @  13.6.2008,  20:59 ) Так я и знал!!! w1nd прийдет - всех разнесет за такую чушь.

Автор: Platon 14.6.2008, 08:55

Знаете, был тут я на одном собеседовании, так меня тоже так пытались "на понт взять". Правда вопрос был много крат примитивней, но ситуация, можно сказать, аналогичная. С: В Java5 появилось множественное наследование... Я(удивленно бормоча): тааак, интересно... С: да, есть. Есть 2 класса, определяющих один и тот же метод. 3-й класс наследует оба эти класса, в какой последовательности или какой из методов будет вызван? Я: а что правда есть? С: Да. Отвечайте. Я: Ну, в первую очередь я бы ответил, что множественного наследования в java нет. Но, раз у нас какая-то "интересная" нестандартная java, я бы полез в документацию, посмотреть как реализован этот механизм. С: Хорошо. Поехали дальше... После собеседования я спросил: "а всё-таки что за вопрос про множественное наследование, и как надо было отвечать?". "Правильный ответ - действительно, в Java нет множественного наследования" Мне кажется, меня проверяли на ситуацию, в которой я не знаю ответа, и как я буду вести себя в этой ситуации.

Автор: LSD 16.6.2008, 11:34

Цитата(w1nd @  13.6.2008,  21:18 ) Это точно не так. Вы забываете, что итерирование ArrayList (как и любой другой коллекции) - это не низкоуровневый проход по массиву данных. Так что неупорядоченные обращения к памяти происходят в любом случае, а вышеприведённая аргументация... ну вы понимаете Ну да конечно  1. Кеш у процессора не "непрерывный", и он прекрасно может справиться с ситуацией когда счетчик расположен в одном блоке памяти, а сами данные в другом. 2. Подгрузка блоков с данным в ArrayList-е имеет большую эффективность и лучшую предсказуемость. 3. Кто знает в какой код JIT скомпилирует foreach итерацию по массиву.

Автор: w1nd 16.6.2008, 16:09

Цитата(LSD @  16.6.2008,  11:34 ) Кеш у процессора не "непрерывный", и он прекрасно может справиться с ситуацией когда счетчик расположен в одном блоке памяти, а сами данные в другом. Кэш весьма небольшой, и с задачей кэширования данных некоего процесса (в данном случае - процедура итерирования) на протяжении всего периода выполнения справится очень и очень вряд ли. По крайней мере, прогнозировать это никак нельзя. Цитата(LSD @  16.6.2008,  11:34 ) Подгрузка блоков с данным в ArrayList-е имеет большую эффективность и лучшую предсказуемость. Посмотрите на исходник AbstractList.Itr.next() и забудьте о "большей" предсказуемости. А если ещё вспомнить о динамической проверке выхода за границы массива... А в будущем, возможно, и динамической проверке типа массива для параметризованных элементов... А ещё такая "мелочь", как постоянная релокация данных в современных системах вообще и в msvista в частности... Цитата(LSD @  16.6.2008,  11:34 ) Кто знает в какой код JIT скомпилирует foreach итерацию по массиву. Этот код в любом случае будет очень и очень далёк от строчной операции процессора ;)

Автор: LSD 17.6.2008, 16:07

Цитата(w1nd @  16.6.2008,  17:09 ) Кэш весьма небольшой, и с задачей кэширования данных некоего процесса (в данном случае - процедура итерирования) на протяжении всего периода выполнения справится очень и очень вряд ли. По крайней мере, прогнозировать это никак нельзя. Ну во первых в тех же Core Duo он 2 и более Мб, для небольшого массива вполне достаточно. Во вторых задачей кеша не является закачать в себя всю оперативку, тут самое главное предсказание переходов. Если бы удалось сделать предсказатель со 100% правильных предсказаний, то хватило бы и 128Кб кеша. В случае массива, даже если предсказание будет неверными, нужный блок будет загружен в память (а это ~8-16К) и еще на несколько тысяч циклов процессора в кэше будут нужные данные. В случае связанного списка, каждый новый переход, это лотерея будет блок в кэше или не будет. Цитата(w1nd @  16.6.2008,  17:09 ) Посмотрите на исходник AbstractList.Itr.next() и забудьте о "большей" предсказуемости. А если ещё вспомнить о динамической проверке выхода за границы массива... А в будущем, возможно, и динамической проверке типа массива для параметризованных элементов... А ещё такая "мелочь", как постоянная релокация данных в современных системах вообще и в msvista в частности... Во первых причем тут AbstractList? Мы тут вроде ArrayList обсуждаем. Во вторых ничего такого чтобы заставило меня забыть о "большей" предсказуемости я там не увидел. Данные хранятся компактно в 3-х блоках: 1. данные ArrayList, 2. данные ArrayList.Itr 3. даные массива. Первые два попадут в кэш сразу при начале итерации, третьи по мере итерации будут подгружаться. В третьих как проверка типов связанна с итерацией? В четвертых такая "мелочь", как постоянная релокация данных тут вообще никаким боком. Эта операция случается редко (по сравнению со временем затраченным на итерацию) и одинаково влияет как на ArrayList так и на LinkedList.

Автор: Kangaroo 17.6.2008, 16:14

LSD vs w1nd - это всегда интересно

Автор: w1nd 17.6.2008, 17:22

Цитата(LSD @  17.6.2008,  16:07 ) Ну во первых в тех же Core Duo он 2 и более Мб, для небольшого массива вполне достаточно. Во вторых задачей кеша не является закачать в себя всю оперативку, тут самое главное предсказание переходов. Оперативный кэш - это кэш первого уровня. Процессов много. Данных очень много. А про предсказание переходов - это вы уже другой кэш приплетаете, кэш данных только для быстрого доступа к данным. Цитата(LSD @  17.6.2008,  16:07 ) Во первых причем тут AbstractList? Мы тут вроде ArrayList обсуждаем. Да, мы обсуждаем ArrayList, метод iterator() которого унаследован от AbstractList. Вы взгляните туда, взгляните. Цитата(LSD @  17.6.2008,  16:07 ) Во вторых ничего такого чтобы заставило меня забыть о "большей" предсказуемости я там не увидел. Данные хранятся компактно в 3-х блоках: 1. данные ArrayList, 2. данные ArrayList.Itr 3. даные массива. Первые два попадут в кэш сразу при начале итерации, третьи по мере итерации будут подгружаться. В третьих как проверка типов связанна с итерацией? А я говорил о подобной связи? Мы про кэш говорим, который забивается помимо массива данных ещё очень много чем даже на каждом вызове Itr.next(). А кэш кода, вполне вероятно, может в каждом вызове Itr.next() и вовсе сбрасываться, не говоря уже о переключениях задач и шаманствах jvm...  Цитата(LSD @  17.6.2008,  16:07 ) В четвертых такая "мелочь", как постоянная релокация данных тут вообще никаким боком. Эта операция случается редко (по сравнению со временем затраченным на итерацию) и одинаково влияет как на ArrayList так и на LinkedList. Относительно редко, согласен (хотя насчёт "относительно" - почитайте ms technet про vista). Но ручаться за то, что именно посередине итерирования этого не произойдёт пару раз - невозможно.

Автор: COVD 17.6.2008, 19:55

Цитата Мне кажется, меня проверяли на ситуацию, в которой я не знаю ответа, и как я буду вести себя в этой ситуации. Наверное, в космос планировали послать   . А вообще, маляры должны уметь красить, а разбираться в живописи - дело личное.

Автор: v2v 17.6.2008, 22:56

Цитата(w1nd @  13.6.2008,  20:18 ) Это точно не так. Вы забываете, что итерирование ArrayList (как и любой другой коллекции) - это не низкоуровневый проход по массиву данных. Так что неупорядоченные обращения к памяти происходят в любом случае, а вышеприведённая аргументация... ну вы понимаете smile Добавлено через 10 минут и 37 секунд Вообще, прогнозировать попадания в кэш можно только при отсутствии прерываний, переключения задач и только если вы пишете на ассемблере.   я конечно не сильно разбираюсь во внутреннем строении jvm ... но попробую не согласиться: заполнение, добавление, удаление элементов в масив ArrayList происходит с помощью native функции System.arraycopy (в отличии от LinkedList) ... которая может и следит за тем, что бы где то рядом в кешу размещаться ...

Автор: w1nd 18.6.2008, 00:25

Цитата(v2v @  17.6.2008,  22:56 ) заполнение, добавление, удаление элементов в масив ArrayList происходит с помощью native функции System.arraycopy (в отличии от LinkedList) С помощью System.arraycopy() только копируется информация из старого массива в новый, только при расширении ArrayList. И мне не интересно, как быстро оно добавляется/удаляется, я говорил про итерирование.

Автор: v2v 18.6.2008, 09:38

Цитата(w1nd @  18.6.2008,  00:25 ) С помощью System.arraycopy() только копируется информация из старого массива в новый, только при расширении ArrayList. И мне не интересно, как быстро оно добавляется/удаляется, я говорил про итерирование. я не про то что оно быстро или нет добавляется, а про то, что оно выполняется на достаточно низком уровне, что бы попасть в кеш.

Автор: w1nd 18.6.2008, 11:12

Цитата(v2v @  18.6.2008,  09:38 ) я не про то что оно быстро или нет добавляется, а про то, что оно выполняется на достаточно низком уровне, что бы попасть в кеш. О, ужас

Автор: LSD 18.6.2008, 14:00

Цитата(w1nd @  17.6.2008,  18:22 ) Оперативный кэш - это кэш первого уровня. Процессов много. Данных очень много. А про предсказание переходов - это вы уже другой кэш приплетаете, кэш данных только для быстрого доступа к данным. Данные из кеша второго уровня, перемещаются в первого уровня достаточно быстро. Так что наличие их только в кеше второго уровня, это уже хорошо. Кеш второго уровня не делится на данные и код. Цитата(w1nd @  17.6.2008,  18:22 ) Да, мы обсуждаем ArrayList, метод iterator() которого унаследован от AbstractList. Вы взгляните туда, взгляните. Я взглянул в ArrayList и нашел там такую штуку Код     private class Itr implements Iterator<E> {         int cursor;       // index of next element to return         int lastRet = -1; // index of last element returned; -1 if no such         int expectedModCount = modCount;         public boolean hasNext() {             return cursor != size;         }         @SuppressWarnings("unchecked")         public E next() {             checkForComodification();             int i = cursor;             if (i >= size)                 throw new NoSuchElementException();             Object[] elementData = ArrayList.this.elementData;             if (i >= elementData.length)                 throw new ConcurrentModificationException();             cursor = i + 1;             return (E) elementData[lastRet = i];         }         public void remove() {             if (lastRet < 0)                 throw new IllegalStateException();             checkForComodification();             try {                 ArrayList.this.remove(lastRet);                 cursor = lastRet;                 lastRet = -1;                 expectedModCount = modCount;             } catch (IndexOutOfBoundsException ex) {                 throw new ConcurrentModificationException();             }         }         final void checkForComodification() {             if (modCount != expectedModCount)                 throw new ConcurrentModificationException();         }     } Цитата(w1nd @  17.6.2008,  18:22 ) Мы про кэш говорим, который забивается помимо массива данных ещё очень много чем даже на каждом вызове Itr.next(). А кэш кода, вполне вероятно, может в каждом вызове Itr.next() и вовсе сбрасываться, не говоря уже о переключениях задач и шаманствах jvm...  Кто же спорит, что забивается, для этого его и увеличивают всеми силами. Изначальный вопрос был почему еще ArrayList быстрее LinkedList, и в ситуации когда данные могут удаляться из кеша, ситуация с ArrayList гораздо лучше. Цитата(w1nd @  17.6.2008,  18:22 ) Относительно редко, согласен (хотя насчёт "относительно" - почитайте ms technet про vista). Но ручаться за то, что именно посередине итерирования этого не произойдёт пару раз - невозможно. Это вполне можно пережить  А вообще написать тест который бы продемонстрировал это, дело 5 минут.

Автор: w1nd 18.6.2008, 14:24

Цитата(LSD @  18.6.2008,  14:00 ) А вообще написать тест который бы продемонстрировал это, дело 5 минут. Написать тест для воспроизведения абсолютно неконтролируемого со стороны явления?

Автор: LSD 18.6.2008, 17:04

Цитата(w1nd @  18.6.2008,  15:24 ) Написать тест для воспроизведения абсолютно неконтролируемого со стороны явления? Какие дикие фантазии   Тест который продемонстрирует, что итерация по массиву по порядку идет быстрей, чем итерация в случайном порядке (уж порядок итерации мы контролировать то можем, я надеюсь  ).

Автор: w1nd 18.6.2008, 21:49

Цитата(LSD @  18.6.2008,  17:04 ) Какие дикие фантазии   Ваши - протестировать влияние работы менеджера памяти ОС на скорость итерирования списка ;) Цитата(LSD @  18.6.2008,  17:04 ) Тест который продемонстрирует, что итерация по массиву по порядку идет быстрей, чем итерация в случайном порядке <...> Ну вот вам черновик: Код import java.util.Random; public class ListSpeedTest {     public static void main(String[] args) {         int count = 100000000, array[] = new int[count], indexes[] = new int[count];         Random random = new Random();                  for (int i = 0; i < count; i++) {             array[i] = random.nextInt(count);         }                  if (false) { // тут переключаем             for (int i = 0; i < count; i++) {                 indexes[i] = random.nextInt(count);             }         }         else {             for (int i = 0; i < count; i++) {                 indexes[i] = i;             }         }                  long time = System.currentTimeMillis();                  for (int i = 0, j; i < count; i++) {             j = array[indexes[i]];         }                  System.out.printf(             "Elapsed time: %d ms\n", System.currentTimeMillis() - time         );     }      } Что я упустил?

Автор: LSD 19.6.2008, 12:46

Цитата(w1nd @  18.6.2008,  22:49 ) Ваши - протестировать влияние работы менеджера памяти ОС на скорость итерирования списка ;) Я такого не писал, а если кто-то там такое узрел, это его личное воображение подсобило  Цитата(w1nd @  18.6.2008,  22:49 ) Что я упустил?  Зачем вообще нужно 2 массива? Тут уже одновременно идут 2 итерации, 2 последовательных или 1 последовательная и 1 непоследовательная. Код import java.util.Random; public class Test {   public static final int SIZE = 16 * 1024 * 1024;   public static final int[] DATA = new int[SIZE];   public static final Random rnd = new Random();   public static void main(String[] args)   {     iterSeq();     iterRnd();     long seqTime = System.currentTimeMillis();     iterSeq();     seqTime = System.currentTimeMillis() - seqTime;     long rndTime = System.currentTimeMillis();     iterRnd();     rndTime = System.currentTimeMillis() - rndTime;     System.out.println("Sequential time: " + seqTime + " ms");     System.out.println("Random time:     " + rndTime + " ms");   }   private static void fill()   {     for(int i = 0; i < SIZE; i++)       DATA[i] = rnd.nextInt();   }   private static long iterSeq()   {     long result = 0L;     for(int i = 0; i < SIZE; i++)     {       rnd.nextInt(SIZE);       result += DATA[i];     }     return result;   }   private static long iterRnd()   {     long result = 0L;     for(int i = 0; i < SIZE; i++)     {       result += DATA[rnd.nextInt(SIZE)];     }     return result;   } } у меня получилась разница во времени 4 раза.

Автор: w1nd 19.6.2008, 15:05

Цитата(LSD @  19.6.2008,  12:46 ) Я такого не писал, а если кто-то там такое узрел, это его личное воображение подсобило  Вы предложили написать тест в ответ на реплику про релокацию памяти.  Цитата(LSD @  19.6.2008,  12:46 ) Тут уже одновременно идут 2 итерации, 2 последовательных или 1 последовательная и 1 непоследовательная. По вашей логике в моём тесте в вариант с последовательным итерированием должен работать всегда быстрее. Цитата(LSD @  19.6.2008,  12:46 ) у меня получилась разница во времени 4 раза. На моей рабочей машинке разница составляет 2 (P4); на домашней (CORE2; 64-битная jvm) разницы нет вообще. Имеете ещё что-то рассказать про кэш процессора?

Автор: Metal_Heart 19.6.2008, 15:44

Ну, чтож интересно, потестим, итак: Код public static final int SIZE = 1 * 1024 *1024; Цитата Sequential time: 172 ms Random time:     297 ms Машинка: Intel P4 - 2.8ГГц  RAM 1Гб

Автор: Platon 19.6.2008, 16:30

Celeron 2GHz RAM 1Gb Цитата Sequential time: 859 ms Random time:     2797 ms Вот ничего себе! интересный факт. Добавлено через 38 секунд размер 8 мегабайт

Автор: LSD 19.6.2008, 17:56

Цитата(w1nd @  19.6.2008,  16:05 ) Вы предложили написать тест в ответ на реплику про релокацию памяти. Эта фраза была сказана к дискуссии о кэше вообще, она даже специально отделена. Ну а кто как воспринял...  Цитата(w1nd @  19.6.2008,  16:05 ) По вашей логике в моём тесте в вариант с последовательным итерированием должен работать всегда быстрее. Так у меня и быстрее: 63 миллисекунды против 1406 (я уменьшил размер до 20 000 000). Я неправильно тест запускаю?  Цитата(w1nd @  19.6.2008,  16:05 ) На моей рабочей машинке разница составляет 2 (P4); на домашней (CORE2; 64-битная jvm) разницы нет вообще. Имеете ещё что-то рассказать про кэш процессора? Пора проводить исследование на тему: "Влияние скепсиса на CPU, на примере Sun JRE"

Автор: LSD 19.6.2008, 18:52

Погонял тест на Celeron M 900 MHz (до этого был P4 3.0 GHz) получил: Мой тест: Цитата Sequential time: 2593 ms Random time:     7485 ms Тест w1nd Цитата Elapsed time: 234 ms Elapsed time: 2781 ms

Автор: w1nd 19.6.2008, 23:35

Цитата(LSD @  19.6.2008,  17:56 ) Так у меня и быстрее: 63 миллисекунды против 1406 (я уменьшил размер до 20 000 000). Я неправильно тест запускаю? Как пить дать   Цитата(LSD @  19.6.2008,  17:56 ) Пора проводить исследование на тему: "Влияние скепсиса на CPU, на примере Sun JRE" Пора уже понять, что прогнозировать такие вещи, как поведение кэша, бессмысленно и бесполезно. Кстати, на 32-битной JRE на домашнем CORE2 в моём тесте (где не меряется заодно скорость JIT и вероятность перекомпиляции "горячего" метода) результаты аналогичны полученным на 64-битной (98 +- 10 ms).

Автор: LSD 20.6.2008, 09:46

Цитата(w1nd @  20.6.2008,  00:35 ) Пора уже понять, что прогнозировать такие вещи, как поведение кэша, бессмысленно и бесполезно. Думаю стоит эту мысль донести до http://www.intel.com/cd/software/products/asmo-na/eng/compilers/284132.htm ребят, а то они мучаются, что-то пытаются прогнозировать и оптимизировать, по ночам поди не спят

Автор: w1nd 20.6.2008, 10:45

Цитата(LSD @ 20.6.2008,  09:46) Думаю стоит эту мысль донести до http://www.intel.com/cd/software/products/asmo-na/eng/compilers/284132.htm ребят, а то они мучаются, что-то пытаются прогнозировать и оптимизировать, по ночам поди не спят  А у нас в квартире газ. Содержательный разговор, не правда ли? Ваша ссылка вообще к чему?

Автор: serger 20.6.2008, 14:26

Pentium 4 3ГГц Sequential time: 1453 ms Random time:     4047 ms отношение 2.78 Sequential time: 1469 ms Random time:     4219 ms отношение 2.87 Sequential time: 1469 ms Random time:     4469 ms отношение 3.04 среднее отношение 2.9 Паралельно закрывал/открывал netbeans Sequential time: 2468 ms Random time:     6125 ms отношение 2.48 Sequential time: 2438 ms Random time:     6078 ms отношение 2.49 среднее отношение 2.49 =============== Elapsed time: 343 ms Elapsed time: 344 ms Elapsed time: 343 ms Среднее: 343 ms Паралельно закрывал/открывал netbeans Elapsed time: 656 ms Elapsed time: 656 ms Elapsed time: 750 ms Elapsed time: 719 ms Среднее: 695 ms отношение 2.02 Random^ Elapsed time: 11000 ms Elapsed time: 11015 ms Elapsed time: 11016 ms Среднее: 11015 ms (Пусть!) Паралельно закрывал/открывал netbeans Elapsed time: 12672 ms Elapsed time: 11110 ms Elapsed time: 13375 ms Elapsed time: 12641 ms Среднее: 12450 ms отношение 1.13

Автор: LSD 20.6.2008, 15:25

Цитата(w1nd @  20.6.2008,  11:45 ) Ваша ссылка вообще к чему?  К тому, что эти ребята пишут компилятор который оптимизирует код с учетом поведения процессора (в том числе и кэша). И при этом они не считают свою работу бессмысленной и бесполезной. Вот я и посоветовал пойти и просветить их Цитата(w1nd @  20.6.2008,  00:35 ) что прогнозировать такие вещи, как поведение кэша, бессмысленно и бесполезно.

Автор: w1nd 20.6.2008, 16:10

Цитата(LSD @  20.6.2008,  15:25 ) К тому, что эти ребята пишут компилятор который оптимизирует код с учетом поведения процессора (в том числе и кэша). И при этом они не считают свою работу бессмысленной и бесполезной. Не путайте <непроизносимое> с пальцем. Я где-нибудь говорил, что этот совет предназначен разработчикам КОМПИЛЯТОРОВ? Нет, не говорил. А что вы тут пытаетесь доказать? Эти ребята (а также многие другие) сами скажут, что прогнозировать работу кэшей и блоков предсказания ветвлений не нужно и не полезно. Потому что это делает КОМПИЛЯТОР, если умеет. А всевозможные заточки непосредственно в коде в своё время очень плохо послужили пользователям процессоров P4, когда те вышли, ибо часть софта работала медленее не просто по причине отсутствия оптимизации под P4, а ещё и по причине оптимизации под P3.

Автор: Krivoy 22.6.2008, 14:20

Цитата(w1nd @ 13.6.2008,  20:18) Вообще, прогнозировать попадания в кэш можно только при отсутствии прерываний, переключения задач и только если вы пишете на ассемблере. Конгруэнтно w1nd! Граждане! http://education.aspu.ru/view.php?olif=index хотябы Вам в руки, а потом Olly или лучше SoftIce и только тогда проверять количество операций. А уж смотреть что в кешах проца    да еще и на разных платформах всё равно что прогнозировать направление ветра на пастбищах в Новой зелландии    Хотя может правда - оно Вам как девелоперам и не к чему... Вот еще пару десятков постов с несогласными и я точно не устою и упаду на реверс....

Автор: Greg 22.6.2008, 15:18

Такого типа вопросы на собеседовании обсуждаются лишь с целью удовлетворения самомнения интервьюера. К сожалению существует очень много подобных людей ...

Автор: LSD 23.6.2008, 12:28

Цитата(w1nd @  20.6.2008,  17:10 ) Не путайте <непроизносимое> с пальцем. Я где-нибудь говорил, что этот совет предназначен разработчикам КОМПИЛЯТОРОВ? Нет, не говорил. А что вы тут пытаетесь доказать? Сколько патетики  Два вопроса: 1. Есть какие нибудь сомнения в результатах тестов? 2. Если в тестах сомнений нет, то как объяснить результаты? Цитата(w1nd @  20.6.2008,  17:10 ) Эти ребята (а также многие другие) сами скажут, что прогнозировать работу кэшей и блоков предсказания ветвлений не нужно и не полезно. Потому что это делает КОМПИЛЯТОР, если умеет. А кто утверждал что это нужно делать?

Автор: w1nd 23.6.2008, 13:14

Цитата(LSD @  23.6.2008,  12:28 ) Есть какие нибудь сомнения в результатах тестов? 1. Сомнения есть, но не в результате, а в чистоте. Правда, не приходит в голову ничего путного взамен из-за ограничения на размер .class-файлов. 2. А что требуется объяснять? Результаты явно показывают, что нет ни одной причины расчитывать на кэш, о чём я уже не раз говорил. Цитата(LSD @  23.6.2008,  12:28 ) А кто утверждал что это нужно делать? Странный вопрос. Вы пытались утверждать: http://forum.vingrad.ru/index.php?showtopic=212079&view=findpost&p=1556030.

Автор: LSD 23.6.2008, 14:31

Цитата(w1nd @  23.6.2008,  14:14 ) Сомнения есть, но не в результате, а в чистоте. Правда, не приходит в голову ничего путного взамен из-за ограничения на размер .class-файлов. А поподробней, чем этот эксперимент плох? И что за эксперимент которому мешает ограничение на размер class файлов. Цитата(w1nd @  23.6.2008,  14:14 ) А что требуется объяснять? Требуется объяснить почему последовательная итерация по массиву идет быстрей чем итерация в случайном порядке. Цитата(w1nd @  23.6.2008,  14:14 ) Странный вопрос. Вы пытались утверждать: ссылка. Раз уж такие проблемы с взаимопониманием попробую пояснить: оптимизировать код с учетом архитектуры процессора - можно (изначальный вопрос был скорее о теоретической возможности этого).  Когда это нужно делать вопрос отдельный. Разработчикам компиляторов и виртуальных машин это стоит делать. Прикладникам - не стоит. Хотя утверждать что нет и не может быть ситуации когда прикладникам не придется оптимизировать код под конкретный процессор, я не буду.

Автор: w1nd 23.6.2008, 14:41

Цитата(LSD @  23.6.2008,  14:31 ) А поподробней, чем этот эксперимент плох? И что за эксперимент которому мешает ограничение на размер class файлов. Много лишнего - Random или массивы индексов. Было бы неплохо сделать исходник, куда все необходимые индексы были бы забиты, но, боюсь, не влезет в .class. Цитата(LSD @  23.6.2008,  14:31 ) Требуется объяснить почему последовательная итерация по массиву идет быстрей чем итерация в случайном порядке. Не идёт быстрей, а может быть быстрее при определённых обстоятельствах. В этом весь перец. Цитата(LSD @  23.6.2008,  14:31 ) Разработчикам компиляторов и виртуальных машин это стоит делать. Эх. Ваши бы слова в уши разработчиков hotspot, которые пренебрегают некоторыми элементарными оптимизациями.

Автор: LSD 23.6.2008, 15:27

Цитата(w1nd @  23.6.2008,  15:41 ) Не идёт быстрей, а может быть быстрее при определённых обстоятельствах. Я про данный конкретный случай. Почему одна итерация быстрее другой. Цитата(w1nd @  23.6.2008,  15:41 ) Много лишнего - Random или массивы индексов. Было бы неплохо сделать исходник, куда все необходимые индексы были бы забиты, но, боюсь, не влезет в .class. Не понимаю, чем они так сильно влияют на результат? Речь же идет не о 5-10% а 2-х кратной разнице.

Автор: cube 24.6.2008, 12:11

второй тайм!    И вот мы снова вместе! Это прямая трансляция с форума Винграда                                                               сегодня 24-е июня 2008 года        мы находимся в разделе "Java: Общие вопросы"....                                     погода отличная                              настроение у участников бодрое                        продолжаем следить за событиями!                                   Кто же прав в этой ситауции??                 А кто сомневался в своих суждениях?                              Кто НЕ КОМПИТЕНТЕН?!                                                          Настало время узнать это!...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)