Re[8]: [performance] ладно, заинтриговал - C/C++

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

C>Я обычно предполагаю, что люди должны иметь хотя бы базовые знания, чтобы попытаться ответить. Знание того, что в C# все строки в юникоде и сравнивать анси с юникодом неправильно — это как раз из числа базовых знаний.

А С# парсит символ '٨' в 8? (согласно документации — нет). Раз нет, то какой тогда смысл использовать юникодную строку в С++ для хранения строкового представления чисел?

В общем, погонял в ленсуке:

$ dotnet --version
6.0.301
$ g++ --version
g++ (Ubuntu 11.2.0-19ubuntu1) 11.2.0

C#

using System.Diagnostics;

var vals = new string[0x4000_000];
var random = new Random(DateTime.Now.Second);

var watch = Stopwatch.StartNew();
for (var i = 0; i < vals.Length; i++)
    vals[i] = random.Next().ToString();
watch.Stop();

Console.WriteLine($"Init: {watch.Elapsed.TotalSeconds}");

TestPerformanceManaged(vals);

static void TestPerformanceManaged(string[] vals)
{
    var watch = Stopwatch.StartNew();

    var res = 0;
    foreach (var val in vals)
        res ^=  ParseInt(val);

    Console.WriteLine("Hash = {0:X}", res);

    watch.Stop();
    Console.WriteLine($"TestPerformanceManaged: {watch.Elapsed.TotalSeconds}");
}

