Rust и двусвязный список

Вот чё за прикол юзать какие-то заднеприводные либы в примере для чатика? Не то что в gcc нет, я в гугле эту меморию набрал, хрен что нашёл.

В любом случае, судя по коду, ты забенчил производительность OoO. Замени

for (uint64_t ii: indices_) {
            sum += buffer_[ii];
        }

на

const uint64_t mask = (1ull << 30) - 1;
for (int i = 0; i < 1024/16*1024*1024; i++) {
            sum += buffer_[sum & mask];
        }

и получишь паттерн, более соответствующий обходу списка.

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

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

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

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

Bingo! Только не OoOE, а параллелизм памяти. 2 канала DDR4 дают до 32 загрузок в параллель. И эксплуатировать этот параллелизм можно даже на in-roder superscalar CPU, потому что ответственен за него контроллер памяти.

Твой код дает:

Done. 67108864 ops in 1879.51 ms, 28.01 ns/op

Т.е. среднее время доступа всё равно в 2.5-3 раза меньше задержек RAM. Ты прав в том, что правильная организация данных в памяти решает. Просто эта «правильная организация» – (в большинстве случаев) не массив. Любой алгоритм генерирует семейство паттернов доступа к данным. Данные надо организовывать в памяти так, чтобы архитектура памяти могла эксплуатировать присущий паттерну доступа параллелизм. И далеко не всегда это будет массив. Даже для GPU, которые изначально под массивы делались.

«что будет с вашими индексами, если придется удалить какой-то элемент»

Вы код видели? - Похоже что нет.

По индексам хранится АДРЕС след и предыдущего члена списка. До тех пор пока существует данный узел у него есть индекс с указателем на другой узел. Если узел удаляется, то удаляется и индекс. И массив линков точно так же чистится при удалении данного узла. Другой узел меняет свой индекс на любой другой согласно логики - например следующий.

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

Я вообще не вижу разницы.

I Обычный вариант:

node0           node1           node2

next0 = &node1 next1 = &node2 next2 = &node0 prev0 = &node2 prev1 = &node0 prev2 = &node1

1. next0 = next1
2. prev2 = prev1
3. del node1 - лишняя долгая операция или утечка памяти!

II Индекс вариант.

node[0]             node[1]             node[2]

link[0]=&node[0] link[1] = &node[1] link[2] = &node[2] nid[0]=1 nid[1]=2 nid[2]=0
pid[0]=2 pid[1]=0 pid[2]=1

1. nid[0] = 2;
2. pid[2] = 0;

Если операции удаления частые, то удалять сами узлы - элементы массива вообще не обязательно. Можно помечать их как пустые и использовать для вставки элемента. Утечек памяти НЕТ!

После использования 2 массива удаляются всего 2мя операциями.

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

Такой вариант быстрее! чем обычный и занимает меньше места в памяти.

Удалять и добавлять элемент при необходимости выделением/освобождением памяти это изврат.

На самом деле хранить можно и нужно не сами индексы, а смещение относительно данного узла. Т.е. не nid[1] = 2; а nid[1] = +1;

Это позволяет соединять 2 таких списка в один. Или делать другие операции более быстро и просто.

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

Тот указатель это по сути тот же самый индекс, только в размере памяти. И он всегда 64битный - использует больше памяти. В то время как индекс может быть любым в зависимости от потребностей. и 8 битным и 32 и 64.

Работать с индексами и быстрее И безопаснее.

del node1 - лишняя долгая операция или утечка памяти!

А пулы и Slab-аллокаторы еще не изобрели?

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

При росте разрядности PC от 16 до 32 и далее до 64, хотя таких компов ещё никто не сделал! максимум есть 48 кажется. Использование указателей кроме необходимых случаев вредно и не эффективно. Тем более если размерность единицы данных не растёт так же быстро как разрядность шины адреса. А она точно не растёт!

Обычно с ростом числа элементов растёт и размер узла. Либо это структура, либо это какой-нибудь double 64 и более бит. В таком случае указатель используется совершенно не эффективно.

