О хвостовой рекурсии

Расплывчатое, но тем не менее ты знаешь что там будет внутри. Я вот не совсем представляю

ну вот что-то типа этого:

main.cpp

#include "gc.hpp"

int main(int argc, char *argv[])
{
	GString X = "abc\n";
	GString Y = X;
	Y.output(stdout);
	return 0;
}

#ifndef GC_HPP
#define GC_HPP

#include <stdio.h>

class GString_m;

class GString
{
	private:
		GString_m *m;
	public:
		GString();
		GString(const char *);
		GString(const GString &);
		const GString &operator=(const GString &);
		int output(FILE *f) const;
		virtual ~GString();
};

#endif

#include <string.h>

#include "gc.hpp"

class GString_m
{
	friend class GString;
	private:
		char *str;
		int n_links;
	public:
		GString_m() : str(NULL), n_links(1)
		{}
		GString_m(const char *s) : n_links(1)
		{
			str = new char[strlen(s) + 1];
			strcpy(str, s);
		}
		virtual ~GString_m()
		{
			delete[] str;
		}
};

GString::GString()
{
	m = new GString_m;
}

GString::GString(const char *s)
{
	m = new GString_m(s);
}

GString::GString(const GString &y)
{
	m = y.m;
	m->n_links++;
}

int GString::output(FILE *f) const
{
	return fprintf(f, "%s", m->str);
}

GString::~GString()
{
	if(!--m->n_links)
		delete m;
}

Это хорошо. Но всё равно ref. counting - invoke этого удалятора будет срабатывать при обнулении количества ссылок за счётов деструкторов стековых объектов, сам счётчик будет накручиваться за счёт конструкторов копирования. Tracing GC иначе работает, только ref. counting находит применение в C++, а tracing - как-то не очень.

Ну это и есть счётчик как в shared_ptr.

Я бы предпочёл квалификацию доступа, чем полное закрытие полей (смешно же - не иметь хотя бы const доступа к полям структуры без правки исходников или хаков).

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

Такая техника будет работать всегда

вот в прошлом посте такая техника уже не сработает - нет там указателя на данные. Есть указатель на класс, в котором данные. ИЧСХ, в hpp файле нет даже этого класса.

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

каких полей?

например, sockaddr_in всегда можно привести безопасно к sockaddr

только потому, что создателям стандарта нужен был ООП, но у них не было C++, а был только Си. Вот и пришлось им кастовать структуры. Хотя по уму это должно делатся наследованием, (почти)без всяких кастов. Кастовать придётся разве что базовые классы в производные, для описания универсальных функций, которые должны работать с базовыми классами. И то это нужно лишь для обеспечения каких-то особенностей отдельных сокетов. И для этого есть dynamic_cast<base>.

А вот зачем тебе понадобился reinterpret_cast, мне до сих пор не ясно. Доказать, что на C++ можно писать быдлокод? Молодец, ты это доказал.

Классы с закрытыми полями точно так же можно привести к зеркальным-классам в которых всё открыто.

сдуру можно и йух сломать.

Это хорошо. Но всё равно ref. counting - invoke этого удалятора будет срабатывать при обнулении количества ссылок за счётов деструкторов стековых объектов, сам счётчик будет накручиваться за счёт конструкторов копирования. Tracing GC иначе работает

с этого места подробнее можно?

Ну это и есть счётчик как в shared_ptr.

вот только указатели ты туда засунуть не сможешь. Разве что так:

	char *z = new char[123];
	const char *s = "test\n";
	char *z1 = z;
	while((*z1++ = *s++));
	GString Z(z);
	delete[] z;
	Z.output(stdout);

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

Какая забота, однако :) Кому хуже станет от того, что можно будет посмотреть нормально на все поля класса? Их же всё равно можно посмотреть. Может у нас непредвиденная ситуация и это нужно для дебага, библиотека вообще не наша, так что либо идти патчить, либо хачить, вместо нормального написания кода.

Если-бы C++ позволял даже читать закрытые данные, то код поломался-бы.

