Re[9]: [performance] чего-то я не понимаю в этой жизни
От: σ  
Дата: 04.07.22 22:10
Оценка: +1
V>P.S. Кстати, почему-то С# инкрементит на единицу, как-будто у него строка из char-ов состоит
Ты про
inc      esi
?
Оно умножается на 2:
       movsxd   rcx, esi-------------˅
       movzx    rbx, word  ptr [rdi+2*rcx+12]
Re[3]: [performance] ладно, заинтриговал
От: Quebecois Канада https://www.canada.ca/
Дата: 05.07.22 02:09
Оценка: 18 (4)
Здравствуйте, rg45, Вы писали:

R>Вот здесь
Автор: rg45
Дата: 03.07.22
есть два примера для сравниния — на C++ и на C# — с максимально приближенным кодом и рукописными процедурами парсинга — примитивными, но равноценными. И пример на C++ проигрывает примеру на C# процентов на 10 — 15. Не в пять раз, конечно, но проигрывает! Пока никто не смог даже предположительно объяснить, как такое может быть. Там быстродействие зависит от значений во входной последовательности. Этому вопросу я тоже уже уделил внимание — все примерно равноценно.


Чёрт, хотел Rise of Nations пройти в порядке отдыха, а в итоге убил полчаса на числодробительство. Ладно, по порядку:

На древнем i7-5960x код по ссылке дает: 1.5sec (C#) и порядка 1400 мсек (C++). (ВАЖНО: запускаем вне отладчика по Ctrl-F5, иначе будет огромный разброс). Время складывается из:

1. Собственно работы CPU
2. Доступа к RAM (и эффективности кэша)
3. Погрешности измерения

Запускаем C# 3 раза подряд: 1.55s, 1.38s, 1.42s. Это разброс больше, чем разница между вариантами. Оборачиваем проход всех значений в:
    for (int i = 0; i < 10; i++)
    {
    /* ... */
    }


Получаем 13400±100ms в C# и 12700±700ms в C++. Разброс меньше, но все равно сравним с разницей.

Убираем из картины память. Делим количество элементов на 1000 и умножаем на него же количество прогонов. 13000±200ms (C#) против 8800±200 у С++. Плюсы почти в полтора раза быстрее!

Проверяем гипотезу, вручную загнав все строки в последовательный массив:
  мегакостыль — proof-of-concept quality
  я предупредил
std::vector<wchar_t> g_AllChars;

class ContiguouslyAllocatedString
{
private:
    size_t _Start = 0, _End = 0;

public:
    ContiguouslyAllocatedString(const std::wstring &str)
    {
        _Start = g_AllChars.size();
        for (const auto ch : str)
            g_AllChars.push_back(ch);
        _End = g_AllChars.size();
    }

    class iterator
    {
    private:
        size_t _Index;

    public:
        iterator(int index)
            : _Index(index)
        {
        }

        wchar_t operator*() const
        {
            return g_AllChars[_Index];
        }

        bool operator!=(const iterator &right) const
        {
            return _Index != right._Index;
        }

        void operator++()
        {
            _Index++;
        }
    };

    iterator begin() const
    {
        return iterator(_Start);
    }

    iterator end() const
    {
        return iterator(_End);
    }
};


Получаем 9500±200ms на C++. Т.е. в 1.36x быстрее, чем C#.

Если очень надо, костыль можно зарефакторить через custom allocator к изящному коду, полностью взаимозаменяемому с библиотечным, и 100% сравнимому по быстродействию. На C# для этого нужна черная магия под названием unsafe.

Ну и раз уж я заглянул одним глазом в ассемблер, то держите оптимизацию, снижающую время на C++ до 7750±100мс (в 1.67 раз быстрее оригинала на C#):
  буквоедство
    for (auto d : wstr)
    {
        uint32_t number = (uint32_t)d - (uint32_t)'0';
        if (number <= 9)
        {
            res = res * 10 + number;
        }
        else
        {
            throw std::out_of_range("'" + std::to_string(d) + "': Symbol is out of range");
        }
    }

Механика переполнения, позволяет делать одну проверку вместо двух, плюс, оптимизатор не догадался сначала вычесть '0' а потом проверять range, и в итоге, лазил в память дважды.


Итого:

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

2. На C++ этот bottleneck можно легко переопределить, написав свой аллокатор, и не потеряв совместимость с остальным кодом (через typedef). На C# так нельзя.

Вердикт: если уметь пользоваться C++, то можно хорошо обогнать C# без потерь масштабируемости. Если не хочется заморачиваться, или производительность не критична, на C# писать гораздо быстрее.
Re: [performance] чего-то я не понимаю в этой жизни
От: Quebecois Канада https://www.canada.ca/
Дата: 05.07.22 02:13
Оценка:
Здравствуйте, Codealot, Вы писали:

C>Для тех же данных, код на C++ выполняется за 5.9 секунд и на C# за 1.2 секунды.

C>
вот здесь
Автор: Quebecois
Дата: 05.07.22
детально разобраны примеры, приведенные к общему знаменателю трудами rg45.
Отредактировано 05.07.2022 2:13 Quebecois . Предыдущая версия .
Re[6]: [performance] чего-то я не понимаю в этой жизни
От: rg45 СССР  
Дата: 05.07.22 05:26
Оценка:
Здравствуйте, σ, Вы писали:

R>>У C# выхлоп не непосредственно в машинные коды, а в промежуточный платформенно-независимый код intermediate language (IL).

σ>https://godbolt.org/z/1oanThds6

Да-да, можно. Машинный код можно посмотреть и прямо в студии.
--
Re[4]: [performance] ладно, заинтриговал
От: rg45 СССР  
Дата: 05.07.22 05:37
Оценка:
Здравствуйте, Quebecois, Вы писали:

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


Да-да, трюк известный! Я его применял еще на заре своей деятельности как программиста. Но, помнится, как-то раз мне за такое надавали линейкой по рукам и сказали, что "битхаки нам тут не нужны". Мол, современные оптимизаторы (Visual Studio 5.0 ) и сами умеют выполнять такие преобразования, поэтому текст программы должен быть ориентирован на человека, в первую очередь. Можно сказать, травма детства

Ну и соображение вдогонку: этот же самый финт можно проделать и в примере на C#. Так что, думаю, что это не та оптимизация, которая способна изменить баланс сил.
--
Отредактировано 05.07.2022 6:13 rg45 . Предыдущая версия .
Re[4]: [performance] ладно, заинтриговал
От: rg45 СССР  
Дата: 05.07.22 05:47
Оценка:
Здравствуйте, Quebecois, Вы писали:

Q>1. Исходный вариант на C# работает быстрее, потому что C#-ный аллокатор пихает строки подряд, а C++-ный распределяет их по адресному пространству.


Хорошее объяснение, спасибо.
--
Re[9]: [performance] чего-то я не понимаю в этой жизни
От: rg45 СССР  
Дата: 05.07.22 05:56
Оценка:
Здравствуйте, Videoman, Вы писали:

V>А причем тут умножение на 10. Он всю строчку: res = res * 10 + d — '0'; в два lea загнал.


Кстати, немного оффтопа. Когда я набирал это выражение для примера на C#, после ввода "плюса" студийный интеллисенс предложил мне в качестве подсказки оставшуюся часть выражения, именно в таком виде, как записано. До сих пор недоумеваю, как он догадался. В плюсовом примере подсмотрел, что ли? Плюсовый пример был в этом же солюшене.
--
Re[8]: [performance] чего-то я не понимаю в этой жизни
От: rg45 СССР  
Дата: 05.07.22 06:07
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>Согласен. Ещё у Александреску был быстрый вариант на switch без цикла. Но это не для wchar


Интересно было бы глянуть. Ссылки не сохранилось?
--
Re[5]: [performance] ладно, заинтриговал
От: Videoman Россия https://hts.tv/
Дата: 05.07.22 06:22
Оценка:
Здравствуйте, rg45, Вы писали:

R>Хорошее объяснение, спасибо.


Не-а. С++ строки имеют SSO. 16-20 элементов не вызовут никаких аллокаций.
Re[6]: [performance] ладно, заинтриговал
От: rg45 СССР  
Дата: 05.07.22 06:30
Оценка:
Здравствуйте, Videoman, Вы писали:

V>Не-а. С++ строки имеют SSO. 16-20 элементов не вызовут никаких аллокаций.


А я вот как раз об этом вспомнил. Только я вот не помню, эта оптимизация является требованием стандарта, или опциональна?
--
Re[9]: [performance] чего-то я не понимаю в этой жизни
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 05.07.22 06:32
Оценка: 7 (1)
Здравствуйте, rg45, Вы писали:

N>>Согласен. Ещё у Александреску был быстрый вариант на switch без цикла. Но это не для wchar

R>Интересно было бы глянуть. Ссылки не сохранилось?

Вот оно.
Но я не запускал.
Re[7]: [performance] ладно, заинтриговал
От: Videoman Россия https://hts.tv/
Дата: 05.07.22 06:45
Оценка:
Здравствуйте, rg45, Вы писали:

R>А я вот как раз об этом вспомнил. Только я вот не помню, эта оптимизация является требованием стандарта, или опциональна?


Опциональна, но во всех современных С++ библиотеках она используется.

P.S. Относительно вопроса скорости примера: похоже, что С# 6.0 компилятор тупо сгенерировал более быстрый код, чем MSVC. Либо действительно числа не помещаются в буфера SSO и ты, по сути, меряешь скорости разных структур в памяти.
Re[8]: [performance] ладно, заинтриговал
От: rg45 СССР  
Дата: 05.07.22 07:26
Оценка:
Здравствуйте, Videoman, Вы писали:

V>Опциональна, но во всех современных С++ библиотеках она используется.

V>P.S. Относительно вопроса скорости примера: похоже, что С# 6.0 компилятор тупо сгенерировал более быстрый код, чем MSVC. Либо действительно числа не помещаются в буфера SSO и ты, по сути, меряешь скорости разных структур в памяти.

В текушем коде примера случайные числа генерируются в диапазоне [0 .. std::numeric_limits<int32_t>::max()]. То есть, максимальная длина строки не должна превышайть 9-ти символов и SSO должна быть эффективна, если только она используется. Я, не мудрствуя лукаво, добавил функцию, которая выводит в конце минимальный и максимальный интервалы между буферами соседних элементов входной последовательности. И вот, выходит, что не используется SSO, строки здорово разбросаны по памяти:

Hash = 41910796
Processing time: 0.83061 sec
[Distribution in memory]: Min Interval: -3218203360, Max Interval: 1680855496


  Полный текст примера
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <random>

using Int = int32_t;

std::vector<std::wstring> 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<std::wstring> v;
   v.reserve(size);
   for (size_t 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;
}

void testDistributionInMemory(const std::vector<std::wstring>& 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();

   Int 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;
}
--
Отредактировано 05.07.2022 7:28 rg45 . Предыдущая версия .
Re[4]: [performance] ладно, заинтриговал
От: rudzuk  
Дата: 05.07.22 08:02
Оценка: :))) :)
Здравствуйте, Quebecois, Вы писали:

Q> Вердикт: если уметь пользоваться C++, то можно хорошо обогнать C# без потерь масштабируемости. Если не хочется заморачиваться, или производительность не критична, на C# писать гораздо быстрее.


Не, вердикт тут другой: возьмутся два программиста решать задачу типичными средствами своего языка... Сисиплюсник потом долго будет пытаться "догнат и перегнат", а дотнетчик будет в Rise of Nations играть
avalon/3.0.0
Re[5]: [performance] ладно, заинтриговал
От: B0FEE664  
Дата: 05.07.22 08:50
Оценка:
Здравствуйте, rudzuk, Вы писали:

R>Не, вердикт тут другой: возьмутся два программиста решать задачу типичными средствами своего языка... Сисиплюсник потом долго будет пытаться "догнат и перегнат", а дотнетчик будет в Rise of Nations играть


Не факт. Мерить надо интегральное время, а не кусочка кода. Чудес не бывает, а значит в С# время будет тратиться на аллокацию/освобождение памяти.
И каждый день — без права на ошибку...
Re[4]: [performance] ладно, заинтриговал
От: σ  
Дата: 05.07.22 09:07
Оценка:
Q>Ну и раз уж я заглянул одним глазом в ассемблер, то держите оптимизацию, снижающую время на C++ до 7750±100мс (в 1.67 раз быстрее оригинала на C#):
Q>Механика переполнения, позволяет делать одну проверку вместо двух

В который ассемблер смотрел? Все проверяют только один раз https://godbolt.org/z/jKvjjbbM8
Отредактировано 05.07.2022 9:23 σ . Предыдущая версия .
Re[5]: [performance] чего-то я не понимаю в этой жизни
От: σ  
Дата: 05.07.22 09:56
Оценка: +1 :)
C>Знание того, что в C# все строки в юникоде и сравнивать анси с юникодом неправильно — это как раз из числа базовых знаний.

