Здравствуйте, WolfHound, Вы писали:

WH>Статью читать не пробовал?

Там много букв.

WH>Я тут подумал и понял, что описанный в статье метод можно обобщить, сделать более мощным и в то же время в 99% случаев вообще убрать все аннотации и вызовы expose/localize.
WH>Потом напишу как.

У нас уже есть одна очень обобщенная задача. Из работы над ней я убедился, что чем более обобщенным получается решение, там сложнее его реализовать и поддерживать.

Здравствуйте, VladD2, Вы писали:

WH>>Статью читать не пробовал?
VD>Там много букв.
Зря. Я не просто так ссылка дал.

VD>У нас уже есть одна очень обобщенная задача. Из работы над ней я убедился, что чем более обобщенным получается решение, там сложнее его реализовать и поддерживать.
Путаешь тёплое с зелёным.
Тут все трансформации строго O(1).

На мой взгляд идеальный способ это ARC + GC для поиска циркулярных ссылок, который будет работать в debug режиме. GC, собственно, нужен, чтобы находить циклы и сообщать об этом программисту, который в коде будет их разбивать (слабыми ссылками).

Здравствуйте, WolfHound, Вы писали:

VD>>Там много букв.
WH>Зря. Я не просто так ссылка дал.

Да я тоже считаю, что зря. Нужно было на страничке идею обрисовать, а не статью на 200 страниц клепать.
Я ее потом прочту, обязательно, но это дело не быстрое.

VD>>У нас уже есть одна очень обобщенная задача. Из работы над ней я убедился, что чем более обобщенным получается решение, там сложнее его реализовать и поддерживать.
WH>Путаешь тёплое с зелёным.
WH>Тут все трансформации строго O(1).

Тебя послушать, так проблем на свете нет. Но почему-то вот не все у нас гладко работает и уже довольно долго.

Здравствуйте, VladD2, Вы писали:

DM>>Это и есть барьер в одном из видов, об этом я (автор того блога) там упомянул явно. Фишка в том, что это очень недешевая штука.
VD>Барьер (как предполагает само название) — это код в который оборачивается присвоение указателя.

Само название предполагает лишь забор.
Если угодно позанудствовать о терминах:
"A barrier is a block on reading from or writing to certain memory locations by certain threads or processes.
Barriers can be implemented in either software or hardware. Software barriers involve additional instructions around load or store operations, which would typically be added by a cooperative compiler. Hardware barriers don’t require compiler support, and may be implemented on common operating systems by using memory protection."
http://www.memorymanagement.org/glossary/b.html#term-barrier-1

"Write barriers are used for incremental or concurrent garbage collection. They are also used to maintain remembered sets for generational collectors."
http://www.memorymanagement.org/glossary/w.html#term-write-barrier

Здравствуйте, VladD2, Вы писали:

VD>Да я тоже считаю, что зря. Нужно было на страничке идею обрисовать, а не статью на 200 страниц клепать.
VD>Я ее потом прочту, обязательно, но это дело не быстрое.
Ну, так ты просто доказательства пропускай.
Для того чтобы понять идею они не нужны.

VD>Тебя послушать, так проблем на свете нет.
Не вообще, а конкретно в данном случае.

VD>Но почему-то вот не все у нас гладко работает и уже довольно долго.
А у кого гладко?

Здравствуйте, VladD2, Вы писали:

Описанный метод является развитием этой идеи:
Capabilities for External Uniqueness
http://infoscience.epfl.ch/record/135708/files/capabilities_for_uniqueness_TR.pdf

Для эффективного управления памятью необходимо разбить множество объектов на кластеры.
Каждый кластер объектов мы размещаем в отдельной куче.
Объекты внутри кластера могут произвольно ссылаться друг на друга.
Объект из одного кластера не может, ссылаться на объект из другого кластера.
Кластеры объектов могут быть объединены.
Все проверки осуществляются статически.

С каждым кластером ассоциирован уникальный объект. В Capabilities for External Uniqueness это чисто эфемерный объект нужный только для статических проверок. В нашем же случае это ещё и ссылка на кучу, в которой выделяется память для объектов данного кластера.

Для того чтобы иметь возможность работать с объектами кластера нужно иметь доступ к кластеру.

Доступ может быть эксклюзивным или разделённым.
Если доступ, разделённый то можно читать, создавать и изменять объекты в кластере. Так же можно предоставить разделенный доступ другой функции.

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

