Re: Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB vector: a practical general purpose immutable sequence.

[Sergei Romanenko sergei . romanenko_AT_supercompilers . ru]

Короче говоря, если использовать Vector-ы, как они реализованы в
стандартной библиотеке Скалы, то, в случае алгоритмов типа "разделяй и
властвуй" можно себе позволить программировать в "нагло-функциональном"
стиле.

Хороший пример - битональная сортировка:

https://github.com/sergei-romanenko/spinalhdl-samples/blob/master/src/main/scala/shs/btsort_f/BitonicSortVN.scala
https://github.com/sergei-romanenko/spinalhdl-samples/blob/master/src/main/scala/shs/btsort_f/README.md

Режем вектор пополам, что-то рекурсивно делаем с половинками, получаем два
новых вектора, которые склеиваем.

  def merge(up: Boolean, x: Vector[Int]): Vector[Int] = {
// Produces a sorted list, on condition that x is bitonic.
val l = x.length
if (l == 1)
  return x
val h = l / 2
val (x1, x2) = x.splitAt(h)
val ok = Vector.tabulate(h)(i => if (up) x1(i) <= x2(i) else x2(i) <= x1(i))
val y1 = Vector.tabulate(h)(i => if (ok(i)) x1(i) else x2(i))
val y2 = Vector.tabulate(h)(i => if (ok(i)) x2(i) else x1(i))
merge(up, y1) ++ merge(up, y2)
  }

  def sort(up: Boolean, x: Vector[Int]): Vector[Int] = {
val l = x.length
require(isPow2(x.length), "x.length must be a power of 2")
if (l <= 1)
  return x
val h = l / 2
val (x1, x2) = x.splitAt(h)
val y1 = sort(up = true, x1)
val y2 = sort(up = false, x2)
merge(up, y1 ++ y2)
  }

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

На всякий случай, обращаю внимание, что Vector - это не Array, поскольку он
неизменяем (как и выражение в Рефале), отчего и можно утверждать, что
манипуляции с Vector-ами - это программирование в "функциональном" стиле.

Понятно также, что если поручить студенту написать на Скале
Рефал-интерпретатор, и при этом представить Рефал-выражения Vector-ами, то
будет работать вполне сносно. Потом можно поручить студенту "закаррить"
этот интерпретатор в соответствии с рецептами, изложенными в

   - Sergei A. Romanenko. Higher-Order Functions as a Substitute for
   Partial Evaluation (A Tutorial). In *First International Workshop on
   Metacomputation in Russia (Proceedings of the first International Workshop
   on Metacomputation in Russia. Pereslavl-Zalessky, Russia, July 2-5, 2008)*.
   A. P. Nemytykh, Ed. - Pereslavl-Zalessky: Ailamazyan University of
   Pereslavl, 2008, 108 p. ISBN 978-5-901795-12-5, pages 145-162. PDF
   

   slides
   

   eLibrary 

и тогда получится как бы компилятор, эффективности которого будет заведомо
достаточно для выполнения заданий из студенческого практикума.

А лексер/парсер лепятся элементарно с помощью парсерных комбинаторов:

https://github.com/sergei-romanenko/spsc-scala/blob/master/src/main/scala/spsc/SLLParsers.scala

Можно поручить 5-ти студентам изготовить 5 вариантов парсера для 5-ти
разных синтаксисов Рефала (чтобы каждый мог выбирать тот вариант
синтаксиса, который ему больше нравится).

СР

Re: Re[4]: Немного статистики

[Anton Orlov orlovan_AT_gmail . com]

Александр,

Я, пожалуй, просто вставлю сюда код :)
Он не самодостаточен, но алгоритм из него читаем.