Да нет вроде. Если я прочитаю твою *m, то не смогу её никак использовать кроме как адрес некого opaque типа который ты не хочешь конкретизировать. Ничего не сломается. А вот если в private будет int internal_valuable_data которую мне _нужно_ знать, то, опять же, ничего не сломается, а польза от чтения может быть.

каких полей?

В POD и standard layout классах.

Хотя по уму это должно делатся наследованием

Okay.

А вот зачем тебе понадобился reinterpret_cast, мне до сих пор не ясно.

Покажи как сделать пример с ptr выше без них или обычных сишных кастов тогда.

с этого места подробнее можно?

Что именно? Я неправильно про unique_ptr пересказал или работа tracing GC интересует? Есть RC (простая форма GC), а есть tracing (сложная). Это вещи разные. Tracing консервативен если у него мало информации (или ему не нужно копировать и консервативность - фича) и accurate если ему дают достаточно этой информации (как в LLVM). Сам по себе хороший tracing по части аллокации и освобождения похож на инверсный вариант системного аллокатора - системный malloc бродит по куче, ищет в ней себе места, записывает размеры и прочие данные про аллоцированные объекты, но free может работать очень быстро. В случае c tracing GC аллокация работает быстро, но сам сбощик бродит по куче долго. space / time, throughput / latency tradeoff.

Да нет вроде. Если я прочитаю твою *m, то не смогу её никак использовать кроме как адрес некого opaque типа который ты не хочешь конкретизировать. Ничего не сломается.

угу. Если ты ничего не используешь, то ничего и не сломается.

А вот если в private будет int internal_valuable_data которую мне _нужно_ знать, то, опять же, ничего не сломается, а польза от чтения может быть.

польза будет. Например я могу там хранить длину строки, которая тебе несомненно пригодится. Мне это нужно для того, что-бы например уметь мгновенно усекать строки - т.е. в общем буфере m->str лежит «xyzt», а я быстренько ставлю size=1, и переменная у меня становится «x». Удобно? Конечно удобно. Вот только завтра мну переклинит хранить не только длину, но и оффсет, что-бы из «xyzt» сделать «yz». Очевидно, после этой модификации твой код можно будет выкинуть на помойку, особенно, если я захочу хранить не длину строки, а оффсеты начала и конца. Если-бы ты воспользовался предоставленным мной методом get_size() твой код работал-бы дальше, но... Ты решил стать умнее всех.

А вот зачем тебе понадобился reinterpret_cast, мне до сих пор не ясно.

Покажи как сделать пример с ptr выше без них или обычных сишных кастов тогда.

какой именно? может тебе ещё и на ноль поделить?

Если-бы ты воспользовался предоставленным мной методом get_size() твой код работал-бы дальше, но...

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

какой именно?

CTRL-F «struct ptr», но это ещё извращённый пример. Запрещать в сишке и сишко отпрыске касты которые заботливо определены в стандарте для экзотических и не очень случаев это что-то странное. Вообще, имея A <: B или A <: B + Условие(A, B) может быть сколько угодно вполне безопасных и нужных кастов которые по твоей логике - быдлокод.

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

Наконец ты признал, что статическая типизация - это искусственные ограничения :)

Он консервативный.

я не читал предыдущую дискуссию, но для С++ логично иметь именно консервативный GC

А shared_ptr - просто счётчик ссылок и обвязка над обычными new/delete.

а какая разница? речь шла о «порче», нет ручных new/delete - нет порчи

Подсчет ссылок - это не сборка мусора(хотя Objective-C так и живет). И его не надо писать - она уже есть в std::shared_ptr/std::weak_ptr.

Можно подробнее про LLVM и GC?

Можно подробнее про LLVM и GC?

http://llvm.org/docs/GarbageCollection.html - на уровне IR можно добавлять аннотации, так что LLVM будет генерировать stack maps и сборщик сможет по ним идентифицировать root set. Хотя не всех такой подход устраивает.

Подсчет ссылок - это не сборка мусора

Откуда пошло это поверие? Подсчет ссылок - простейшая стратегия сборки мусора.