На практике это выглядит так:

public class LinkedList[T]
{
    public Value : T;
    private mutable Next : LinkedList[T];
    public this(value : T)
    {
      Value = value;
      Next = null;
    }
    public Append(that : LinkedList[T]) : void
    {
        if (that == null)
          return;
        mutable cur = this;
        while (cur.Next != null)
          cur = cur.Next;
        cur.Next = that;
    }
}

Send(list : unique LinkedList[T]) : void
{
  ...
}

Main() : void
{
  //Создали новый кластер и получили эксклюзивное владение.
  def l1 = unique(LinkedList)(1);

  //Тут не нужно ничего явно указывать. 
  //При создании нового объекта он создаётся в том кластере
  //в который ссылка на этот объект записывается.
  //Это легко вычислить на этапе компиляции.
  //Метод Append получает разделённое право на работу с кластером.
  def l2 = l1.Append(LinkedList(2));
  
  //Передаём ссылку на l2 и эксклюзивное право на работу с кластером.
  Send(l2);
  
  //Тут любые обращения к l1 или l2 вызовут ошибку компиляции.
}

Полный пример со всеми подробностями:

В {} неявные параметры.
Их при вызове указывать не надо. Компилятор сам передаст.

Тип $ cluster — связывает тип с кластером.
Метод $ cluster — связывает тип this этого метода с кластером.

def l1 : LinkedList[T] $ cluster1 = ...;
def l2 : LinkedList[T] $ cluster1 = ...;
def l3 : LinkedList[T] $ cluster2 = ...;
l1.Append(l2);//Ok
l2.Append(l3)//Error: "l3" in "cluster2". Expected in "cluster1".

public class LinkedList[T]
{
  public Value : T;
  private mutable Next : LinkedList[T];
  public this $ cluster {cluster : shared}(value : T $ cluster)
  {
    //this имеет тип LinkedList[T] $ cluster
    //Так как объект может ссылаться только на объекты своего кластера
    //То поле Value получает тип T $ cluster
    //И присвоение проходит проверку типов
    this.Value = value;
    this.Next = null;
  }
  public Append $ cluster {cluster : shared}(that : LinkedList[T] $ cluster) : void
  {
    if (that == null)
      return;
    mutable cur = this;
    while (cur.Next != null)
      cur = cur.Next;
    cur.Next = that;
  }
}

Send{cluster : exclusive}(list : LinkedList[T] $ cluster) : void
{
  ...
}

Main() : void
{
  def cluster = new cluster;
  def l1 = LinkedList $ cluster(1);

  def l2 = l1.Append(LinkedList $ cluster(2));
  
  Send(l2);
}

На практике почти во всех случаях в метод передаётся разделяемое право на работу с одним кластером и все передаваемые параметры и this размещены в этом кластере.
Для каждого параметра помеченного модификатором unique мы передаём в метод эксклюзивное право на доступ к кластеру и ассоциируем этот кластер с типом параметра.

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

Foo{cluster1 : exclusive, cluster2 : exclusive}(p1 : T1 $ cluster1, p2 : T2 $ cluster1, p3 : T3 $ cluster2, p4 : T4 $ cluster2) : void

Объединение кластеров

def l1 : LinkedList[T] $ cluster1 = ...;
def l2 : LinkedList[T] $ cluster2 = ...;
l1.Append(l2);//error

def l3 : LinkedList[T] $ cluster1 = merge l2 into l1;
l1.Append(l3);//ok

cluster2 должен быть эксклюзивным. При выполнении операции merge доступ к cluster2 теряется. И обращение объектам в нем становится невозможным. Те любой доступ к l2 приведёт к ошибке.

Если нам нужно возвратить кластер из функции то мы можем написать так

Foo(...) : unique Bar
{
...
}

Полная запись:

Foo(...) : {cluster : exclusive} Bar $ cluster
{
...
}

Для того чтобы можно был хранить один кластер внутри другого нам понадобится специальный тип который хранит кластер и ссылку на один из объектов кластера:

//Тип системный. Проверку типов в нормальном режиме не пройдёт.
class ClusterBox[T]
{
    private mutable obj : T;
    private mutable cluster : Cluster;
  public this(obj : unique T) : void
  {
      this.obj = obj;
      this.cluster = cluster_of(obj);
  }
  public Get() : unique T
  {
    if (this.cluster == null)
      throw ...;
    def res = (this.obj, this.cluster);
      this.obj = null;
      this.cluster = null;
      res;
  }
  public Put(obj : unique T) : void
  {
    if (this.cluster == null)
      this.cluster.Destroy();
      this.obj = obj;
      this.cluster = cluster_of(obj);
  }
}

class JobQueue[T]
{
  private queue : Queue[ClusterBox[T]] = Queue();
  public Send(job : unique T) : void
  {
    queue.Enqueue(ClusterBox(job));
  }
  public Receive() : unique T
  {
    queue.Dequeue().Get();
  }
}

Здравствуйте, WolfHound, Вы писали:

Легко реализуемые полезные функции:
Эти функции можно использовать для передачи по сети, сохранения в файл итп.

Serialize[T]{from : shared, to : shared}(obj : T $ from) : array[byte] $ to
Deserialize[T]{from : shared, to : shared}(obj : array[byte] $ from) : T $ to

Эта функция нужна, если нужно скопировать граф объектов из одного кластера в другой.

CloneObjectGraph[T]{from : shared, to : shared}(obj : T $ from) : T $ to

Ну или

CollectGarbage[T](obj : unique T) : unique T
{
  def cluster = new cluster;
  CloneObjectGraph(obj) : T $ cluster;
}

Здравствуйте, WolfHound, Вы писали:

Финалайзеры.
Некоторым объектам, например ClusterBox[T] при удалении кластера или если объект удалён при сборке мусора в кластере, нужно что-то сделать.
В случае с ClusterBox[T] если в нём лежит кластер то удалить его.
Такие объекты при создании записывают себя в список финализации кластера.

Межпоточное взаимодействие.

Объект, который можно разделить между потоками.
Реализуется через маленький объект со счётчиком ссылок.
При клонировании счётчик ссылок увеличивается. При вызове финалайзера уменьшается.

class SharedBox[T]
{
  public Clone() : unique SharedBox[T];
  public Get() : unique T;
  public TryGet() : unique option[T];
  public Put(obj : unique T) : void;
  public PutOrReplace(obj : unique T) : void;
}

Разделяемая очередь.

NewSharedQueue[T]{sender : shared, receiver : shared}() : SharedQueueSender[T] $ sender * SharedQueueReciever[T] $ receiver;
class SharedQueueSender[T]
{
  public Send(obj : unique T) : void;
}
class SharedQueueReciever[T]
{
  public Recieve() : unique T;
}

Почтовый ящик. Может получать сообщения из множества потоков.

class MailBox[T]
{
  public Recieve() : unique T;
  public GetSender[T] $ self {sender : shared, self : shared}() : MailBoxSender[T] $ sender;
}
class MailBoxSender[T]
{
  public Send(obj : unique T) : void;
  public GetSender[T] $ self {sender : shared, self : shared}() : MailBoxSender[T] $ sender;
}

Здравствуйте, WolfHound, Вы писали:

Можно автоматически создавать кластеры, связанные с фреймом стека.
Такой кластер создаётся при входе в функцию. И удаляется при выходе из неё.
Внутри тела функции предоставляется разделяемый доступ к кластеру.
Если обращений к кластеру нет, то оптимизатор его уберёт.
Объект ассоциируется со стековым кластером, если не ясно в какой кластер его класть.

IntToString(i : int) : string
{
...
}
class StringBuilder
{
    //StringBuild и аргумент могут находится в разных кластерах.
    public Append $ self{self : shared, arg : shared}(str : string $ arg) : void
    {
    ...
    }
    public ToString() : string
    {
    ...
    }
}
Foo(n : int) : string
{
    def sb = StringBuiler();
    for (mutable i = 0; i < n; ++i)
        sb.Append(IntToString(i));
    sb.ToString();
}

По умолчанию все параметры и возвращаемое значение функции ассоциированы с одним кластером.
Соответственно из использования метода ToString мы выводим, что StringBuiler ассоциирован с кластером возвращаемого значения.
Метод Append не связывает свой аргумент с кластером, с которым ассоциирован сам StringBuiler.
Функция IntToString не навязывает, какой либо кластер своему возвращаемому значению.
Таким образом, у нас остался, не определён кластер, в котором мы выделяем строки.
В этом случае используется стековый кластер.

