среда, 22 февраля 2017 г.

C++: Эффективная разбивка строки на токены

По интернету гуляет два основных варианта токенайзера строк (strotk() мы не рассматриваем, он из С и корявый, а использование StringStream это для недоумков и тормозов. Ну а Boost для такой задачи тащить это карандаш мельничным жерновом затачивать):

 // Many delimiters possible, null-tokens protection  
 std::vector<std::string> split(const std::string &str, const std::string &delims)  
 {  
   std::vector<std::string> tokens;  
   std::size_t start = str.find_first_not_of(delims), end = 0;  
   
   while((end = str.find_first_of(delims, start)) != std::string::npos)  
   {  
     tokens.push_back(str.substr(start, end - start));  
     start = str.find_first_not_of(delims, end);  
   }  
   if (start != std::string::npos)  
     tokens.push_back(str.substr(start));  
   
   return tokens;  
 }  
   
 // One delimiter only  
 std::vector<std::string> split(const std::string &str, const std::string &delim)  
 {  
      std::vector<std::string> tokens;  
      size_t prev = 0, pos = 0;  
      do  
      {  
           pos = str.find(delim, prev);  
           if (pos == std::string::npos)  
                pos = str.length();  
           std::string token = str.substr(prev, pos-prev);  
           if (!token.empty())  
                tokens.push_back(token);  
           prev = pos + delim.length();  
      }  
      while (pos < str.length() && prev < str.length());  
      return tokens;  
 }  
   

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

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

И что, думаете, он эффективен по максимуму?

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

Вот оптимальный вариант:

 // Optimized split  
 // One delimiter only  
 std::vector<std::string> split(const std::string &str, const std::string &delim)  
 {  
      std::vector<std::string> tokens;  
      size_t prev = 0, pos = 0;  
      do {  
           pos = str.find(delim, prev);  
           if (pos == std::string::npos)  
                pos = str.length();  
           if (!str.substr(prev, pos-prev).empty())  
                tokens.push_back(str.substr(prev, pos-prev));  
           prev = pos + delim.length();  
      } while (pos < str.length());  
      return tokens;  
 }  
   

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

Ну и помните про реентрантность - с вектором она нереентрантна (см. предыдущую статью).

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

пятница, 17 февраля 2017 г.

std::vector is non-reentrant

Я говорил, что, в отличие от разработчиков Boost, разработчики STL хотя бы люди? Я хочу взять свои слова назад.

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

Взгляните на код:

 void processdata()  
 {  
      std::vector<std::string> inToken;  
   
  // Some stuff  
   
  for (size_t i = 1; i < v_max; i++) {  
     // Some stuff  
                     inToken.push_back(token);  
      }  
                       
  // Some stuff  
   
 }
  
 int main(int argc, char* argv[])  
 {  
   
  // Some stuff  
    
      while (!std::cin.eof()) {  
           /* Start processing threads */  
           for (size_t i = 0; i < v_max_threads; i++) {  
                threads.push_back(std::thread([]() {  
                     processdata();  
                }));  
           }  
           /* Finish all threads */  
           std::for_each(threads.begin(), threads.end(), [](std::thread &t) {  
                t.join();  
           });  
           threads.clear();  
      }  
      /*-------------Main Loop----------------*/  
      return 0;  
 }  

Все красиво, не правда ли? Полностью локальный вектор в тредовой процедуре. В этой процедуре вектор используется для парсинга строк (std::string) переменной длины. Конкретно - строка разбивается на токены, причем первый токен коротенький, и его длина не превышает нескольких символов, второй может варьироваться от 20 до 2048 символов, изредка - более.

 Все хорошо и прекрасно, но иногда, вне какой либо связи с нагрузкой или любыми другими видимыми событиями, данное приложение сегфолтилось. Причем GDB при обратной трассировке показывал только выход из процессингового треда по join() (приложение было собрано с ключом -g), а DBX давал странную трассировку:

 t@336 (l@336) terminated by signal SEGV (no mapping at the fault address)  
 Current function is std::__detail::_Executor<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::__cxx11::sub_match<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >, std::__cxx11::regex_traits<char>, true>::_M_dfs  
  795     { return *(this->_M_impl._M_start + __n); }  
 
 (dbx) where  
 current thread: t@336  
 =>[1] std::__detail::_Executor<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::__cxx11::sub_match<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >, std::__cxx11::regex_traits<char>, true>::_M_dfs(this = 0xfffffd7ffea90ef0, __match_mode = _Match_mode::_Prefix, __i = 17), line 795 in "stl_vector.h"  
  [2] std::__detail::_Executor<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::__cxx11::sub_match<__gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >, std::__cxx11::regex_traits<char>, true>::_M_dfs(this = 0xfffffd7ffea90ef0, __match_mode = <value unavailable>, __i = <value unavailable>), line 267 in "regex_executor.tcc"  

