Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884531 Mon, 09 Jan 2023 03:18:08 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884531 Цитата Majestio @ 06.01.23, 04:02

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

Какую же дичь я сморозил! :blush:

В приведенном мною примере, когда в коде идет явный вызов оператора[] с разным числом параметров, все вполне решается вариардиком. Ибо еще на этапе компиляции изменение количество размерностей - вполне детерминировано! А вот если заранее неизвестен ход вычислений, и заранее неизвестно изменение размерностей многомерного вектора в каком-то месте кода - в качестве аргумента можно и нужно передать динамически формируемый вектор индексов. Вот блин :)]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884520 Sun, 08 Jan 2023 18:32:48 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884520 Цитата Qraizer @ 08.01.23, 18:25

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

Ну да, я там вторую ссылку давал - как раз про ПО самолётов. Там ответственность - не ровня банкоматам и автобусного табло.]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884518 Sun, 08 Jan 2023 18:25:52 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884518 Цитата 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) // ...

т.е. поменял местами условия, то увы и ах.]]> Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884517 Sun, 08 Jan 2023 18:25:21 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884517 Цитата Qraizer @ 08.01.23, 18:21

Увы, высококритичное ПО не доводилось писать. Как правило UI+DB]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884516 Sun, 08 Jan 2023 18:21:52 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884516 Цитата Majestio @ 08.01.23, 02:14

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

Высококритичное ПО без этого не обходится никак. Но в целом если... если ты когда-нибудь пользовался чем-то типа profile-guided optimization или просто смотрел в среде твоего отладчика, какими путями ты сюда попал (и какие пути вообще были задействованы, это довольно распространённый сервис), то ты однозначно пользовался инструментированием кода. А также если когда использовал расширенный профайлинг для чего-то очень точного.]]> Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884495 Sun, 08 Jan 2023 02:14:27 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884495 Цитата 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) // ...

Тут явно одно из условий лишнее, будет ли оно выкинуто в процессе последующей компиляции?]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884492 Sat, 07 Jan 2023 20:51:36 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884492

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);}

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", а вместо функций использует макросы. Там вообще жесть разобраться с нагенеренным, если вдруг приспичит.
Но настоящее веселье начинается, когда инструментатор сталкивается с ?: :D . Интересно же, как инструментатор выкрутится на:

*(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 C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884483 Sat, 07 Jan 2023 17:44:25 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884483 Цитата Qraizer @ 07.01.23, 17:38

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

Где-то прочел, сорян, не запомнил где.]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884482 Sat, 07 Jan 2023 17:38:20 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884482 Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884464 Sat, 07 Jan 2023 06:37:11 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884464 Цитата Qraizer @ 05.01.23, 17:34

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

Операция запятая внутри [] по идее будет объявлена как deprecated.]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884462 Sat, 07 Jan 2023 05:29:12 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884462 Цитата Qraizer @ 07.01.23, 00:24

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

Да, возможно еще наверное некоторое ускорение при предварительном резервировании - выделение памяти все же операция относительно не быстрая. Одним участком это гораздо быстрее, чем в циклах мелкими.]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884460 Sat, 07 Jan 2023 00:24:43 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884460

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(). Но окупится это лишь в специфических алгоритмах работы с таким массивом.]]> Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884399 Fri, 06 Jan 2023 04:02:23 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884399 Цитата 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[] меня радуют. Для многомерных массивов с проекцией на одномерный, но с неизменяемой размерностью - меня радуют!
Последний вопрос к тебе по этой теме. Реализация многомерности в виде "проекции" на одномерный вектор - чем-то хороша, или это просто очередной велосипед с квадратными колесами?]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884396 Thu, 05 Jan 2023 23:24:47 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884396 Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884371 Thu, 05 Jan 2023 17:43:44 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884371 Цитата Qraizer @ 05.01.23, 17:34

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

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

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

Иными словами. В зависимости от текущей размерности - указывать разное количество индексов в рантайме.]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884368 Thu, 05 Jan 2023 17:34:35 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884368
В целом, я не вижу выгод от применения этой фичи. Замена [][][]... на [,,,...] сугубо косметическая. Думаю, её приняли исключительно из-за её дешевизны в реализации, и малого риска поломать старый код. Хотя, если кто юзал operator,() между [], того ждёт неприятный сюрприз. В частности, это все автоматизированные средства инструментирования кода.]]> Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884343 Thu, 05 Jan 2023 06:24:23 +0000 Реализация многомерного вектора https://forum.sources.ru/index.php?showtopic=432284&view=findpost&p=3884343
Вопрос конечно уже поднимался. Простое в лоб решение - делать это с помощью векторов-векторов-...-векторов-типов. Но я вот задумался, а что если многомерность "спроецировать" на одномерный вектор? Даст ли это какие-то преимущества в каких-либо случаях, да и вообще, "стоит ли овчинка выделки"? На сколько я где-то видел, пролетала инфа, что в последней версии стандарта С++ дали возможность в операторе [] использовать не один аргумент, а по количеству от нуля и более. Таким образом, теперь должно быть возможным выражение типа:

value = vector[2,3,4];

// что эквивалентно

value = vector.operator[](2,3,4);

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

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

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

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

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

Qraizer, чё скажешь? ;) Стоит этим заморачиваться? И если "да", сможешь накидать простенький шаблонный класс для п.1-п.2?]]> Majestio C/C++: Общие вопросы