Соответственно все строки, которые создаст IntToString, будут удалены при выходе из функции Foo.

Здравствуйте, Sharov, Вы писали:

S>Зачем значениям (value type) при возврате из функций выделять динамическую память? Все жизнь вроде в регистры писалось.

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

Я кидал в предыдущей темке ссылку на эту http://habrahabr.ru/post/208608/ статью — ты её прочитал тогда или нет? ) Мне кажется, что тебе должно быть особенно интересно, т.к. автор так же как и ты решил пойти (правда он чётко отмечает, что это временно решение, для начала) от управляемого языка в сторону нативного, а не наоборот. И соответственно там весьма интересен список того, что они планируют стащить из плюсов (в том числе и в области управления памятью).

P.S. Так, а мне пора бы уже пойти и написать первое тестовое приложение на Rust'е...

Здравствуйте, VladD2, Вы писали:

VD>3. Увеличить количество куч в управляемых программах. Тут возможны варианты, но мне больше нравится идея акторов:
VD> * Вводим по одной кучи на поток. Запрещаем обращение к памяти из этой кучи из других потоков.

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

VD> * Вводим специальную обменную кучу в которой разрешаем размещать исключительно неизменяемые объекты.

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

VD> * Вводим для каждого потока очередь в которой можно помещать объекты из обменной кучи.

нифига не понял.
можно поподробнее в этом месте?

VD>Так же ввести глобальную кучу рэйдонли-объектов куда можно помещать совместно используемые объекты и константы.

нереализуемо.
как ты себе это представляешь? объект становится ридонли после завершения работы его конструкторов?
он создаётся в этой куче, или копируется туда?
если его туда "помещать", то как контролировать его неизменяемость?

VD>Еще можно позволить вводить специальные локальные кучи с фиксированным временем жизни (по стеку или с ручным уничтожением). После уничтожения кучи можно просто пометить все ссылки на нее нулями или даже выкидывать исключение, если таковые ссылки имеются. В прочем, и без этого варианта предлагаемые изменения должны снять проблемы которые обычно ассоциируют с GC.

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

Здравствуйте, Философ, Вы писали:

Ф>нифига не понял.
Ф>можно поподробнее в этом месте?

Что непонятного то? ) Влад описал практически классическую модель акторов. Я правда не очень понял зачем, т.к. в принципе она не является жёстко завязанной на систему управления памяти (хотя конечно конкретная реализация зависит от неё), про которую тут вроде как идёт речь. К примеру всё это стало популярным с приходом Эрланга (наиболее классическая реализация и там сборщик мусора), но имеются варианты и на C++ (соответственно без всяких сборщиков мусора или подсчётов ссылок).

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

Здравствуйте, VladD2, Вы писали:

VD>Ты и автор этого блока просто не знаешь, что в 21 веке эту работу можно переложить на ОС, которая отследит изменение памяти с помощью прерываний. В Винде для этого используется флаг MEM_WRITE_WATCH при вызове функции VirtualAlloc() и GetWriteWatch() для того чтобы получить список измененных страниц.
Это очень плохой способ:
1) Страница — это слишком большое количество памяти для сканирования. В Java используются карты по 128 байт.
2) На больших системах нынче модно использовать hugepages — это страницы размером по 2Мб (или даже 64Мб).

Здравствуйте, VladD2, Вы писали:

VD>Теперь немного "крамолы" (для не посвященных). На самом деле скорость GC существенно выше чем скорость ARC или ручного управления памятью на базе malloc/free, так как выделение памяти требует всего лишь одного приращения указателя, а освобождение не стоит ничего (мортвые объекты просто игнорируются). Платим мы только за поиск живых объектов и за дефрагментацию кучи. Поиск живых объектов дешевле чем подсчет ссылок (точнее приблизительно равен, но подсчетом ссылок нужно заниматься чаще).
Это если не делать умного подсчёта ссылок.

VD>Вот этот то код и создает основной оверхэд от GC, а вовсе не сам GC. В серверных GC этого кода может и не быть, но они могут давать заметные даже не глаз задержки. Причем в некоторых приложениях (где графы объектов малы) задержек не видно. А в некоторых они могут быть вдины.
Это не совсем так. Write barrier не создаёт задержек, причём на практике таблицы карт лежат в горячем кэше, так что даже это не является проблемой.

