То, о чем написал Сергей действительно полезно на практике. У меня написана
некая система работы с полиномами, и там обрабатываются неравенства вида
P(x,y,...) < K, где K - целое число, а P не содержит свободного члена. В
списке таких неравенств часто надо находить неравенства с общей левой
частью (подобные). Конечно, полиномы должны иметь канонизированное
представление. Тогда, джунгли очень даже полезны будут при поиске пар
подобных неравенств посредством образца
e1 (tA e) e2 (tA e) e3
Ну и память экономится, если таких пар много.
А насчет сборки мусора - так Антон и написал же, что ее нет, а есть
счетчики ссылок. А нужна она только чтобы зависшие ящики подчищать. Но мне
кажется, что это особо и не нужно - всегда можно руками вовремя обнулить.
А если и вводить, то надо и "слабые" ссылки вводить.
Другое дело, что возможно счетчики ссылок будут мешать распараллеливанию
"над общей памятью". Даже если функции чистые и формально независимые, при
параллельном выполнении придется корректировки ссылок делать защищенно,
скажем atomic. Вопрос к залу: это не очень тормозить будет? Не потеряется
ли эффект от распараллеливания? Надо б проверить.
Аркадий К.
вт, 12 февр. 2019 г. в 17:22, Eisymont Leonid verger-lk_AT_yandex.ru <
refal@botik.ru>:
> Так это массивное представление оправдало себя или нет? В сухом остатке
> ведь - сборка мусора на ровном месте(раньше не было), какие-то переполнения
> стеков. А в программах копирования списков не так уж и много, откуда этот
> миф? Ради чего?
> Наукообразия? Кто в больших программах про эти "джунгли" думать будет?
> Имеются несколько недоработанных реализаций? Какая лучше всех, чем
> пользоваться можно? Бенчмарки были или нет? М.б. просто рефал-2 взять и все
> дела. Восстановить распараллеливание там хотя бы через машинные операции и
> все. Прирост скорости будет в сотни раз на современных системах, а не
> проценты или разы. Как быть?
> Л.Эйсымонт
>
>
>
>
> 12.02.2019, 15:53, "Sergei M. Abramov abram_AT_botik.ru" <refal@botik.ru>:
>
> День добрый, всем!
>
> Антон, спасибо за детали. Думаю снято много обвинений в сторону
> массивного представления ;-)
>
> Коллеги, и это не все фенечки еще описаны. Как мелкий пример: как мне
> помнится (Антон поправит), были еще реализованы "коллапсирующие
> джунгли" или "табулирование сравнения термов-скобок".
>
> Суть простая:
>
> 0. Терм-скобка это поинтер на первое звено p и длина L.
>
> 1. У сравнения двух термов-скобок на равенство есть масса быстрых слуюаев:
> 1.0 Если L1 == 0 && L2==0, то термы равны
> 1.1 Если L1 /= L2, то термы не равны,
> 1.2 Если p1==p2 && L1==L2, то термы равны
>
> 2. Наконец, если нам пришлось делать длинное сравнение и в конце
> выяснилось, что термы таки равны, то мы делаем "коллапсирующие
> джунгли" -- делаем присваивание: p2 = p1, L2=L1 (второе лишнее, но
> пусть будет). Тут и память освободилась и следующий раз сравнение на
> равенство пройдет быстрее ;-)
>
> О! Ран-тайм рефала плюс полировался с любовью ;-)
>
> Всего доброго,
>
> Сергей Абрамов
>
>
>
> Anton Orlov orlovan_AT_gmail.com.
>
> Вы писали 11 февраля 2019 г., 21:39:24:
>
>
> Добрый день!
>
>
>
> On Mon, Feb 11, 2019 at 12:50 PM Arkady Klimov
> arkady.klimov_AT_gmail.com <refal@botik.ru> wrote:
>
>
>
> Может ли кто ответить на такие вопросы по реализации Рефал+ на C++
> (в статье они не обсуждается - не тот уровень абстракции):
>
>
>
>
> 1.Какая организована работа с памятью? Какой менеджер памяти
> используется? Свой или каждый новый чанк через malloc запрашивается?
>
>
>
>
>
> Сделан свой аллокатор по алгоритму близнецов, описанному Кнутом
> (https://en.wikipedia.org/wiki/Buddy_memory_allocation). Это делал
> Андрей Слепухин.
>
> 2.Используются ли счетчики ссылок? Или полная сборка мусора время от
> времени? Какой сборщик мусора?
>
>
>
>
>
> Используются счётчики ссылок. Полной сборки мусора нет, поэтому
> память может течь (например, возможны циклы через ящики). Сборка
> мусора была в планах, но так и не была реализована (на практике
> надобность в ней не ощущалась).
>
> 3.Есть ли версия конкатенации inplace (когда память для выражения
> взята "с запасом")? Андрей уже ответил частично.
>
>
>
>
>
> В алгоритме близнецов все выделяемые куски имеют размер 2^n.
> Выражение помещается посередине нового куска, а справа и слева
> естественным образом получается запас по месту. При конкатенации,
> если этой дырки рядом с одним из выражений достаточно, то копируется
> только одно из выражений, а новая память не выделяется.
>
>
>
>
> Например, если выражение длины N строится дописыванием в
> конец/начало по одному терму, то это требует O(log N) аллокаций
> (амортизированная стоимость O(1)).
>
>
>
>
> Антон
>
>
>
>
> P.S. Помимо списков и массивов есть ещё потенциально интересные
> структуры данных для представления выражений. Например, rope
> (https://en.wikipedia.org/wiki/Rope_(data_structure)) и Finger tree
> (https://en.wikipedia.org/wiki/Finger_tree), но серьёзно для
> рефальского применения их никто не исследовал, насколько я знаю.
>
>
>
>
>
>
> Буду благодарен за разъяснения.
> Аркадий
>
>
>
> пн, 11 февр. 2019 г. в 11:12, Sergei M. Abramov abram_AT_botik.ru <
> refal@botik.ru>:
>
>
>
> Замысловатый ответ ни о чем. Так какой результат, если есть статьи,
>
> >> то ссылки где?.
>
>
> http://www.botik.ru/PSI/RCMS/publications/publications.html
>
> А далее Гуугл "site:www.botik.ru/PSI/RCMS/publications Рефал Плюс"
>
> И там сразу находим:
>
>
> http://www.botik.ru/PSI/RCMS/publications/publ-texts/04-Abramov-Novyj-podkhod-p-373.pdf
>
> С уважением,
>
> Абрамов С.М.
> ab...@botik.ru
> мобильный: +7(903)2928308
>
>
>
>
>
>
>
>
>
> --
> С уважением,
> Абрамов С.М. mailto:ab...@botik.ru
>
>
>
>
--
_______________
*С уважением, *
*Аркадий Климов,*
*с.н.с. ИППМ РАН,*
*+7(499)135-32-95*
*+7(916)072-81-48*
