Ну можете почитать код ojalgo

Нет, это обычная тема. Когда порция данных растёт, и переваливает сначала за кеш1, потом за кеш2.

Вообще картинка очень хорошая

Обычно либы автоматом это внутри оптимизируют

гуглится по "кривая шипилева" )))

Вот только в моей области графа производительности на этом графике логарифмическая

Да и в твоей, думаю, тоже

От константных факторов и не более чем O(log n) замедления — никак.

Конкретно по спискам. Бегать по уже материализованному в памяти списку занятие, действительно так себе. Но! Список это часто не data structure, а control structure. Т.е. программа сожрала голову списка, а следующий элемент списка — это задумка которую ещё надо вычислить. GHC вполне способен скомпилировать создание/деконструкцию списка в цикл. Когда я разбил рекурсивную функцию на поток итераций в виде списка и потребитель спика я поличл ~10% просадки производительности

А для того чтобы не строить промежуточные структуры - build/foldr fusion

Пошли семинар делать лучше

А вообще зачем юзать линкед лист? Эррейлист топ. Он внутри использует массив, по которому ходить оч быстро. Наверное именно поэтому и List и MutableList в котлине это на самом деле ArrayList. Сейчас даже проверил

val list = List(10) { 0 }
println(list::class.java)

>> class java.util.ArrayList

Что значит ходить быстро? Это массив ссылок, перейти к обьекту = разименовать ссылку. Итерироваться ли линкед листу можно примерно так же, кроме случая, если вы по индексу прыгаете в середину.

val list = List(10) { 0 }
println(list::class.java)

Чтоб вопросы были на собесах

Линкед лист нужен в некоторых алгоритмах. Он при добавлении элемента в конец никогда не копирует весь массив, например. в 99% случаев он не нужен.

Попробуй побенчмаркать проходы по линкедлисту и эррейлисту, причём внутри должны быть не примитивы. Последний справится быстрее, причём значительно.

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

Я как-то давно игрался с этим, юзал jmh

Смотрел почему?
Типа дополнительный проход по ссылке - сначала на ноду, а потом на некст, вместо ссылки на некст сразу из массива?

Я тогда ток въезжал в джаву и котлин, смотрел курс по java core, чувак сказал что linked list в 99% случаев сливает эррейлисту по перфомансу, и объяснил это как-то, я потыкал эту тему в jmh и пошёл дальше. С тех пор я не возвращался к этой теме, поэтому точную причину не скажу. Но по логике - да, по идее ты прав.

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

val list = List(10) { 0 }
println(list::class.java)

Там выше был разговор про persistent коллекции, и массив тут не подходит. А если нужен просто список, то конечно arraylist