Переношу реплику Аркадия под этот сабж. А то мысли про джунгли окажутся потерянными в нескольких тредах. Андрей
On Wed, Feb 13, 2019 at 6:26 PM Arkady Klimov arkady.klimov_AT_gmail.com < refal@botik.ru> wrote: > То, о чем написал Сергей действительно полезно на практике. У меня > написана некая система работы с полиномами, и там обрабатываются > неравенства вида 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 <http://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* >
