LINUX.ORG.RU

Этот ваш reference counting

 ,


1

4

Во время попытки доказать одному товарищу, что Swift — ненужно, я наткнулся на интересную особенность:

import Foundation

let noLeak = 131028
let withLeak  = noLeak*10

class R {
    var _a : R?
    init(a : R?) {
        _a = a
    }
}

func test(n:Int, leak:Bool) {
    var p0 = R(a : nil)
    var p = R(a : p0)
    for _ in 1...n {
        p = R(a : p)
    }
    if leak {
        p0._a = p
    }
}

test(withLeak, true)
println("Evil leaking function")
test(noLeak, false)
println("Good function")

Первый вызов test просто течёт в лучших традициях Reference Counting, а вот второй падает со stack overflow (деаллокация, похоже, делается рекуррентно).

Интересно, есть ли такое же в Rust?



Последнее исправление: fmdw (всего исправлений: 1)
Ответ на: комментарий от fmdw

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

anonymous
()

Конечно есть, там же тоже RC. И RC надо использовать там где он нужен, а не пихать все подряд переменные в кучу да еще и с определением времени жизни во время исполнения.

Aswed ★★★★★
()
Ответ на: комментарий от fmdw

Хаскель тут так же может упасть по stack overflow при работе с очень длинным списком, когда попытается зафорсить его, например.

Aswed ★★★★★
()
Ответ на: комментарий от Aswed

Нет. deepseq там не случайно воткнут.

fmdw
() автор топика
Ответ на: комментарий от anonymous

Я неточно выразился. Она выделяется на стеке при вызове деструкторов.

asaw ★★★★★
()
Ответ на: комментарий от fmdw

Модифицированный рабочий вариант сабжа должен выглядеть как-то примерно так:

#include <memory>
#include <list>

struct ListNode;
using List = std::unique_ptr<const ListNode>;

struct ListNode {
    const int data;
    const List next;
    
    ~ListNode()
    {
        if(!next)
	    return;
	else {
	    std::list<ListNode*> nodes;
	    for(auto pn = next.get(); pn->next; pn = pn->next.get()) {
		nodes.push_back(const_cast<ListNode*>(pn));
	    }
	    for(decltype(nodes)::reverse_iterator in = nodes.rbegin(); in != nodes.rend(); ++in) {
		const_cast<List&>((*in)->next).reset();
	    }
	}
    }
};

List Cons(int head, List tail)
{
    return List(new ListNode{head, std::move(tail)});
}

List Nil()
{
    return List();
}

size_t len(const List & self)
{
    if (!self) {
        return 0;
    }
    return 1 + len(self->next);
}

#include <iostream>

void test(size_t n)
{
    auto p = Nil();
    for (size_t i = 0; i < n; ++i) {
        auto x = std::move(p);
        p = Cons(1, std::move(x));
    }
    std::cout << "done: " << std::endl;
}

int main()
{
    test(131028);
}
asaw ★★★★★
()

Добрался, наконец, до XCode. Проверил. Таки да, падает. И, похоже, именно поэтому. Что, конечно, суксь.

Miguel ★★★★★
()
Ответ на: комментарий от asaw

У автора приемлемый код. То, что он падает - иллюстрация к обсуждаемой темп, не более. А вот ты добавил отвратительный код.

anonymous
()
Ответ на: комментарий от anonymous

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

asaw ★★★★★
()
Последнее исправление: asaw (всего исправлений: 1)
Ответ на: комментарий от asaw

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

Тебя в последние пару часов кто-нибудь называл идиотом уже?

GC придумали совсем не из-за того, что освобождать память руками - это слишком сложно. Освобождать память руками - это как раз легко, что подтверждается толпами обезьян вроде тебя, пишущих на C++. Проблема в том, что такая работа с памятью в контексте современных процессоров с многоуровневым кэшем и SMP нифига не оптимальна, на что тебе несколько человек в этом треде уже намекнули. Вместо этого ты начал пускать слюну и орать, что компактирующих GC, перемещающих объекты по памяти, в дикой природе не существует, и всё это сказки. А знаешь, почему ты так делаешь? Потому что ты идиот.

hateyoufeel ★★★★★
()
Ответ на: комментарий от asaw

ГЦ не возвращает память системе, дурилка. Так что память из-под мусора освобождать не требуется - прост она это место потом будут записаны другие данные.

anonymous
()
Ответ на: комментарий от asaw

Ты с дуба рухнул? Ты хочешь сказать, что ты при каждой сборке мусора будешь перемещать туда-сюда достижимые объекты, чтобы у тебя фрагментации не было?

Именно так и делают самые эффективные сборщики, да

anonymous
()
Ответ на: комментарий от asaw

Ну если в твоем мире копирование/перемещение памяти - бесплатная атомарная операция, тогда слышал. А так нет.

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

anonymous
()
Ответ на: комментарий от anonymous

Видишь ли в чем дело, объекты в начале кучи - долгоживущие, в конце кучи - короткоживущие.

Эвристики можно наворачивать сколько угодно, всё равно она слабо помогает.

asaw ★★★★★
()
Ответ на: комментарий от asaw

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

Для функциональных языков только такие сборщики и используются. Более того - никакие другие сборщики (равно как и ручное управление памятью) в данном случае использовать нельзя, потому что _тормозит_.

anonymous
()
Ответ на: комментарий от asaw

В джаве говно вместо сборщика. Это всем известно. Мы не о джаве говорим.

anonymous
()
Ответ на: комментарий от Legioner

Может быть и так. Но то, что GC жрёт больше, если не приседать специально (преаллокация всего на старте), это факт (в общем-то очевидный).

Просто чтобы гц эффективно работал, его надо вызывать в определенные моменты. То есть надо уметь отключать сборку. А обычно этого не дают.