http://funkyimg.com/u2/2720/689/545067lor.png

Я просто оставлю это здесь :)

я не читал предыдущую дискуссию, но для С++ логично иметь именно консервативный GC

Я там ранее как раз об этом и говорил, то есть о том, что попытка сделать accurate GC для C++ уведёт нас куда-то уже в другой язык, не в С++. В Си и С++ слишком многое не сочетается с теми техниками GC которые используются, например, в JVM или GHC, поэтому то преимущество которое иногда может дать такой GC трудно будет продемонстрировать в GC для C++.

а какая разница?

Просто хотелось акцентировать внимание на том, что tracing GC может сам управлять большими кусками памяти и быть слабо связанным с mm функциями из libc/libstdc++.

Наконец ты признал, что статическая типизация - это искусственные ограничения :)

Главное, что разной степени паршивости :) А так _ограничения_, хорошие или нет, как получится.

Я сейчас проверил на деревьях

А ты как проверял? Создавал большие деревья в куче? Тогда это явно тест скорее аллокатора чем стеков. Как раз подойдёт для демонстрации преимуществ GC по части throughput.

Будем мучать кучу таким кодом:

#include <stdio.h>
#include <stdlib.h>

struct tree {
    int x;
    struct tree *l, *r;
};

void sum(int *z, struct tree *n)
{
    if (n) {
        sum(z, n->l);
        *z += n->x;
        sum(z, n->r);
    }
}

void gen(struct tree **n, unsigned z)
{
    if (n) {
        *n = calloc(1, sizeof(struct tree));
        (*n)->x = z;
        if (z > 1) {
            gen(&(*n)->l, z - 1);
            gen(&(*n)->r, z - 2);
        }
    }
}

void del(struct tree **n)
{
    if (n && *n) {
        del(&(*n)->l);
        del(&(*n)->r);
        free(*n);
    }
}

int main(int argc, char *argv[])
{
    if (argc != 2) return 0;

    unsigned z = atoi(argv[1]);

    struct tree *ns[z];
    int s = 0;
    for (unsigned i = 0; i < z; ++i) {
        gen(&ns[i], i + 1);
        sum(&s, ns[i]);
        del(&ns[i]);
    }

    printf("sum = %d\n", s);
}

теперь сделаем то же самое на Haskell:

import Prelude hiding ( sum )
import Text.Printf
import Control.Applicative
import System.Environment

data Tree = Null | Node Tree Int Tree

sum :: Tree -> Int
sum Null = 0
sum (Node l x r) = sum l + x + sum r

gen :: Int -> Tree
gen n | n < 2 = Node Null n Null
      | otherwise = Node (gen $ n - 1) n (gen $ n - 2)

main :: IO ()
main = printf "sum = %d\n" . foldr ((+) . sum) 0 . map gen . enumFromTo 1 =<< read . head <$> getArgs

получается такая картина:

        tree-malloc                     tree-ghc

z       sec     maxrss  pagefaults      sec     maxrss  pagefaults  gc-time

10              500     150                     1820    512         0.0%
15              560     164                     2164    598         0.0%
20              1188    321                     2360    647         0.0%
25      0.05    8088    2046            0.02    2356    646         17.9%
30      0.57    84644   21184           0.24    2360    647         20.2%
31      0.92    136648  34186           0.40    2356    646         27.2%
32      1.50    220788  55221           0.63    2356    646         19.8%
33      2.39    356932  89257           1.02    2356    646         20.7%
34      3.86    577220  144329          1.67    2360    647         19.6%
35      6.28    933648  233436          2.67    2356    646         20.2%
36      11.35   1398708 776153 + 25758! 4.47    2360    647         19.7%
37                                      7.01    2360    647         19.5%
38                                      11.48   2360    647         20.0%
39                                      18.47   2368    649         20.2%
40                                      29.91   2360    647         19.7%
                                        ...

        system allocs/deallocs          system allocs/deallocs