*/*
 * MSG-Exprs (e.Format1) e.Format2
 * Return e.Format3 -- most specific generalizing of formats 1 and 2.
 */**MSG_Exprs* {
  ((*FAIL*)) *e*.Fe2 = *e*.Fe2;
  (*e*.Fe1) (*FAIL*) = *e*.Fe1;
  (*t*.Ft1 *e*.Fe1) *t*.Ft2 *e*.Fe2 \*?*
*/*
 * IF both t.Ft1 and t.Ft2 are hard terms and aren't $const'ants then
 * split them out with MSG-Terms.
 */*
{
  *t*.Ft1 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  *t*.Ft2 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  <*MSG_Terms* *t*.Ft1 *t*.Ft2> <*MSG_Exprs* (*e*.Fe1) *e*.Fe2>;
};
  (*e*.Fe1 *t*.Ft1) *e*.Fe2 *t*.Ft2 \*?*
*/*
 * IF both t.Ft1 and t.Ft2 are hard terms and aren't $const'ants then
 * split them out with MSG-Terms.
 */*
{
  *t*.Ft1 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  *t*.Ft2 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  <*MSG_Exprs* (*e*.Fe1) *e*.Fe2> <*MSG_Terms* *t*.Ft1 *t*.Ft2>;
};
  ((*CONST* *t*.name) *e*.Fe1) *e*.Fe2, {
*e*.Fe2 : (*CONST* *t*.name) *e*.Rest = (*CONST* *t*.name)
<*MSG_Exprs* (*e*.Fe1) *e*.Rest>;
<*MSG_Exprs* (<*Format_Exp* <*Lookup* &*Const* *t*.name>> *e*.Fe1) *e*.Fe2>;
  };
  (*e*.Fe1 (*CONST* *t*.name)) *e*.Fe2, {
*e*.Fe2 : *e*.Rest (*CONST* *t*.name) = <*MSG_Exprs* (*e*.Fe1)
*e*.Rest> (*CONST* *t*.name);
<*MSG_Exprs* (*e*.Fe1 <*Format_Exp* <*Lookup* &*Const* *t*.name>>) *e*.Fe2>;
  };
  (*e*.Fe1) (*CONST* *t*.name) *e*.Fe2 =
<*MSG_Exprs* (*e*.Fe1) <*Format_Exp* <*Lookup* &*Const* *t*.name>> *e*.Fe2>;
  (*e*.Fe1) *e*.Fe2 (*CONST* *t*.name) =
<*MSG_Exprs* (*e*.Fe1) *e*.Fe2 <*Format_Exp* <*Lookup* &*Const* *t*.name>>>;
  (*e*.Fe1) *e*.Fe2, {
<*IsEmpty_Expr* *e*.Fe1>, <*IsEmpty_Expr* *e*.Fe2> = */*empty*/*;
*/*
 * If both e.Fe1 and e.Fe2 have non-(EVAR) terms then we can unify
 * them to (VVAR). Be VERY careful! We can meet &C, but it easy can be
 * that it points to empty expression.
 */*
\*?*
*e*.Fe1 : *e* *t*.Ft1 *e*, *t*.Ft1 : \{
  (*VVAR*);
  (*CONST* *t*.name), # <*IsEmpty_Const* *t*.name>;
} \*!*
  *e*.Fe2 : *e* *t*.Ft2 *e*, *t*.Ft2 : \{
(*VVAR*);
(*CONST* *t*.name), # <*IsEmpty_Const* *t*.name>;
  } =
  (*VVAR*);
*/*
 * Else at least one of expressions has form of (EVAR)...(EVAR). So we
 * should return (EVAR).
 */*
(*EVAR*);
  };
};
*MSG_Terms* {
  (*PAREN* *e*.Fe1) (*PAREN* *e*.Fe2) = (*PAREN* <*MSG_Exprs*
(*e*.Fe1) *e*.Fe2>);
  *t*.Ft *t*.Ft = *t*.Ft;
  *s* *s* = (*SVAR*);
  (*SVAR*) *s* = (*SVAR*);
  *s* (*SVAR*) = (*SVAR*);
  (*SVAR*) (*SVAR*) = (*SVAR*);
  (*REF* *e*) *s* = (*SVAR*);
  *s* (*REF* *e*) = (*SVAR*);
  (*REF* *e*) (*SVAR*) = (*SVAR*);
  (*SVAR*) (*REF* *e*) = (*SVAR*);
  *t* *t* = (*TVAR*);
};


Хотел бы просто дать ссылку на исходники, но, к сожалению, сайт с ними
лежит (что с ним довольно регулярно случается, так как никто не замечает,
когда он падает).

Антон


On Thu, Feb 21, 2019 at 12:29 AM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Доброе утро, Антон!
>
> *«В компиляторе (на уровне преобразования AS → AS) есть фаза порождения
> возвращаемых форматов — делается наиболее тесное обобщение результатных
> выражений (Most Specific Generalization — дуальная операция к Most General
> Unifier — как НОК/НОД).»*
>
> *«Это нужно, в частности, для более качественной компиляции блоков: {
> Exp1; Exp2; ... } : Pattern.»*
>
> Я правильно понимаю, что в выражениях Exp1, Exp2… вместо скобок активации
> подставляются выходные форматы соответствующих функций, после чего
> обобщению подвергаются фактически образцовые выражения?
>
> А где можно прочитать про алгоритм вычисления наиболее тесного обобщения?
> (Можно даже ссылку на исходник, я пойму.) Просто я занимался аналогичной
> задачей применительно к оптимизации сопоставления с несколькими образцами,
> вот записка моего дипломника, где алгоритм описан:
>
>
> https://github.com/bmstu-iu9/refal-5-lambda/blob/c48cf0179b66c407a5932c03cd8bf38958a8c477/doc/OptPattern/Савельев_Записка_2018.pdf
>
> Вот более лаконичное (но менее понятное) описание задачи в таск-трекере:
>
> https://github.com/bmstu-iu9/refal-5-lambda/issues/154
>
> Поясню к последнему. Рассматриваются только жёсткие выражения. Образцы,
> содержащие e-переменную на верхнем уровне (например, A s.1 *e**.2* t.3 (e.4)
> s.3), названы образцами класса (M, N), где M и N — количество термов
> до и после e-переменной соответственно, образцы, не содержащие e-переменной
> на верхнем уровне (например, A s.1 (e.2 t.3) (e.4) s.3) названы образцами
> класса (K), где K — длина терма. ГСО — глобальное сложнейшее обобщение,
> ЛСО — локальное сложнейшее обобщение. Сложность — количество элементарных
> операций отождествления. Локальное-глобальное — по аналогии с локальным
> и глобальным максимумом в математике.
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
>
>
> *From:* A

