BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 11:09
Оценка: 2 (1)
Доброго времени суток!

Понадобилось 'посплитить' строки (вообще задача более сложная, но обо всем по порядку), и по совету “мудрых старцев” (которые по новомодной традиции, при каждом чихе отправляют к boost-у) решил потестировать производительность boost::algoruthm:split.

Честно говоря, результаты меня обескуражили…

Код на C++, STL/BOOST:

int r = 0;

vector<string> tokens(5);

for(int i = 0; i < 1000000; i++)
{
    split(tokens, "123 345 asdf 23453 asdfas", is_any_of(" "));
    r += tokens.size();
}


cout << r;

Компилятор: MS VC 8.0
(Релиз)
Опции: /Ox /Oy /I "C:\WORK\boost_1_32_0\\" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_VC80_UPGRADE=0x0700" /D "_MBCS" /FD /EHsc /MT /GS- /Gy /Za /Yu"stdafx.h" /Fp"Release\aaa.pch" /FA /Fa"Release\\" /Fo"Release\\" /Fd"Release\vc80.pdb" /W3 /nologo /c /Wp64 /Zi /TP /errorReport:prompt /D_SECURE_SCL=0

Время работы: 20 секунд. (и это при полной оптимизации и отключенными проверками !?!)

Код на C#, .NET Framework:


int res = 0;
    
for(int i = 0; i < 1000000; i++)
    res += "123 345 asdf 23453 asdfas".Split(' ').Length;
            
Console.WriteLine(res);


Время работы: ~1 сек, при 10^7 итераций ~6 сек.

Я уж тут подумал на кривизну рук, но пишу/писал на C++ достаточно долго, еще с первых GCC, TCPP 1.0, ..., и с оптимизаторами знаком не понаслышке.
[Есть подозрение на неграмотное дефолтовое аллокирование std::vector и std::string.]

Кстати .NET-ий JIT в Release-е особо не 'химичил' с этим кодом, и честно вызывал split для константной строки и далее inline-ил вызов get_Length() на возвращенном строковом массиве;

Пока переписал с исп. strtok и сделал запасной вариант под .NET.
Может есть что сказать приверженцам BOOST-а, и по возможности объяснить где "кривые руки"?
Re: BOOST, .NET, String.Split и производительность…
От: Cyberax Марс  
Дата: 16.09.06 12:26
Оценка:
Denis2005 wrote:
> split(tokens, "123 345 asdf 23453 asdfas", is_any_of(" "));
> r += tokens.size();
А если вот так:
split(tokens, "123 345 asdf 23453 asdfas", is_any_of(' '));

?
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re: BOOST, .NET, String.Split и производительность…
От: achmed Удмуртия https://www.linkedin.com/in/nail-achmedzhanov-9907188/
Дата: 16.09.06 12:31
Оценка:
Здравствуйте, Denis2005, Вы писали:

D>Доброго времени суток!


D>Понадобилось 'посплитить' строки (вообще задача более сложная, но обо всем по порядку), и по совету “мудрых старцев” (которые по новомодной традиции, при каждом чихе отправляют к boost-у) решил потестировать производительность boost::algoruthm:split.


D>Честно говоря, результаты меня обескуражили…

[skipped]

D>[Есть подозрение на неграмотное дефолтовое аллокирование std::vector и std::string.]

так и есть.

Столкнулся с такой же ситуацией, когда пререписывал анализатор логов написанный на perl на C++,
ожидалось, что программа на C++ будет работать быстрее, но perl функция split выигрывала в скорости в
десятки раз!
В итоге переписал с использованием strtok.



D>Может есть что сказать приверженцам BOOST-а, и по возможности объяснить где "кривые руки"?

ИМХО у разработчиков boost::algoruthm:split, если так хотелось STL интерфейс, то можно было
хотя бы std::list использовать вместо std::vector.
Re[2]: BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 12:31
Оценка:
Здравствуйте, Cyberax, Вы писали:

C>Denis2005 wrote:

>> split(tokens, "123 345 asdf 23453 asdfas", is_any_of(" "));
>> r += tokens.size();
C>А если вот так:
C>
C>split(tokens, "123 345 asdf 23453 asdfas", is_any_of(' '));
C>

C>?

Вообще говоря даже не компилируется.
Кстати .NET-ий имеет сигнатуру String.Split(params char[] separators), поэтому от тоже бежит по коллекции сепараторов.
Re[3]: BOOST, .NET, String.Split и производительность…
От: Cyberax Марс  
Дата: 16.09.06 12:38
Оценка:
Denis2005 wrote:
> Вообще говоря даже не компилируется.
> Кстати .NET-ий имеет сигнатуру String.Split(params char[] separators),
> поэтому от тоже бежит по коллекции сепараторов.
Тогда непонятно. В коде split'а при беглом просмотре нет ничего
криминального. Или баг, или какая-то странная фича (типа использования
локалей).
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re[4]: BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 12:43
Оценка:
Здравствуйте, Cyberax, Вы писали:

C>Denis2005 wrote:

>> Вообще говоря даже не компилируется.
>> Кстати .NET-ий имеет сигнатуру String.Split(params char[] separators),
>> поэтому от тоже бежит по коллекции сепараторов.
C>Тогда непонятно. В коде split'а при беглом просмотре нет ничего
C>криминального. Или баг, или какая-то странная фича (типа использования
C>локалей).

Врятли. Как я упоминал в первом сообщении подозрение на дуболомность дефолтовых аллокаторов у std::string и std::vector. У вас случаем не 'завалялось' какого-нибудь смарт-аллокатора для STL-контейнеров?
Re[2]: BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 12:58
Оценка:
A>ИМХО у разработчиков boost::algoruthm:split, если так хотелось STL интерфейс, то можно было
A>хотя бы std::list использовать вместо std::vector.

Использование std::list не привело к повышению производительности. Более того, оно равно в данном случае, т.к. при конструировании задаётся размер контейнера.
Re: BOOST, .NET, String.Split и производительность…
От: FR  
Дата: 16.09.06 13:00
Оценка: 1 (1) +1 :)
Здравствуйте, Denis2005, Вы писали:

D>Я уж тут подумал на кривизну рук, но пишу/писал на C++ достаточно долго, еще с первых GCC, TCPP 1.0, ..., и с оптимизаторами знаком не понаслышке.

D>[Есть подозрение на неграмотное дефолтовое аллокирование std::vector и std::string.]

Вряд ли тут аллокаторы помогут. Тут просто сами строки неправильные. Попробуй поискать реализации const_string наверно будет шустрее. Кстати от компилятора сильно зависит, vc71 отработал у меня за 22 секунды, а gcc3.4 за 7.

D>Кстати .NET-ий JIT в Release-е особо не 'химичил' с этим кодом, и честно вызывал split для константной строки и далее inline-ил вызов get_Length() на возвращенном строковом массиве;


D>Пока переписал с исп. strtok и сделал запасной вариант под .NET.

D>Может есть что сказать приверженцам BOOST-а, и по возможности объяснить где "кривые руки"?

на питон переходи, вот такой код:
r = 0
for i in xrange(1000000):
    r += len("123 345 asdf 23453 asdfas".split(" "))
    
print r

отрабатывает за 2.5 секунды
Re[2]: BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 13:03
Оценка:
FR>на питон переходи, вот такой код:
FR>
FR>r = 0
FR>for i in xrange(1000000):
FR>    r += len("123 345 asdf 23453 asdfas".split(" "))
    
FR>print r 
FR>

FR>отрабатывает за 2.5 секунды