10      452 / 452                       61 / 59
20      57290 / 57290                   83 / 81
30      7049122 / 7049122               644 / 642 (up to x5)

                                        Alloc rate up to ~2600000000 bytes per MUT second

        without deallocations

        sec     maxrss  pagefaults

35      4.19    1359116 610905

Boehm:

+ #include "gc.h"

-         *n = calloc(1, sizeof(struct tree));
+         *n = GC_malloc(sizeof(struct tree));
+         (*n)->r = (*n)->l = NULL;

-         del(&ns[i]);

z       sec     maxrss  pagefaults

30      0.46    228688  11226

  ^ valgrind:

    28 allocs, 28 frees
    ERROR SUMMARY: 4409 errors from 35 contexts

31      0.89    371124  15662
32      1.40    596260  22893
33      2.54    963868  33034
34      5.60    1442568 119556 + 4!

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

Ну это наебка. strict-аннотации в хаскеле где?

А его нет!

как же «нет»? просто он не показан. Как ещё клиенту класса узнать длинну строки без грязных хаков?

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

дык всегда можно скажем вернуть например константную ссылку на размер строки, если таковая имеется. Или вообще открыть для всех это поле, если по логике работы его менять нельзя. Квалификатор private: как раз и существует для того, что-бы спрятать от клиента класса какие-то детали, которые ему(клиенту) лучше не трогать, ибо они _могут_ поменяться. Если _не_ _могут_, то почему не отдать поле? Ведь

class A
{
    private:
        int x;
    public:
        const int &get_x() const
        { return x; }
};

A a;

int x = a.get_x(); // №1
int x = *((int *)&(a.x)); // №2

Расскажи мне, зачем писать потенциально ненадёжный код №2?

И да, ограничение совсем не искусственное, но наложенное автором class A. Почему он так сделал - пинай его. Если A::get_x() отсутствует, то опять таки - либо пни аффтора, либо форкни этот класс. Городить касты в этом случае - маздайная привычка.

CTRL-F «struct ptr», но это ещё извращённый пример. Запрещать в сишке и сишко отпрыске касты которые заботливо определены в стандарте для экзотических и не очень случаев это что-то странное.

в сишечке касты необходимы для того, что-бы накостылять ООП. Вот например в твоём примере с struct sockaddr касты необходимы для преобразования «базового класса» в «производный» и обратно. Но позвольте, зачем это нужно в C++, в котором ООП и так нативно реализовано, и производный легко превращается в базовый, а базовый можно кастануть безопасным dynamic_cast?

Вообще, имея A <: B или A <: B + Условие(A, B) может быть сколько угодно вполне безопасных и нужных кастов которые по твоей логике - быдлокод.

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

Подсчет ссылок - это не сборка мусора(хотя Objective-C так и живет). И его не надо писать - она уже есть в /std::weak_ptr.

не ты-ли сам демонстрировал кривизну std::shared_ptr? С моим классом так сделай?

Я там ранее как раз об этом и говорил, то есть о том, что попытка сделать accurate GC для C++ уведёт нас куда-то уже в другой язык, не в С++. В Си и С++ слишком многое не сочетается с теми техниками GC которые используются, например, в JVM или GHC, поэтому то преимущество которое иногда может дать такой GC трудно будет продемонстрировать в GC для C++.

потому-что это преимущество редко нужно. Вообще. Именно потому ЯП вроде жабы обычно работают намного медленнее, чем скажем С++. Но, в случаях, когда задача такая, что тебе нужен именно accurate GC, ничто не помешает реализовать его и на C++. Пойдёт тебе такой GC, который при free() аккуратно раскладывает мусор по кучкам размером 2,4,8,16,32... байта, а при malloc() берёт кусок из нужной кучки? Конечно free() может быть отложенной на любое время (самый простой вариант - подсчёт ссылок: если ссылок 0, то кусок считается мусором). Такой код у меня есть, если тебе интересно. Если ты против этого метода - расскажи, что тебя не устраивает?

Просто хотелось акцентировать внимание на том, что tracing GC может сам управлять большими кусками памяти и быть слабо связанным с mm функциями из libc/libstdc++.

