Очень плохое повышение:: производительность 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<string>(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)
Времена я вижу
с ++: 6700 миллисекунд
Java: 1178 миллисекунд
питон: 6702 миллисекунды
С ++ работает так же медленно, как Python, и в 6 раз медленнее, чем Java.
Двойное литье:
c++:
std::string s ;
for(int i = 0; i < 10000000; ++i)
{
s = boost::lexical_cast<string>(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 миллисекунд
питон: 30780 миллисекунд
Так что для двойников с ++ на самом деле вдвое медленнее, чем Python, и в 20 раз медленнее, чем решение Java! Есть идеи по улучшению производительности boost::lexical_cast? Происходит ли это из-за плохой реализации stringstream или мы можем ожидать общего снижения производительности в 10 раз от использования библиотек boost.
9 ответов
Редактировать 2012-04-11
rve совершенно справедливо прокомментировал производительность lexical_cast, предоставив ссылку:
http://www.boost.org/doc/libs/1_49_0/doc/html/boost_lexical_cast/performance.html
У меня сейчас нет доступа для повышения версии 1.49, но я помню, как быстрее делал мой код на старых версиях. Так что я думаю:
- следующий ответ остается в силе (если только для целей обучения)
- вероятно, была введена оптимизация где-то между двумя версиями (я буду искать это)
- Это означает, что повышение все еще становится все лучше и лучше
Оригинальный ответ
Просто чтобы добавить информацию о превосходных ответах Барри и Мотти:
Некоторый фон
Помните, что 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 объекты.
Потоковое решение 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()) ;
Источник и цель любого типа, включая встроенные, такие как boolean или же int, что возможно в C++ из-за шаблонов.
Расширяемость? Это грязное слово?
Нет, но это хорошо известно: при написании одним и тем же кодером общие решения конкретных проблем обычно медленнее, чем конкретные решения, написанные для их конкретных проблем.
В текущем случае, в наивной точке зрения, lexical_cast будет использовать потоковые средства для преобразования из типа A в поток строк, а затем из этого потока строк в тип B,
Это означает, что до тех пор, пока ваш объект может быть выведен в поток и введен из потока, вы сможете использовать lexical_cast на нем, не касаясь ни одной строки кода.
Итак, каковы цели использования lexical_cast?
Основное использование лексического литья:
- Простота использования (эй, C++ приведение, которое работает для всего, что является ценностью!)
- Комбинируя его с тяжелым кодом шаблона, где ваши типы параметризованы, и поэтому вы не хотите иметь дело со спецификой и не хотите знать типы.
- Все еще потенциально относительно эффективен, если у вас есть базовые знания шаблона, как я покажу ниже
Точка 2 здесь очень и очень важна, потому что это означает, что у нас есть один и только один интерфейс / функция для преобразования значения типа в равное или подобное значение другого типа.
Это реальная точка, которую вы упустили, и это точка, которая стоит с точки зрения производительности.
Но это так slooooooowwww!
Если вы хотите получить быструю производительность, помните, что вы имеете дело с C++, и что у вас есть много возможностей для эффективной обработки преобразования, и все же сохраняйте lexical_cast простота использования функции.
Мне потребовалось несколько минут, чтобы посмотреть на источник lexical_cast и найти жизнеспособное решение. Добавьте в свой код C++ следующий код:
#ifdef SPECIALIZE_BOOST_LEXICAL_CAST_FOR_STRING_AND_INT
namespace boost
{
template<>
std::string lexical_cast<std::string, int>(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 для строк и целых (определяя макрос 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<int>( str );
std::string str2 = boost::lexical_cast<std::string>( str_int );
return 0;
}
Этот вариант будет быстрее, чем при использовании реализации по умолчанию, потому что в реализации по умолчанию есть создание объектов с большим потоком. И это должно быть немного быстрее, чем printf, так как printf должен разобрать строку формата.
lexical_cast является более общим, чем конкретный код, который вы используете в Java и Python. Неудивительно, что общий подход, который работает во многих сценариях (лексическое приведение немного больше, чем потоковая передача, а затем возврат во временный поток и обратно), оказывается медленнее, чем конкретные подпрограммы.
(Кстати, вы можете получить лучшую производительность от Java, используя статическую версию, Integer.toString(int), [1])
Наконец, синтаксический анализ и разбор строк обычно не так чувствителен к производительности, если только вы не пишете компилятор, в этом случае lexical_cast вероятно слишком общего назначения, и целые числа и т. д. будут рассчитываться при сканировании каждой цифры.
[1] Комментатор "Степанчег" усомнился в моей подсказке, что статическая версия может дать лучшую производительность. Вот источник, который я использовал:
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, серверная виртуальная машина:
10MM Time taken: 688 ms
10MM Time taken: 547 ms
И в клиентской ВМ:
10MM Time taken: 687 ms
10MM Time taken: 610 ms
Несмотря на то, что теоретически анализ escape может разрешить размещение в стеке, а встраивание может ввести весь код (включая копирование) в локальный метод, позволяя исключить избыточное копирование, такой анализ может занять довольно много времени и привести к значительному увеличению кодовое пространство, которое имеет другие затраты в кеше кода, которые не оправдывают себя в реальном коде, в отличие от микробенчмарков, как показано здесь.
То, что делает лексическое приведение в вашем коде, можно упростить до этого:
string Cast( int i ) {
ostringstream os;
os << i;
return os.str();
}
К сожалению, многое происходит каждый раз, когда вы вызываете Cast():
- создается поток строки, возможно, выделяющий память
- Оператор << для целого числа I называется
- результат сохраняется в потоке, возможно, выделяя память
- копия строки берется из потока
- копия строки (возможно) создана для возврата.
- память освобождена
Thn в вашем собственном коде:
s = Cast( i );
присвоение включает в себя дальнейшие распределения и освобождения выполняются. Вы можете немного уменьшить это, используя:
string s = Cast( i );
вместо.
Однако, если производительность действительно важна для вас, вы должны рассмотреть возможность использования другого механизма. Вы можете написать свою собственную версию Cast (), которая (например) создает статический поток строк. Такая версия не будет поточно-ориентированной, но это может не иметь значения для ваших конкретных потребностей.
Подводя итог, можно сказать, что lexical_cast является удобной и полезной функцией, но такое удобство приходит (как это всегда должно быть) с компромиссами в других областях.
lexical_cast может быть, а может и не быть таким медленным по отношению к Java и Python, как показывают ваши тесты, потому что ваши измерения в тестах могут иметь небольшую проблему. Любые распределения / освобождения рабочего пространства, выполняемые лексическим преобразованием или методами iostream, которые он использует, измеряются вашими тестами, потому что C++ не откладывает эти операции. Тем не менее, в случае Java и Python связанные освобождения могут фактически быть просто отложены до будущего цикла сборки мусора и пропущены измерениями тестов. (Если цикл GC случайно не произойдет, пока идет тест, и в этом случае вы будете измерять слишком много). Таким образом, трудно понять без изучения специфики реализаций Java и Python, сколько "затрат" следует отнести на отложенное бремя GC, которое может (или не может) быть в конечном итоге наложено.
Этот тип проблемы, очевидно, может относиться ко многим другим языковым тестам C++ против сборщика мусора.
К сожалению, у меня пока недостаточно комментариев, чтобы комментировать...
lexical_cast в основном не медленный, потому что он универсальный (поиск шаблонов происходит во время компиляции, поэтому вызовы виртуальных функций или другие поиски / разыменования не нужны). lexical_cast на мой взгляд, медленный, потому что он основан на iostreams C++, которые в первую очередь предназначены для потоковых операций, а не единичных преобразований, и потому что lexical_cast необходимо проверить и преобразовать сигналы ошибок iostream. Таким образом:
- объект потока должен быть создан и уничтожен
- в приведенном выше случае вывода строки обратите внимание на то, что компиляторам C++ трудно избежать копий буфера (альтернативой является форматирование непосредственно в буфер вывода, например
sprintfхотяsprintfне будет безопасно обрабатывать переполнения буфера) lexical_castдолжен проверить на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. Также есть связанная статья с более подробной информацией.
Если скорость вызывает беспокойство, или вы просто заинтересованы в том, насколько быстрыми могут быть такие приведения с помощью 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<typename TYPE>
inline const DATATYPES::TString lexical_castNumericToString(
const TYPE& arg,
const DATATYPES::TCString fmt) {
enum { MAX_SIZE = ( std::numeric_limits<TYPE>::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<typename TYPE>
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<DATATYPES::THuge>(arg));
}
template<>
inline DATATYPES::TString lexical_cast(const DATATYPES::THuge& arg) {
return (lexical_castNumericToString<DATATYPES::THuge>(arg,"%li"));
}
template<>
inline DATATYPES::TUHuge lexical_cast(const DATATYPES::TString& arg) {
return (lexical_castStringToNumeric<DATATYPES::TUHuge>(arg));
}
template<>
inline DATATYPES::TString lexical_cast(const DATATYPES::TUHuge& arg) {
return (lexical_castNumericToString<DATATYPES::TUHuge>(arg,"%lu"));
}
template<>
inline DATATYPES::TDouble lexical_cast(const DATATYPES::TString& arg) {
return (lexical_castStringToNumeric<DATATYPES::TDouble>(arg));
}
template<>
inline DATATYPES::TString lexical_cast(const DATATYPES::TDouble& arg) {
return (lexical_castNumericToString<DATATYPES::TDouble>(arg,"%f"));
}
} // end namespace boost