Зачем мне питон, когда такой пример под .NET отрабатывает за 0.6 сек, и код даже короче (на C#_, чем в приведенном примере.
Re[2]: BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 13:07
Оценка:
FR>отрабатывает за 2.5 секунды

Хоть напиши свой проц/память. У меня AMD Athlon 64 3000 (1.8), память DDR 667 Mhz.
А то непонятно чего с чем меряем.
Re[3]: BOOST, .NET, String.Split и производительность…
От: FR  
Дата: 16.09.06 13:45
Оценка:
Здравствуйте, Denis2005, Вы писали:

FR>>на питон переходи, вот такой код:

FR>>
FR>>r = 0
FR>>for i in xrange(1000000):
FR>>    r += len("123 345 asdf 23453 asdfas".split(" "))
    
FR>>print r 
FR>>

FR>>отрабатывает за 2.5 секунды

D>Зачем мне питон, когда такой пример под .NET отрабатывает за 0.6 сек, и код даже короче (на C#_, чем в приведенном примере.


Ты там смайлик видел?
У меня шарп за полторы секунды отработал.
А код на шарпе длинее:
using System;

class MainApp 
{
    public static void Main() 
    { 
        int res = 0;
    
        for(int i = 0; i < 1000000; i++)
            res += "123 345 asdf 23453 asdfas".Split(' ').Length;
            
        Console.WriteLine(res);
    }
}


Re[3]: BOOST, .NET, String.Split и производительность…
От: FR  
Дата: 16.09.06 13:45
Оценка:
Здравствуйте, Denis2005, Вы писали:

FR>>отрабатывает за 2.5 секунды


D>Хоть напиши свой проц/память. У меня AMD Athlon 64 3000 (1.8), память DDR 667 Mhz.

D>А то непонятно чего с чем меряем.

Cel D 2.6 память не знаю какая, но тормозная.
Re[3]: BOOST, .NET, String.Split и производительность…
От: FR  
Дата: 16.09.06 14:10
Оценка:
Здравствуйте, Denis2005, Вы писали:

кстати профайлер говорит что процентов 20 времени сидит в ntdll.dll на примерно таком коде:

Samples     Address        Code Bytes             Instruction                  Symbol      CPU 0     
10          0x7c902f10     0x 0B C0               or eax,eax                   tan+210     10        
20          0x7c902f12     0x 74 0C               jz $+0eh (0x7c902f20)        tan+212     20        
29          0x7c902f14     0x 8D 4A FF            lea ecx,[edx-01h]            tan+214     29        
14          0x7c902f17     0x 8B 18               mov ebx,[eax]                tan+217     14        
            0x7c902f19     0x F0 0F C7 4D 00      lock cmpxchg8b [ebp+00h]                           
2842        0x7c902f1e     0x 75 F0               jnz $-0eh (0x7c902f10)       tan+224     2842


Похоже синхронизация неплохо отъедает производительность. Вообще в ntdll.dll сидит 49% времени в основном в строковых функциях и кусочках похожих тому что выше.
Re[2]: BOOST, .NET, String.Split и производительность…
От: Denis2005 Россия  
Дата: 16.09.06 14:17
Оценка:
Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Denis2005, Вы писали:


D>>Я уж тут подумал на кривизну рук, но пишу/писал на C++ достаточно долго, еще с первых GCC, TCPP 1.0, ..., и с оптимизаторами знаком не понаслышке.

D>>[Есть подозрение на неграмотное дефолтовое аллокирование std::vector и std::string.]

FR>Вряд ли тут аллокаторы помогут. Тут просто сами строки неправильные. Попробуй поискать реализации const_string наверно будет шустрее.


Даже если сделать такой неправельный const_string (заглушка, чисто для теста):


struct bad_const_str
{
    const char *ptr;

    const_str()
    {
        ptr = NULL;
    }

    const_str(const char *pa, const char *pb)
    {
        ptr = pa;
    }
};


Производительность возрасла всего на 1 секунду, иными словами проблема даже не в тормознутости std::string (как ни странно).
Re: [Benchmark] DMD быстрее всех
От: Андрей Хропов Россия  
Дата: 16.09.06 17:19
Оценка: 3 (1) :))
Здравствуйте, Denis2005, Вы писали:

Обожаю бенчмарки

Померил с использованием таймеров (чтобы не учитывать JIT компиляцию)
Вот результаты (усреднены по 10 запускам)
(Athlon XP 1700+ @ 1.5 GHZ + 512Mb DDR266)
:

1) DMD — 0.775 сек
2) GDC — 0.905 сек
3) С#/Nemerle — 1.1 сек
4) Python — 3.48 сек
5) Python+Psyco — 4.12 (не ускорил!)
6) GCC + Boost — 22.5 сек
7) MS VC++ + Boost — 35 сек

Компиляторы:
DMD — Digital Mars D 0.166
GDC — GNU D Compiler 0.19 для MinGW 3.4.2
C# — MS C# Compiler в составе VS2005
Nemerle — 0.9.3.99(svn) (от 12.09)
Python 2.4.2
Python 2.4.2 + Psyco 1.5
GCC — GCC 3.4.2 (в виде MinGW) + Boost 1.33.1
MS VC++ — MS C++ Compiler в составе VS2005 + Boost 1.33.1

Опции:
dmd -O -release -inline -ofsplit-d.exe split.d
gdc split.d -O99 -osplit-gdc.exe
csc /o+ /out:split-cs.exe split.cs
ncc -out:split-n.exe split.n
g++ split.cpp -If:/boost -O99 -osplit-gpp
сl split.cpp /Ox /Oi /Ot /GT /GL /I "F:\boost" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D_SECURE_SCL=0 /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /GS- /Fo"Release\\" /Fd"Release\vc80.pdb" /W3 /nologo /c /Wp64 /Zi /TP /errorReport:prompt
/Fesplit-cpp.exe


Исходники:

D:
import std.stdio, std.string, std.perf;

void main()
{
  auto t = new HighPerformanceCounter();
    
  t.start();
  
  uint res = 0;

    for(uint i = 0; i < 1000000; ++i)
    res += split("123 345 asdf 23453 asdfas"," ").length;
                
  t.stop();
    
  writefln("res is ", res ," ", t.milliseconds()," ms elapsed.");
}


C#:

using System;
using System.Diagnostics;

class Runner
{
  public static void Main()
  {
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    
    int res = 0;
  
    for(uint i = 0; i < 1000000; ++i)
      res += "123 345 asdf 23453 asdfas".Split(' ').Length;
      
    stopwatch.Stop();
          
    Console.WriteLine("res is {0}, {1} elapsed",
                      res, stopwatch.Elapsed);
  }
}