ну вот мой код как раз и слабо связан с libstdc++, потому-что malloc() оттуда выделяет почти всегда память из заготовленных куч мусора, а не из системной памяти. Ну а освобождает(в систему) только в том случае, если мусором становится посл. объект.

А ты как проверял? Создавал большие деревья в куче?

нет конечно. Я создавал небольшие деревья в несколько тыс. узлов в куче, и после _каждого_ добавления узла считал сумму всех узлов. Даже если дерево получалось-бы идеально сбалансированным (а это не так), то время подсчёта суммы было-бы никак не меньше C1*(N*log2(N)), что намного больше добавления узла, которое у меня C2*log2(N). При этом C1 ≈ C2. В итоге, практически всё время ушло именно на обход дерева, код которого я и предоставил. Если хочешь, могу целиком выложить...

Будем мучать кучу таким кодом:

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

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

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

почему подсчёт ссылок не может автоматически отслеживать циклические ссылки? В C++ для этого всё необходимое имеется - если мы ссылаемся на this, то это никакая не ссылка(в смысле GC), а та же самая переменная. Потому код x=x; не приведёт к циклу. Этот код будет просто выкинут компилятором, т.к. ничего не делает. Как и код

x=y;//(1)
y=x;//(2)

x.M->links--; // в деструкторе x
x.M = y.M, y.M->links++; // в x.operator=()

Т.о. мой код не подвержен образованию «островов», как эта ваша ява.

Подсчет ссылок не может автоматически отслеживать циклические ссылки по определению. У тебя поле одного объекта может ссылаться на другой объект, поле которого ссылается на первый объект. И все.

В С++ для этого std::weak_ptr нужно юзать. В Objective-C - weak. Если есть нормальный GC - это не нужно(там мягкие ссылки используются немного для других задач).

strict-аннотации в хаскеле где?

За счёт ленивости такой результат и есть. Со strict совсем хреново получается.

А какие острова в Java? Ее GC отслеживает циклы.

как же «нет»?

Иначе бы не было смысла читать приватное поле. Я говорю о случае когда getтера именно нет, не предусмотрели его, а почитать класс надо.

А вот код №2 - сломается.

Не «сломается», а «не скомпилируется». Так как приватный x по которому разрешено константное чтение вида a.x просто исчезнет.

либо пни аффтора, либо форкни этот класс

Вот, о том и речь - о бессмысленной лишней работе. Вместо того чтобы просто написать object.private_field_for_const_reading.

зачем это нужно в C++, в котором ООП

Для C++-- без ООП :)

базовый можно кастануть безопасным dynamic_cast

А теперь это же, но без RTTI и/или для неполиморфных классов.

ну-ка расскажи мне с примерами, зачем эти касты нужны?

static_cast годится только для кастов между типами для которых A <: B понимается в смысле представления о подтипировании в C++, то есть только для числовых типов разных размеров и указателей на типы связанные отношением наследования. dynamic_cast делает то же, но ещё, за счёт RTTI, проверяет typeid и обнуляет указатели в случае плохих даункастов. Всё остальное C++ не умеет кастовать никак, кроме как с помощью reinterpre_cast и c-style casts.

В Си касты имеют отношение исключительно к layouts, так что для любых типов с A <: B в смысле layouts можно делать безопасные A -> B и, при соблюдении определённого условия, - B -> A, то есть работать с областью памяти как с объектом то одного, то другого типа. Что это будет - адреса как числа, числа как адреса или разные POD-классы, - зависит от того зачем нам нужно работать с плоской памятью как с объектом разных типов с разными или одинаковыми layouts. Ну, например, пакет какого-нибудь протокола можно описать множеством разных структур никак не связанных наследованием, читать и писать эти структуры с помощью write/read и send/recv совершенно без разбора и кастовать структуры друг к другу чтобы почитать пакет в той или иной интерпретации. Ну или тегированные указатели делать - уже приводил пример. Что угодно может быть. В С++ это ещё и костыль для чтения закрытых классов.

Зачем читать закрытые классы? Или зачем закрывать то, что нужно читать?

