Скорее будет не векторное, а типа CDR-кодирование, к которому в Лисп-машинах пришли в итоге.
Это разные вещи. Под CDR-кодирование хорошо подойдет односвязная память с кольцевыми цепочками, что у нас с Колей Мансуровым была.
А вообще - процессор другой нужен, который бы был толерантен к таким задержкам. Ну, это "любимая песня" про мультитредовость и распараллеливание.
Лучше бы этим занялись, чем чудачеством с цепочкой "abc", так ведь все равно цепочки не сопоставляют. Это классическая задача, там даже динамическое программирование используется, да и объемы совсем другие. Я удивляюсь уже какой день.
Л.Эйсымонт
01.03.2019, 18:57, "Andrei Klimov andrei_AT_klimov.net" <refal@botik.ru>:
On Fri, Mar 1, 2019 at 5:17 PM Sergei M. Abramov abram_AT_botik.ru <refal@botik.ru> wrote:День добрый, всем!
> ... По мере тасования памяти скорость падает до 2 раз.
Тема диссертации Светланы Подколзиной (Трубицыной): реализация Лиспа с
массивным представлением по направлению CDR.
CAR -- ссылка, CDR -- соседняя ячейка (близось адресов).
Тракторная сборка мусора, которая как бульдозер сдвигала все нужное,
собирая свободные ячейки в крупные массивы.
С чем боролись? Кэша тогда не было, а вот виртуальная память была. И
по мере "тасования памяти" шаг в с;едующую ячейку списка с большой
вероятностью приводил к пэйдж-фолту.
Вот с этим и боролись.И сейчас есть с чем и за что бороться:
- произвольный доступ в оперативную память – в кеш: один, другой... всё дольше и дольше, а в конце в большую память – 50-100 тактов
- а доступ подряд идет с предвыборкой в кеш на максимальной скорости памяти
Списковая память была еще терпима в 70-е годы, когда, например, на БЭСМ-6 доступ в память (2 мкс) был того же порядка, что и одна логическая операция (0.5 мкс) и совпадал с временем плавающей арифметики. Да и тогда на БЭСМ-6 доступ подряд шел по разным кубам памяти и был быстрее. А сейчас разница между произвольным доступом и доступом по подряд идущим адресам на 1-2 десятичных порядка – вопиюща. То есть пришло время векторных представлений в т.ч. и символьной информации. Хотя кеши тоже стали большими и рабочие множества в задачах обработки символьной информации стали больше в них помещаться, но по идее векторное представление должно обгонять.Очень было бы интересно провести сравнительные измерения такой же тщательности, как команда Леонида Эйсымонта делала в 80-е годы. Нужно брать задачи/тесты, которые можно промасштабировать от помещающихся в кеш до превышающих во много раз и посмотреть на графиках как списковая память проваливается. Обсуждающийся пример хорош. Но хотелось бы еще иметь прототипы реальных задач, например, обходы больших графов графов (коммивояжер и др.), компьютерная алгебра (базис Гребнера, феймановские диаграммы) и т.п.Я ставлю на то, что векторное представление заметно обгонит, когда объемы данных превысят кеш во много раз.(Не говоря уж об экономии памяти на ссылки.)АндрейТак что, грусть по массивному представлению имеет давнюю историю.
А тот поход за массивным лиспом помню с удовольствием...
Мы опирались на реализацию лиспа на фортране с исходными текстами.
Фортрановская колода, не очень здоровая. В начале которой просто были
описаны два COMMON массива: CAR(1000000) и CDR(1000000). ;-) Ну а мы
это дело перелопатили потом.
Всего доброго,
Сергей Абрамов