Nemerle:

using System.Console;
using System.Diagnostics;

def stopwatch = Stopwatch();
stopwatch.Start();
  
mutable res = 0;

repeat(1000000)
  res += "123 345 asdf 23453 asdfas".Split(' ').Length;
  
stopwatch.Stop();
      
WriteLine($"res is $res, $(stopwatch.Elapsed) elapsed");


Python:

import time

start = time.clock()
      
res = 0
for i in xrange(1000000):
    res += len("123 345 asdf 23453 asdfas".split(" "))
    
finish = time.clock()    
    
print 'res is %s, %f sec elapsed' % ( res, finish - start )


Python+Psyco:

import time
import psyco
psyco.full()

start = time.clock()
      
res = 0
for i in xrange(1000000):
    res += len("123 345 asdf 23453 asdfas".split(" "))
    
finish = time.clock()    
    
print 'res is %s, %f sec elapsed' % ( res, finish - start )


С++:

#include <vector>
#include <string>
#include <iostream>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>

#include <windows.h> // for GetTickCount

using namespace std;
using namespace boost::algorithm;

int main()
{
  DWORD start = GetTickCount();
    
  int res = 0;
  for(int i = 0; i < 1000000; i++)
  {
    // так корректней сравнивать, ведь в др программах мы размер не указывали
    // + по моим тестам почти не повлияло на скорость
    vector<string> tokens; 
    split(tokens, "123 345 asdf 23453 asdfas", is_any_of(" "));
    res += tokens.size();
  }

  DWORD stop = GetTickCount();

  cout << "res is " << res << ',' << stop - start << " ms elapsed\n";
  
  return 0;
}
Re[2]: [Benchmark] DMD быстрее всех
От: CreatorCray  
Дата: 16.09.06 18:08
Оценка:
Здравствуйте, Андрей Хропов, Вы писали:

АХ>6) GCC + Boost — 22.5 сек

АХ>7) MS VC++ + Boost — 35 сек
А добавьте ка пунктик C++ + самописный split
Бо что то мне кажется что тут надо в "консерватории" что то подправить
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: [Benchmark] DMD быстрее всех
От: FR  
Дата: 16.09.06 18:14
Оценка:
Здравствуйте, Андрей Хропов, Вы писали:

АХ>5) Python+Psyco — 4.12 (не ускорил!)


Psyco не любит когда код в основном теле модуля надо его в функцию засунуть, тогда чуть ускорит:
from time import clock
import psyco
psyco.full()

def run():
    res = 0
    for i in xrange(1000000):
        res += len("123 345 asdf 23453 asdfas".split(" "))
    return res


start = clock()
res = run()   
finish = clock()    
    
print 'res is %s, %f sec elapsed' % ( res, finish - start )

У меня python 2.4.1 ~ 2.6 сек.
python 2.4.1 + psyco 1.5.0 ~ 1.8 сек.
IronPython-1.0 ~ 3.0 сек.
Re[3]: [Benchmark] DMD быстрее всех
От: FR  
Дата: 16.09.06 18:55
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, Андрей Хропов, Вы писали:


АХ>>6) GCC + Boost — 22.5 сек

АХ>>7) MS VC++ + Boost — 35 сек
CC>А добавьте ка пунктик C++ + самописный split
CC>Бо что то мне кажется что тут надо в "консерватории" что то подправить

лучше держи на очень не шустром интерпретаторе:
REBOL [] res: 0
probe loop 1000000 [res: res + length? parse "123 345 asdf 23453 asdfas" { }]

3.6 секунды
Re[4]: [Benchmark] DMD быстрее всех
От: CreatorCray  
Дата: 16.09.06 19:07
Оценка:
Здравствуйте, FR, Вы писали:

CC>>А добавьте ка пунктик C++ + самописный split

CC>>Бо что то мне кажется что тут надо в "консерватории" что то подправить
FR>лучше держи на очень не шустром интерпретаторе:
не, сравнение агоритма boost с алгоримом встроенным в интерпретатор меня не очень то интересует. Больше все таки интересует насколько хреново реализовали split в самом бусте.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: [Benchmark] DMD быстрее всех
От: Denis2005 Россия  
Дата: 16.09.06 19:38
Оценка:
CC>А добавьте ка пунктик C++ + самописный split

Есть такой, итеративно strtok-ом собирает в vector<string> с заранее заданной размерностью.
По результатам производительность чуть ниже .NET-кого варианта.
Вообщем в BOOST-е, чего-то бравые парни перемудрили,
и нулевыми издержками в данном случае совсем не попахивает.
Надеюсь в C++0x это безобразие полностью не попадет,
или если попадет, то в более продуманном варианте.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.