Так что, ИМХО, но если это и должно позволяться, то именно что через костыль. Чтоб говно пахло издалека.

Зачем читать закрытые классы? Или зачем закрывать то, что нужно читать?

Shit happens?

Так что, ИМХО, но если это и должно позволяться, то именно что через костыль. Чтоб говно пахло издалека.

Вот в CL можно читать внутренние символы пакета, доступ к ним отличается от доступа к экспортируемым символам. В Haskell никак нельзя использовать внутренние функции модуля. В итоге в CL ты сначала напишешь всё что тебе нужно, а потом, по желанию, пойдёшь жаловаться на API, в Haskell ты сразу пойдёшь делать git clone кода в котором ты ковыряться не планировал.

Можно парочку примеров reinterpret_cast'ов сюда, чтоб не искать? С остальными кастами понятно.

«Напишешь все, что нужно» - это как? Ведь ты мог порушить инварианты и не факт, что это сразу проявится...

В итоге, практически всё время ушло именно на обход дерева, код которого я и предоставил

Это понятно. Но

Я создавал небольшие деревья в несколько тыс. узлов в куче

Меня больше cache misses с page faults волнуют, на фоне них что-то сказать про push/pop vs массив-как-стек сложно.

Можно парочку примеров reinterpret_cast'ов сюда, чтоб не искать?

Там много. Указатели как адреса, адреса как указатели, бинарные структуры данных и их сериализация, тегированные указатели для местных тайптегов и алгоримики. Навскидку:

template<typename T> struct DenseMapInfo<ImmutableList<T> > {
  static inline ImmutableList<T> getEmptyKey() {
    return reinterpret_cast<ImmutableListImpl<T>*>(-1);
  }
  static inline ImmutableList<T> getTombstoneKey() {
    return reinterpret_cast<ImmutableListImpl<T>*>(-2);
  }

template<typename PointerTy, unsigned IntBits, typename IntType>
struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > {
  typedef PointerIntPair<PointerTy, IntBits, IntType> Ty;
  static Ty getEmptyKey() {
    intptr_t Val = -1;
    Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
    return Ty(reinterpret_cast<PointerTy>(Val), IntType((1 << IntBits)-1));
  }
  static Ty getTombstoneKey() {
    intptr_t Val = -2;
    Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
    return Ty(reinterpret_cast<PointerTy>(Val), IntType(0));
  }
  static unsigned getHashValue(Ty V) {
    uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
    return unsigned(IV) ^ unsigned(IV >> 9);
  }
  static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
};

template <typename ImutInfo >
class ImutAVLFactory {

  bool ownsAllocator() const {
    return Allocator & 0x1 ? false : true;
  }

  BumpPtrAllocator& getAllocator() const {
    return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
  }

  ImutAVLFactory()
    : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}

  ImutAVLFactory(BumpPtrAllocator& Alloc)
    : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}

  ~ImutAVLFactory() {
    if (ownsAllocator()) delete &getAllocator();
  }

  /// MemDepResult - A memory dependence query can return one of three different
  /// answers, described below.
  class MemDepResult {
    enum DepType {

      /// Other - This marker indicates that the query has no known dependency
      /// in the specified block.  More detailed state info is encoded in the
      /// upper part of the pair (i.e. the Instruction*)
      Other
    };    /// If DepType is "Other", the upper part of the pair

    /// (i.e. the Instruction* part) is instead used to encode more detailed
    /// type information as follows
    enum OtherType {
      /// NonLocal - This marker indicates that the query has no dependency in
      /// the specified block.  To find out more, the client should query other
      /// predecessor blocks.
      NonLocal = 0x4,
      /// NonFuncLocal - This marker indicates that the query has no
      /// dependency in the specified function.
      NonFuncLocal = 0x8,
      /// Unknown - This marker indicates that the query dependency
      /// is unknown.
      Unknown = 0xc
    };

    static MemDepResult getNonLocal() {
      return MemDepResult(
        PairTy(reinterpret_cast<Instruction*>(NonLocal), Other));
    }
    static MemDepResult getNonFuncLocal() {
      return MemDepResult(
        PairTy(reinterpret_cast<Instruction*>(NonFuncLocal), Other));
    }
    static MemDepResult getUnknown() {
      return MemDepResult(
        PairTy(reinterpret_cast<Instruction*>(Unknown), Other));
    }

template <typename PointerTy, unsigned IntBits, typename IntType=unsigned,
          typename PtrTraits = PointerLikeTypeTraits<PointerTy> >
class PointerIntPair {
  intptr_t Value;
  enum {
    /// PointerBitMask - The bits that come from the pointer.
    PointerBitMask =
      ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1),

    /// IntShift - The number of low bits that we reserve for other uses, and
    /// keep zero.
    IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable-IntBits,
    
    /// IntMask - This is the unshifted mask for valid bits of the int type.
    IntMask = (uintptr_t)(((intptr_t)1 << IntBits)-1),
    
    // ShiftedIntMask - This is the bits for the integer shifted in place.
    ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
  };

  void setPointer(PointerTy Ptr) {
    intptr_t PtrVal
      = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
    assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 &&
           "Pointer is not sufficiently aligned");
    // Preserve all low bits, just update the pointer.
    Value = PtrVal | (Value & ~PointerBitMask);
  }

  PointerTy *getAddrOfPointer() {
    assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
           "Can only return the address if IntBits is cleared and "
           "PtrTraits doesn't change the pointer");
    return reinterpret_cast<PointerTy *>(&Value);
  }
  void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);}