RE: Т-язык // Was: Потенциальная востребованность

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Антон!

«Список провязан не обычными указателями, а TPtr, то есть куски Т-система 
вычисляет лениво, может двигать между узлами кластера и т.п. Кажется в 
Т-системе было ограничение на размер обычного последовательного массива (может 
быть, Юра Климов лучше помнит).»

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

Просто из презентации я понял неправильно.

 

Спасибо,
Александр Коновалов

 

From: Anton Orlov orlovan_AT_gmail.com [mailto:refal@botik.ru] 
Sent: Friday, February 22, 2019 9:01 AM
To: refal@botik.ru
Subject: Re: Т-язык // Was: Потенциальная востребованность

 

 

 

On Thu, Feb 21, 2019 at 3:49 AM Александр Коновалов a.v.konovalov87_AT_mail.ru 
  mailto:refal@botik.ru> > 
wrote:

Добрый день, Сергей!

Т.е. в TRefal’е мы имеем списково-массивовый гибрид? Когда объектное выражение 
представлено не списком термов, а списком кусков?

 

Список провязан не обычными указателями, а TPtr, то есть куски Т-система 
вычисляет лениво, может двигать между узлами кластера и т.п. Кажется в 
Т-системе было ограничение на размер обычного последовательного массива (может 
быть, Юра Климов лучше помнит).

 

Антон

 

По асимптотике, как я понимаю, это представление не отличается от спискового с 
подвешенными скобками. На практике оно может экономить память за счёт 
отсутствия ссылок туда-сюда в каждом терме, эффективнее осуществляться 
копирование (поскольку копируется меньше узлов списка. Но вот с другими 
операциями — взятием подвыражения и конкатенацией — не так всё очевидно. 
Допустим, у нас размер куска равен 100, и имеем выражение 300 термов, три 
полных куска. От выражения отрезаем префикс длиной 101 и суффикс тоже длиной 
101. Потом их конкатенируем. Получается новое выражение длиной 202, состоящее 
из трёх кусков, первый и последний — по 100 термов, средний — из двух термов. 
Либо даже из четырёх, где два средних куска будут иметь по одному терму. Так 
что в теории мы можем получить жуткое дробление этих самых кусков. Если, 
конечно, я правильно всё понял.


С уважением,
Александр Коновалов 

-Original Message-
From: Sergei M. Abramov abram_AT_botik.ru mailto:refal@botik.ru> > 
Sent: Thursday, February 21, 2019 11:00 AM
To: Eisymont Leonid verger-lk_AT_yandex.ru mailto:refal@botik.ru> >
Subject: Re: Т-язык // Was: Потенциальная востребованность

> ...  и, к слову, очень родственен Рефалу...

14.03.2005... А про эту ветку я даже подзабыл...

Всего доброго,

Сергей Абрамов

RE: Рефал Плюс – Was: Синтаксический анализ в Рефале

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Доброе утро, Антон!

«…там применяется эвристика при конкатенации выражений, когда пришлось выделить 
новый чанк: если левое выражение длиннее, то результат помещается в начало 
чанка, если правое, то в конец»

А если равны — то посередине? :-)

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

Если выделять памяти в два раза больше, то, наверное, стоит рассмотреть такую 
эвристику: при конкатенации L+R слева оставлять дырку длиной |R|, справа — |L|.

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

 

Только жалко эти эвристики не так просто перенести на векторно-списковое 
представление Скоробогатова. Там конкатенируются за раз не два массива, а целый 
список массивов.

 

С уважением,
Александр Коновалов

 

From: Anton Orlov orlovan_AT_gmail.com [mailto:refal@botik.ru] 
Sent: Friday, February 22, 2019 1:47 AM
To: refal@botik.ru
Subject: Re: Рефал Плюс – Was: Синтаксический анализ в Рефале

 

Александр,

 

Да, всё верно. Я глянул в исходники (сам уже подзабыл и не был уверен) -- там 
применяется эвристика при конкатенации выражений, когда пришлось выделить новый 
чанк: если левое выражение длиннее, то результат помещается в начало чанка, 
если правое, то в конец. То есть, в моём конкретном примере будет таки O(N) 
присваиваний.

 