Смотрите очень внимательно. Regex тут не при чем. Дамп в принципе не содержит отсылки к коду приложения, то есть исключение прилетает не оттуда. Что-то с аллокатором, да? Какой-то контейнер вызывает проблему.


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

Посмотрите на код еще раз.

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

Говоря простым языком, у контейнера std::vector есть аллокатор памяти, который общий для всех векторов, которые вы определяете - неважно, локальные или глобальные.

И, когда происходит push_back в вектор, иногда перераспределяется память (помните, я говорил выше, что вектор используется для строк переменной длины?). Так вот, поскольку реализация аллокатора сделана не совсем людьми, никто о реентрантности и не думал. Более того, в разных системах, с разными libc и разными реализациями вышеприведенный код может вести себя как угодно. Если какие-нибудь алиены в дистрибутиве Бла-Бла-Бла-Линукс вдруг озаботились реентрантностью, они могли использовать примитивы синхронизации в аллокаторе контейнеров. Хорошо, если мьютексы. Много хуже, если спин-локи. Если не озаботились - получайте сегфолт в любой момент времени. На одной платформе мы не получали сегфолтов, но процессор взлетал в момент вызова аллокатора до 50 или 100% резким и кратковременным пиком. Что сказывалось на работе всего сервера, поскольку происходило достаточно часто.

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


Окей, чтобы убедиться что я прав, давайте закостылим:

 std::mutex vec_mtx;  
   
 void processdata()  
 {  
      std::vector<std::string> inToken;  
   
  // Some stuff  
   
  for (size_t i = 1; i < v_max; i++) {  
     // Some stuff  
                {  
                     std::lock_guard<std::mutex> lock(vec_mtx);  
                     inToken.push_back(token);  
                }  
   
      }  
                       
  // Some stuff  
   
      }  
   
 int main(int argc, char* argv[])  
 {  
   
  // Some stuff  
    
      while (!std::cin.eof()) {  
           /* Start processing threads */  
           for (size_t i = 0; i < v_max_threads; i++) {  
                threads.push_back(std::thread([]() {  
                     processdata();  
                }));  
           }  
           /* Finish all threads */  
           std::for_each(threads.begin(), threads.end(), [](std::thread &t) {  
                t.join();  
           });  
           threads.clear();  
      }  
      /*-------------Main Loop----------------*/  
      return 0;  
 }  

Обернем push_back в мьютекс.

Ой! Что мы видим! Сегфолт ушел!

Одно плохо. Скорость выполнения тоже ухудшилась. Примерно в 3-30 раз. В зависимости от данных.

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

Решение плохое во всех отношениях. Точка сериализации. Конкуренция блокировок.

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

Все было коряво, дьявольски усложняло алгоритмику, вело к утечкам (потенциальным) памяти итд. итп.

В конечном итоге проблему удалось решить радикально, переписав процедуру processdata() полностью без векторов, с использованием лишь наиболее примитивных контейнеров. Мне повезло, что в векторе могло быть от 1 до 4 элементов. Поэтому я отделался малой кровью лишь слегка изменив алгоритм и затолкав элементы в нумерованные переменные типа строка.



Но представьте себе, что вам надо обработать в потоке больше 100 элементов? Представили? Я как-то плохо представляю себе подобное без массив-подобных структур. Более того, я очень плохо представляю себе потоковую обработку, где я ограничен самыми примитивными типами данных из-за реентрантности.