anonymous
()
Ответ на: комментарий от asaw

Это частный случай - раз. Памятью в реальной жизни приходится управлять по-настоящему, а не просто копировать всё каждый раз туда-сюда - два.

В реальности - не приходится, представь себе.

anonymous
()
Ответ на: комментарий от asaw

Ты как дятел долбишь одно и то же. «Просто память» может быть только если она упорядочена, а чтобы её упорядочить, нужно копировать, что очень дорого - дороже, чем управлять кучей.

А почему тогда во всех тестах компактификация быстрее?

anonymous
()
Ответ на: комментарий от asaw

Живые объекты, разумеется. Догадайся с десяти раз зачем.

Зачем тебе их копировать при каждой сборке? один единственный раз скопировал и хватит.

anonymous
()
Ответ на: комментарий от anonymous

Для функциональных языков только такие сборщики и используются. Более того - никакие другие сборщики (равно как и ручное управление памятью) в данном случае использовать нельзя, потому что _тормозит_.

Черт, я же совсем забыл о какой секте идет речь: Конспирология как мировоззрение Там эфиродинамика и всё такое, не удивительно, что у вас в JVM GC-говно (и это «всем известно»), а быстро - только копирование.

asaw ★★★★★
()
Ответ на: комментарий от asaw

Самые первые и самые примитивные - это подсчет ссылок. А самые эффективные сборщики на данный момент - это generational перемещающие.

anonymous
()
Ответ на: комментарий от asaw

Эвристики можно наворачивать сколько угодно, всё равно она слабо помогает.

В твоем выдуманном мире - конечно, может, и не помогает. А на практике все именно так и обстоит.

anonymous
()
Ответ на: комментарий от anonymous

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

asaw ★★★★★
()
Ответ на: комментарий от asaw

Черт, я же совсем забыл о какой секте идет речь: Конспирология как мировоззрение Там эфиродинамика и всё такое, не удивительно, что у вас в JVM GC-говно (и это «всем известно»), а быстро - только копирование.

Дурашка, для функциональных языков нормальное явление - выделять и освобождать порядка десятков гигабайт памяти для сотен миллионов объектов за секунды. Попробуй-ка добиться нормальной поизводительности с ручным управлением памяти, не используя арены/собственные аллокаторы.

anonymous
()
Ответ на: комментарий от asaw

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

Когда обезьянки пишут код на джаве - конечно замирает.

anonymous
()
Ответ на: комментарий от asaw

Просто чтобы ты понимал - нормальным control-flow программы yf l;fdt считается отсутствие major gc. Если ты пишешь программы с мемори ликами - сам себе злой буратино.

anonymous
()
Ответ на: комментарий от anonymous

Конечно:

We find that copying garbage collection can require six times the physical memory as the Lea or Kingsley allocators to provide comparable performance. We also show that garbage collection suffers orders-of-magnitude performance penalties when paging occurs. This first-ever comparison of explicit memory management and copying garbage collection shows where garbage collection must improve in the future. While we expect the incorporation of L3 caches to minimize the impact of garbage collection’s poor L2 locality, the relative cost of disk latency continues to grow. Improving the space efficiency and page-level locality of garbage collection will thus become increasingly important.

http://people.cs.umass.edu/~emery/pubs/04-17.pdf

Теперь я жду твои пруфы.

asaw ★★★★★
()
Ответ на: комментарий от asaw

Опять опущенная джава, измерения проведены на задачах, специально заточенных под ручное управление памятью. Кого-то пытаешься наебать, петушок? Покажи мне, как пара миллиардов маллок+фри оказывается быстрее выделения и сборки пары миллиардов объектов с перемещающим гц.

anonymous
()
Ответ на: комментарий от asaw

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

то что ты не умеешь программировать ты уже успешно показал, можешь дальше не продолжать.

maloi ★★★★★
()
Ответ на: комментарий от anonymous

Покажи мне, как пара миллиардов маллок+фри оказывается быстрее выделения и сборки пары миллиардов объектов с перемещающим гц.

почему он тебе должен приводить доказательства, когда утверждал ты?

anonymous
()
Ответ на: комментарий от asaw

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

maloi ★★★★★
()
Ответ на: комментарий от anonymous

почему он тебе должен приводить доказательства, когда утверждал ты?

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

anonymous
()
Ответ на: комментарий от anonymous

почему он тебе должен приводить доказательства, когда утверждал ты?

Да как угодно, вот, например

ручное управление памятью, сишка:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&amp...

managed, c# mono:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&amp...

это не учитывая того факта, что сам по себе mono тормознее сишки и сборщик был неоттьюнен.

тьюненый вариант по скорости выделения памяти будет отличаться вот от этого:

http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&amp...

на урвоне стат. погрешности (т.к. алгоритм одинаковый)

anonymous
()
Ответ на: комментарий от quiet_readonly

Ну ARC тоже тормоз. А сборщик дает преимущества и по скорости=) Для операций выделения памяти, копирования ссылок и т.д. Да, во время сборки у нас могут быть неприемлемые тормоза. А еще нам для эффективной работы нужно иметь больше памяти.

Так что все зависит от задачи. В несуществующем идеальном языке был бы выбор.

forCe
()
Ответ на: комментарий от asaw

Не хотел бы вмешиваться, но тот код на крестах, куда вы влезли, был просто переписанный код Rust. В теме спросили, будет ли в C++ такое же поведение.

Ваш же деструктор, объективно, плохо написан. Вы же не пишите на C++ на работе?

forCe
()
Ответ на: комментарий от hateyoufeel

По первой ссылке в сишке используется дефолтный аллокатор. В решении на расте - арены. Вариант сишки с аренами быстрее раста.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.