Очень низкая производительность: lexical_cast

Windows XP SP3. Core 2 Duo 2.0 ГГц. Я считаю, что производительность boost: lexical_cast очень медленная. Хотел выяснить способы ускорения кода. Использование оптимизаций / O2 на Visual C ++ 2008 и сравнение с java 1.6 и python 2.6.2. Я вижу следующие результаты.

Целое литье:

c++: std::string s ; for(int i = 0; i < 10000000; ++i) { s = boost::lexical_cast(i); } java: String s = new String(); for(int i = 0; i < 10000000; ++i) { s = new Integer(i).toString(); } python: for i in xrange(1,10000000): s = str(i) 

Время, которое я вижу, это

c ++: 6700 миллисекунд

java: 1178 миллисекунд

python: 6702 миллисекунды

c ++ медленнее, чем python, и в 6 раз медленнее, чем java.

Двойной кастинг:

 c++: std::string s ; for(int i = 0; i < 10000000; ++i) { s = boost::lexical_cast(d); } java: String s = new String(); for(int i = 0; i < 10000000; ++i) { double d = i*1.0; s = new Double(d).toString(); } python: for i in xrange(1,10000000): d = i*1.0 s = str(d) 

Время, которое я вижу, это

c ++: 56129 миллисекунд

java: 2852 миллисекунды

python: 30780 миллисекунд

Таким образом, для удвоений c ++ на самом деле половина скорости python и в 20 раз медленнее, чем java-решение !!. Любые идеи по улучшению производительности boost: lexical_cast? Оказывается ли это из-за плохой строковой реализации, или мы можем ожидать, что общее снижение производительности на 10 раз связано с использованием библиотек повышения.

Изменить 2012-04-11

rve совершенно справедливо прокомментировал производительность lexical_cast, предоставив ссылку:

http://www.boost.org/doc/libs/1_49_0/doc/html/boost_lexical_cast/performance.html

У меня нет доступа прямо сейчас, чтобы увеличить 1.49, но я помню, как сделать мой код быстрее на более старой версии. Так что я думаю:

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

Оригинальный ответ

Просто чтобы добавить информацию о превосходных ответах Барри и Мотти:

Некоторые предпосылки

Помните, что Boost написана лучшими разработчиками C ++ на этой планете и рассмотрены теми же самыми лучшими разработчиками. Если lexical_cast был настолько ошибочным, кто-то мог бы взломать библиотеку либо с критикой, либо с кодом.

Я думаю, вы пропустили реальную ценность lexical_cast

Сравнение яблок и апельсинов.

В Java вы производите целое число в строку Java. Вы заметите, что я не говорю о массиве символов или определенной пользователем строке. Вы также заметите, что я не говорю о вашем определяемом пользователем целом. Я говорю о строгом Java Integer и строгой строке Java.

В Python вы более или менее выполняете то же самое.

Как говорится в других сообщениях, вы, по сути, используете эквиваленты Java и Python для sprintf (или менее стандартного itoa ).

В C ++ вы используете очень мощный трансляции. Не мощный в смысле скорости скорости (если вам нужна скорость, возможно, sprintf лучше подходит), но мощный в смысле расширяемости.

Сравнение яблок.

Если вы хотите сравнить метод Java Integer.toString , вы должны сравнить его с C sprintf или средствами C ++ ostream .

