Являюсь автором tg канала про оптимизации

Тема в разделе "WASM.HEAP", создана пользователем ioann_V, 4 дек 2020.

Метки:
  1. ioann_V

    ioann_V New Member

    Публикаций:
    0
    Регистрация:
    4 дек 2020
    Сообщения:
    15
    Я не против, даже как-то за, помогать форуму развиваться, в частности. Я же и сам на таком вырос.
     
  2. НетРегистрации

    НетРегистрации Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    72
    https://habr.com/ru/post/522820/
    Код (ASM):
    1. T_  Equ  TByte ptr
    2. W_  Equ  Word  ptr
    3. ...
    4. Qdec  dQ 987654321987654321
    5. DebugMem  dd 4 Dup (0)
    6. ChrQdec  Db 18 Dup (0)
    7. ...
    8.   fNInit ; если не было
    9.   fILd  [Qdec]
    10.   fBstP  T_[DebugMem]
    11.   xOr  eDi,eDi
    12.   Mov  eCx,9
    13.   __1:  ; может можно и еще пооптимизировать
    14.   MovZx eAx,B_[DebugMem + eCx - 1]
    15.   RoR  Ax,4
    16.   SHR  Ah,4
    17.   Or  Ax,3030h
    18.   Mov  W_[ChrQdec + eDi * 2],Ax
    19.   Inc  eDi
    20.   LoopD __1
     
  3. ioann_V

    ioann_V New Member

    Публикаций:
    0
    Регистрация:
    4 дек 2020
    Сообщения:
    15
    минимализм != оптимизация, ну или, где же замеры?
    я же разные варианты тестировал, и этот тоже.
     
  4. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.546
    Адрес:
    Russia
    ioann_V,
    не совсем так, оптимизация бывает разной
    1) по размеру кода
    2) по скорости.
    так что это тоже своего рода оптимизация
     
    UbIvItS нравится это.
  5. Entropy

    Entropy Member

    Публикаций:
    0
    Регистрация:
    23 авг 2020
    Сообщения:
    174
    3) количество памяти которое потребляет алгоритм
     
  6. ioann_V

    ioann_V New Member

    Публикаций:
    0
    Регистрация:
    4 дек 2020
    Сообщения:
    15
    Мой алгоритм в статье - он конечно, по кол-ву кодобайт длинный, да. Но, работает быстро, раз, во вторых - память не потребляет вообще - никаких обращений к Кешу, в этом и фишка, точнее одна из. Ну и почему-то на Arm-ах, он работает вдвое быстрее, алгоиртма от Abseil lib(google), который считается наибыстрейшим. А вот на x86_64 - можно получить прирост в 1.5 раза ну и незасоренный кеш. Так мне интересно в целом все, я и WDK использовал в своей практике и какие-то другие, низкоуровневые вещи. Может, за тем чтобы какие то пробелы восполнить я тут. Ну и что-то сделать интересное, в этом низкоуровневом направлении: мечтал всегда, честно говоря. Еще со времен wx.net
     
  7. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Ну, вообще, по коду много вопросов, на самом деле.
    1. Почему, например, количество разрядов целого числа не устанавливаете методом половинного деления, а последовательно сравниваете с 10, 100, 1000 и т.д.?
    2. Большое количество if'ов - большая нагрузка на branch predictor.
    3. Большое количество команд в функции - большая нагрузка на кэш команд.
    4. memcpy для копирования очень маленьких кусков памяти и не запись результата прямо по переданному адресу - хммммм....
    5. Работает только на LE-архитектуре.
     
    q2e74 нравится это.
  8. ioann_V

    ioann_V New Member

    Публикаций:
    0
    Регистрация:
    4 дек 2020
    Сообщения:
    15
    1. Здесь на самом деле, можно и так, но у меня на тестах - этот вариант показал лучший результат. Я запускал разные бенчмарки, от разных людей. Тем не менее, совсем не спорно, что в зависимости от того, какаие входные данные - условные переходы можно поменять. Если скажем, известно, что нам приходит, только числа больше 6-значных.
    2. Да, это верно. Но, без бренчей тут никак - даже если делать loop, это тоже бренч предиктор, который правда, работает несколько иначе, чем при условных переходах, но дает свой вклад и убивает некоторые механизмы работы процессора. Ну точнее, тот вариант что дали выше, он всегда будет бегать в цикле 9раз, а если оджнозначное число пришло? Обычно, вычисляют длину числа(чтобы сделать потом реверс массива)
    3. А так ли оно велико, для процессоров Intel SB(2k11)+?
    4. МемЦпу тут оптимизируется до простого регистрового копирования, но так сделано - чтобы не попасть на Undefined Behaviour от C++. Это же он самый, а не чистый asm. Первая версия использовала reinterpret_cast - но чувак из google тут меня и поправил, сказал, что memcpy даст гарантии.
    5. Yes, но и переделать для BE реально(? - есть же циклические сдвиги).

    И шестое, это то, что если писать на чистом Ассемблере, учитывая специфику архитектуры, то можно улучшить решение, потому что ассемблер сам по себе, он ну, реально переносим слабо.
    --- Сообщение объединено, 9 дек 2020 ---
    P.s скорее всего сюда и залью статейку по переводу Плав.Запятой в строки - там интересные и сложные вещи, с математикой связанные.
     
  9. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.546
    Адрес:
    Russia
    как раз в этом и смысл низкоуровневой оптимизации.
    нужный алгоритм пишется под разные архитектуры и потом при компиляции выбирается нужный кейс.
    По этому рекомендую вам попробовать на асме показать класс , как раз форум тематический.
     
  10. НетРегистрации

    НетРегистрации Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    72
    DebugMem для наглядности, а для работы -
    DebugMem Equ ChrQdec+8
    Естественно можно и без LoopD, т.е. развернуть.
    Но бывает время LoopD = 0 - конвеер так умеет.
    Быстродействие удобнее сравнить на ваших процессорах, тестах и до 10^18 соответственно.
    Код (ASM):
    1. fNInit ; если не было
    2.   fILd  [Qdec]
    3.   fBstP  T_[ChrQdec + 8]
    4.   ; до 5 раз нечто подобное ниже,
    5.   ; можно и в "обратную сторону"  с Cmp / Jxx
    6.   MovZx eAx,B_[ChrQdec + 15]
    7.   RoR  Ax,4
    8.   SHR  Ah,4
    9.   SHL  eAx,16
    10.   Mov  Al,B_[ChrQdec + 16]
    11.   RoR  Ax,4
    12.   SHR  Ah,4
    13.   Or  eAx,30303030h
    14.   Mov  D_[ChrQdec + 0 * 4],eAx
     
    Последнее редактирование модератором: 10 дек 2020
  11. TrashGen

    TrashGen ТрещГен

    Публикаций:
    0
    Регистрация:
    15 мар 2011
    Сообщения:
    1.173
    Адрес:
    подполье
    Была (а сталобыть и есть уже много-много лет подряд) же конференция на жабере, пойдемте там резвитьца!
     
  12. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    А моя реализация в среднем чуть быстрее:

    Код (Text):
    1.  
    2. Statistics of performance test 'dsp.number':
    3. ┌Case─────────────┬Time[s]┬───Iter┬Samp[s]┬────Est┬─Perf[i/s]┬Cost[us/i]┬Rel[%]┐
    4. │uint32_to_string0│  5.00│6622000│  5.00│6621308│1324261.75│  0.7551│100.00│
    5. │uint32_to_string1│  5.00│6997000│  5.00│6996510│1399302.05│  0.7146│105.67│
    6. └─────────────────┴───────┴───────┴───────┴───────┴──────────┴──────────┴──────┘
    7. Performance test 'dsp.number' has succeeded, execution time: 10.01 s
    8.  
    9. --------------------------------------------------------------------------------
    10. Overall performance test statistics:
    11.   execution time [s]:  10.01
    12.   launched:  1
    13.   ignored:  0
    14.   succeeded:  1
    15.   failed:  0
    16.  
    Ссылка на реализацию:
    https://github.com/sadko4u/lsp-dsp-lib/blob/decimal-optimizations/src/test/ptest/number.cpp

    Код:
    Код (Text):
    1.  
    2. /*
    3.  * Copyright (C) 2020 Linux Studio Plugins Project <https://lsp-plug.in/>
    4.  *           (C) 2020 Vladimir Sadovnikov <sadko4u@gmail.com>
    5.  *
    6.  * This file is part of lsp-dsp-lib
    7.  * Created on: 9 дек. 2020 г.
    8.  *
    9.  * lsp-dsp-lib is free software: you can redistribute it and/or modify
    10.  * it under the terms of the GNU Lesser General Public License as published by
    11.  * the Free Software Foundation, either version 3 of the License, or
    12.  * any later version.
    13.  *
    14.  * lsp-dsp-lib is distributed in the hope that it will be useful,
    15.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    16.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    17.  * GNU Lesser General Public License for more details.
    18.  *
    19.  * You should have received a copy of the GNU Lesser General Public License
    20.  * along with lsp-dsp-lib. If not, see <https://www.gnu.org/licenses/>.
    21.  */
    22.  
    23. #include <lsp-plug.in/test-fw/ptest.h>
    24. #include <lsp-plug.in/common/alloc.h>
    25.  
    26. static const uint16_t table[] =
    27. {
    28.     0x3030, 0x3130, 0x3230, 0x3330, 0x3430, 0x3530, 0x3630, 0x3730, 0x3830, 0x3930,
    29.     0x3031, 0x3131, 0x3231, 0x3331, 0x3431, 0x3531, 0x3631, 0x3731, 0x3831, 0x3931,
    30.     0x3032, 0x3132, 0x3232, 0x3332, 0x3432, 0x3532, 0x3632, 0x3732, 0x3832, 0x3932,
    31.     0x3033, 0x3133, 0x3233, 0x3333, 0x3433, 0x3533, 0x3633, 0x3733, 0x3833, 0x3933,
    32.     0x3034, 0x3134, 0x3234, 0x3334, 0x3434, 0x3534, 0x3634, 0x3734, 0x3834, 0x3934,
    33.     0x3035, 0x3135, 0x3235, 0x3335, 0x3435, 0x3535, 0x3635, 0x3735, 0x3835, 0x3935,
    34.     0x3036, 0x3136, 0x3236, 0x3336, 0x3436, 0x3536, 0x3636, 0x3736, 0x3836, 0x3936,
    35.     0x3037, 0x3137, 0x3237, 0x3337, 0x3437, 0x3537, 0x3637, 0x3737, 0x3837, 0x3937,
    36.     0x3038, 0x3138, 0x3238, 0x3338, 0x3438, 0x3538, 0x3638, 0x3738, 0x3838, 0x3938,
    37.     0x3039, 0x3139, 0x3239, 0x3339, 0x3439, 0x3539, 0x3639, 0x3739, 0x3839, 0x3939
    38. };
    39.  
    40. char* uint32_to_string0(uint32_t n, char *out_str)
    41. {
    42.     if ( n < 10u )
    43.     {
    44.         const uint64_t in = n + 0x30ull;
    45.         memcpy( out_str, &in, 8u );
    46.         return out_str + 1u;
    47.     }
    48.  
    49.     const uint32_t b = n / 10u;
    50.     if ( n < 100u )
    51.     {
    52.         const uint64_t in = 256ull * n - 2559ull * b + 0x3030ull;
    53.         memcpy( out_str, &in, 8u );
    54.         return out_str + 2u;
    55.     }
    56.  
    57.     const uint32_t c = n / 100u;
    58.     if ( n < 1000u )
    59.     {
    60.         const uint64_t in = 65536ull * n - 2559ull * ( 256ull * b + c ) + 0x303030ull;
    61.         memcpy( out_str, &in, 8u );
    62.         return out_str + 3u;
    63.     }
    64.  
    65.     const uint32_t d = n / 1000u;
    66.     if ( n < 10000u )
    67.     {
    68.         const uint64_t in = 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) + 0x30303030ull;
    69.         memcpy( out_str, &in, 8u );
    70.         return out_str + 4u;
    71.     }
    72.  
    73.     const uint32_t e = n / 10000u;
    74.     if ( n < 100000u )
    75.     {
    76.         const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x08ull ) + e + 0x3030303030ull;
    77.         memcpy( out_str, &in, 8u );
    78.         return out_str + 5u;
    79.     }
    80.  
    81.     const uint32_t f = n / 100000u;
    82.     if ( n < 1000000u )
    83.     {
    84.         const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x10ull ) +
    85.                             ( ( 256ull      * e - 2559ull * f ) + 0x303030303030ull );
    86.         memcpy( out_str, &in, 8u );
    87.         return out_str + 6u;
    88.     }
    89.  
    90.     const uint32_t g = n / 1000000u;
    91.     if ( n < 10000000u )
    92.     {
    93.         const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x18ull ) +
    94.                             ( ( 65536ull    * e - 2559ull * ( 256ull * f + g ) + 0x30303030303030ull ) );
    95.         memcpy( out_str, &in, 8u );
    96.         return out_str + 7u;
    97.     }
    98.  
    99.     const uint32_t h = n / 10000000u;
    100.     if ( n < 100000000u )
    101.     {
    102.         const uint64_t in = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x20ull ) +
    103.                             ( ( 16777216ull * e - 2559ull * ( 256ull * ( 256ull * f + g ) + h ) ) + 0x3030303030303030ull );
    104.         memcpy( out_str, &in, 8u );
    105.         return out_str + 8u;
    106.     }
    107.  
    108.     const uint32_t x = n / 100000000u;
    109.     const uint64_t r_0 = ( ( 16777216ull * n - 2559ull * ( 256ull * ( 256ull * b + c ) + d ) - 10 * e ) << 0x20ull ) +
    110.                          ( 16777216ull * e - 2559ull * ( 256ull * ( 256ull * f + g ) + h ) - 10 * x );
    111.  
    112.     if ( 9u < x )
    113.     {
    114.         const uint64_t in_1 = ( ( x % 10u ) << 8ull ) + x / 10u + 0x3030ull;
    115.         memcpy( out_str, &in_1, 8u );
    116.         const uint64_t in_2 = ( ( r_0 + 0x3030303030303030ull ) );
    117.         memcpy( out_str + 2u, &in_2, 8u );
    118.         return out_str + 9u;
    119.     }
    120.     else
    121.     {
    122.         const uint64_t in_1 = x   + 0x30u;
    123.         memcpy( out_str, &in_1, 8u );
    124.         const uint64_t in_2 = r_0 + 0x3030303030303030ull;
    125.         memcpy( out_str + 1u, &in_2, 8u );
    126.         return out_str + 10u;
    127.     }
    128. }
    129.  
    130. char* uint32_to_string1(uint32_t n, char *out_str)
    131. {
    132.     uint8_t bytes;
    133.     uint64_t div;
    134.     uint32_t mod;
    135.  
    136.     // 4294967295
    137.     if (n <= 9999)
    138.     {
    139.         if (n <= 99)
    140.             bytes = (n <= 9) ? 1 : 2;
    141.         else
    142.             bytes = (n <= 999) ? 3 : 4;
    143.     }
    144.     else if (n <= 99999999)
    145.     {
    146.         if (n <= 999999)
    147.             bytes = (n <= 99999) ? 5 : 6;
    148.         else
    149.             bytes = (n <= 9999999) ? 7 : 8;
    150.     }
    151.     else
    152.         bytes = (n <= 999999999) ? 9 : 10;
    153.  
    154.     char *ret = &out_str[bytes+1];
    155.     if (bytes & 1)
    156.     {
    157.         out_str    += bytes - 1;
    158.         div         = n / 10;
    159.         mod         = n % 10;
    160.         out_str[0]  = 0x30 + mod;
    161.         out_str[1]  = '\0';
    162.  
    163.         n           = div;
    164.         bytes      &= ~1;
    165.     }
    166.     else
    167.     {
    168.         out_str    += bytes;
    169.         out_str[0]  = '\0';
    170.     }
    171.  
    172.     uint16_t *dst   = (uint16_t *)out_str;
    173.     while (n)
    174.     {
    175.         --dst;
    176.         div     = n / 100;
    177.         mod     = n % 100;
    178.  
    179.         *dst    = table[mod];
    180.         n       = div;
    181.     }
    182.  
    183.     return ret;
    184. }
    185.  
    186. typedef char* (* uint32_to_string_t)(uint32_t n, char *out_str);
    187.  
    188. static const uint32_t values[] =
    189. {
    190.     0, 1, 2, 3,
    191.     4, 5, 6, 7,
    192.     8, 9, 0, 1,
    193.     2, 3, 4, 5,
    194.  
    195.     11, 22, 33, 44,
    196.     55, 66, 77, 88,
    197.     99, 45, 54, 36,
    198.     63, 27, 72, 81,
    199.  
    200.     100, 212, 323, 434,
    201.     545, 656, 767, 878,
    202.     989, 191, 272, 363,
    203.     454, 999, 153, 709,
    204.  
    205.     1234, 2345, 3456, 5678,
    206.     7890, 8901, 9012, 9876,
    207.     8765, 7654, 6543, 5432,
    208.     4321, 3210, 2109, 1098,
    209.  
    210.     12345, 23456, 34567, 45678,
    211.     56789, 67890, 78901, 89012,
    212.     90123, 76543, 65432, 54321,
    213.     43210, 32109, 21098, 10987,
    214.  
    215.     568947, 689471, 894713, 947134,
    216.     471341, 713412, 134120, 341205,
    217.     568947, 689671, 814713, 957134,
    218.     471641, 712412, 634127, 241205,
    219.  
    220.     7654321, 6543210, 5432109, 4321098,
    221.     3210987, 2109876, 1098765, 9876543,
    222.     8765432, 7591274, 5912747, 9127475,
    223.     1928374, 9283741, 2837419, 8374192,
    224.  
    225.     19283746, 92837461, 28374619, 83746192,
    226.     37461928, 74619283, 46192837, 61928374,
    227.     13822473, 38224731, 82247313, 22473138,
    228.     24731382, 47313822, 73138224, 31382247,
    229.  
    230.     104837519, 483751910, 837519104, 375191048,
    231.     751910483, 519104837, 191048375, 910483751,
    232.     884772641, 847726418, 477264188, 772641884,
    233.     726418847, 264188477, 641884772, 418847726,
    234.  
    235.     1498673324, 1437674341, 1123456789, 1987654321,
    236.     2581275057, 2302857683, 2476301756, 2762307694,
    237.     3278574027, 3495817583, 3459371495, 3048658387,
    238.     4168205863, 4258672947, 4148592495, 4027845728
    239. };
    240.  
    241. PTEST_BEGIN("dsp", number, 5, 1000)
    242.  
    243.     void call(const char *label, char *out, uint32_to_string_t func)
    244.     {
    245.         printf("Testing %s ...\n", label);
    246.  
    247.         PTEST_LOOP(label,
    248.             for (size_t i=0; i<sizeof(values)/sizeof(uint32_t); ++i)
    249.                 func(values[i], out);
    250.         );
    251.     }
    252.  
    253.     PTEST_MAIN
    254.     {
    255.         char buf[0x20];
    256.  
    257.         #define CALL(func) \
    258.             call(#func, buf, func)
    259.  
    260.         CALL(uint32_to_string0);
    261.         CALL(uint32_to_string1);
    262.         PTEST_SEPARATOR;
    263.     }
    264.  
    265. PTEST_END
    266.  
    267.  
     
    TermoSINteZ и ioann_V нравится это.
  13. ioann_V

    ioann_V New Member

    Публикаций:
    0
    Регистрация:
    4 дек 2020
    Сообщения:
    15
    У меня результаты, тоже близки, но все же, берет немного мое решение:


    Код (Text):
    1. BM_FastIntToBuffer_1<int32_t>/0               0.463 ns        0.463 ns   1000000000
    2. BM_FastIntToBuffer_1<int32_t>/0               0.463 ns        0.463 ns   1000000000
    3. BM_FastIntToBuffer_1<int32_t>/1                3.64 ns         3.64 ns    206269735
    4. BM_FastIntToBuffer_1<int32_t>/8                4.01 ns         4.01 ns    183023062
    5. BM_FastIntToBuffer_1<int32_t>/64               4.24 ns         4.24 ns    165640593
    6. BM_FastIntToBuffer_1<int32_t>/512              4.27 ns         4.27 ns    163858753
    7. BM_FastIntToBuffer_1<int32_t>/4096             4.28 ns         4.28 ns    163977891
    8. BM_FastIntToBuffer_1<int32_t>/32768            4.25 ns         4.25 ns    164379338
    9. BM_FastIntToBuffer_1<int64_t>/0               0.463 ns        0.463 ns   1000000000
    10. BM_FastIntToBuffer_1<int64_t>/0               0.463 ns        0.463 ns   1000000000
    11. BM_FastIntToBuffer_1<int64_t>/1                3.60 ns         3.60 ns    206391114
    12. BM_FastIntToBuffer_1<int64_t>/8                3.98 ns         3.98 ns    187250811
    13. BM_FastIntToBuffer_1<int64_t>/64               4.24 ns         4.24 ns    165850672
    14. BM_FastIntToBuffer_1<int64_t>/512              4.27 ns         4.27 ns    163552205
    15. BM_FastIntToBuffer_1<int64_t>/4096             4.27 ns         4.27 ns    163668873
    16. BM_FastIntToBuffer_1<int64_t>/32768            4.29 ns         4.29 ns    162510009
    17. BM_FastIntToBuffer_1<int64_t>/262144           4.29 ns         4.29 ns    163283259
    18. BM_FastIntToBuffer_1<int64_t>/2097152          4.29 ns         4.29 ns    162782934
    19. BM_FastIntToBuffer_1<int64_t>/16777216         4.32 ns         4.31 ns    162079999
    20. BM_FastIntToBuffer_1<int64_t>/134217728        4.18 ns         4.18 ns    167288345
    21. BM_FastIntToBuffer_1<int64_t>/1073741824       3.46 ns         3.46 ns    202346753
    22. BM_FastIntToBuffer_2<int32_t>/0                2.08 ns         2.08 ns    335005897
    23. BM_FastIntToBuffer_2<int32_t>/0                2.09 ns         2.08 ns    334739517
    24. BM_FastIntToBuffer_2<int32_t>/1                4.03 ns         4.03 ns    178465825
    25. BM_FastIntToBuffer_2<int32_t>/8                4.24 ns         4.24 ns    173153228
    26. BM_FastIntToBuffer_2<int32_t>/64               4.34 ns         4.34 ns    162019339
    27. BM_FastIntToBuffer_2<int32_t>/512              4.38 ns         4.38 ns    159033800
    28. BM_FastIntToBuffer_2<int32_t>/4096             4.38 ns         4.38 ns    159785547
    29. BM_FastIntToBuffer_2<int32_t>/32768            4.45 ns         4.45 ns    159699516
    30. BM_FastIntToBuffer_2<int64_t>/0                2.08 ns         2.08 ns    334980342
    31. BM_FastIntToBuffer_2<int64_t>/0                2.08 ns         2.08 ns    335701603
    32. BM_FastIntToBuffer_2<int64_t>/1                4.02 ns         4.02 ns    178519955
    33. BM_FastIntToBuffer_2<int64_t>/8                4.15 ns         4.15 ns    173342059
    34. BM_FastIntToBuffer_2<int64_t>/64               4.38 ns         4.38 ns    161389677
    35. BM_FastIntToBuffer_2<int64_t>/512              4.40 ns         4.39 ns    155380901
    36. BM_FastIntToBuffer_2<int64_t>/4096             4.99 ns         4.99 ns    159681985
    37. BM_FastIntToBuffer_2<int64_t>/32768            4.35 ns         4.35 ns    161239193
    38. BM_FastIntToBuffer_2<int64_t>/262144           4.53 ns         4.53 ns    159868333
    39. BM_FastIntToBuffer_2<int64_t>/2097152          4.35 ns         4.35 ns    161291794
    40. BM_FastIntToBuffer_2<int64_t>/16777216         4.42 ns         4.42 ns    159047903
    41. BM_FastIntToBuffer_2<int64_t>/134217728        4.57 ns         4.56 ns    155172682
    42. BM_FastIntToBuffer_2<int64_t>/1073741824       4.09 ns         4.09 ns    171145714
    43.  
    --- Сообщение объединено, 9 дек 2020 ---
    Я прогонял гуглбенчмарком, компилировал на *nix, gcc-10, O3. Процессор - Ryzen 3900x. Но то, что оно может идти в ровень +- - момент не спорный, фишка в том, что у меня кеш не используется. И, не более того.
    --- Сообщение объединено, 9 дек 2020 ---
    Сама идея этого метода родилась когда Антон Полухин - контрибутор gcc искал новый метод, который, как раз не использовал бы кеш. А так, у тебя идея таже считай лежит - тоже ифы и ветвления, но то как ты к этому подошел - интересно тоже(организация ветвлений - я так не делал), интересно, мой метод таким образом переписать можно(бин. поиск)? Ну и конечно, респект тебе за то, что не только слова предоставляешь, но и результаты.

    З.Ы: То есть, я по другому ветвления бинарно делал, не так как ты.
     
    Последнее редактирование: 9 дек 2020
  14. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Я пробовал с -O2, Ryzen 2700, gcc 7.5.
    Тут ещё где-то в сети проскакивал хитрый вариант, где предлагали число на полином хитрый умножать, и правильные значения сразу по байтикам расставлялись.
    Но найти не могу. Это какая-то библиотека по парсингу json + simd была...
     
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
  16. ioann_V

    ioann_V New Member

    Публикаций:
    0
    Регистрация:
    4 дек 2020
    Сообщения:
    15
    Да, есть такое - хотя для 64бит можно тоже придумать, а вот если побольше, то будет сложнее - да. Но большая разрадность, это уже про длинную арифметику, FFT и вот это все.
    Идея основная то в чем - это посмотреть на старую проблему, под другим углом, которого нигде нету. Вот это мне интересно - ну и про это я заодно и пишу. Я уверен, что многие задачи можно решить неожиданно по-другому, так, чтобы ну как минимум заинтересовать, или как максимум - удивить!
    --- Сообщение объединено, 10 дек 2020 ---
    У меня есть на хабре, начало полного разбора скажем JeMalloc, или про интересную оплошность старого трюка с заменой деления на умножения в компиляторах - то есть такие вещи, которые не описаны. Хотя про Джемаллок только https://twitter.com/kyprizel оценил. И собственно недостаток заинтересованной аудитории в таких редких вещах - демотивирует писать дальше. А мне только это и интересно, нежели писать про то, что у процессора есть кеши, буффера обмена и все другое, что как бы должен знать каждый уважающий себя программист.
    --- Сообщение объединено, 10 дек 2020 ---
    Задача Инди меня тоже интересует - но мне так и не дали описания.
     
  17. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    Это моя наработка 2013 (http://masm32.com/board/index.php?topic=1852.msg19874#msg19874)
    Код (ASM):
    1. ; masm windows console #
    2. include \masm32\include\masm32rt.inc
    3. .686
    4. .mmx
    5. .xmm
    6.  
    7.     Eprst proto lpReal10:ptr REAL10,lpDest:DWORD
    8.  
    9. .data
    10.     _Real10_R REAL10 3.141592653589793238462E61; no crash
    11. .code
    12. main proc
    13. LOCAL result[32]:BYTE
    14.  
    15. ;    fldpi
    16. ;    fstp _Real10_R
    17.     invoke Eprst,addr _Real10_R,ADDR result
    18.     print ADDR result,13,10  
    19.     inkey " *** STOP - Eprst --- E N D ---*** "
    20.     exit  
    21. main endp
    22.  
    23.     $max equ 60; <-- This number may be increased
    24.     magic1 equ 4D10h;lg(2)*65536=19728,3...
    25.     magic2  equ 35269h;log2(10)*65536=3,32192809488736234780*65536=217705,8796265381788254208..
    26. .const
    27.     cntr = -$max
    28.     REPEAT 2*$max+1
    29.         IF cntr NE 0
    30.             REAL10 @CatStr(<1.0e>,%-cntr)
    31.         ELSE
    32.             tabs REAL10 1.0
    33.         ENDIF
    34.         WORD 0
    35.         cntr = cntr + 1
    36.     ENDM
    37.  
    38.     table0   label word
    39. n=0
    40. rept 100
    41. dw (n mod 10 shl 8)+(n/10)+"00"
    42. n=n+1
    43. endm      
    44.     table1  dd shift0,shift1,shift2,shift3,shift4
    45. .code
    46. Eprst proc uses edi esi ebx lpReal10:ptr REAL10,lpDest:DWORD
    47. local iExp:dword
    48. local x[3]:dword
    49. local temp1:dword
    50. local temp2:dword
    51.     fninit
    52.         mov ecx,lpReal10
    53.     fld tbyte ptr [ecx]
    54.     mov edi,lpDest
    55.     mov ebx,[ecx]
    56.     mov eax,[ecx+4]
    57.     mov [x],ebx
    58.     movzx edx,word ptr [ecx+8]
    59.     mov [x+4],eax
    60.     mov [x+8],edx
    61.     cmp edx,8000h
    62.     mov byte ptr [edi],'-'
    63.     sbb esi,esi
    64.     and esi,0Dh
    65.     sub [edi],esi
    66.     and edx,7FFFh
    67.     jnz a2
    68. Zero_Or_Denormal: cmp edx,eax
    69.     jnz Denormal
    70.         cmp ebx,eax
    71.     jnz Denormal
    72.     mov dword ptr [edi+1],'oreZ'
    73.     mov dword ptr [edi+5],0
    74.         ret
    75. a2: cmp edx,7FFFh
    76.     jz Infinity_Or_SNAN_Or_QNAN_Or_Uncertainty
    77. Denormal:mov esi,10
    78.     sub edx,16383
    79.     mov word ptr [edi+21],'+E'
    80.     imul edx,magic1
    81.     and edx,0FFFF0000h
    82.     sar edx,14
    83.     mov iExp,edx
    84.     jz @f
    85.     cmp edx,4*$max
    86.     jg a1
    87.     cmp edx,-4*$max
    88.     jge load
    89. ;------------------------------------------------
    90.     dec edx
    91. a1:neg edx
    92.     sar edx,2
    93.     mov temp1,edx
    94.     imul edx,magic2
    95.     sar edx,16
    96.     mov temp2,edx
    97.     fild temp2         ; get the characteristic
    98.     fild temp1         ; log2(10)*expscale
    99.     fldl2t    ; log2(10)
    100.         fmul               ; log2(10)*expscale
    101.         fsub st,st(1)      ; get only the mantissa but keep the characteristic
    102.         f2xm1              ; 2^(mantissa)-1
    103.         fld1
    104.         fadd               ; add 1 and pop
    105.         fscale
    106.         fstp    st(1)      ; remove the characteristic
    107.         jmp multiply
    108. load: fld tabs[edx+edx*2]
    109. multiply:fmul              ; X * 10^expscaleS
    110.     fld st
    111.     fstp tbyte ptr x
    112.     xor edx,edx
    113. @@: mov ecx,x+8
    114.     mov ebx,x
    115.         mov eax,x+4
    116.     and ecx,7FFFh
    117.     sub ecx,16382
    118. cmp ecx,4
    119. ja shift0
    120.     jmp table1[ecx*4]
    121. shift4::test eax,60000000h
    122.     jz a6
    123.     fld tabs[12]
    124.     fmul
    125.     add iExp,4
    126.     fstp tbyte ptr x
    127.     mov eax,x+4
    128.         mov ebx,x
    129.     shld edx,eax,1
    130.     shld eax,ebx,1
    131.     shl ebx,1
    132.     add ebx,4
    133.     jmp shift0
    134. a6: shld edx,eax,4 ;ecx=1 ebx+4
    135.     shld eax,ebx,4 ;ecx=2 ebx+8
    136.     shl ebx,4      ;ecx=3 ebx+9
    137.     add ebx,12     ;ecx=4 ebx+12
    138.     jmp shift0
    139. shift3::shld edx,eax,3
    140.     shld eax,ebx,3
    141.     shl ebx,3
    142.     add ebx,9;10
    143.     jmp shift0
    144. shift2::shld edx,eax,2
    145.     shld eax,ebx,2
    146.     shl ebx,2
    147.     add ebx,8
    148.     jmp shift0
    149. shift1::shld edx,eax,1
    150.     shld eax,ebx,1
    151.     shl ebx,1
    152.     add ebx,4
    153. shift0::adc eax,0
    154.     adc edx,0
    155.     mov [edi+1],dl
    156.     mov byte ptr [edi+2],','
    157.     or byte ptr [edi+1],'0'
    158.    
    159.     k=3
    160.     REPEAT 17
    161.         mul esi
    162.         mov [edi+k],dl
    163.         mov ecx,eax
    164.         mov eax,ebx
    165.         mul esi
    166.         add ecx,edx
    167.         adc byte ptr [edi+k],'0'
    168.         mov ebx,eax
    169.         mov eax,ecx
    170.     k=k+1
    171.     ENDM
    172.  
    173.     mul esi
    174.     mov [edi+k],dl
    175.     mov ecx,eax
    176.     mov eax,ebx
    177.     mul esi
    178.     add ecx,edx
    179.     adc byte ptr [edi+k],'0'
    180. ;--------------------------------------
    181.     mov eax,iExp
    182.     mov edx,eax
    183.     sar eax,2
    184.     sar edx,31
    185.     mov ecx,esi
    186.     xor eax,edx
    187.     sub eax,edx
    188.     and edx,2
    189.     add byte ptr [edi+22],dl
    190.     mov esi,eax
    191.     mov edx,42949673;2^32/100
    192.     mul edx
    193.     mov eax,dword ptr table0[edx*2] ;edx = quotient of the division by 100
    194.     mov dword ptr [edi+23],eax
    195.     lea eax,[edx*4]
    196.     shl edx,2
    197.     lea edx,[edx+edx*2]
    198.     lea edx,[eax+edx*8] ;edx = quotient*100
    199.     sub esi,edx ;esi = remainder of the division by 100
    200.     mov eax,dword ptr table0[esi*2]
    201.     mov dword ptr [edi+25],eax
    202.     mov dword ptr [edi+27],0
    203.     ret
    204. Infinity_Or_SNAN_Or_QNAN_Or_Uncertainty:
    205.     cmp eax,80000000h
    206.     jnz SNAN_Or_QNAN_Or_Uncertainty
    207.     and ebx,ebx
    208.     jnz SNAN_Or_QNAN_Or_Uncertainty
    209.         mov dword ptr [edi+1],'ifnI'
    210.         mov dword ptr [edi+5],'ytin'
    211.         mov dword ptr [edi+9],0
    212.     ret
    213. SNAN_Or_QNAN_Or_Uncertainty:
    214.     test eax,eax
    215.     jns error
    216.     test eax,40000000h
    217.     jnz QNAN
    218.         mov dword ptr [edi+1],'ngiS'
    219.         mov dword ptr [edi+5],'N la'
    220.         mov dword ptr [edi+9],'a no'
    221.         mov dword ptr [edi+13],'muN '
    222.         mov dword ptr [edi+17],'reb'
    223.     ret
    224. QNAN: test eax,3FFFFFFFh
    225.     jnz @f
    226.     test ebx,ebx
    227.     jnz @f
    228.         mov dword ptr [edi+1],'ecnU'
    229.         mov dword ptr [edi+5],'iatr'
    230.         mov dword ptr [edi+9],'ytn'
    231.     ret
    232. @@: mov dword ptr [edi+1],'eiuQ'
    233.         mov dword ptr [edi+5],'oN t'
    234.         mov dword ptr [edi+9],' a n'
    235.         mov dword ptr [edi+13],'bmuN'
    236.         mov dword ptr [edi+17],'re'
    237.     ret
    238. error: mov dword ptr [edi+1],'orrE'
    239.         mov dword ptr [edi+5],'r'
    240.     ret
    241. Eprst endp
    242. end main
     
  18. НетРегистрации

    НетРегистрации Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    72
    All, а чем плоха стандартная связка fXtract,fBstP? Сам не разбирался.
     
  19. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    НетРегистрации,
    если что-то можно сделать не так, то так оно и будет ;)
    «if anything that can go wrong then will go wrong» Приписывается капитану Эдварду А. Мерфи, инженеру Лаборатории реактивного движения, служившему на авиабазе Эдвардс в 1949
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    про «под новым углом» всё же не соглашусь, ибо идея развёртки циклов и аппроксимации по табличкам известны да применялись ещё задолго до компов (вспомним те же тригонометрические таблицы). и у меня ещё вопросик накатился == а ты свой алго протестил по всему диапазону, ошибок трансляции нет?
    в задачах оптимазы больше юзверей, чем разрабов.. разрабов тамо единицы из единиц :)

    ЗЫ.. да, и в сущности не понимаю в чём сыр-бор. тот же хухль вполне может перекидывать задачу конвертации чисел в строки на комп юзверя, разгружая свои моща.