Реализация многомерного вектора

[Majestio]

Всем привет!

Вопрос конечно уже поднимался. Простое в лоб решение - делать это с помощью векторов-векторов-...-векторов-типов. Но я вот задумался, а что если многомерность "спроецировать" на одномерный вектор? Даст ли это какие-то преимущества в каких-либо случаях, да и вообще, "стоит ли овчинка выделки"? На сколько я где-то видел, пролетала инфа, что в последней версии стандарта С++ дали возможность в операторе [] использовать не один аргумент, а по количеству от нуля и более. Таким образом, теперь должно быть возможным выражение типа:

  value = vector[2,3,4];
  // что эквивалентно
  value = vector.operator[](2,3,4);

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

  value = vector.at(2,3,4);

У меня нет компилятора с последним стандартом, но хотелось бы поэкспериментировать с метапрограммированием, где постараться реализовать (если это возможно будет):

1) Менять количество размерностей в рантайме
2) В операторе[] попробовать задавать переменное количество аргументов для последующего использования с учетом п.1 (если последний стандарт это разрешит)

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

Qraizer, чё скажешь? Стоит этим заморачиваться? И если "да", сможешь накидать простенький шаблонный класс для п.1-п.2?

[Qraizer]

То, о чём ты говоришь, планируется только в C++23 который ещё не ратифицирован. На данный момент эту фичу поддерживают лишь GCC и CLang. И да, если рассматривать весь аспект твоего поста, то это чисто сахар. В рантайме ты можешь поменять размерность, но на лету сменить синопсис [] не выйдет, для этого нужна была бы соответствующая перегрузка, а параметры по умолчанию, поверь, очень плохая идея в этом контексте. Ты можешь накидать в {} какой-нибудь std::initializer_list, но тогда тебе не требуется много операндов, и такое ты и сейчас можешь сделать. Срезы потребуют от тебя промежуточных классов, типа "строка", "столбец" и "слой" в 3D объекте, но это ты и сейчас можешь. И так и делают со времён C++98. И более того, в многооперандном [] тут вообще нужны не будет, он тупо ничем не поможет.

В целом, я не вижу выгод от применения этой фичи. Замена [][][]... на [,,,...] сугубо косметическая. Думаю, её приняли исключительно из-за её дешевизны в реализации, и малого риска поломать старый код. Хотя, если кто юзал operator,() между [], того ждёт неприятный сюрприз. В частности, это все автоматизированные средства инструментирования кода.

Сообщение отредактировано: Qraizer - 05.01.23, 17:36

[Majestio]

Цитата Qraizer @ 05.01.23, 17:34

В рантайме ты можешь поменять размерность, но на лету сменить синопсис [] не выйдет

Вот вот поэтому и вопрос тебе задал! Можно будет делать что-то в виде (это вопрос):

T& operator[] (size_t Idx1, ...)

Иными словами. В зависимости от текущей размерности - указывать разное количество индексов в рантайме.

[Qraizer]

Формально да, но вот как ты её будешь реализовывать, это вопрос. У тебя будет компайл-тайм генерация оператора, и что ты будешь делать, если его вариадик не совпадает с текущей размерностью, определяемой в ран-тайм? Бросить исключение – самый разумный вариант. ИМХО через initializer_list будет не сложнее, и в производительности не потеряешь, всё равно проверки делать.

Сообщение отредактировано: Qraizer - 05.01.23, 23:25

[Majestio]

Цитата Qraizer @ 05.01.23, 23:24

ИМХО через initializer_list будет не сложнее, и в производительности не потеряешь, всё равно проверки делать.

Да, скорее всего, да не - точно ты прав. Я насчёт initializer_list.
Я вот попробовал на старых стандартах провести "Операцию Ы" (кристально чистая синтетика), получается, но увы, не так красиво.
Один вопрос пока не знаю - в новейшем стандарте можно ли в operator[] объявлять переменное число аргументов (не вариардик, а именно Си-стайл рантайма):

#include <iostream>
#include <cstdarg>
 
using namespace std;
 
template<typename T>
class SimpleClass {
    
    int dim = 0;
    int ret = 0;
  
  public:
    
    T& operator_bl(size_t Dim,...) {
       if (Dim != dim) throw std::range_error("Dimension Error");
       ret = 0;
       va_list list;
       va_start(list, Dim);
       for(int i=0; i<Dim; i++) {
         ret += va_arg(list, T);
       }
       va_end(list);
       cout << "Get: " << Dim << ", Ret: " << ret << endl;
       return ret;        
    }
    