Т.е. он растет на +4 или +8 или больше при каждом следующем элементе. Это значит, что младшие биты 2 или 3 вообще не используются. Т.е. мы используем 64 бита для хранения нечто, которое по факту 48-3 = 45 бит или меньше. И где с вероятностью 99% 32 бита тоже будет достаточно.

А пулы и Slab-аллокаторы еще не изобрели?

А это без разницы. Время на это все равно теряется. Само по себе обращение к ядру не бесплатно.

И самое худшее когда это происходит случайным образом когда по прошествии долгого времени вдруг система засыпает и задержки в критических точках начинают убивать производительность.

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

Нельзя заранее сказать, что это нечто займет X msec.

код у вас странный.

DoubleLinkedList(int size):size(){
	links = malloc (size * sizeof(DLLNode*));
	nodes = malloc (size * sizeof(DLLNode));

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

опять же тезис о том, что списки гетерогенны по природе своей, вы не слышите, а если б услышали, то не аллокировали бы под ноды массив. СПИСКИ НЕ СОСТОЯТ ИЗ ЭЛЕМЕНТОВ ОДНОГО ТИПА!!! а массивы - состоят.

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

Bingo! Только не OoOE, а параллелизм памяти.

Не, подозреваю что именно OoO. Как оно работает? Ну на самом деле я не знаю, есть 2 варианта. Вариант, что умный компилятор раскидал твой код на векторные инструкции, а мой не смог тоже нельзя отбрасывать, но я таки отброшу, предположу что компилятор сгенерировал скалярный код. Как в таком случае может появиться разница? Декодер видит чтение из памяти суммирование и сохранение, отмечает зависимости и отправляет на исполнение. Операции зависают в виду неготовности памяти, но декодер это не беспокоит. Потом видит следующую итерацию, тоже декодирует, только уже в другие хардварные регистры, потом ещё раз и ещё раз. Видимо где-то на 4й итерации регистровый файл кончается, или может OoO окно, а старые операции всё ещё стоят и ждут, и новые так же, хотя запрос на чтение уже отправлен. Потом, когда приедут данные, он по быстрому просуммирует всё и перейдёт к следующим 4м итерациям.

Ну или это же сделал компилятор, запихал 4 64битные операции в 256-битному avx-регистру и дальше та же схема.

Ты прав в том, что правильная организация данных в памяти решает. Просто эта «правильная организация» – (в большинстве случаев) не массив.

Ну как сказать. Вот твой бенч замерил какой контейнер? vector<unique_ptr<smth>>. Всё-таки одна косвенная адресация на айтем массива присутствовала, но переход к следующему не требовал узнавать адрес. А после моего патча замерили фактически, list<smth>, элемент как бы на месте прямо в ноде, но переход к следующему снова требует косвенности. И уже проседание в 4 раза. А представь, если бы мы замеряли не vector<unique_ptr<smth>>, а vector<smth>. Или хотя бы vector<vector<smth>>. Насколько бы выросла пропускная способность? Даже для смеха можно тип smth сделать большим, чтоб не было читерства с чтением из одной строки кэша.

for (int i = 0; i < 1024/16*1024*1024; i++) {
            sum += buffer_[i * 16]; // каждый следующий адрес на 128 байт отступает, линия кэша вроде как раз 128
        }

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

В общем префетчеры хороши, но тоже любят чтоб о них заботились и не предлагали им догадываться, что там где-то далеко лежит.

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

Но мне другое не нравится - почему в ваших тестах хранятся такие маленькие, и к тому же одинаковые объекты. Вот для примера, в текстовом редакторе в A2 текст хранится как двусвязный список «кусочков»:

	Piece* = окласс
	перем
		next*, prev* : Piece;
		len*, startpos* : размерМЗ; (* в литерах *)
		attributes* : Attributes;
		pstyle* : ParagraphStyle;
		cstyle* : CharacterStyle;
		link* : Link;

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

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

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

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

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

Не, подозреваю что именно OoO. Как оно работает?

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

А как там оно (алгоритмика) реализовано на уровне кэшей и контроллера памяти – это обычно страшная коммерческая тайна. Вендоры никому про это не рассказывают. Так что мы можем только гадать.

Вот твой бенч замерил какой контейнер? vector<unique_ptr>

vector<uint64_t>. там используется второй массив со случайно сгенерированными индексами в первый. Это просто для того, чтобы не бенчмаркать RNG. Индексный массив читается последовательно, т.е. не вносит в итоговую среднюю задержку заметного смещения.

То, что ты предложил – это ввести зависимость по данным между итерациями, что отключило OoOE (и, скорее всего, сгенерировало худший код, без векторизации – это не так важно). Но контроллер памяти как-то вырулил даже в этой ситуации. На сколько я эту тему знаю, там «под капотом» у железа куча разных оптимизаций, каждая из которых дает пару процентов к производительности, но все вместе они «вытягивают» в разы.

В общем префетчеры хороши, но тоже любят чтоб о них заботились и не предлагали им догадываться, что там где-то далеко лежит.

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

7 ns на одно обращение к памяти, что примерно равно 30 тактам.

7ns? не верю что-то

это на каком железе?

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

Это просто khrundel полемическим приемами увел дискуссию глубоко в частный случай. Если строить структуру данных на статическом массиве (единым куском, один раз выделенном), то у такой структуры будет плохое время обновления. Если хочется и быстрых (относительно O(N) для статического случая) апдейтов, и быстрого чтения одновременно, то применяется комбинированный подход. Для списков и очередей это deque, для деревьев – семейство b?tree с высокой арностью. И т.д.

Для твоего случая редактора текста это будет rope. Только в листьях не пара символов, а вполне можно и ~4K блоки текста хранить. А если кто сейчас текстовые редакторы всё еще на связных списках делает, тот ССЗБ.

Там khrundel уже разоблачил г-на копперфильда. У DDR4 может быть до 32 загрузок одновременно при двух каналах. При чтении по псевдо-случаным адресам и при отсутствии зависимости по данным меду итерациями, произошло эффективное заполнение внутреннего параллелизма DDR. Но потом, как показали следующие тесты, не всё определялось одним только OoOE.

все же пожалуйста прогони свой тест честно, т.е. time ./a.out

на 8ГБ 7ns? я дико удивлен

Там всё честно, и железо названо, и time a.out приведен. Могу отодрать от Мемории, сам запустишь.

На, проверяй.

#include <chrono>
#include <iostream>
#include <vector>
#include <random>

static inline uint64_t getTimeInNanos() {
    return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}

int main(void)
{
    using RngEngine64 = std::mt19937_64;

    std::mt19937_64 engine_;
    std::uniform_int_distribution<uint64_t> distribution_;

    auto random = [&](){
        return distribution_(engine_);
    };

    size_t size_ln2 = 30;
    size_t buf_size = 1ull << size_ln2; // 8GB
    size_t idx_size = buf_size/16;

    uint64_t mask = buf_size - 1;

    int64_t t0, t1;
    uint64_t sum{};

    auto tx = getTimeInNanos();
    {
        std::vector<uint64_t> buffer_(buf_size);
        std::vector<uint64_t> indices_(idx_size);

        for (auto& v: buffer_) {
            v = random();
        }

        for (auto& v: indices_) {
            v = random() % buf_size;
        }

        t0 = getTimeInNanos();

//        for (size_t c = 0; c < idx_size; c++) {
//            sum += buffer_[sum & mask];
//        }

        for (auto ii: indices_) {
            sum += buffer_[ii];
        }

        t1 = getTimeInNanos();
    }
    auto tz = getTimeInNanos();

    double ns_in_ms = 1000000;
    double time = t1 - t0;

    std::cout << "Done. " << idx_size << " ops in " << (time/ns_in_ms) << " ms, " << time/idx_size << " ns/op" << std::endl;
    std::cout << "Setup time: " << ((t0 - tx)/ns_in_ms) << " ms, total " << ((tz - tx)/ns_in_ms) << " ms, sum = " << sum << std::endl;

    return 0;
}

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

#include <iostream>

using u08   = unsigned  int8_t;
using u16   = unsigned int16_t;
using u32   = unsigned int32_t;
using u64   = unsigned int64_t;

using Item  = u32;
using Index = u32;

const Index memory_size_in_bytes = 1<<(10+10+9)  ;                      // should be 2^n
const Index memory_size_in_items = memory_size_in_bytes / sizeof(Item); // should be 2^n

// quick_random returns value that: 0<= value < maximum

inline Index quick_random( Index maximum )
{
  static Index seed=1;
  seed += seed<<2;
  return (seed & (2*maximum-1))>>1 ;
}

int main()
{
  auto array = new Item[memory_size_in_items];

  for(Index i=0; i<memory_size_in_items; ++i )
  {
    array[quick_random(memory_size_in_items)] = i;
  }

  Item result = 0;

  for(Index i=0; i<memory_size_in_items; ++i )
  {
    result += array[i];
  }

  std::cout << (long long)(result) << "\n1 секунда теста даст время " << (1e9/memory_size_in_items)  << '\n';
  return 0;
}

Алё! new на таких размерах дорогой! Его, а так же инициализацию массива нужно убирать из теста. Я там выше тебе адаптированный текст теста дал с детальными замерами.

ты сначала дай мне time ./a.out моего кода а потом обсуждать будем — у меня немного другое меряется, чем у тебя (поскольку меня оно больше интересовало — так сложилось)

и вообще, разговоров без полного time ./a.out моего кода НЕ ВЕДУ — тут тебе не java

victor@victor-X570:~/tmp$ time ./a.out
4261412864
1 секунда теста даст время 7.45058

real	0m0.810s
user	0m0.714s
sys	0m0.096s

UPD: Извиняюсь, в первый раз скомпилировал без -O3.

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

Что такое заранее заданный? Он ВСЕГДА когда-то становится известным. Сейчас 3, завтра 1000. В чем проблема? В единицу времени ВСЕГДА известно солько элементов списка имеется. Это 100%. Иначе быть не может.

Нет. Элементы не обязательно одного типа. Я написал int value; Вы можете вместо этого поставить указатель на что угодно. Можно хранить указатели на что-то еще.

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

Короче Ваши аргументы НЕ работают.

inline Index quick_random( Index maximum )
{
  static Index seed=1;
  seed += seed<<2;
  return (seed & (2*maximum-1))>>1 ;
}

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

2 12 62 312 1562 7812 39062 195312 976562 688508 296814 435496 80330 401652 959686 604128 923490 423148 18590 92952 464762 226660 84726 423632 21010

Что такое заранее заданный? Он ВСЕГДА когда-то становится известным. Сейчас 3, завтра 1000. В чем проблема? В единицу времени ВСЕГДА известно солько элементов списка имеется. Это 100%. Иначе быть не может.

вы пишете компилятор. область видимости, это список обьектов декларировнных в данной области, это есть список. у вас в конструкторе - размер списка… какой размер ставить в данном случае?

за какое-такое «ранее» вам известно сколько в компилируемом файле видимо внешних обьектов? в с++ за счет инклудов их могут быть десятки тыщ. какой ставить размер?

вложенность областей видимости не органичена. и в каждой будет массив на десятки тыщ ваших линков и нод??? и ваше творение будет пожирать память просто так.

как то нет увернности что это нормальный рандом

для криптографии даже и близко не подойдет, но для случайного прохода по памяти годится

грубо говоря это 5 в степени эн по модулю длинны буфера (и чуть подвинутое вправо)

так верю

даже несмотря на new (к которому ты придирался) все равно у тебя получилось 6нс (даже быстрее чем 7)

хотя там 512МБ, а не 8ГБ — но все равно надеюсь больше, чем кэш проца?

У меня кэш 32 мб на CCD. В принципе, 512 - это более, чем.

OoOE совсем не про это.

Про это. Собственно наши с тобой примеры отличаются 2мя элементами. У тебя нет зависимости между итерациями при вычислении адреса. И ты кроме запроса к буферу делаешь так же обращение к вектору индексов (кстати, по твоим же словам не самому эффективному методу организации памяти). Казалось бы, ты производишь больше чтений, но при этом почему-то твой код работает быстрее моего в 4 раза. Как так получилось? Между запусками бенчмарка ты поменял DDR4 на какую-то у которой меньшая способность одновременно обрабатывать несколько запросов? Нет. Может контроллер памяти в твоём процессоре сгорел и больше не может? Тоже нет. Я отключил параллелизм исполнения программы (неважно даже, это эксплицитный параллелизм векторизации или имплицитный OoO) и сразу всё сломалось. Ergo я был абсолютно прав, а ты - абсолютно не прав.

Но главное не это, а тот факт, что я, введя зависимость адреса для следующей итерации, сэмулировал настоящее поведение листа. Именно так, ты не можешь узнать адрес 2го узла пока не прочитал память первого.

vector<uint64_t>. там используется второй массив со случайно сгенерированными индексами в первый.

Я не о твоих намерениях, а о том что ты реально пробенчил. Пробенчил ты именно вектор указателей. Ты последовательно брал элементы, расположенные в памяти один за другим и на основе их значений получал указатель на данные в другом месте. Это vector<unique_ptr<uint64_t>>. Не самый дружественный кэшу контейнер. Если бы внутри был указатель не на один элемент, а на сотню, т.е. vector<vector<uint64_t>> то суммирование их было бы в разы быстрее. Но даже этого хватило чтоб дать 4хкратное преимущество перед списком.

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

Не знаю какие ты там разы себе придумал, я вот открываю википедию: https://en.wikipedia.org/wiki/CAS_latency и читаю там про латентность DDR4 в 8-15 наносекунд, в зависимости от модели. Но если перейти от латентности к тактам процессора, то в случае CPU, работающего на 3.5ГГц, предложенный мой бенч показывает 3.5 т/нс * 28 нс/итерацию = 98 такта/итерацию. почти 100 циклов на одно суммирование, на процессоре способном выполнять несколько инструкций за такт. Просто подумай, сколько нужно операций проводить над одним элементом чтоб можно было сказать, что запрос к адресу следующего элемента скомпенсирован вычислениями над текущим.

Это просто khrundel полемическим приемами увел дискуссию глубоко в частный случай.

А зачем вестись? На вопрос «всегда ли массив подходит на замену списка» уже был дан исчерпывающий ответ. Основной полемический приём данного персонажа состоит в том, что он обзывается, его надо просто послать далеко, тогда и остальные приёмы не сработают.

А зачем вестись? На вопрос «всегда ли массив подходит на замену списка» уже был дан исчерпывающий ответ.

Не мог бы ты привести ссылку? Потому что я вижу ровно обратное, несколько неудачных попыток придумать специальные условия, в которых список будет вести себя лучше основанных на массиве структур.

А если не можешь, попрошу прекратить клеветать на меня.

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

P.S. Кстати вопрос. При попытке найти обычный динамический массив в RUST во первых выскакивает, что массив обязан быть с фиксированным во время компиляции числом элементов, что есть нонсенс само по себе.

Необязательно, есть безразмерный слайс. Просто раст проверяет индексы, поэтому это либо слайс с известным на этапе компиляции размером ([T; length]), который в машинном коде представлен одним указателем, либо получаемый простым приведением типа из предыдущего безразмерный слайс ([T]), состоящий из 2х указателей. Не уверен, что в безопасном расте есть способ выделить такой слайс напрямую, но если нужно, то делают через создание и заполнение вектора, а потом вызывают into_boxed_slice() и эта функция поглощает вектор, возвращая Box<[T]>

Не знаю какие ты там разы себе придумал, я вот открываю википедию: https://en.wikipedia.org/wiki/CAS_latency и читаю там про латентность DDR4 в 8-15 наносекунд, в зависимости от модели.

Але! Кроме задержки чипа есть еще задержки контроллера и кэшей. И суммарная задержка для R9 5950X и DDR4 3600 составляет примерно 77нс. Я же просто привел тебе пример, что наблюдаемая алгоритмом задержка может сильно отличаться от этого значения (в обе стороны), в зависимости от паттерна доступа к памяти, который этот алгоритм генерирует. На моем тесте получается 6-26нс (без и с OoOE). Что всё равно меньше 77нс в разы.

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

Ты, видимо, читаешь то, что я пишу очень выборочно. Я же именно про это и говорил. Что структура данных может быть значительно эффективней «связанного списка»(х), если она умеет использовать эти самые 100-1000 тактов, которые процессор тратит на ожидание прихода данных из памяти. Я просто хочу указать, что массив тут – лишь частный случай для демонстрации преимущества такого подхода. И всё.

(х) под которым тут понимается любая структура на основе указателей: список, дерево, объектный граф и т.д.

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

Но это не делает тебя здоровым и полноценным и не мешает послать тебя лесом в частном порядке каждому. Что большинство и сделало. В этой ситуации твои полемические приёмы не работают.

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

И ещё раз лично от меня: иди лесом!

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

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

Але! Кроме задержки чипа есть еще задержки контроллера и кэшей. И суммарная задержка для R9 5950X и DDR4 3600 составляет примерно 77нс.

Хмм…

Я не уверен, что ситуацию, когда табличные значения для DDR3600 (от 8.33 нс до 12.5, в зависимости от таймингов и положения ячейки) превращаются в 28 нс, корректно описывать как «кэши и префетчеры спасли от задержек DDR4». Я это привёл как подтверждение, что в задержках порядка 8-28 нс нет каких-то уж слишком удивительных. Более того, я не знаю как надо мерять, чтоб получить 77нс, вроде как мой вариант с зависимым от предыдущей итерации адресом самый упоротый.

Есть ещё токсично-негативный стиль. Хотя, пожалуй, ты прав - на ЛОРе норм.

Касаемо задачи - более реальная задача - это та же реляционная СУБД. Пусть она для простоты будет одноверсионная, однопользовательская, в памяти. Есть таблица с первичным ключём и с ещё одним индексом по другому полю. Операции - вставка, поиск по ключу, выдача элементов по порядку возрастания. Можно ли это реализовать в Расте без unsafe и потери эффективности?

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

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

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

Но это не делает тебя здоровым и полноценным

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

Что большинство и сделало. В этой ситуации твои полемические приёмы не работают.

Должен тебя огорчить, то что ты и твои воображаемые друзья слились не означает, что вы «одержали верх» или что я пользовался какими-то «полемическими приёмами». Это означает просто что вы не смогли придумать вменяемое возражение. Это не твоя вина, дело в том, что я просто в данном вопросе оказался прав. Сложно придумать правдоподобную задачу, в которой при этом связный список окажется лучше массива, или чего-то сделанного поверх массивов.

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

Клевета - это распространение заведомо ложных и порочащих сведений. Как очевидно из моего к тебе обращения, я считаю клеветой твоё утверждение, что якобы вопрос «массивы против списка» рассмотрен и дан исчерпывающий ответ, один я только его не понял. Вот я и прошу предъявить ссылку. Или прекратить клеветать. Я не знаю как можно было перепутать, если не специально.

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

Итак, будет ссылка на исчерпывающий разбор списков/массивов? Или ваше высочество слишком одухотворено, чтоб подтверждать свои слова? Если последнее, то, пожалуйста, будь последовательным и воздержись от обсуждения меня в 3м лице.

Можно ли это реализовать в Расте без unsafe и потери эффективности.

Нет, конечно же, если говорить про unsafe. Модель владения в Rust не умеет в обобщенные графы (только в DAG), и следующей «неприятной» находкой будет дерево с parent links. По ровно той же причине мы не можем полностью полагаться на RC (вообще, а не только в Rust) как на сборщик мусора, и нам нужно «руками» расставлять хаки weak_ptr, и особым образом с ними работать.

И тут как раз всплывает «грубая ошибка дизайна» состоящая в том, что unsafe назвали «unsafe», а не, скажем, «unchecked» или еще как, что бы более соответствовало тому, что реально происходит. Слово unsafe формирует у людей слишком негативный контекст в отношении кода внутри этих блоков, как будто он нежелателен. Корректно написанный код unsafe ничуть не более «опасен», чем остальной «safe» код Rust. Просто контролем системы типов со стороны компилятора он не охвачен. И, что самое главное, «без unsafe вообще» – нельзя. А, как мы знаем из этики, «неизбежное зло» на самом деле вовсе и не зло.

Тут нужно просто расслабиться, перестать бояться unsafe и начать жить. Единственное, что окажется, что Rust в целом всё же совсем не такой «безопасный», как про него говорит реклама. Ну так то такое: «не обманешь – не продашь». (с) Народная мудрость.

Rust «безопасней» С++, так как есть возможность явно и однозначно разделить зоны со строгой типизацией и с ослабленной, а так же за счет того, что многие практические случаи неизбежного ослабления системы типов «упакованы» в библиотеки и скрыты за безопасным API.

Но Rust более опасный, чем ванильная Java, так как unsafe всё же использовать придется. В Java его тоже приходится использовать в виде sun.misc.Unsafe, если нужна «ювелирная» работа с памятью. Но такое использование со стороны обычных программистов считается грязным хаком, ломающим оптимизации JVM. В Java Unsafe быть не должно, и всё, что в рамках парадигмы языка, можно писать без него. Просто платформу используют вне парадигмы (для создания СУБД, например).

Касаемо задачи - более реальная задача - это та же реляционная СУБД. Пусть она для простоты будет одноверсионная, однопользовательская, в памяти. Есть таблица с первичным ключём и с ещё одним индексом по другому полю. Операции - вставка, поиск по ключу, выдача элементов по порядку возрастания. Можно ли это реализовать в Расте без unsafe и потери эффективности?

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

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

Тоже мне проблему придумал.

Но Rust более опасный, чем ванильная Java,

Вот это сильно спорное утверждение. Ванильная java с помощью отказа от delete решила проблему use after free, но это лишь один из симптомов общей проблемы с алиасингом указателей, а они не решены вообще никак. С этим пытаются бороться в других GC-языках, поощряющих иммутабельность, но это как-то не очень эффективные программы на выходе даёт. В расте решили кардинально, через владение/заимствование.

Я это привёл как подтверждение, что в задержках порядка 8-28 нс нет каких-то уж слишком удивительных.

Ну про это я и сказал, что иерархия памяти как-то смогла это всё в среднем вытянуть.

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

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

Просто худший для памяти случай IRL не так уж часто и реализуется (к теме про влияние распределения). А если и реализуется, то это не так уже драматически заметно. Переход от 4K страниц к 2G страницам для больших куч не даст 10х прироста, хотя промах в TLB ну очень дорогой. Поэтому, городить какую-то продвинутую структуру данных можно, но только если очень нужно. Они всегда специфичны для задачи, а программирование тоже не бесплатное. Особенно – программирование структур данных.

Я в рамках этого утверждения делаю поправку на парадигму использования языка. В Rust нельзя без unsafe. В Java – можно и нужно, но вот просто мы на Java не будем писать то, что на Rust можно написать с unsafe. Те же, например, продвинутые структуры данных, ювелирно работающие с памятью. Java просто не дает такого тонкого доступа к памяти, как дает Rust. Вот только поэтому Java и безопаснее, по факту.

Т.е. Java безопаснее Rust, но только за счет значительно более слабой в структурном плане модели памяти.

и следующей «неприятной» находкой будет дерево с parent links.

Именно.

Но Rust более опасный, чем ванильная Java, так как unsafe всё же использовать придется.

Так вот и получается, что отказались от GC, наделали костылей, ходить неудобно, а безопасности такой же, как в GC, всё равно нет. И плюс в штате персонажи, которые заметают проблемы производительности под коврик, предпочитая вместо этого обзывать окружающих :)