VD>2. Сваливанию всех объектов в одну кучу. В больших приложениях графы объектов достигают гигантских размеров, так что сборка последних (не эфемерных) поколений может вызывать заметную на глаз задержку.
3) Алгоритмы для pauseless GC требуют либо слишком большого runtime-оверхеда, либо хитрых хаков на уровне ОС (см.: Azul Systems).

VD>На практике второй пункт без ARC или GC попросту не живет. Да и представитель у такого подхода по сути ровно один — Rust.
Ну вообще-то, есть ещё Cyclon и Ocaml с region inference. Rust — это скорее первый неакадемический представитель.

VD>В двух словах идея управления жизни в Rust сводится к тому, что объекты можно размещать на стеке или в куче (как в С/С++). Но при этом есть специальный вид размещения в куче:

VD>Box — которая обеспечивает условие одиночного владения объектом в единицу времени (т.е. это уникальная ссылка, но контролируемая компилятором).
VD>ARC — ну, с ней все ясно.
Это не совсем так. Box — в Rust'е это прямой аналог "boxed-типа" в С#, то есть типа, который лежит не на стеке. Этот тип может быть совершенно любым. В частности, Arc — это просто один тип "коробки" с разделяемым владением. Обычный "box" — это просто аналог unique_ptr'а. В современном Rust'е это выглядит так:

let boxed1 = box "Hello";
let boxed2 = box(RC) "Hello";

Соответственно, GC-объекты просто будут представлены коробкой типа GC. Она даже уже была, но её выпилили из-за того, что никто её не подерживал.

VD>Причем у этого подхода есть и ограничения. Так указатель в Rust не отслеживается, а значит он не должен сдвигаться. Это значит, что точный GC (GC поддерживающий дефрагментацию) вряд ли может быть использован в Rust.
Нет, не так. В Rust есть полная информация о типах объектов, если не заниматься магией с небезопасным transmute. Тоный GC есть в планах, но пока никто в этом сильно не заинтересован.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, VladD2, Вы писали:

VD>>Ты и автор этого блока просто не знаешь, что в 21 веке эту работу можно переложить на ОС, которая отследит изменение памяти с помощью прерываний. В Винде для этого используется флаг MEM_WRITE_WATCH при вызове функции VirtualAlloc() и GetWriteWatch() для того чтобы получить список измененных страниц.
C>Это очень плохой способ:
C>1) Страница — это слишком большое количество памяти для сканирования. В Java используются карты по 128 байт.

В других источниках я видел, что там 512.

C>2) На больших системах нынче модно использовать hugepages — это страницы размером по 2Мб (или даже 64Мб).

И
3) False positives — метод не отличает изменения указателей от изменения неуказателей.

Здравствуйте, Cyberax, Вы писали:

C>Это не совсем так. Write barrier не создаёт задержек

Только что в Go их добавили — народ жалуется, некоторые программы в полтора раза замедлились.

VD>>На практике второй пункт без ARC или GC попросту не живет. Да и представитель у такого подхода по сути ровно один — Rust.
C>Ну вообще-то, есть ещё Cyclon и Ocaml с region inference.

Только не окамл, а MLKit (реализация Standard ML), и без GC он таки не живет все равно.

Здравствуйте, D. Mon, Вы писали:

C>>Это не совсем так. Write barrier не создаёт задержек
DM>Только что в Go их добавили — народ жалуется, некоторые программы в полтора раза замедлились.
Поправка — write barrier не вызывает долгих пауз, он равномерно замедляет всю программу.

C>>Ну вообще-то, есть ещё Cyclon и Ocaml с region inference.
DM>Только не окамл, а MLKit (реализация Standard ML), и без GC он таки не живет все равно.
Да, точно. Там был чистый ML.

Здравствуйте, D. Mon, Вы писали:

C>>1) Страница — это слишком большое количество памяти для сканирования. В Java используются карты по 128 байт.
DM>В других источниках я видел, что там 512.
Возможно, что поменялось.

C>>2) На больших системах нынче модно использовать hugepages — это страницы размером по 2Мб (или даже 64Мб).
DM>И
DM>3) False positives — метод не отличает изменения указателей от изменения неуказателей.
То есть? Write barrier нужен для того, чтобы отмечать какие части старого поколения нужно повторно сканировать на предмет указателей на новое поколение.