Решение streamа C ++ было бы в 6 раз быстрее (на моем g ++), чем lexical_cast , и в гораздо меньшей степени расширяемо:

 inline void toString(const int value, std::string & output) { // The largest 32-bit integer is 4294967295, that is 10 chars // On the safe side, add 1 for sign, and 1 for trailing zero char buffer[12] ; sprintf(buffer, "%i", value) ; output = buffer ; } 

Решение C sprintf будет в 8 раз быстрее (на моем g ++), чем lexical_cast но намного менее безопасным:

 inline void toString(const int value, char * output) { sprintf(output, "%i", value) ; } 

Оба решения являются либо быстрыми, либо быстрыми, чем ваше Java-решение (согласно вашим данным).

Сравнение апельсинов.

Если вы хотите сравнить C ++ lexical_cast , то вы должны сравнить его с этим псевдокодом Java:

 Source s ; Target t = Target.fromString(Source(s).toString()) ; 

Source и Target имеют любой тип, который вы хотите, включая встроенные типы, такие как boolean или int , что возможно на C ++ из-за шаблонов.

Расширяемость? Это грязное слово?

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

В текущем случае, с наивной точки зрения, lexical_cast будет использовать средства streamа для преобразования из типа A в stream строк, а затем из этого streamа строк в тип B

Это означает, что до тех пор, пока ваш объект может быть выведен в stream и вводится из streamа, вы сможете использовать lexical_cast на нем, не касаясь какой-либо одной строки кода.

Итак, что такое использование lexical_cast ?

Основные виды использования лексического литья:

  1. Простота использования (эй, C ++, который работает для того, чтобы все было ценным!)
  2. Объединяя его с тяжелым кодом шаблона, где ваши типы параметризуются, и поэтому вы не хотите иметь дело со спецификой, и вы не хотите знать типы.
  3. Все еще потенциально относительно эффективно, если у вас есть базовые знания шаблона, как я продемонстрирую ниже

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

Это реальная точка, которую вы пропустили, и это то, что стоит в плане производительности.

Но это так скучно!

Если вам нужна производительность с низкой скоростью, помните, что вы имеете дело с C ++, и что у вас есть множество возможностей для эффективного обработки конверсий и, тем не менее, сохраните lexical_cast простоты использования lexical_cast .

Мне потребовалось несколько минут, чтобы посмотреть на источник lexical_cast и прийти к жизнеспособному решению. Добавьте в свой код C ++ следующий код:

 #ifdef SPECIALIZE_BOOST_LEXICAL_CAST_FOR_STRING_AND_INT namespace boost { template<> std::string lexical_cast(const int &arg) { // The largest 32-bit integer is 4294967295, that is 10 chars // On the safe side, add 1 for sign, and 1 for trailing zero char buffer[12] ; sprintf(buffer, "%i", arg) ; return buffer ; } } #endif 

Включив эту специализацию lexical_cast для строк и ints (определяя макрос SPECIALIZE_BOOST_LEXICAL_CAST_FOR_STRING_AND_INT ), мой код быстрее на 5 раз быстрее работал на моем компиляторе g ++, а значит, по вашим данным, его производительность должна быть похожа на Java.

И мне потребовалось 10 минут, чтобы посмотреть код повышения и написать удаленно эффективную и правильную 32-битную версию. И с некоторой работой он мог бы работать быстрее и безопаснее (если бы у нас был прямой доступ на запись к внутреннему буферу std::string , мы могли бы, например, избежать временного внешнего буфера).

Вы можете специализировать lexical_cast для int и double типов. Используйте strtod и strtol в своих специализациях.

 namespace boost { template<> inline int lexical_cast(const std::string& arg) { char* stop; int res = strtol( arg.c_str(), &stop, 10 ); if ( *stop != 0 ) throw_exception(bad_lexical_cast(typeid(int), typeid(std::string))); return res; } template<> inline std::string lexical_cast(const int& arg) { char buffer[65]; // large enough for arg < 2^200 ltoa( arg, buffer, 10 ); return std::string( buffer ); // RVO will take place here } }//namespace boost int main(int argc, char* argv[]) { std::string str = "22"; // SOME STRING int int_str = boost::lexical_cast( str ); std::string str2 = boost::lexical_cast( str_int ); return 0; } 

Этот вариант будет быстрее, чем использование реализации по умолчанию, потому что при реализации по умолчанию происходит строительство объектов с тяжелым streamом. И это должно быть немного быстрее, чем printf , потому что printf должен анализировать строку формата.

lexical_cast более общий, чем конкретный код, который вы используете в Java и Python. Неудивительно, что общий подход, который работает во многих сценариях (лексический актер – это немного больше, чем streamовая передача, а затем обратно в временный stream и обратно) заканчивается медленнее, чем конкретные процедуры.

(BTW, вы можете получить более высокую производительность из Java, используя статическую версию Integer.toString(int) . [1])

Наконец, синтаксический анализ строк и депарафинизация обычно не чувствительны к производительности, если только не пишется компилятор, и в этом случае lexical_cast , вероятно, слишком универсален, а целые числа и т. Д. Будут вычисляться по мере сканирования каждой цифры.

[1] Комментарий «stepancheg» усомнился в моем намеке на то, что статическая версия может дать лучшую производительность. Вот источник, который я использовал:

 public class Test { static int instanceCall(int i) { String s = new Integer(i).toString(); return s == null ? 0 : 1; } static int staticCall(int i) { String s = Integer.toString(i); return s == null ? 0 : 1; } public static void main(String[] args) { // count used to avoid dead code elimination int count = 0; // *** instance // Warmup calls for (int i = 0; i < 100; ++i) count += instanceCall(i); long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; ++i) count += instanceCall(i); long finish = System.currentTimeMillis(); System.out.printf("10MM Time taken: %d ms\n", finish - start); // *** static // Warmup calls for (int i = 0; i < 100; ++i) count += staticCall(i); start = System.currentTimeMillis(); for (int i = 0; i < 10000000; ++i) count += staticCall(i); finish = System.currentTimeMillis(); System.out.printf("10MM Time taken: %d ms\n", finish - start); if (count == 42) System.out.println("bad result"); // prevent elimination of count } } 

Время выполнения, используя JDK 1.6.0-14, VM ​​сервера:

 10MM Time taken: 688 ms 10MM Time taken: 547 ms 

А в клиентской VM:

 10MM Time taken: 687 ms 10MM Time taken: 610 ms 

Несмотря на то, что теоретически анализ эвакуации может разрешить выделение в стеке, а inlining может вводить весь код (включая копирование) в локальный метод, позволяя исключить избыточное копирование, такой анализ может занять довольно много времени и привести к довольно большому количеству которое имеет другие затраты в кеше кода, которые не оправдывают себя в реальном коде, в отличие от микрообъектов, как здесь видно.

То, что делает лексический актер в вашем коде, можно упростить:

 string Cast( int i ) { ostringstream os; os << i; return os.str(); } 

К сожалению, каждый раз, когда вы вызываете Cast (), происходит много:

  • stream строк создается, возможно, выделяя память
  • оператор << для целого числа i называется
  • результат сохраняется в streamе, возможно, выделяя память
  • строковая копия берется из streamа
  • копия строки (возможно) создана для возврата.
  • память освобождается

Thn в вашем собственном коде:

  s = Cast( i ); 

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

 string s = Cast( i ); 

вместо.

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

Подводя итог, lexical_cast - удобная и полезная функция, но такое удобство приходит (как всегда) с компромиссами в других областях.

К сожалению, мне еще не хватает репутации, чтобы прокомментировать …

lexical_cast не является в основном медленным, потому что он является общим (поиск шаблонов происходит во время компиляции, поэтому вызовы виртуальных функций или другие поисковые запросы / разметки не нужны). lexical_cast , на мой взгляд, медленный, потому что он основан на C ++ iostreams, которые в первую очередь предназначены для streamовых операций, а не для отдельных преобразований, и потому что lexical_cast должен проверять и преобразовывать сигналы ошибки iostream. Таким образом:

  • объект streamа должен быть создан и уничтожен
  • в приведенном выше примере вывода строк обратите внимание, что компиляторам C ++ трудно избежать копий буфера (альтернативой является форматирование непосредственно в выходной буфер, например sprintf , хотя sprintf не будет безопасно обрабатывать переполнение буфера)
  • lexical_cast должен проверять ошибки ss.fail() stringstream ( ss.fail() ), чтобы генерировать исключения при неудачах преобразования

lexical_cast хорош, потому что (IMO) исключения позволяют захватывать все ошибки без дополнительных усилий и потому, что у них есть единый прототип. Я лично не вижу, почему любой из этих свойств требует медленной работы (когда ошибок преобразования не происходит), хотя я не знаю о таких функциях C ++, которые бывают быстрыми (возможно, Spirit или boost :: xpressive?).

Изменить: я просто нашел сообщение, в котором упоминается использование BOOST_LEXICAL_CAST_ASSUME_C_LOCALE чтобы включить оптимизацию «itoa»: http://old.nabble.com/lexical_cast-optimization-td20817583.html . Существует также связанная статья с более подробной информацией.

lexical_cast может или не может быть столь же медленным по отношению к Java и Python, поскольку ваши тесты показывают, что ваши эталонные измерения могут иметь тонкую проблему. Любые распределения / освобождения рабочей области, выполняемые лексическим методом, или используемые им методы iostream, измеряются вашими эталонами, потому что C ++ не откладывает эти операции. Однако в случае Java и Python соответствующие дезадаптации фактически могут быть отложены до будущего цикла сбора мусора и пропущены с помощью эталонных измерений. (Если только цикл GC случайно возникает во время проведения эталонного теста, и в этом случае вы слишком много измеряете). Поэтому трудно понять, не изучая специфику реализаций Java и Python, сколько «затрат» следует отнести на отложенную нагрузку GC, которая может (или не может) быть в конечном итоге наложена.

Этот вид проблемы, очевидно, может применяться ко многим другим языковым ориентирам на языке C ++ vs garbage.

Как сказал Барри, lexical_cast очень общий, вы должны использовать более конкретную альтернативу, например, проверить itoa ( int->string ) и atoi ( string -> int ).

если скорость вызывает беспокойство, или вас просто интересует, насколько быстро такие приведения могут быть с C ++, в этом есть интересная тема .

Boost.Spirit 2.1 (который должен быть выпущен с Boost 1.40), кажется, очень быстро, даже быстрее, чем C-эквиваленты (strtol (), atoi () и т. Д.).

Я использую это очень быстрое решение для типов POD …

 namespace DATATYPES { typedef std::string TString; typedef char* TCString; typedef double TDouble; typedef long THuge; typedef unsigned long TUHuge; }; namespace boost { template inline const DATATYPES::TString lexical_castNumericToString( const TYPE& arg, const DATATYPES::TCString fmt) { enum { MAX_SIZE = ( std::numeric_limits::digits10 + 1 ) // sign + 1 }; // null char buffer[MAX_SIZE] = { 0 }; if (sprintf(buffer, fmt, arg) < 0) { throw_exception(bad_lexical_cast(typeid(TYPE), typeid(DATATYPES::TString))); } return ( DATATYPES::TString(buffer) ); } template inline const TYPE lexical_castStringToNumeric(const DATATYPES::TString& arg) { DATATYPES::TCString end = 0; DATATYPES::TDouble result = std::strtod(arg.c_str(), &end); if (not end or *end not_eq 0) { throw_exception(bad_lexical_cast(typeid(DATATYPES::TString), typeid(TYPE))); } return TYPE(result); } template<> inline DATATYPES::THuge lexical_cast(const DATATYPES::TString& arg) { return (lexical_castStringToNumeric(arg)); } template<> inline DATATYPES::TString lexical_cast(const DATATYPES::THuge& arg) { return (lexical_castNumericToString(arg,"%li")); } template<> inline DATATYPES::TUHuge lexical_cast(const DATATYPES::TString& arg) { return (lexical_castStringToNumeric(arg)); } template<> inline DATATYPES::TString lexical_cast(const DATATYPES::TUHuge& arg) { return (lexical_castNumericToString(arg,"%lu")); } template<> inline DATATYPES::TDouble lexical_cast(const DATATYPES::TString& arg) { return (lexical_castStringToNumeric(arg)); } template<> inline DATATYPES::TString lexical_cast(const DATATYPES::TDouble& arg) { return (lexical_castNumericToString(arg,"%f")); } } // end namespace boost 
Давайте будем гением компьютера.