//
// B+-tree nodes can be leaves or branches, so we need a polymorphic node
// pointer that can point to both kinds.
//
// All nodes are cache line aligned and the low 6 bits of a node pointer are
// always 0. These bits are used to store the number of elements in the
// referenced node. Besides saving space, placing node sizes in the parents
// allow tree balancing algorithms to run without faulting cache lines for nodes
// that may not need to be modified.
//
// A NodeRef doesn't know whether it references a leaf node or a branch node.
// It is the responsibility of the caller to use the correct types.
//
// Nodes are never supposed to be empty, and it is invalid to store a node size
// of 0 in a NodeRef. The valid range of sizes is 1-64.
//

  PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;

  /// subtree - Access the i'th subtree reference in a branch node.
  /// This depends on branch nodes storing the NodeRef array as their first
  /// member.
  NodeRef &subtree(unsigned i) const {
    return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
  }

template <typename ImutInfo>
class ImutAVLTreeGenericIterator {
  SmallVector<uintptr_t,20> stack;
public:
  enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
                   Flags=0x3 };

  inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
    if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
  }

  TreeTy* operator*() const {
    assert(!stack.empty());
    return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
  }

  uintptr_t getVisitState() {
    assert(!stack.empty());
    return stack.back() & Flags;
  }

inline hash_code hash_integer_value(uint64_t value) {
  // Similar to hash_4to8_bytes but using a seed instead of length.
  const uint64_t seed = get_execution_seed();
  const char *s = reinterpret_cast<const char *>(&value);
  const uint64_t a = fetch32(s);
  return hash_16_bytes(seed + (a << 3), fetch32(s + 4));
}

  static unsigned getHashValue(ImmutableList<T> X) {
    uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
    return (unsigned((uintptr_t)PtrVal) >> 4) ^
           (unsigned((uintptr_t)PtrVal) >> 9);
  }

template<>
inline Region* RegionNode::getNodeAs<Region>() const {
  assert(isSubRegion() && "This is not a subregion RegionNode!");
  return reinterpret_cast<Region*>(const_cast<RegionNode*>(this));
}

  void DestroyAll() {
    MemSlab *Slab = Allocator.CurSlab;
    while (Slab) {
      char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
                                              (char *)Slab + Slab->Size;
      for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
        Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
        if (Ptr + sizeof(T) <= End)
          reinterpret_cast<T*>(Ptr)->~T();
      }
      Slab = Slab->NextPtr;
    }
    Allocator.Reset();
  }

Ведь ты мог порушить инварианты

Только-чтением?