Тщательный (очень тщательный поиск!) привел лишь к одной-единственной ссылке, где в принципе упоминалась теоретическая возможность (лишь возможность!) подобной ситуации. При этом все гуру СПО/GCC/STL всюду вещают, что контейнеры - и векторы в частности - потокобезопасные, нигде не сообщая, что они могут оказаться нереентрантными. (я умолчу о том, что в СПО в принципе дело плохо с документированием. Читайте исходники. Вы видели исходники STL? :)).

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

Вся суть проблемы совершенно понятна - мышление уровня IBM PC с одним-единственным процессором Pentium-D ведет к тому, что программист, пишущий инструментальные средства, принципиально не задумывается, во-первых, обо всех возможных вариантах программирования, а, во-вторых, не представляет, что код может исполняться более, чем в один поток более, чем одним процессорным ядром. Не стоит говорить - "пиши иначе". В данной конкретной задаче иначе - не получится. Надо работать с локальными векторами и баста. И у меня все равно не укладывается в голове, как можно иметь локальную структуру, которая заявлена как потокобезопасная, но имеет глобальный некопируемый аллокатор, который никаким вывертом невозможно сделать локальным. И ради одной небольшой подпрограммы надо либо писать собственный класс контейнера + аллокатор. Если это прелести объектно-ориентированного программирования, то я - за процедурный подход.

Резюмируя вышенаписанное, я утверждаю, что разработчики STL - это дети осла, свиньи и Чужого из фильма "Чужой-4" (таким образом, они лишь на 1/3 генетически люди):


Поздоровайтесь с родителем, упыри! Это один из ваших отцов. 

среда, 1 февраля 2017 г.

Оптимизация Squid 3+: Часть III

Архитектура (продолжение)

Асинхронные задания

Все было бы совершенно печально в одном потоке, если бы не некоторые девелоперские ухищрения. С некоторой натяжкой можно считать Squid частично-параллельным, так как некоторые движения в нем выполняются как асинхронные задания (этот параллелизм так тонок, что его почти не видно. В частности, вы не увидите появления LWP, как бы ни напрягали зрение, вглядываясь в вывод top). 

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

Кстати, не спешите материть разработчиков. Чтобы переписать весь код в thread-aware, надо бОльшую его часть по факту написать заново (вы проклянете только синхронизацию, когда увидите, сколько глобальных переменных и данных вам надо будет защищать мьютексами. И можете даже не заикаться про atomic - это будет еще больше работы и вряд ли получится. Можете попробовать).

Масштабирование

Исходя из всего вышесказанного, следует понять и усвоить следующее.

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

Причем масштабирование на одну большую машину весьма быстро упрётся в встроенные ограничения (самое радикальное из которых заключается в том, что Squid внутри далеко не во всех местах 100% 64-битный. Вот так, чешуйчатые. Сюрприз. Я не говорю, что его нельзя собрать в 64 бита. Можно. Только вот указатели и типы данных внутри далеко не все окажется 64-битными. И если вы наивно попытаетесь от собранного кода получить лимиты истинно 64-битного кода, вас ждет нехилый сюрприз). Постепенно и очень неспешно код правится, однако лишь когда репортится действительно фатальный и воспроизводимый баг, связанный с этим кодом.

Главным сюрпризом является тот факт, что большие машины в настоящее время уже  не SMP, а CMT. Соответственно, собственная архитектура SMP в Squid на таких машинах поведет себя.....эээээээ..... несколько не так, как ожидают разработчики.

Из вышесказанного вытекает вот что. Одиночный инстанс Squid лучше не раздувать до небес (выигрыш очень быстро будет перекрыт административными затратами на сопровождение и аномалиями в поведении), а оставить его маленьким. И масштабировать Squid как Grid, то есть создать кластер относительно некрупных кэшей-сиблингов с мощным горизонтальным интерконнектом а-ля-кластер, или иерархическую структуру - двух- или трехуровневую. Возможно - но не обязательно - с использованием CARP.