static int ParseInt(string val)
{
    int res = 0;
    foreach (var d in val)
    {
        if ('0' <= d && d <= '9')
            res = res * 10 + d - '0';
        else
            throw new ArgumentOutOfRangeException("'" + d + "': Symbol is out of the range");
    }
    return res;
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <random>


std::vector<std::wstring> MakeIntSequence(int size)
{
   std::mt19937 gen(std::random_device{}());
   std::uniform_int_distribution<> distrib(0, std::numeric_limits<int>::max());
   std::vector<std::wstring> v;
   v.reserve(size);

   for (int i = 0; i < size; ++i)
      v.push_back(std::to_wstring(distrib(gen)));

   return v;
}

int ParseInt(const std::wstring& wstr)
{
   int res{};

   for (auto d : wstr)
   {
      if ('0' <= d && d <= '9')
         res = res * 10 + d - '0';
      else
         throw std::out_of_range("'" + std::to_string(d) + "': Symbol is out of range");
   }

   return res;
}

int main()
{
   namespace tm = std::chrono;

   const auto vals = MakeIntSequence(0x4000000);

   const auto t0 = tm::steady_clock::now();

   int hash{};
   for (const auto& val : vals)
      hash ^= ParseInt(val);
   const auto dt = tm::duration_cast<tm::milliseconds>(tm::steady_clock::now() - t0);

   std::cout << "Hash = " << std::hex << hash << std::endl;
   std::cout << "Processing time: " << std::dec << dt.count() << "ms" << std::endl;
}

Флаги g++: `-std=c++17 -O2`. Флаги C# — ХЗ, запускал так: `dotnet run --configuration Release`.

Цепепе: 698, 704 и 715ms.
Сисярп: 0.7095647, 0.729915 и 0.7312779

std::string: ~690-695ms.

UPD

u16string

#include <chrono>
#include <codecvt>
#include <iostream>
#include <locale>
#include <random>
#include <string>
#include <vector>


std::u16string to_u16string(int i)
{
    std::wstring_convert<std::codecvt_utf8_utf16<char16_t>, char16_t> conv;
    return conv.from_bytes(std::to_string(i));
}

std::vector<std::u16string> MakeIntSequence(int size)
{
    std::mt19937 gen(std::random_device{}());
    std::uniform_int_distribution<> distrib(0, std::numeric_limits<int>::max());
    std::vector<std::u16string> v;
    v.reserve(size);

    for (int i = 0; i < size; ++i)
        v.push_back(to_u16string(distrib(gen)));

    return v;
}

int ParseInt(const std::u16string& wstr)
{
    int res{};

    for (auto d : wstr)
    {
        if ('0' <= d && d <= '9')
            res = res * 10 + d - '0';
        else
            throw std::out_of_range("'" + std::to_string(d) + "': Symbol is out of range");
    }

    return res;
}

int main()
{
    namespace tm = std::chrono;

    const auto vals = MakeIntSequence(0x4000000);

    const auto t0 = tm::steady_clock::now();

    int hash{};
    for (const auto& val : vals)
        hash ^= ParseInt(val);
    const auto dt = tm::duration_cast<tm::milliseconds>(tm::steady_clock::now() - t0);

    std::cout << "Hash = " << std::hex << hash << std::endl;
    std::cout << "Processing time: " << std::dec << dt.count() << "ms" << std::endl;
}

763, 772, 775ms и жрёт кучу памяти, больше, чем с 4-хбайтовым wstring. Думаю, из-за конверсий.

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

Q>1. Исходный вариант на C# работает быстрее, потому что C#-ный аллокатор пихает строки подряд, а C++-ный распределяет их по адресному пространству. Это замедляет работу программ, которые единоразово выделяют много небольших объектов, и потом их однократно обрабатывают. С другой стороны, реалистичные примеры с многократным выделением/освобождением будут, скорее всего, работать быстрее.

Я писал уже выше, я считаю, что это самое хорошее объяснение на текущий момент. Чтобы его подвердить, я набросал прямо в примере простенький шаблонный класс строк фиксированного размера, совместимый по интерфейсу со стандратными строками, чтобы можно было легко переключаться между типами и достиг заметного ускорения плюсового кода — примерно от 840 мс до примерно 550 мс. По-моему, предположение полностью подтвердилось.

Привожу актуальные варианты плюсового и сишарпного кода, которые участвовали в сравнении:

C++ 550 ms

#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <chrono>
#include <random>
#include <limits>

template <typename T, size_t S>
class FixedSizeStr
{
public:

   using value_type = T;
   using iterator = T*;
   using const_iterator = const T*;

   FixedSizeStr() = default;
   FixedSizeStr(const std::basic_string<T>& string)
   : m_size(string.size())
   {
      if (m_size <= S)
         std::copy(string.begin(), string.end(), m_buf);
      else
         throw std::out_of_range(
            "Input string size (" + std::to_string(m_size)+
            ") exceeds the limit (" + std::to_string(S) + ")");
   }
   bool empty() const { return m_size == 0; }
   size_t size() const { return m_size; }
   const_iterator begin() const { return m_buf; }
   const_iterator end() const { return m_buf + m_size; }
   const value_type* data() const { return m_buf; }

private:
   T m_buf[S]{};
   size_t m_size{};
};

//using ValStr = std::wstring;
using ValStr = FixedSizeStr<wchar_t, 10>;

std::vector<ValStr> MakeIntSequence(size_t size)
{
   std::random_device rd;  //Will be used to obtain a seed for the random number engine
   std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
   std::uniform_int_distribution<> distrib(0, std::numeric_limits<int32_t>::max());
   std::vector<ValStr> v;
   v.reserve(size);
   for (size_t i = 0; i < size; ++i)
   {
      v.push_back(std::to_wstring(distrib(gen)));
   }
   return v;
}

int32_t ParseInt(const ValStr& valStr)
{
   int32_t res{};
   for (const auto& c : valStr)
   {
      const uint32_t d = c - '0';
      if (d <= 9)
      {
         res = res * 10 + d;
      }
      else
      {
         throw std::out_of_range("'" + std::to_string(c) + "': Symbol is out of range");
      }
   }
   return res;
}

void testDistributionInMemory(const std::vector<ValStr>& v)
{
   if (v.size() >= 2)
   {
      std::intptr_t minInterval = std::numeric_limits<std::intptr_t>::max();
      std::intptr_t maxInterval{};
      const wchar_t* prev = v[0].data();

      for (size_t i = 1; i < v.size(); ++i)
      {
         const wchar_t* next = v[i].data();
         std::intptr_t nextInterval = next - prev;
         if (minInterval > nextInterval)
         {
            minInterval = nextInterval;
         }
         if (maxInterval < nextInterval)
         {
            maxInterval = nextInterval;
         }
         prev = next;
      }
      std::cout << "[Distribution in memory]: Min Interval: " << minInterval << ", Max Interval: " << maxInterval << std::endl;
   }
}

int main()
try
{
   namespace tm = std::chrono;

   const auto vals = MakeIntSequence(0x4000000);

   const auto t0 = tm::steady_clock::now();

   int32_t hash{};
   for (const auto& val : vals)
   {
      hash ^= ParseInt(val);
   }
   const tm::duration<double> dt = tm::steady_clock::now() - t0;

   std::cout << "Hash = " << std::hex << hash << std::dec << std::endl;
   std::cout << "Processing time: " << dt.count() << " sec" << std::endl;
   testDistributionInMemory(vals);
}
catch (const std::exception& ex)
{
   std::cerr << "[Unhandled Exception]: " << ex.what() << std::endl;
}

C# 750 ms

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ParseIntCS
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var vals = new string[0x4000_000];

            var watch = Stopwatch.StartNew();
            var random = new Random(DateTime.Now.Second);
            for (var i = 0; i < vals.Length; i++)
            {
                vals[i] = random.Next().ToString();
            }

            watch.Stop();
            Console.WriteLine($"Init: {watch.Elapsed.TotalSeconds}");

            TestPerformanceManaged(vals);
        }

        static void TestPerformanceManaged(string[] vals)
        {
            try
            {
                var watch = Stopwatch.StartNew();

                var res = 0L;

                foreach (var val in vals)
                {
                    //res ^= int.Parse(val);
                    res ^= ParseInt(val);
                }

                Console.WriteLine("Hash = {0:X}", res);

                watch.Stop();
                Console.WriteLine($"TestPerformanceManaged: {watch.Elapsed.TotalSeconds} sec");
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.ToString());
            }
        }

        static int ParseInt(string val)
        {
            int res = 0;
            foreach (var d in val)
            {
                if ('0' <= d && d <= '9')
                {
                    res = res * 10 + d - '0';
                }
                else
                {
                    throw new ArgumentOutOfRangeException("'" + d + "': Symbol is out of the range");
                }
            }
            return res;
        }
    }
}