    void setDimension(size_t Dim) {
      dim = Dim;        
    }
};
 
int main() {
    try {
      SimpleClass<int> value;
      value.setDimension(1);
      value.operator_bl(1, 11);
      value.setDimension(2);
      value.operator_bl(2, 22, 33);
      value.operator_bl(3, 1, 1, 1);
    } catch (std::exception &err) {
      cout << "Ваапще Лев Лещенко: " << err.what();
    } catch (...) {
      cout << "Случилось штото страшное!";
    }
    return 0;
}

Get: 1, Ret: 11
Get: 2, Ret: 55
Ваапще Лев Лещенко: Dimension Error

Online there

Ну а вообще "да", нововведения в планируемом стандарте относительно operator[] меня радуют. Для многомерных массивов с проекцией на одномерный, но с неизменяемой размерностью - меня радуют!
Последний вопрос к тебе по этой теме. Реализация многомерности в виде "проекции" на одномерный вектор - чем-то хороша, или это просто очередной велосипед с квадратными колесами?

[Qraizer]

Формально тебе никто не запрещает написать

    template <typename ...U> requires(std::same_as<U, std::size_t> && ...)
    auto operator[](U... idx)
    {
      return operator_bl(sizeof...(U), idx...);
    }

и не надо никакого cstdarg. Та и operator_bl() не надо, в operator[] уже всё есть. Но будет ли с этого всего профит...

Добавлено 07.01.23, 00:29

Цитата Majestio @ 06.01.23, 04:02

Реализация многомерности в виде "проекции" на одномерный вектор - чем-то хороша, или это просто очередной велосипед с квадратными колесами?

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

[Majestio]

Цитата Qraizer @ 07.01.23, 00:24

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

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

[Majestio]

Цитата Qraizer @ 05.01.23, 17:34

Хотя, если кто юзал operator,() между [], того ждёт неприятный сюрприз.

Операция запятая внутри [] по идее будет объявлена как deprecated.

[Qraizer]

С чего бы? Много чести. В конце концов это затронет только перегруженные [], которые спецом проектируются под такое использование. Я не читал Стандарт на этот счёт, возможно там есть исключение для токенизаторов, требующее от них переходить к старой семантике , в случае отсутствия подходящих перегрузок. Но даже если и нет, для перегруженных &&, || и , и так есть семантическое исключение: они не вносят точки следования. И даже для >> есть: эта хрень не должна рассматриваться как арифметическая операция в контексте списка аргументов шаблонов. Есть и ещё примеры посложнее, с typename например.

[Majestio]

Цитата Qraizer @ 07.01.23, 17:38

С чего бы? Много чести.

Где-то прочел, сорян, не запомнил где.

[Qraizer]

Говоря об автоматизированных средствах инструментирования кода. Вот смотри. У нас есть код типа такого:

if (a == b)
  x = y;
else
  z = t;

Предположим, нам нужно собрать структурное покрытие блоков. Что делает инструментатор? А вот что:

if (a == b){StartBlock(tag1);
  x = y; EndBlock(tag1);}
else{StartBlock(tag2);
  z = t; EndBlock(tag2);}

где StartBlock() и EndBlock() его функции сбора статистики, а tag1 и tag2 однозначно указывают на блоки {} кода в его базе, построенной при анализе сырцов. Обычно эти функции просто взводят биты в битовом массиве, изначально обнулённом, так что при анализе собранной в ран-тайм статистики легко определить, какие блоки покрыты, какие нет. Но нередко используются и более сложные действия. Например, если мы захотим оптимизировать размещение кодовых секций для более ёмкого заполнения кеша или переупорядочить блоки условных операторов для более вероятного предсказания ветвлений, то простых битиков будет уже недостаточно. Предположим, мы решили собрать покрытие решений. Тогда вот такой код, казалось бы более простой:

if (a == b)
  x = y;

вызовет генерацию примерно такого инструментированного

if (AnalyzeDecision(tag1, a == b)){StartBlock(tag1);
  x = y; EndBlock(tag1);} else {StartBlock(tag2); EndBlock(tag2);}