В остальном задача не такая уж сложная. Если убрать требование по индексам

ЛОЛ :)

Ты, надеюсь, не станешь отрицать, что весь смысл её начала состоял во вбросе для очередного растосрача?

Ты неплохо сформулировал, но я не буду комментировать. Это - не клевета благодаря условной формулировке, но инсинуации.

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

Я разве делал такое утверждение? Мог, конечно, неосторожно поступить, но в целом не мой уровень. Покажешь, где я это говорил? Если покажешь, будет зачтён один гол в мои ворота. А если нет, то это инсинуации (видишь, ты уже научился быть осторожнее и избегать прямой клеветы).

Итак, будет ссылка на исчерпывающий разбор списков/массивов?

Какая ссылка, блин? Худшее время добавления в твой массив - O(N), в то время как худшее время добавления в настоящий список - O(1). Что ещё нужно тут объяснять? Это вопрос школьного уровня. Нужно быть полным идиотом или отмороженным пропагандистом, чтобы ещё после этого упираться.

В расте решили кардинально, через владение/заимствование.

Или не решили.

Так вот и получается, что отказались от GC, наделали костылей

Ну так это известная тема: или GC и безопасность памяти в рамках пермиссивной системы типов, но проблемы с большими кучами, или вечная борьба с линейными типами и тонкая (эффективная) работа с памятью, но не для любых структур. Выбирай, что тебе надо.