В плюсовом варианте дополнительно выводится информация по распределению строк в памяти.

R>я набросал прямо в примере простенький шаблонный класс строк фиксированного размера, совместимый по интерфейсу со стандратными строками, чтобы можно было легко переключаться между типами и достиг заметного ускорения плюсового кода — примерно от 840 мс до примерно 550 мс. По-моему, предположение полностью подтвердилось.

В std::string INT_MAX влазит без динамического выделения памяти. Но переключение на std::string выиграло ~20ms (от ~700).

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

σ>В общем, погонял в ленсуке:
σ>

$ dotnet --version
σ>6.0.301
σ>$ g++ --version
σ>g++ (Ubuntu 11.2.0-19ubuntu1) 11.2.0

σ>Флаги g++: `-std=c++17 -O2`. Флаги C# — ХЗ, запускал так: `dotnet run --configuration Release`.

σ>Цепепе: 698, 704 и 715ms.
σ>Сисярп: 0.7095647, 0.729915 и 0.7312779

Глядя на цифры, я бы предположил, что в gcc SSO работает более эффективно, чем в msvc. Чтобы проверить, можно попробовать запустить расширенную версию отсюда: http://rsdn.org/forum/cpp/8309001.1. Там выводится дополнительная информация о распределении буферов строк в памяти. Нужно не забыть только переключить алиас ValStr на std::wstring.

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

σ>В std::string INT_MAX влазит без динамического выделения памяти. Но переключение на std::string выиграло ~20ms (от ~700).

Я это понимаю. И мне нравится, как ты высказался здесь: http://rsdn.org/forum/cpp/8308744.1. Но раз уж мы повелись на провокацию и начали работать с wstring, то давай уже доведем начатое до какого-то логического завершения.

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

R>Глядя на цифры, я бы предположил, что в gcc SSO работает более эффективно, чем в msvc. Что бы проверить, можно попробовать запустить расширенную версию отсюда: http://rsdn.org/forum/cpp/8309001.1. Там выводится дополнительная информация о распределении буферов строк в памяти. Нужно не забыть только переключить алиас ValStr на std::wstring.
еще в линухе sizeof(wchar_t)=4