Всё равно появился блок else, но главное – if() теперь тоже не так прост, ведь нужно не только блоки собрать, но и решения, которые привели к тому или иному поведению кода. А ведь они небинарны, они не только либо true, либо false, они ведь ещё могут быть indeterminated, т.е. не исполнялись. Поэтому AnalyzeDecision() уже не просто что-то там битово взводит. Но как бы там ни было, исходное поведение кода инструментатор легко сохраняет, если AnalyzeDecision() будет возвращает свой второй аргумент как результат.
Усложним входные данные. Нужно собрать покрытие условий. Представим себе решение, чуточку посложнее:

if (a == b+d || c == 123)
  x = y;
else
  z = t;

Ну что ж, мы уже это проходили:

if (AnalyzeCondition(tag1, a == b+d) || AnalyzeCondition(tag2, c == 123))
  {StartBlock(tag1); x = y; EndBlock(tag1);}
else
  {StartBlock(tag2); z = t; EndBlock(tag2);}

Не буду подробно это комментировать, должно быть и так понятно. Если кто не понял, мы сейчас о сборе структурного покрытия уровней SC, DC и MC/DC.
Но вот вдруг нужно собрать покрытие MCC. Здесь учитываются не только все условия в решении, но и каждый вход в эти условия:

if (AnalyzeCondition(tag1, AnalyzeEntry(tag1, a) == AnalyzeEntry(tag2, b)+AnalyzeEntry(tag3, d)) || AnalyzeCondition(tag2, AnalyzeEntry(tag4, c) == 123))
  {StartBlock(tag1); x = y; EndBlock(tag1);}
else
  {StartBlock(tag2); z = t; EndBlock(tag2);}

Он работает, но это неоптимальный сценарий. Здесь требуется хранить много данных, ведь одна и та же переменная может использоваться многократно даже в одном выражении, не говоря уже о других, для которых тоже собираются свои MCC. Поэтому количество различных и уникальных tag для больших проектов огромное, всевозможных комбинаций входов в условиях экспоненциальное, так что элементарно может не хватить даже разрядности целого, не говоря уже о памяти под стастистику. А анализ статистики может занять непомерно огромное время. Поэтому на практике инструментаторы используют гораздо более сложные, но сильно экономящие ресурсы, алгоритмы. Я разбил длинную строку для наглядности, но инструментаторы предпочитают сохранять исходную нумерацию строк. Так людям проще потом анализировать собранное покрытие. Получится что-то типа

unsigned __dec, __cond, __eval, __mask;
/* ... */
if ((
     __dec  = FindDecision(tag1),
     __cond = FindCondition(__dec, tag1),
     __eval = a == b+d,
     __mask = RegisterEntries4(__dec, __cond, a, b, d, c, __eval),
     CheckCondition(__dec, __cond, __mask),
     __eval
    )
    ||
    (
     __cond = FindCondition(__dec, tag2),
     __eval = c == 123,
     __mask = RegisterEntries4(__dec, __cond, a, b, d, c, __eval),
     CheckCondition(__dec, __cond, __mask),
     __eval
    )
   )
{StartBlock(tag1);
  x = y; EndBlock(tag1);}
else{StartBlock(tag2);
  z = t; EndBlock(tag2);}

Инструментатор для каждого решения заранее создаёт все возможные варианты, учитывающие true/false/indeterminated и собирает их в массивы. Служебные функции FindDecision() ищет в базе нужные массивы, функция FindCondition() возвращает ссылку на массив возможных исходов для конкретного условия в этом решении, функция RegisterEntriesX() – их несколько, для каждого встреченного в сырцах количества входов в выражениях по одной штуке – регистрирует значения входов в решение, в зависимости от вычисленного __eval это могут быть разные элементы в найденном __cond, но по-любому их количество невелико, т.к. не экспоненциально, а арифметично. В итоге RegisterEntriesX() возвращает реальное что-то, что случилось в реалтайме, и CheckCondition() остаётся лишь сравнить это с тем, что было подготовлено в компайл-тайм. Если ты тут заметил операцию , среди прочих, то ты молодец.
Эту операцию инструментаторы очень любят как раз за её странные качества: вычисление и игнор левого операнда и внесение точки следования перед вычислением правого, и всё это в пределах одного выражения. Сразу предупреждаю, что тут только демонстрация концепций. Реальные инструментаторы могут их реализовывать по-разному. Например, RTRT для MC/DC и MCC массивы условий/решений для приведённого выше выражения (a == b+d || c == 123) формирует в виде строк типа "XXXX", "1111", "1113" и "333X", а вместо функций использует макросы. Там вообще жесть разобраться с нагенеренным, если вдруг приспичит.
Но настоящее веселье начинается, когда инструментатор сталкивается с ?: . Интересно же, как инструментатор выкрутится на:

*(a == b ? &x : &z) = (a == b ? y : t);

который в общем-то аналогичен первому if()? (Ну, почти аналогичен, тут надо, чтобы x и z были подобающих типов, в if() этого не требовалось.) Примерно так:

unsigned __tag;
decltype(0 ? &x : &z) __res1;
decltype(0 ?  y :  t) __res2;
/* ... */
*(__res1 = (AnalyzeDecision(tag1, a == b) ? (__tag = tag1, StartBlock(__tag), &x)
                                          : (__tag = tag2, StartBlock(__tag), &z)),
  EndBlock(__tag), __res1) =
 (__res2 = (AnalyzeDecision(tag2, a == b) ? (__tag = tag3, StartBlock(__tag),  y)
                                          : (__tag = tag4, StartBlock(__tag),  t)),
  EndBlock(__tag), __res2);

Как легко увидеть, здесь , понадобилась уже на SC.

P.S. Что такое tag и с чем их есть. Это просто тэги, навешанные инструментатором на точки наблюдения и собранные в статические базы, когда он анализирует сырцы и генерит инструментированный код. Формально это просто числа, но не всегда, иногда это могут быть целые структуры с кучей доп.инфы. Для них главное быть уникальными и точно идентифицировать точку в коде. Тот факт, что они у меня тут нередко совпадают для разных точек... ну, это смущает, но не противоречит, т.к. тэги для блоков, решений, условий и входов собираются в разные базы и анализируются разными функциями, так что их назначение не пересекается, даже когда они численно равны.
P.P.S. И да, это всё C. А вот с Плюсами гораздо интереснее. У него есть ссылки, нетривиальные классы, которые нельзя вот так просто взять и посохранять и покопировать, шаблоны, для которых решения в одной конкретизации совсем не то же решение, что в другой конкретизации этого же шаблона. Но самый смак – это исключения. Они вносят настолько иногда неожиданные потоки управления, что диву даёшься, как это всё инструментаторы умудряются учитывать.

Добавлено 07.01.23, 21:04
Это всё к слову о , внутри []. Мне как-то что-то по голове стукнуло, и я решил замутить сортировку без ветвлений. Там и не только , в индексации была.

Сообщение отредактировано: Qraizer - 07.01.23, 21:04

[Majestio]

Цитата Qraizer @ 07.01.23, 20:51

Говоря об автоматизированных средствах инструментирования кода.

Цитата Qraizer @ 07.01.23, 20:51

Не буду подробно это комментировать, должно быть и так понятно. Если кто не понял, мы сейчас о сборе структурного покрытия уровней SC, DC и MC/DC.
Но вот вдруг нужно собрать покрытие MCC. Здесь учитываются не только все условия в решении, но и каждый вход в эти условия:

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

Чисто ради интереса ... что будет с разбором вот такой конструкции этими средствами:

if ( (a == 1 || a > 0) && b > 1) // ...

Тут явно одно из условий лишнее, будет ли оно выкинуто в процессе последующей компиляции?

[Qraizer]

Цитата Majestio @ 08.01.23, 02:14

Но это все же специфическая область разработки.

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

[Majestio]

Цитата Qraizer @ 08.01.23, 18:21

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

Увы, высококритичное ПО не доводилось писать. Как правило UI+DB

[Qraizer]

Цитата Majestio @ 08.01.23, 02:14

Тут явно одно из условий лишнее, будет ли оно выкинуто в процессе последующей компиляции?

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

Добавлено 08.01.23, 18:29

Цитата Majestio @ 08.01.23, 18:25

высококритичное ПО не доводилось писать

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

Добавлено 08.01.23, 18:32

Цитата Qraizer @ 08.01.23, 18:25

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

А впрочем не получишь. Лишнее-нелишнее, но покрыть по MC/DC там всё можно. Но вот если б ты написал

if ( (a > 0 || a == 1) && b > 1) // ...

т.е. поменял местами условия, то увы и ах.