Я за Rust следил где-то с 2014-го, но для моих случаев он был слишком слаб как язык. У Rust и сейчас слабое метапрограммирование уровня типов, где-то на уровне С++98 или даже слабее (еще большая трясина Тьюринга, чем C++ TMP было на то время). На сколько я знаю, HKT до сих пор нет. В обсуждениях говорят про какие-то сложности в реализации, а это намекает на то, что язык изначально мыслился «слабым» и/или дизайнеры не понимали, для чего они вносят в такой язык мономорфные дженерики (в плане того, как и для чего эти дженерики будут потом использоваться в этом языке). Останавливало так же отсутствие хоть какой-то совместимости с С++. А переписывать всё на Rust – хватит, пробовали это с Java.

В пользу Rust по сравнению с С++ сейчас говорит более строгая в отношении памяти система типов, а так же значительно лучший тулинг. Последнее во многих случаях решает. Однако я для себя не вижу смысла переезжать на Rust и терять огромную унаследованную кодовую базу на С++. Гораздо проще подянуть тулинг в С++, чем всё переписывать на Rust.

UPD: Пока Rust пытался порешать искусственно созданные дизайнерами проблемы (отсутствие совместимости с С++, слабое метапрограммирование уровня типов и т.д.), С++ не стоял на месте и тоже развивался. И С++14 уже очень даже ничего. А С++20 так и вообще няшечка. К сожалению, С++ продолжает развиваться не в том направлении, в котором реально нужно. Тулинг останется на уровне 80-х годов прошлого века, о метапрограммировании уровня AST только разговоры и т.д. Так что у Rust в плане developer friendliness буде еще большой задел долгое время.