R>>Глядя на цифры, я бы предположил, что в gcc SSO работает более эффективно, чем в msvc. Что бы проверить, можно попробовать запустить расширенную версию отсюда: http://rsdn.org/forum/cpp/8309001.1. Там выводится дополнительная информация о распределении буферов строк в памяти. Нужно не забыть только переключить алиас ValStr на std::wstring.
_>еще в линухе sizeof(wchar_t)=4

oops, забыл добавить `-fshort-wchar`. Но с ним валится:

terminate called after throwing an instance of 'std::out_of_range'
  what():  '37': Symbol is out of range

R>Глядя на цифры, я бы предположил, что в gcc SSO работает более эффективно, чем в msvc. Что бы проверить, можно попробовать запустить расширенную версию отсюда: http://rsdn.org/forum/cpp/8309001.1.

По объёму SSO, если верить интернету, баффер одинаковый по размеру, но MSVC как-то странно его использует. Это можно проверить по https://godbolt.org/z/jKvjjbbM8, где в MSVC в начале есть проверка на 8 и прыжки:

int ParseInt(std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> > const &) PROC ; ParseInt, COMDAT
$LN60:
        sub     rsp, 168                      ; 000000a8H
        xor     edx, edx
        mov     r8, rcx
        cmp     QWORD PTR [rcx+24], 8
        jb      SHORT $LN54@ParseInt
        mov     r8, QWORD PTR [rcx]
        mov     r9, r8
        jmp     SHORT $LN57@ParseInt
$LN54@ParseInt:
        mov     r9, rcx
$LN57@ParseInt:

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

R>Если я упрусь рогом, тявкать ты больше не сможешь.

Какой грозный.

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

R>Мечтай потихоньку.

Реплики твои становятся все бессвязнее и бессвязнее. Так скоро до "абырвалг" дойдешь.

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

C>Реплики твои становятся все бессвязнее и бессвязнее. Так скоро до "абырвалг" дойдешь.

Брысь отсюда, чертило. В хлеву твоем место. А здесь люди.

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

R>Тем не менее, ты ждешь чего-то.

У меня иногда бывают такие случаи, когда я думаю о людях слишком хорошо.

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

?>Знание того, что std::string не значит автоматически анси — это как раз из числа базовых знаний.

Как в том анекдоте — ответ теоретически верный, но неуместный и бесполезный.

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

C>>Реплики твои становятся все бессвязнее и бессвязнее. Так скоро до "абырвалг" дойдешь.
R>Брысь отсюда, чертило. В хлеву твоем место. А здесь люди.

Сделай уже последние полшага до "абырвалг" наконец

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

?>Сравнивают юникод (utf8) с юникодом (utf16). То, что C# не умеет в эффективные строки — это его проблема, никто не обязан специально ухудшать C++-код из-за этого.

Исходные данные — текст, в котором есть как числа, так и строки. Так что писать/читать файл как юникод — единственный разумный вариант. Ну а если тебе хочется сначала перекодировать числа в анси, то вперед и с песней.

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

Q>На C# для этого нужна черная магия под названием unsafe.

Чтобы сложить символы в массив, никакой unsafe не нужен. Да и сам по себе он не более черный, чем указатели в C++, которые чуть менее чем везде.

C>Исходные данные — текст, в котором есть как числа, так и строки.
Как это понимать? Числа туда в бинарном виде из памяти сдамплены?
C>Так что писать/читать файл как юникод — единственный разумный вариант.
Если читать в std::string, получится 0 перекодирований. Куда разумнее?
C>Ну а если тебе хочется сначала перекодировать числа в анси, то вперед и с песней.
Так это при чтении в двухбайтовые сисярпые строки как раз приходится перекодировать, ведь 99.999% исходных данных это UTF-8 (JSON/XML/HTML…)

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

C>Сделай уже последние полшага до "абырвалг" наконец

Сделай пол шага и иди на... Мелкой рысью.

	От:	B0FEE664
	Дата:	05.07.22 11:40
	Оценка:

	От:	σ
	Дата:	05.07.22 14:13
	Оценка:

	От:	rg45
	Дата:	05.07.22 14:23
	Оценка:

	От:	σ
	Дата:	05.07.22 14:27
	Оценка:

	От:	rg45
	Дата:	05.07.22 14:31
	Оценка: