1. C++ / Говнокод #27074

    0

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    //библиотеки cuda_runtime.h и device_launch_parameters.h
    //для работы с cyda
    #include "cuda_runtime.h"
    #include "device_launch_parameters.h"
    #include<vector>
    #include<string>//для getline
    #include <stdio.h>
    #include<fstream>
    using namespace std;
    __global__ void Upload_to_GPU(unsigned long long  *Number,unsigned long long  *Stepn, bool *Stop,unsigned long long  *INPUT,unsigned long long  *max) {
    	int thread = threadIdx.x;
    	unsigned long long  MAX_DEGREE_OF = max[0];
        int X = thread;
    	unsigned long long  Calculated_number = 1;
    	unsigned long long  Current_degree_of_number = 2;
        unsigned long long   Original_numberP = INPUT[0];
    	Stop[thread] = false;
    	bool BREAK = false;
    	if (X!=0&&X!=1) {
    		while (!BREAK) {
    			if (Current_degree_of_number <= MAX_DEGREE_OF) {
    				Calculated_number = 1;
    				for (int counter = 0; counter < Current_degree_of_number; counter++) {
    				 Calculated_number	*=X;
    				}
    				if (Calculated_number == Original_numberP) {
    					Stepn[thread] = Current_degree_of_number;
    					Number[thread] = X;
    					Stop[thread] = true;
    					BREAK = true;
    				}
    				Current_degree_of_number++;
    			}
    			else { BREAK = true; }
    		}
    	}
    }

    https://habr.com/post/525892/
    > Сравнение времени выполнения алгоритма на CPU и GPU

    Запостил: gost, 31 Октября 2020

    Комментарии (70) RSS

    • Как видно из таблицы, время выполнения алгоритма на GPU немного больше, чем на CPU.
      Однако, отмечу, что вовремя работы алгоритма использующего для вычислений GPU загрузка
      им CPU, в Диспетчере задач, не превышала 30%, в то время как алгоритм использующий для
      вычислений CPU, загружал его на 68-85%, что в свою очередь иногда приводило к замедлению
      других приложений.
      Ответить
      • Стоит отметить, что cyda имеет ограничения по количеству запускаемых потоков,
        поэтому в обоих алгоритмах я взял одинаковое количество потоков, равное 1000.
        Ответить
      • vanished
        Ответить
        • Да, особенно это помогает, когда в коде для CPU очень эффективно проводится ожидание конца работы:
          thread *T = new thread[size];
          Running_thread_counter = 0;
          for (int i = 0; i < size; i++) {
              T[i] = thread(Upload_to_CPU, Number, Stepn, Stop, INPUT, max, i);
              T[i].detach();
          }
          while (Running_thread_counter < size - 1);//дождаться завершения выполнения всех потоков


          P. S. Перевёл алгоритм автора на «Python» с «Numba», третий с конца результат, который у него считался 16 секунд, вычислил за 65.
          >>> @numba.jit(nopython=True)
          ... def calc():
          ...     for x in range(2, 1001):  # У него каждый поток проверяет x с собственным номером
          ...         for deg in range(1, 8500):
          ...             if x ** deg == N:
          ...                 yield (x, deg)
          ...
          >>> start = time.time(); res = list(calc()); end = time.time(); print(end - start)
          0.1561572551727295
          >>> res
          [(108, 4)]
          >>> start = time.time(); res = list(calc()); end = time.time(); print(end - start)
          0.06783914566040039
          >>> start = time.time(); res = list(calc()); end = time.time(); print(end - start)
          0.08180832862854004
          >>> start = time.time(); res = list(calc()); end = time.time(); print(end - start)
          0.06485199928283691

          …миллисекунд.
          Ответить
          • vanished
            Ответить
          • > миллисекунд

            Мда. Выебать преждевременного оптимизатора наивным кодом на питоне - это бесценно.
            Ответить
            • vanished
              Ответить
              • Да, чисто, к сожалению, не получится: на арифметических задачах «Питон» просто пиздец какой медленный.
                Ответить
                • vanished
                  Ответить
                  • Потому что наивная интерпретация всего и бигинты.
                    >>> dis.dis(calc_unskill)
                      2           0 LOAD_GLOBAL              0 (range)
                                  2 LOAD_CONST               1 (2)
                                  4 LOAD_CONST               2 (1001)
                                  6 CALL_FUNCTION            2
                                  8 GET_ITER
                            >>   10 FOR_ITER                42 (to 54)
                                 12 STORE_FAST               0 (x)
                    
                      3          14 LOAD_GLOBAL              0 (range)
                                 16 LOAD_CONST               3 (1)
                                 18 LOAD_CONST               4 (8500)
                                 20 CALL_FUNCTION            2
                                 22 GET_ITER
                            >>   24 FOR_ITER                26 (to 52)
                                 26 STORE_FAST               1 (deg)
                    
                      4          28 LOAD_FAST                0 (x)
                                 30 LOAD_FAST                1 (deg)
                                 32 BINARY_POWER
                                 34 LOAD_GLOBAL              1 (N)
                                 36 COMPARE_OP               2 (==)
                                 38 POP_JUMP_IF_FALSE       24
                    
                      5          40 LOAD_FAST                0 (x)
                                 42 LOAD_FAST                1 (deg)
                                 44 BUILD_TUPLE              2
                                 46 YIELD_VALUE
                                 48 POP_TOP
                                 50 JUMP_ABSOLUTE           24
                            >>   52 JUMP_ABSOLUTE           10
                            >>   54 LOAD_CONST               0 (None)
                                 56 RETURN_VALUE

                    Без «JIT» ВМ Питона просто берёт вот эти вот опкоды и тупо их исполняет до победного в одном внутреннем евале.

                    UPD: Только сейчас заметил: он же в самом горячем месте цикла делает LOAD_GLOBAL, то есть идёт в словарь и ищет в нём глобалку по имени. Какой анскилл )))
                    Ответить
                    • Да и BINARY_POWER - не самая быстрая операция. Нумба, видимо, заменила её на умножение.
                      Ответить
                  • Ма-те-ма-ти-ки любят «Питон», потому что числа в нём переменного размера (bigint). Можно записать целое число с огромным количеством знаков и не думать о типах данных.
                    Ответить
                    • Я всегда был против строгой типизации. Поэтому я за PHP.
                      А явисты, <как> долбоёбы, ставят буковку "f" после дробных чисел )))
                      Ответить
    • Ебать там в комментариях самобытность!
      Barabashkad сегодня в 19:13
      для начала, CPU код можно еще оптимизиорвать если использовать векторные AVX инструкции
      но и для GPU… можно не мерять время выделения памяти и копирования…
      и тогда картина станет более многогранной и пестрой :-)

      И ни один петух не заметил, что для CPU-bound задачи цыплёнок запускает 1000 потоков…
      Ответить
      • показать все, что скрытоvanished
        Ответить
        • На видюхе их овер 3к. Так что он маловато тредов наделал.
          Ответить
          • показать все, что скрытоvanished
            Ответить
            • А где здесь cpu bound? Для брутфорса корня данных почти не надо передавать на видюху, число для проверки можно по индексам треда получить. В обратную сторону разве что мешок флажков придётся передать. И то я думаю можно reduce прям на видюхе сделать за несколько проходов.

              З.Ы. Я код не читал если что, там много буков.
              Ответить
      • А есть подробное условие задачи? Лень реверсить его по коду.
        Ответить
        • Для чисел от 0 до 999 (по одному на поток) и степеней от 1 до N (N задаётся в конкретном тесте) найти все пары (число, степень), которые при вычислении «число^степень» дают заданное в тесте число.
          Ответить
          • > число^степень

            По модулю 2**64?
            Ответить
            • А, да, там unsigned.

              Показалось сначала, что по модулю UB. Какой багор )))
              Ответить
              • Ну тогда где здесь cpu bound, gost?

                Дождаться пока все треды на gpu закончат и пробежаться по массиву в 4 килобайта - не такая уж тяжёлая задача для cpu (на входе массив нинужен т.к. номер треда можно заюзать). Параллелится этот брутфорс вроде неплохо, память не напрягает (не то чтобы не было более красивого решения без брутфорса).
                Ответить
              • З.Ы. А, понял, ты про версию на cpu, где тыща обычных тредов поднимается. Ну да, выглядит пиздецово. С другой стороны в них IO нету, ось не будет контекст сильно часто переключать. Так что сойдёт. Вон даже gpu обогнать умудрились.
                Ответить
                • Да, про них.
                  > ось не будет контекст сильно часто переключать
                  Я недавно ради интереса одну CPU-bound задачку распараллелил на 4 потока (чтобы все ядра забить), померял, добавил ещё один и получил просадку в полтора раза. Добавил ещё то ли два, то ли три — просело во что-то вроде десяти раз. Так что не всё так однозначно (да и по заверениям автора, у него во время работы CPU-версии проц был загружен на 85%, лол).

                  Ну и как бы вся задача — это несколько миллионов умножений, это считается реально за миллисекунды, если, конечно, считать, а не ебать планировщик.
                  Ответить
    • А вообще, "сравнения производительности" на хабре всегда чисто на поржать.
      Ответить
      • показать все, что скрытоvanished
        Ответить
        • Кстати для cuda были контейнеры и аналоги крестовых алгоритмов которые на gpu крутятся.
          Ответить
          • Почему были? Thrust вроде не сдох пока.
            Ответить
          • показать все, что скрытоvanished
            Ответить
            • CUDA-конпелятор, который юзает чел из статьи, как раз таки позволяет в одном исходнике и для cpu и для gpu писать...

              Но у gpu очень специфичная архитектура и как попало под неё писать нельзя, иначе все терафлопсы вылетят в трубу. Сложный код, где много переменных, много нелокальных обращений к памяти, циклы переменной длины с внезапными бряками и т.п. видюхи очень плохо переносят. Им нужны тысячи и миллионы простых, независимых, однообразных задач.
              Ответить
              • показать все, что скрытоvanished
                Ответить
                • > спекулянты

                  Всё хуже. "Треды" исполняются группами по 16 штук, по сути это SIMD. Сам понимаешь, что control flow у них один на всех. Поэтому пока половина исполняет then, вторая пинает хуи. А потом наоборот. Ну и выйти из цикла они могут только всей группой.

                  А у памяти большое латенси и маленькие кеши, что-то в духе сотни килобайт на "тыщу ядер" (один мультипроцессор). Поэтому рандомный доступ куда попало очень дорого обходится.

                  Ну и регистры статически распределяются, поэтому чем больше переменных - тем меньше тредов ты сможешь загнать на однин мультипроцессор.
                  Ответить
    • показать все, что скрытоvanished
      Ответить
      • Вы ошиблись сайтом, тут не стековерфлоу.
        Ответить
      • Хочешь конст - ебись с двоеточием. Без конста можно и просто в теле конструктора присвоить. Жаль конечно, что они как в джавке не сделали, конпелятор вполне мог бы проверить, что ты ровно 1 раз присваиваешь и соблюдаешь правильный порядок.

        З.Ы. Можно и int m_foo = 12; если кресты свежие. Но с const'ом это не имеет особого смысла, только память зря тратить. Зачем тебе поле в котором всегда одно и то же?
        Ответить
        • показать все, что скрытоvanished
          Ответить
          • Ага, но в теле конструктора это будет уже присваивание, а не конструирование как в инициализаторе. Не то чтобы это реально мешало, но помнить об этом стоит.
            Ответить
            • показать все, что скрытоvanished
              Ответить
              • Для int'ов и прочего говна - нет. Там будет мусор пока что-нибудь не присвоишь.

                У объектов сработает дефолтный конструктор, а потом ты в них присвоишь новое значение. Реальная проблема только если дефолтный конструктор тяжёлый, с побочками или его вообще нет. Но такого на практике почти не бывает.
                Ответить
              • > НЕ ПОДДЕРЖИВАЕТ копирование

                Оператор мувающего присваивания прикрути ему. По аналогии с мув конструктором.
                Ответить
                • vanished
                  Ответить
                  • Какой vanished )))
                    У кого-то остались бэкапы всего того, что было насрано через guest8?
                    Ответить
                    • Загружаю. Ещё пока (послезавтра будет нельзя) можно скачать вчерашний дамп НГК, до ванишей.
                      Ответить
    • test
      Ответить

    Добавить комментарий