Подсчет ссылок не может автоматически отслеживать циклические ссылки по определению. У тебя поле одного объекта может ссылаться на другой объект, поле которого ссылается на первый объект. И все.

расскажи - как?

Не «сломается», а «не скомпилируется». Так как приватный x по которому разрешено константное чтение вида a.x просто исчезнет

появится какой-то Y, и скомпилируется. Только неправильно.

Для C++-- без ООП :)

делим на ноль ;)

static_cast годится

не годится. Давай примеры.

Меня больше cache misses с page faults волнуют, на фоне них что-то сказать про push/pop vs массив-как-стек сложно.

а про push/pop vs массив речи и не было. Речь была именно про стек vs массив.

появится какой-то Y, и скомпилируется. Только неправильно.

Какой Y? Покажи на примере. private (protected) это двойная зашита от дурака. Если бы они давали write доступ к non-const полям внутри класса и друзей (наследников) и только read для остальных, то это была бы просто зашита от дурака via const которую можно сломать только с помощью const_cast.

делим на ноль ;)

Изначальный автор STL с тобой не согласен. Ну и не только он, думаю. Кроме ООП есть ещё, по крайней мере, обобщённое программирование на шаблонах.

Update: и много других плюшек.

не годится

ЩИТО? А malloc уже нельзя использовать? А void* вообще? А даункасты?

Меня больше cache misses с page faults волнуют, на фоне них что-то сказать про стек vs массив сложно.

Что значит как?

class B;

class A
{
public:
...
    void set_b(rc_ptr<A> b)
    {
        m_b = b;
    }
 
private:
    rc_ptr<B> m_b;
};

class B
{
public:
...
    void set_a(rc_ptr<A> a)
    {
        m_a = a;
    }
private:
    rc_ptr<A> m_a;
};

...

{
    rc_ptr<B> b;
    rc_ptr<A> a;
    a.set_b(b);
    b.set_a(a);
}
...

Надо ли пояснять, что в реальной ситуации будет не так просто? Можешь еще показать, как ты через RC сделаешь ноду двусвязного списка.

Любой GC такие циклы легко обнаруживает(ибо оперирует понятием доступности, а не числом ссылок). Собственно, Boehm GC(консервативный сишный GC) часто используется в сочетании с подсчетом ссылок как раз для поиска циклов.

C++ без ООП(плюсовые классы - это далеко не всегда ООП) - вполне годная штука. Так что не надо...

Какой Y? Покажи на примере. private (protected) это двойная зашита от дурака. Если бы они давали write доступ к non-const полям внутри класса и друзей (наследников) и только read для остальных, то это была бы просто зашита от дурака via const которую можно сломать только с помощью const_cast.

я уже приводил пример.

польза будет. Например я могу там хранить длину строки, которая тебе несомненно пригодится. Мне это нужно для того, что-бы например уметь мгновенно усекать строки - т.е. в общем буфере m->str лежит «xyzt», а я быстренько ставлю size=1, и переменная у меня становится «x». Удобно? Конечно удобно. Вот только завтра мну переклинит хранить не только длину, но и оффсет, что-бы из «xyzt» сделать «yz». Очевидно, после этой модификации твой код можно будет выкинуть на помойку, особенно, если я захочу хранить не длину строки, а оффсеты начала и конца. Если-бы ты воспользовался предоставленным мной методом get_size() твой код работал-бы дальше, но... Ты решил стать умнее всех.

Изначальный автор STL с тобой не согласен. Ну и не только он, думаю. Кроме ООП есть ещё, по крайней мере, обобщённое программирование на шаблонах.

да. ну и что? Мы сейчас про C++ или про STL разговариваем?

ЩИТО? А malloc уже нельзя использовать?

в смысле malloc(3) в C++? нельзя. для этого есть new.

А void* вообще?

в C++? нельзя. Зачем?

А даункасты?

есть dynamic_cast, этого мало?

Надо ли пояснять, что в реальной ситуации будет не так просто? Можешь еще показать, как ты через RC сделаешь ноду двусвязного списка.

могу. А что?