Вместо эвристики в рантайме можно было бы попробовать дотащить эту информацию 
из компилятора.

 

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

 

Антон

 

 

On Thu, Feb 21, 2019 at 4:41 AM Александр Коновалов a.v.konovalov87_AT_mail.ru 
  mailto:refal@botik.ru> > 
wrote:

Доброе утро, Антон!

Я кое-что не понял про оценку сложности:

«В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение 
помещается посередине нового куска, а справа и слева естественным образом 
получается запас по месту. При конкатенации, если этой дырки рядом с одним из 
выражений достаточно, то копируется только одно из выражений, а новая память не 
выделяется.

Например, если выражение длины N строится дописыванием в конец/начало по одному 
терму, то это требует O(log N) аллокаций (амортизированная стоимость O(1)).»

Но ведь стоимость аллокации для близнецового метода практически константная, 
зачем её считать? Имеет значение стоимость присваивания значения.

Для близнецового метода и размещения куска посередине наилучший случай — размер 
куска, равный 2^n+1 — слева и справа дырки будут иметь длину 2^n/2 (ну, одна — 
2^n/2, вторая — 2^n/2−1, не суть). Соответственно, к такому куску можно с 
каждой стороны приписать (2^n)/2 термов без перераспределения.

Наихудший случай — кусок размером 2^n — любое приписывание 1 терма потребует 
реаллокации и копирования 2^n+1 термов (2^n было и ещё 1, который мы приписали).

Если мы приписываем термы, например, в начало, и начинаем с наилучшего случая 
(2^n+1, дырка имеет длину 2^n/2), то мы сможем приписать по одному терму 2^n/2 
раз до перераспределения. Перераспределение потребует 2^n/2 + 2^n + 1 операций 
присваивания, в новом куске обе дырки будут иметь длину уже 2^n/4. А это 
значит, что теперь мы сделаем только n^2/4 копирований.

Продолжая в том же духе, получим, что приписывание к выражению длиной 2^n+1 
термов 2^n раз по одному терму мы действительно выполним O(n) аллокаций, но с 
каждой из них будет сопряжено O(2^n) присваиваний. Действительно, пусть после 
очередной переаллокации у нас занято L ячеек, с обоих сторон имеем H=(2^n−L)/2 
свободных ячеек — дырок. Тогда до следующей переаллокации мы выполним H 
присваиваний, сама переаллокация потребует присваивания L+H ячеек. Всего за 
один цикл будет выполнено L + 2×(2^n−L)/2 = 2^n присваиваний. За каждый цикл 
дырка уменьшается в два раза, значит, число циклов будет O(n).

Таким образом, удлинение выражения длины L = 2^n+1 до L′=2^(n+1)+1 требует 
O(n×2^n) = O(L log L) присваиваний.

Можно показать, что построение выражения длины L=2^n начиная с пустого также 
требует O(n×2^n) = O(L log L) присваиваний. Могу эти выкладки написать, если 
интересно. Для L≠2^n тоже будет O(L log L) (оценка снизу), тоже могу доказать, 
если кто-то мне не верит. Аллокаций, кстати, на самом деле потребуется O(log² 
L), логарифм в квадрате.

Так что, если выражение длины N строится дописыванием в конец/начало по одному 
терму, то это потребует O(N log N) присваиваний (амортизированная стоимость 
O(log N)).

 

Если бы дырок не было вообще, то потребовалось бы O(N) аллокаций и O(N²) 
присваиваний. Амортизированная стоимость — O(N).

Если бы мы знали, что приписывание терма выполняется только в конец, то могли 
бы распределять память степенями двойки и размещать занятое место с начала. 
Количество аллокаций было бы O(log N), количество присваиваний O(N), 
амортизированная ст

Re: Т-язык // Was: Потенциальная востребованность

[Anton Orlov orlovan_AT_gmail . com]

On Thu, Feb 21, 2019 at 3:49 AM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Добрый день, Сергей!
>
> Т.е. в TRefal’е мы имеем списково-массивовый гибрид? Когда объектное
> выражение представлено не списком термов, а списком кусков?
>

Список провязан не обычными указателями, а TPtr, то есть куски Т-система
вычисляет лениво, может двигать между узлами кластера и т.п. Кажется в
Т-системе было ограничение на размер обычного последовательного массива
(может быть, Юра Климов лучше помнит).

Антон