Не очень хочется об этом говорить, но один я всё же чувствую себя слабоватым для задачи. Немного вводных:

• сборка мусора иногда незаменима, поэтому если её выкинуть из языка совсем, то потом будет больно
• на подсчёте ссылок работает гуй в Apple, и работает он быстро. После Явы программы для Эпл просто поражают своей быстротой
• питон успешно использует комбинацию подсчёта ссылок и gc. Но из-за общей тормознутости сложно понять, насколько подсчёт ссылок его замедляет

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

Я сначала думал, что нужно взять механизмы из Раста и добавить их к Оберону, чтобы получился гибрид между растовым механизмом и сборкой мусора. Но теперь я думаю, что нефиг тут изображать из себя гения, особенно, когда ничего не получается, и нужно взять модель из Питона. Потому что наша задача про список с помощью RC вполне себе решается. Соответственно на данный момент стратегический план хочет стать таким:

• создаём кучи, локальные для «активностей». Активность - это римерно зелёный тред. Соответственно, создаём предпосылки, чтобы активности больше пользовались локальными данными и уменьшить количество разделяемых данных

• используем подсчёт ссылок и сборку мусора совместно, как в Питоне. При этом стараемся использовать потоко-локальный подсчёт ссылок, который дешевле

• где можно, выделяем на стеке (такая возможность в Обероне уже и так есть, но немного криво нарезана, объекты выделять на стеке нельзя, только записи и фиксированные массивы).

В итоге тут возникают корреляции с Растом, но не в том. ХОрошие вещи - это контроль компилятором за передачей данных между потоками и различие между внутрипоточным и многопоточным Rc.

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

Ещё нужно RAII добавить как-то.