​Vector vs List

Знание алгоритмов и структур данных - критично для нашей профессии. Ведь в принципе все, что мы делаем - это берем какие-то явления реального мира, создаем их представления в программе и управляем ими. От нашего понимания эффективного представления данных в памяти компьютера и управления ими зависит количество ресурсов, которое требуется на предоставление какой-то услуги, а значит и доход заказчика. Чем лучше мы знаем эти вещи, тем дешевле предоставлять услугу и тем больше мы ценны как специалисты. И наши доходы растут. Но computer science намного обширнее, чем абстрактные вещи типа теории алгоритмов или архитектуры ПО. Это еще и знание и понимание работы конкретного железа, на котором наш софт выполняется. Что важнее - непонятно. Но только в синергии можно получить топовые результаты.

Согласно теории, проход по массиву и двунаправленному списку происходит за одинаковое алгоритмическое время. O(n). То есть время прохода линейно зависит от количества элементов в структуре. И без применения знаний о принципах работы железа, можно подумать, что они взаимозаменяемы. Просто в одном случае элементы лежат рядом, а в другом - связаны ссылками. А на практике получается, что не совсем линейно и совсем не взаимозаменяемы. Расскажу подробнее о последнем.

Дело в существовании кэша у процессора. Когда мы запрашиваем доступ к одной ячейке памяти, процессор верно предполагает, что нам скорее всего будут нужны и соседние ячейки тоже. Поэтому он копирует целый интервал в памяти, называемый кэш-строкой, в свой промежуточный буфер. А доступ к этому буферу происходит намного быстрее, чем к оперативной памяти. И процессору не нужно ходить за этими рядом лежащими данными в ОЗУ, он их просто берет из кэша.

Элементы же списка хранятся в разных участках памяти и связаны между собой ссылками. В общем виде нет никакой гарантии, что они будут лежать рядом. Если конечно вы не используете кастомный аллокатор. Поэтому за каждым элементом листа процессору приходится ходит в ОЗУ.

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

Написал простенькую программку, которая проверит разницу во времени прохода.
Получилось, что для 100кк чисел в массиве и в листе, время отличается от 1.5 до 2 раз на разных машинах. Нихрена себе такая разница. И это без оптимизаций!
С ними разница вообще 6-8 раз. Это кстати еще один повод для того, чтобы понимать, как именно мы работаем на уровне железа и какие структуры данных хорошо ложатся на разные оптимизации.

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

Stay based. Stay cool.

#STL #algorithms #cppcore

​std::for_each

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

Чем она хороша? В подходящих условиях она дает больше семантики по сравнению с "конкурентами".

Например, есть range-based-for цикл. Он записывается примерно так:

for(auto & traitor: traitors) {
  // exquisitely torture the traitor
}

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

Но если такой логики нет и мы просто делаем определенную операцию над каждым элементом, то создается совершенно лишнее напряжение, которого можно было бы избежать. И этому побегу поможет std::for_each.

Функция имеет явную семантику: для каждого элемента последовательности выполняется вот эта функция. И все. Думать много не нужно. Нужно просто понять, как преобразуется или обрабатывается элемент и дело в шляпе.

Но не каждый знает, что эта функция возвращает не void, а тот же тип унарной операции, что мы передали в нее. Значит мы можем использовать stateful операции, то есть функциональные объекты, и сохранять результат вычислений в этом объекте не используя никакие глобальные переменные, ссылки и прочее. Стандарт гарантирует, что возвращаемое значение for_each содержит финальное состояния функтора после завершения операций над всеми элементами.

Эта особенность может пригодиться, когда помимо обработки элемента необходимо собрать по ним статистику. Допустим, я хочу убрать из массива строк все пробелы и сосчитать, сколько в среднем на каждую строку приходится пробелов. И тут как бы вроде скорее всего наверное вероятно лучше std::transform подходит(по семантике основной операции), но все портит сбор статистики. Можно засунуть в трансформ лямбду со ссылкой на внешний счетчик, но по смыслу это уже не будет чистая трансформация строк. Поэтому можно подобрать менее точечный по предназначению алгоритм, но он лучше подходит этой ситуации. Единственное, что лямбду нельзя будет использовать.

Пример:

struct SpaceHandler {
  void operator()(std::string& str) {
    auto new_end_it = std::remove_if(str.begin(), str.end(), [](const auto & ch){ return ch == ' ';});
    space_count += str.size() - std::distance(str.begin(), new_end_it);
    str.erase(new_end_it, str.end());
  }
  int space_count {0};
};

int main() {
  std::vector<std::string> container = {"Ole-ole-ole ole", "C++ is great!",
  "Just a random string just to make third elem"};
  int i = std::for_each(container.begin(), container.end(), SpaceHandler()).space_count;
  std::for_each(container.begin(), container.end(), [](const auto& str) { std::cout << str << std::endl;});
  std::cout << "Average number of spaces is " << static_cast<double>(i) / container.size() << std::endl;
}

//Output

Ole-ole-oleole
C++isgreat!
Justarandomstringjusttomakethirdelem
Average number of spaces is 3.66667

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

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

Кстати, с С++20 std::for_each стал constexpr, что позволяет удобнее обрабатывать наборы данных во время компиляции .

Use proper tools. Stay cool.

#cppcore #cpp20 #algorithms

​XOR Swap

Есть такая интересная техника для свопинга содержимого двух переменных без надобности во временной третьей! Стандартный подход выглядит примерно так:

template <class T>
void swap(T& lhs, T& rhs) {
  T tmp = std::move(lhs);
  lhs = std::move(rhs);
  rhs = std::move(tmp);
}

Все мы с программистких пеленок уже выучили это. И примерно так и реализована функция std::swap из стандартной библиотеки. Однако вот вам задали на собесе вопрос: "вот у вас есть 2 числа, но я хочу, чтобы вы обменяли их значения без временной переменной?". Какие мысли? Подумайте пару секунд.

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

template <class T, typename std::enable_if_t<std::is_integral_v<T>> = 0>
void swap(T& x, T& y) {
  if (&x == &y)
    return;
  x = x ^ y;
  y = x ^ y;
  x = x ^ y;
}

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

Тут есть один интересный момент, что в случае подачи на вход функции одной и той же переменной, то произойдет эффект зануления. Первый же xor занулит x, а значит и y. Поэтому в самом начале стоит условие на проверку одинакового адреса.

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

Ну и работает это дело только с целочисленными параметрами.

Но предостерегаю вас - не используйте эту технику в современных программах! Результаты этих трех ксоров напрямую зависят друг от друга по цепочке. А значит параллелизма на уровне инструкций можно не ждать.

Современные компиляторы вполне могут и соптимизировать третью переменную и вы ее вовсе не увидите в ассемблере. Да и еще и вариант с доп переменной тупо быстрее работает. Всего 2 store'а и 2 load'а, которые еще и распараллелить можно, против 3 затратных ксоров. Да и даже довольно тяжеловесная XCHG работает быстрее, чем 3 xor'а.

Зачем я это все рассказываю тогда, если эта техника уже никому не уперлась? Для ретроспективы событий. Дело в том, что раньше люди писали программы без компиляторов, напрямую на ассемблере. Плюс в то время компьютеры имели такое маленькое количество памяти, что биться приходилось буквально за каждый байт. А используя операции xor, мы экономим 33% памяти на эту операцию. Довольно неплохо. В стародавние времена как только не извращались люди, чтобы выжимать все из железа. Эх, были времена...

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

Learn technics from the past. Stay cool.

#cppcore #fun #algorithms