По асимптотике, как я понимаю, это представление не отличается от
> спискового с подвешенными скобками. На практике оно может экономить память
> за счёт отсутствия ссылок туда-сюда в каждом терме, эффективнее
> осуществляться копирование (поскольку копируется меньше узлов списка. Но
> вот с другими операциями — взятием подвыражения и конкатенацией — не так
> всё очевидно. Допустим, у нас размер куска равен 100, и имеем выражение 300
> термов, три полных куска. От выражения отрезаем префикс длиной 101 и
> суффикс тоже длиной 101. Потом их конкатенируем. Получается новое выражение
> длиной 202, состоящее из трёх кусков, первый и последний — по 100 термов,
> средний — из двух термов. Либо даже из четырёх, где два средних куска будут
> иметь по одному терму. Так что в теории мы можем получить жуткое дробление
> этих самых кусков. Если, конечно, я правильно всё понял.
>
>
> С уважением,
> Александр Коновалов
>
> -Original Message-
> From: Sergei M. Abramov abram_AT_botik.ru 
> Sent: Thursday, February 21, 2019 11:00 AM
> To: Eisymont Leonid verger-lk_AT_yandex.ru 
> Subject: Re: Т-язык // Was: Потенциальная востребованность
>
> > ...  и, к слову, очень родственен Рефалу...
>
> 14.03.2005... А про эту ветку я даже подзабыл...
>
> Всего доброго,
>
> Сергей Абрамов
>

Re: Рефал Плюс – Was: Синтаксический анализ в Рефале

[Anton Orlov orlovan_AT_gmail . com]

Александр,

Да, всё верно. Я глянул в исходники (сам уже подзабыл и не был уверен) --
там применяется эвристика при конкатенации выражений, когда пришлось
выделить новый чанк: если левое выражение длиннее, то результат помещается
в начало чанка, если правое, то в конец. То есть, в моём конкретном примере
будет таки O(N) присваиваний.

Вместо эвристики в рантайме можно было бы попробовать дотащить эту
информацию из компилятора.

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

Антон


On Thu, Feb 21, 2019 at 4:41 AM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Доброе утро, Антон!
>
> Я кое-что не понял про оценку сложности:
>
> *«В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение
> помещается посередине нового куска, а справа и слева естественным образом
> получается запас по месту. При конкатенации, если этой дырки рядом с одним
> из выражений достаточно, то копируется только одно из выражений, а новая
> память не выделяется.*
>
> *Например, если выражение длины N строится дописыванием в конец/начало
> по одному терму, то это требует O(log N) аллокаций (амортизированная
> стоимость O(1)).»*
>
> Но ведь стоимость аллокации для близнецового метода практически
> константная, зачем её считать? Имеет значение стоимость присваивания
> значения.
>
> Для близнецового метода и размещения куска посередине наилучший случай —
> размер куска, равный 2^n+1 — слева и справа дырки будут иметь длину 2^n/2
> (ну, одна — 2^n/2, вторая — 2^n/2−1, не суть). Соответственно, к такому
> куску можно с каждой стороны приписать (2^n)/2 термов без
> перераспределения.
>
> Наихудший случай — кусок размером 2^n — любое приписывание 1 терма
> потребует реаллокации и копирования 2^n+1 термов (2^n было и ещё 1,
> который мы приписали).
>
> Если мы приписываем термы, например, в начало, и начинаем с наилучшего
> случая (2^n+1, дырка имеет длину 2^n/2), то мы сможем приписать по одному
> терму 2^n/2 раз до перераспределения. Перераспределение потребует 2^n/2 +
> 2^n + 1 операций присваивания, в новом куске обе дырки будут иметь длину
> уже 2^n/4. А это значит, что теперь мы сделаем только n^2/4 копирований.
>
> Продолжая в том же духе, получим, что приписывание к выражению длиной 2^n+1
> термов 2^n раз по одному терму мы действительно выполним O(n) аллокаций,
> но с каждой из них будет сопряжено O(2^n) присваиваний. Действительно,
> пусть после очередной переаллокации у нас занято L ячеек, с обоих сторон
> имеем H=(2^n−L)/2 свободных ячеек — дырок. Тогда до следующей
> переаллокации мы выполним H присваиваний, сама переаллокация потребует
> присваивания L+H ячеек. Всего за один цикл будет выполнено L +
> 2×(2^n−L)/2 = 2^n присваиваний. За каждый цикл дырка уменьшается в два
> раза, значит, число циклов будет O(n).
>
> Таким образом, удлинение выражения длины L = 2^n+1 до L′=2^(n+1)+1
> требует O(n×2^n) = O(L log L) присваиваний.
>
> Можно показать, что построение выражения длины L=2^n начиная с пустого
> также требует O(n×2^n) = O(L log L) присваиваний. Могу эти выкладки
> написать, если интересно. Для L≠2^n тоже будет O(L log L) (оценка снизу),
> тоже могу доказать, если кто-то мне не верит. Аллокаций, кстати, на самом
> деле потребуется O(log² L), логарифм в квадрате.
>
> Так что, если выражение длины N строится дописыванием в конец/начало
> по одному терму, то это потребует *O**(**N* *log* *N**) присваиваний
> (амортизированная стоимость **O**(**log* *N**)).*
>
>
>
> Если бы дырок не было вообще, то потребовалось бы O(N) аллокаций и O(N²)
> присваиваний. Амортизированная стоимость — O(N).
>
> Если бы мы знали, что приписывание терма выполняется только в конец,
> то могли бы распределять память степенями двойки и размещать занятое место
> с начала. Количество аллокаций было бы O(log N), количество присваиваний O
> (N), амортизированная стоимость — O(1).
>
> Так что близнецовый метод (вернее, распределение памяти по степеням двойки
> с размещением куска посередине) существенно лучше наивного варианта без
> дырок, но чуть хуже идеального варианта.
>
>
>
> *«P.S. Помимо списков и массивов есть ещё потенциально интересные
> структуры данных для представления выражений. Например, rope
>  и Finger tree
> , но серьёзно для рефальского
> применения их никто не исследовал, насколько я знаю.»*
>
> К слову, в той же задаче — построении строки длиной N путём
> последовательного приписывания термов по одному — обе упомянутые структуры
> данных потребуют O(N log N) времени, поскольку приписывание одного
> символа в обоих видах строк требует O(log N) времени.
>
> Я когда-то давал на курсовой проект задачу — реализовать Простой Рефал
> с использованием rope’ов для представления объектных выражений. Студент
> не осилил сделать, задача оказалась слишком сложной для курсового (я
> по неопытности не смог оценить объём работ

Re: Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB vector: a practical general purpose immutable sequence.

[Sergei Romanenko sergei . romanenko_AT_supercompilers . ru]

On Fri, Feb 22, 2019 at 1:12 AM Anton Orlov orlovan_AT_gmail.com <
refal@botik.ru> wrote:

Интересно было бы сравнить с реализацией векторов в Clojure, которая
> опирается на работу того же Phil Bagwell. Статьи нормальной я не нашёл, но
> есть подробный блог-пост:
> https://hypirion.com/musings/understanding-persistent-vector-pt-1
> (и исходники).
>

Вот тут есть некое обсуждение:

*RFE: Replace immutable.Vector with a faster implementation (src included)*
https://github.com/scala/bug/issues/3724

@TiarkRompf said:
First of all, there seems to be some confusion about the nature of Scala's
Vector implementation. I don't know who spread the myth about the
underlying data structure being a skip-list (I've read that in a couple of
places now) but this is definitely false. The implementation is based on
32-wide trees, just as in Clojure. This renders any wholesale arguments
(e.g. about locality) invalid.

While the trie structure is similar, there are some differences in how the
implementation optimizes specific access patterns. Clojure chose a fairly
simple model to make access to the right end faster: the last 32-wide block
is kept outside the tree so that it can be accessed in constant time,
without going through multiple tree levels. To add an element (on the
right) to a Clojure Vector, only this max. 32-wide array has to be copied.

We took this model a step further. In Scala, Vectors have a notion of
'focus', which identifies a single 32-wide block that is accessible in
constant time. Every update operation (be it at the left end, the right
end, or any other position), will put the target block in focus. Updates to
a block 'in focus' will copy only that particular 32-wide block (Clojure's
implementation has to copy all blocks on the path to the root for positions
that are not in the rightmost block). Moreover, all the tree nodes from the
root to the block in focus are kept in a 'display', i.e. a constant-time
stack. Moving the focus to an adjacent 32-block incurs only one indirection
through the display (possibly copying the node one level up). Indexed reads
also use the display to minimize the number of indirections.

СР

Re: Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB vector: a practical general purpose immutable sequence.

[Anton Orlov orlovan_AT_gmail . com]

Интересно было бы сравнить с реализацией векторов в Clojure, которая
опирается на работу того же Phil Bagwell. Статьи нормальной я не нашёл, но
есть подробный блог-пост:
https://hypirion.com/musings/understanding-persistent-vector-pt-1
(и исходники).

Антон

On Thu, Feb 21, 2019 at 4:18 PM Sergei Romanenko
sergei.romanenko_AT_supercompilers.ru  wrote:

> Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB
> vector: a practical general purpose immutable sequence. In *Proceedings
> of the 20th ACM SIGPLAN International Conference on Functional Programming*
> (ICFP 2015). ACM, New York, NY, USA, 342-354. DOI=
> http://dx.doi.org/10.1145/2784731.2784739
>
> State-of-the-art immutable collections have wildly differing performance
> characteristics across their operations, often forcing programmers to
> choose different collection implementations for each task. Thus, changes to
> the program can invalidate the choice of collections, making code evolution
> costly. It would be desirable to have a collection that performs well for a
> broad range of operations. To this end, we present the RRB-Vector, an
> immutable sequence collection that offers good performance across a large
> number of sequential and parallel operations. The underlying innovations
> are: (1) the Relaxed-Radix-Balanced (RRB) tree structure, which allows
> efficient structural reorganization, and (2) an optimization that exploits
> spatio-temporal locality on the RRB data structure in order to offset the
> cost of traversing the tree. In our benchmarks, the RRB-Vector speedup for
> parallel operations is lower bounded by 7x when executing on 4 CPUs of 8
> cores each. The performance for discrete operations, such as appending on
> either end, or updating and removing elements, is consistently good and
> compares favorably to the most important immutable sequence collections in
> the literature and in use today. The memory footprint of RRB-Vector is on
> par with arrays and an order of magnitude less than competing collections.
> 
>
> В порядке информации.
>
> СР
>
>

Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB vector: a practical general purpose immutable sequence.

[Sergei Romanenko sergei . romanenko_AT_supercompilers . ru]

Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB
vector: a practical general purpose immutable sequence. In *Proceedings of
the 20th ACM SIGPLAN International Conference on Functional Programming*
(ICFP 2015). ACM, New York, NY, USA, 342-354. DOI=
http://dx.doi.org/10.1145/2784731.2784739

State-of-the-art immutable collections have wildly differing performance
characteristics across their operations, often forcing programmers to
choose different collection implementations for each task. Thus, changes to
the program can invalidate the choice of collections, making code evolution
costly. It would be desirable to have a collection that performs well for a
broad range of operations. To this end, we present the RRB-Vector, an
immutable sequence collection that offers good performance across a large
number of sequential and parallel operations. The underlying innovations
are: (1) the Relaxed-Radix-Balanced (RRB) tree structure, which allows
efficient structural reorganization, and (2) an optimization that exploits
spatio-temporal locality on the RRB data structure in order to offset the
cost of traversing the tree. In our benchmarks, the RRB-Vector speedup for
parallel operations is lower bounded by 7x when executing on 4 CPUs of 8
cores each. The performance for discrete operations, such as appending on
either end, or updating and removing elements, is consistently good and
compares favorably to the most important immutable sequence collections in
the literature and in use today. The memory footprint of RRB-Vector is on
par with arrays and an order of magnitude less than competing collections.


В порядке информации.

СР

Re: Т-язык // Was: Потенциальная востребованность

[Sergei M. Abramov]

День добрый, Александр!

> Т.е.  в TRefal’е мы имеем списково-массивовый гибрид?  Когда
> объектное выражение представлено не списком термов, а списком
> кусков?

К сожалению я не помню ни деталей проекта, ни на сколко в нем удалось
продвинуться.  Просто натолкнулся на слайды, когда доставал слайды про
Т-системе.  И они просто были признаком связи проектов Рефал о
Т-система.

С Т-системой и Т++ лучше.  Там все доведено до реализации и
развивается дальше.

Ну, и когда работали по Т-системе и вообще по HPC постепенно вставали
на места некоторые общепризнанные вещи.

Например, не надо слишком прямолинейно понимать слова "балансировка
нагруски".  Например, выравнивание на всех узлах длин очередей готовых
к счету процессов делать не надо.  Или, понимание того, что происходит
на самом деле с соотношением веса гранулы параллелизма и веса
накладных на организацию этой гранулы (или ее миграции).

Всего доброго,

Сергей Абрамов

RE: Рефал Плюс – Was: Синтаксический анализ в Рефале

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Доброе утро, Антон!

Я кое-что не понял про оценку сложности:

«В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение 
помещается посередине нового куска, а справа и слева естественным образом 
получается запас по месту. При конкатенации, если этой дырки рядом с одним из 
выражений достаточно, то копируется только одно из выражений, а новая память не 
выделяется.

Например, если выражение длины N строится дописыванием в конец/начало по одному 
терму, то это требует O(log N) аллокаций (амортизированная стоимость O(1)).»

Но ведь стоимость аллокации для близнецового метода практически константная, 
зачем её считать? Имеет значение стоимость присваивания значения.

Для близнецового метода и размещения куска посередине наилучший случай — размер 
куска, равный 2^n+1 — слева и справа дырки будут иметь длину 2^n/2 (ну, одна — 
2^n/2, вторая — 2^n/2−1, не суть). Соответственно, к такому куску можно с 
каждой стороны приписать (2^n)/2 термов без перераспределения.

Наихудший случай — кусок размером 2^n — любое приписывание 1 терма потребует 
реаллокации и копирования 2^n+1 термов (2^n было и ещё 1, который мы приписали).

Если мы приписываем термы, например, в начало, и начинаем с наилучшего случая 
(2^n+1, дырка имеет длину 2^n/2), то мы сможем приписать по одному терму 2^n/2 
раз до перераспределения. Перераспределение потребует 2^n/2 + 2^n + 1 операций 
присваивания, в новом куске обе дырки будут иметь длину уже 2^n/4. А это 
значит, что теперь мы сделаем только n^2/4 копирований.

Продолжая в том же духе, получим, что приписывание к выражению длиной 2^n+1 
термов 2^n раз по одному терму мы действительно выполним O(n) аллокаций, но с 
каждой из них будет сопряжено O(2^n) присваиваний. Действительно, пусть после 
очередной переаллокации у нас занято L ячеек, с обоих сторон имеем H=(2^n−L)/2 
свободных ячеек — дырок. Тогда до следующей переаллокации мы выполним H 
присваиваний, сама переаллокация потребует присваивания L+H ячеек. Всего за 
один цикл будет выполнено L + 2×(2^n−L)/2 = 2^n присваиваний. За каждый цикл 
дырка уменьшается в два раза, значит, число циклов будет O(n).

Таким образом, удлинение выражения длины L = 2^n+1 до L′=2^(n+1)+1 требует 
O(n×2^n) = O(L log L) присваиваний.

Можно показать, что построение выражения длины L=2^n начиная с пустого также 
требует O(n×2^n) = O(L log L) присваиваний. Могу эти выкладки написать, если 
интересно. Для L≠2^n тоже будет O(L log L) (оценка снизу), тоже могу доказать, 
если кто-то мне не верит. Аллокаций, кстати, на самом деле потребуется O(log² 
L), логарифм в квадрате.

Так что, если выражение длины N строится дописыванием в конец/начало по одному 
терму, то это потребует O(N log N) присваиваний (амортизированная стоимость 
O(log N)).

 

Если бы дырок не было вообще, то потребовалось бы O(N) аллокаций и O(N²) 
присваиваний. Амортизированная стоимость — O(N).

Если бы мы знали, что приписывание терма выполняется только в конец, то могли 
бы распределять память степенями двойки и размещать занятое место с начала. 
Количество аллокаций было бы O(log N), количество присваиваний O(N), 
амортизированная стоимость — O(1).

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

 

«P.S. Помимо списков и массивов есть ещё потенциально интересные структуры 
данных для представления выражений. Например, rope 
  и Finger tree 
 , но серьёзно для рефальского 
применения их никто не исследовал, насколько я знаю.»

К слову, в той же задаче — построении строки длиной N путём последовательного 
приписывания термов по одному — обе упомянутые структуры данных потребуют O(N 
log N) времени, поскольку приписывание одного символа в обоих видах строк 
требует O(log N) времени.

Я когда-то давал на курсовой проект задачу — реализовать Простой Рефал с 
использованием rope’ов для представления объектных выражений. Студент не осилил 
сделать, задача оказалась слишком сложной для курсового (я по неопытности не 
смог оценить объём работы). Поставили тройку и отпустили.

 

Rope и Finger tree требуют для конкатенации двух строк логарифмическое время. 
Про Finger tree не знаю точную оценку, rope выполняет конкатенацию за O(|log M 
− log N|) времени. Интересно оценить среднее время конкатенации для массивного 
представления и близнецового метода, но для этого нужно знать распределение 
длин строк и размеров дырок.

 

С уважением,
Александр Коновалов

 

 

From: Александр Коновалов a.v.konovalov87_AT_mail.ru  
Sent: Tuesday, February 12, 2019 12:19 AM
To: refal@botik.ru
Subject: RE: Рефал Плюс – Was: Синтаксический анализ в Рефале

 

Добрый вечер, Антон!

«В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение 
помещается посередине нового куска, а справа и слева естественным образом 
получается запас по месту. При конкатенации,

RE: Т-язык // Was: Потенциальная востребованность

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Добрый день, Сергей!

Т.е. в TRefal’е мы имеем списково-массивовый гибрид? Когда объектное выражение 
представлено не списком термов, а списком кусков?

По асимптотике, как я понимаю, это представление не отличается от спискового с 
подвешенными скобками. На практике оно может экономить память за счёт 
отсутствия ссылок туда-сюда в каждом терме, эффективнее осуществляться 
копирование (поскольку копируется меньше узлов списка. Но вот с другими 
операциями — взятием подвыражения и конкатенацией — не так всё очевидно. 
Допустим, у нас размер куска равен 100, и имеем выражение 300 термов, три 
полных куска. От выражения отрезаем префикс длиной 101 и суффикс тоже длиной 
101. Потом их конкатенируем. Получается новое выражение длиной 202, состоящее 
из трёх кусков, первый и последний — по 100 термов, средний — из двух термов. 
Либо даже из четырёх, где два средних куска будут иметь по одному терму. Так 
что в теории мы можем получить жуткое дробление этих самых кусков. Если, 
конечно, я правильно всё понял.


С уважением,
Александр Коновалов 

-Original Message-
From: Sergei M. Abramov abram_AT_botik.ru  
Sent: Thursday, February 21, 2019 11:00 AM
To: Eisymont Leonid verger-lk_AT_yandex.ru 
Subject: Re: Т-язык // Was: Потенциальная востребованность

> ...  и, к слову, очень родственен Рефалу...

14.03.2005... А про эту ветку я даже подзабыл...

Всего доброго,

Сергей Абрамов