Знание того, что std::string не значит автоматически анси — это как раз из числа базовых знаний.
Re[3]: [performance] чего-то я не понимаю в этой жизни
От: σ  
Дата: 05.07.22 09:59
Оценка: +2 :)
C>Ну начнем с того, что у тебя там string а не wstring. Так что ты сравниваешь яблоки с апельсинами.

Сравнивают юникод (utf8) с юникодом (utf16). То, что C# не умеет в эффективные строки — это его проблема, никто не обязан специально ухудшать C++-код из-за этого.
Ещё потребуй завезти GC в C++, а то ведь иначе получается сравнение яблок с апельсинами.
Re: [performance] чего-то я не понимаю в этой жизни
От: tryAnother  
Дата: 05.07.22 10:12
Оценка: +1
В тред врывается питон.
а точнее pypy
  код
import random
import sys
import time

def make_int_seq(cnt):
    res = []
    for _ in range(cnt):
        s = str(random.randint(0, 0xffffffff))
        res.append(s)
    return res

def get_hash(strs):
    hash = 0
    for s in strs:
        i = int(s)
        hash ^= i
    return hash
   
   
if len(sys.argv) < 2:
    pritn("usage: program N")
    sys.exit(1)
    
cnt = int(sys.argv[1])

t1 = time.time()
strs = make_int_seq(cnt)

t2 = time.time()

h = get_hash(strs)
t3 = time.time()

print(f"make strings: {(t2 - t1)*1000:.0f} ms")
print(f"hash = {h}. calc time: {(t3 - t2)*1000:.0f} ms")



C:\bin\pypy3.9-v7.3.9-win64\pypy.exe 1.py 10000000
make strings: 5016 ms
hash = 2448578156. calc time: 177 ms


код с++ http://rsdn.org/forum/cpp/8307046.1
Автор: rg45
Дата: 02.07.22
на моей старенькой машине
с i2600 и 8 GB памяти и собранный ms версии 19.29.30038.1 для x86 на тех же 10 млн элементах выполняется за

Hash = 4732e034
Processing time: 141ms


10 млн так как больше в память не влезает
Re[7]: [performance] чего-то я не понимаю в этой жизни
От: σ  
Дата: 05.07.22 11:19
Оценка:
V>Фига он соптимизировал:
lea eax, [rax+4*rax]
lea eax, [rbx+2*rax-48]

V>
Но при этом не соптимизировал сравнение до одного раза:
       cmp      ebx, 48
       jl       SHORT G_M39492_IG05
       cmp      ebx, 57
       jg       SHORT G_M39492_IG05

Ср. с MSVC
        sub     cx, 48
        cmp     cx, 9
        ja      SHORT $LN5@ParseInt

GCC
        sub     eax, 48
        cmp     ax, 9
        ja      .L35

Clang
        lea     edi, [rbx - 48]
        cmp     di, 9
        ja      .LBB0_6
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.