Это точно не так. Вы забываете, что итерирование ArrayList (как и любой другой коллекции) - это не низкоуровневый проход по массиву данных. Так что неупорядоченные обращения к памяти происходят в любом случае, а вышеприведённая аргументация... ну вы понимаете 

Добавлено через 10 минут и 37 секунд
Вообще, прогнозировать попадания в кэш можно только при отсутствии прерываний, переключения задач и только если вы пишете на ассемблере. 

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

  

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

После собеседования я спросил: "а всё-таки что за вопрос про множественное наследование, и как надо было отвечать?". "Правильный ответ - действительно, в Java нет множественного наследования"

Мне кажется, меня проверяли на ситуацию, в которой я не знаю ответа, и как я буду вести себя в этой ситуации.

Это сообщение отредактировал(а) Platon - 14.6.2008, 08:56

Ну да конечно 

1. Кеш у процессора не "непрерывный", и он прекрасно может справиться с ситуацией когда счетчик расположен в одном блоке памяти, а сами данные в другом.
2. Подгрузка блоков с данным в ArrayList-е имеет большую эффективность и лучшую предсказуемость.
3. Кто знает в какой код JIT скомпилирует foreach итерацию по массиву.

Кэш весьма небольшой, и с задачей кэширования данных некоего процесса (в данном случае - процедура итерирования) на протяжении всего периода выполнения справится очень и очень вряд ли. По крайней мере, прогнозировать это никак нельзя.


Посмотрите на исходник AbstractList.Itr.next() и забудьте о "большей" предсказуемости. А если ещё вспомнить о динамической проверке выхода за границы массива... А в будущем, возможно, и динамической проверке типа массива для параметризованных элементов... А ещё такая "мелочь", как постоянная релокация данных в современных системах вообще и в msvista в частности...


Этот код в любом случае будет очень и очень далёк от строчной операции процессора ;)

Это сообщение отредактировал(а) w1nd - 16.6.2008, 16:28

Ну во первых в тех же Core Duo он 2 и более Мб, для небольшого массива вполне достаточно. Во вторых задачей кеша не является закачать в себя всю оперативку, тут самое главное предсказание переходов. Если бы удалось сделать предсказатель со 100% правильных предсказаний, то хватило бы и 128Кб кеша. В случае массива, даже если предсказание будет неверными, нужный блок будет загружен в память (а это ~8-16К) и еще на несколько тысяч циклов процессора в кэше будут нужные данные. В случае связанного списка, каждый новый переход, это лотерея будет блок в кэше или не будет.




Во первых причем тут AbstractList? Мы тут вроде ArrayList обсуждаем.
Во вторых ничего такого чтобы заставило меня забыть о "большей" предсказуемости я там не увидел. Данные хранятся компактно в 3-х блоках: 1. данные ArrayList, 2. данные ArrayList.Itr 3. даные массива. Первые два попадут в кэш сразу при начале итерации, третьи по мере итерации будут подгружаться.
В третьих как проверка типов связанна с итерацией?
В четвертых такая "мелочь", как постоянная релокация данных тут вообще никаким боком. Эта операция случается редко (по сравнению со временем затраченным на итерацию) и одинаково влияет как на ArrayList так и на LinkedList.

 

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

Оперативный кэш - это кэш первого уровня. Процессов много. Данных очень много. А про предсказание переходов - это вы уже другой кэш приплетаете, кэш данных только для быстрого доступа к данным.


Да, мы обсуждаем ArrayList, метод iterator() которого унаследован от AbstractList. Вы взгляните туда, взгляните.


А я говорил о подобной связи? Мы про кэш говорим, который забивается помимо массива данных ещё очень много чем даже на каждом вызове Itr.next(). А кэш кода, вполне вероятно, может в каждом вызове Itr.next() и вовсе сбрасываться, не говоря уже о переключениях задач и шаманствах jvm... 


Относительно редко, согласен (хотя насчёт "относительно" - почитайте ms technet про vista). Но ручаться за то, что именно посередине итерирования этого не произойдёт пару раз - невозможно.


Это сообщение отредактировал(а) w1nd - 17.6.2008, 17:53

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

я конечно не сильно разбираюсь во внутреннем строении jvm ... но попробую не согласиться:
заполнение, добавление, удаление элементов в масив ArrayList происходит с помощью native функции System.arraycopy (в отличии от LinkedList) ... которая может и следит за тем, что бы где то рядом в кешу размещаться ...

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

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

О, ужас  

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



Я взглянул в ArrayList и нашел там такую штуку




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


Это вполне можно пережить 


А вообще написать тест который бы продемонстрировал это, дело 5 минут.