1. JavaScript / Говнокод #27392

    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
    function test3()
{
		const a = 10.5
	        switch (a) 
		{                                            
		    case 10.5:
        	        print("cool. 10.5");                          
			break;                                          
	        }
}

function test3()
{		
	        switch ("kokoko") 
		{                                            
		    case "kokoko":
        	        print("pituh");                          
			break;                                          
	        }
}

    Продолжаем говнокомпилить...

    А ваш С такое прокомпилирует? мой - запросто :)

    Запостил: ASD_77, 05 Мая 2021

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

    • ava ASD_77 05.05.2021 11:12 # 0

      ну это ... асм дамп давать?
      Ответить

    • ava guest6 05.05.2021 11:20 # 0

      Твой язык с UB-ами или нет?
      Ответить

      • ava ASD_77 05.05.2021 11:44 # 0

        что такое UB? upper bound? unbound?
        Ответить

        • ava guest6 05.05.2021 11:58 # 0

          Undefined behaviour
          Ответить

          • ava ASD_77 05.05.2021 12:11 # 0

            у него весь код пока один большой UB :)
            Ответить

            • ava JloJle4Ka 05.05.2021 12:12 # 0

              У джаыаскрипта? Согласен!
              Ответить

              • ava ASD_77 05.05.2021 14:10 # 0

                у вас конфликт типов который можно решить с помошью жабаскрипта.. иначе надо писать "согласна".
                Ответить

          • ava ASD_77 05.05.2021 12:14 # +1

            ну он то пишется на основе С стандартов поэтому все есть. нужно самому думать что делаешь ... и не допускать такие вещи как 1 << 32
            Ответить

    • ava PolinaAksenova 05.05.2021 11:40 # +2

      А вот C++ — прокомпилирует!
      #include <iostream>
#include <string_view>

// FNV-1a
constexpr uint64_t ct_hash(std::string_view str) noexcept
{
    uint64_t val = 14695981039346656037ull;
    for (const auto & c : str) {
        val ^= static_cast<uint64_t>(c);
        val *= 1099511628211ull;
    }
    return val;
}

int main()
{
    std::string hello = "world";
    
    switch(ct_hash(hello)) {
        case ct_hash("hello"): std::cout << "Case Hello!" << std::endl; break;
        case ct_hash("world"): std::cout << "Case World!" << std::endl; break;
    }
}


      Причём оптимальным образом — сделает бинярный поиск по хэшам!
      Ответить

      • ava ASD_77 05.05.2021 11:41 # 0

        это хак коженного мешка а ни С ни С++ так как мой компилятор - не умеют :)
        Ответить

      • ava ASD_77 05.05.2021 11:43 # 0

        и кожанному мешку не обязательно писать свои хаки на hash. можно просто юзать std::hash по std::string :)
        Ответить

        • ava PolinaAksenova 05.05.2021 11:46 # 0

          Няльзя. std::hash<> ня является constexpr, поэтому в компайлтайме вычислять метки по строкам им ня получится.
          Ответить

        • ava Soul_re@ver 05.05.2021 11:49 # 0

          А у нас std::string constexpr на основных компиляторах разве?
          Ответить

          • ava PolinaAksenova 05.05.2021 11:52 # +1

            std::string_view — constexpr. А вот std::hash<std::string_view>::operator() — ня constexpr｡ﾟ･ (>﹏<) ･ﾟ｡.
            Ответить

      • ava ASD_77 05.05.2021 13:45 # 0

        докажите что данный код будет работать для всех строк и пересечение хеша не произойдет
        Ответить

        • ava PolinaAksenova 05.05.2021 13:47 # +2

          Компилятор докажет. А для исключения коллизий с входной строкой нядо в кейсы добавить сравнение, да. Плата за производительность!
          Ответить

          • ava j123123 05.05.2021 14:20 # 0

            А компилятор умеет генерировать оптимальные хеши без коллизий, если заранее известы все возможные вариации? Типа чтоб как https://www.gnu.org/software/gperf/

            https://neerc.ifmo.ru/wiki/index.php?title=Идеальное_хеширование
            Ответить

            • ava j123123 05.05.2021 14:30 # 0

              Такого даже в boost нет. Видимо крестопарашная метушня слишком убога для таких задач.
              Ответить

            • ava PolinaAksenova 05.05.2021 14:50 # 0

              Там же алгоритм приведён. Перепиши его ня constexpr'ы и всё.
              Ответить

              • ava j123123 05.05.2021 15:22 # 0

                Там, я так подозреваю, нужны не только констэкспры, но и какая-то шаблоносрань. Констэкспрами ты код не сгенерируешь.
                Ответить

              • ava j123123 05.05.2021 15:27 # 0

                Вот реальный пример генерации
                https://git.savannah.gnu.org/gitweb/?p=gperf.git;a=blob;f=tests/test-4.exp;h=af0a2378e088228542636bce3274684a3ee69f94;hb=HEAD

                Одними констэспрами это не решить.
                Ответить

                • ava PolinaAksenova 05.05.2021 16:41 # 0

                  Разумеется, решить: https://wandbox.org/permlink/A2SBKuw91OCYKXl1 . Это, конячно, нямножко читерство (разбираться в математических дебрях лень), но задачу полностью выполняет.
                  Ответить

                  • ava j123123 05.05.2021 17:00 # 0

                    https://godbolt.org/z/K4PrTsaz9 - да не, фигня какая-то.
                    Аллокаторы какие-то
                    call    func(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)

                    Операторы delete какие-то
                    call    operator delete(void*, unsigned long)

                    В сгенерированном коде из
                    https://git.savannah.gnu.org/gitweb/?p=gperf.git;a=blob;f=tests/test-4.exp;h=af0a2378e088228542636bce3274684a3ee69f94;hb=HEAD
                     ничего этого нет. Ни единого выделения на хипе. Где ваше хваленое "zero-cost abstraction"?
                    Ответить

                    • ava PolinaAksenova 05.05.2021 17:05 # 0

                      Эта функция специальня сделана для демонстрации того, что Switcher способен хэшировать рантайм-строки. Измени сигнятуру на void func(std::string_view runtime_str) и радуйся.
                      Ответить

                      • ava j123123 05.05.2021 17:06 # 0

                        А если я хочу в шаблон пропихнуть n-ное количество допустимых строк и того, что в ответ возвращать на такую-то строку, и чтоб там под них нагенерировалось столько-то switch-case - так можно?
                        Ответить

                        • ava PolinaAksenova 05.05.2021 17:11 # 0

                          Нячего ня поняла. Можня сделать
                          str = "good";

Switcher<
    Case<"Hello", "World">,
    Case<"good", "bye">
>{}(str) == "bye"

                          , но тогда придётся бинярный поиск по хэшам вручную делать (в случае с обычным switch () {case} компилятор его сам делает).
                          Ответить

                          • ava j123123 05.05.2021 17:20 # 0

                            > Нячего ня поняла.
                            #define H_abc 0
#define H_cde 1
#define H_efg 2

char *somestring = "abc";
int result = perfect_hash<<"abc", H_abc>, <"cde", H_cde>, <"efg", H_efg>>(somestring);
// result == H_abc == 0

                            И чтоб из этого допустим switch-case код нагенерился, и количество пар ключ-значение произвольно.
                            Ответить

                            • ava PolinaAksenova 05.05.2021 18:09 # 0

                              Ня: https://wandbox.org/permlink/agzUP2JIbCSSzwOR . Тут как раз реализован имення квадратный двухступенчатый perfect hashing. Проверку ня коллизии и отсутствующие ключи оставляю в качестве домашнего задания (в lookup() сделать сравнение ключей). А, ну и у Case сделать шаблонный Value.
                              Ответить

                              • ava j123123 05.05.2021 18:44 # 0

                                Да нет же!
                                void func(std::string_view str)
{
    auto switcher = Switcher<
        Case<"something", "world">,
        Case<"hmmm", "hello">,
        Case<"not", "used">
    >{};

    std::puts(switcher(str).data());  // inb4: UB
}

                                Тут не генерируется никакого switch.
                                Давай так. Забудь вообще про perfect hash.
                                В коде https://wandbox.org/permlink/A2SBKuw91OCYKXl1 есть конструкция
                                .
    switch (switcher.hash(runtime_str)) {
    case switcher.hashkey<"hello">(): std::puts("Hello!"); break;
    case switcher.hashkey<"world">(): std::puts("World!"); break;
    case switcher.hashkey<"bye">(): std::puts("Bye!"); break;
    default: std::puts("No such string."); break;
    }

                                Вот я хочу просто сделать штуку, которая принимает через шаблонные параметры пары ключ-значение, и чтоб из этого в компилтайме генерировался код соотв. функции с такими-то свитчами. Я не хочу отдельно что-то описывать!

                                Где там конкретно конструкция switch - case в твоем примере?
                                Ответить

                                • ava PolinaAksenova 05.05.2021 19:13 # 0

                                  Что-то я ня поняла, куда мы уехали. Изнячальня вопрос стоял так:
                                  > А компилятор умеет генерировать оптимальные хеши без коллизий, если заранее известы все возможные вариации?
                                  Ответ — да, умеет. Теперь это нядо посыпать сахаром?
                                  Ответить

                                  • ava j123123 05.05.2021 19:17 # 0

                                    > Ответ — да, умеет. Теперь это нядо посыпать сахаром?

                                    Ну так... если не посыпать сахаром, с этим отлично справится кодогенерация, и никакие супер-пупер фичи крестов не требуются.

                                    На констэкспрах, раз уж на то пошло, можно набросать собственный компилтайм-мини-компилятор который понабросает опкодов процессора куда-то, и потом это "куда-то" можно сделать в RX сегменте, кастануть в функцию и вызывать. Надо ли говорить, что такой подход не совсем адекватный?
                                    Ответить

                                    • ava PolinaAksenova 05.05.2021 19:21 # 0

                                      Кодогенерация со всем отлично справится. Для таких штук оня, разумеется, гораздо более адекватный подход.
                                      Вопрос в другом: ты убедился, что constexpr-ушня может сгенерировать perfect hash?
                                      Ответить

                                      • ava j123123 05.05.2021 19:26 # 0

                                        То что хеш ей можно генерировать - я и не сомневался. А код она не генерирует.

                                        В крестах для генерации кода нужно шаблоноговно использовать, а это уже другая хуйня, которую констэкспрами не выразить.
                                        Ответить

                                        • ava PolinaAksenova 05.05.2021 19:44 # 0

                                          Ну ладня, держи:
                                          template<typename... Cases>
struct Switcher {
    constexpr Switcher(Cases...) {}
    constexpr static std::tuple<Cases...> cases{ Cases{}... };

    template<size_t I>
    constexpr static void execImpl(std::string_view key)
    {
        constexpr auto & case_ = std::get<I>(cases);
        if (case_.key == key) {
            case_.func();
            return;
        }
        
        if constexpr (I < sizeof...(Cases) - 1) {
            execImpl<I + 1>(key);
        } else {
            assert("No such key");
        }
    }

    constexpr static void exec(std::string_view key)
    {
        execImpl<0>(key);
    }

    constexpr void operator()(std::string_view key) const
    {
        exec(key);
    }
};

void func(std::string_view key)
{
    Switcher(
        Case<"hello", [] { std::puts("Hello World"); }>(),
        Case<"bye", [] { std::puts("Bye World"); }>(),
        Case<"not used", [] { std::puts("123"); }>()
    )(key);
}

int main()
{
    func("bye");
}

                                          https://gcc.godbolt.org/z/droEe4Yrs

                                          Задачу прикручивания к этой фигне perfect hash'а и мутабельных лямбд оставляю ня тебя (*^‿^*)!
                                          Ответить

                                          • ava PolinaAksenova 05.05.2021 19:52 # 0

                                            Кстати, забавня, что этот Switcher с линейным поиском gcc оптимизировал в великолепное:
                                            func(std::basic_string_view<char, std::char_traits<char> >):
        cmp     rdi, 5
        je      .L2
        cmp     rdi, 3
        je      .L19
        cmp     rdi, 8
        jne     .L20
        movabs  rax, 7234315323333439342
        cmp     QWORD PTR [rsi], rax
        jne     .L1
        mov     edi, OFFSET FLAT:.LC0
        jmp     puts
.L19:
        cmp     WORD PTR [rsi], 31074
        je      .L21
.L1:
        ret
.L2:
        cmp     DWORD PTR [rsi], 1819043176
        jne     .L1
        cmp     BYTE PTR [rsi+4], 111
        jne     .L1
        mov     edi, OFFSET FLAT:.LC2
        jmp     puts
.L21:
        cmp     BYTE PTR [rsi+2], 101
        jne     .L1
        mov     edi, OFFSET FLAT:.LC1
        jmp     puts
.L20:
        ret

                                            Что явня быстрее любых perfect hash'ей и бинярных поисков.
                                            Ответить

                                            • ava j123123 05.05.2021 20:14 # 0

                                              А это хоть чем-то кроме GCC вообще собирается?

                                              И там проблемы с оптимизацией заметны, компилятор почему-то делает jne .L20 на метку для инструкции ret в самом конце, хотя инструкция ret и так есть на метке .L1 которая идет после инструкции jmp puts который управление не вернет, так что кусок кода
                                              .L20:
        ret

                                              нафиг не нужен. Переход на метку .L20 можно заменить на переход на метку .L1
                                              Ответить

                                              • ava PolinaAksenova 05.05.2021 20:25 # 0

                                                > А это хоть чем-то кроме GCC вообще собирается?
                                                GCC и MSVC. Шланг ня может.

                                                > jne .L20
                                                Это всё равно холодный путь, так что никакого влияния ня перформанс ня окажет.
                                                Ответить

                                            • ava j123123 05.05.2021 20:17 # 0

                                              И да, руками можно это получше записать. Далеко не идеал.

                                              Кроме того, начиная с какого-то там количества вариантов, подход с таблицей поиска оказывается лучше хрени с условями. И фиг его знает, что там компилятор понакомпилириует
                                              Ответить

                                              • ava PolinaAksenova 05.05.2021 20:28 # 0

                                                > Далеко не идеал.
                                                То ли дело сишка! 
                                                void func(const char *key)
{
    if (strcmp(key, "hello") == 0) {
        puts("Hello World");
    } else if (strcmp(key, "bye") == 0) {
        puts("Bye World");
    } else if (strcmp(key, "not used") == 0) {
        puts("123");
    }
}

                                                func:
        push    rbp
        mov     esi, OFFSET FLAT:.LC0
        mov     rbp, rdi
        call    strcmp
        test    eax, eax
        je      .L7
        mov     esi, OFFSET FLAT:.LC2
        mov     rdi, rbp
        call    strcmp
        test    eax, eax
        je      .L8
        mov     esi, OFFSET FLAT:.LC4
        mov     rdi, rbp
        call    strcmp
        test    eax, eax
        je      .L9
        pop     rbp
        ret
.L8:
        mov     edi, OFFSET FLAT:.LC3
        pop     rbp
        jmp     puts
.L7:
        mov     edi, OFFSET FLAT:.LC1
        pop     rbp
        jmp     puts
.L9:
        mov     edi, OFFSET FLAT:.LC5
        pop     rbp
        jmp     puts

                                                https://gcc.godbolt.org/z/qq8vxvbze
                                                Позорище!
                                                Ответить

                                                • ava j123123 05.05.2021 20:31 # 0

                                                  > То ли дело сишка!

                                                  На сишке я вручную это запрограммирую(возможно даже в асмовставке), если оно окажется боттлнеком.
                                                  Ответить

                                                  • ava PolinaAksenova 05.05.2021 20:34 # 0

                                                    > На сишке я вручную это запрограммирую
                                                    Имення так. Вообще, сишники — это те же джависты, только вместо get set hashcode equals пишут вручную вообще всё: от управления ресурсами до исключений через setjmp.
                                                    Ответить

                                                    • ava j123123 05.05.2021 20:35 # 0

                                                      > пишут вручную

                                                      И получается, чсх, быстрее и эффективнее, чем какая-то заумная крестометушня, которая работает не во всех компиляторах и требует последний стандарт.
                                                      Ответить

                                                      • ava PolinaAksenova 05.05.2021 20:38 # 0

                                                        > быстрее и эффективнее
                                                        [citation needed]

                                                        Пока что мы лишь увидели, как линейный поиск по заранее заданным строкам в крестах как тузик грелку порвал точня такой же линейный поиск по заранее заданным строкам в сишке.
                                                        Ответить

                                                        • ava j123123 05.05.2021 21:06 # 0

                                                          > [citation needed]

                                                          https://wandbox.org/permlink/hrNq6pmrUutcxCt5 - примитивная кодогенерация.

                                                          https://gcc.godbolt.org/z/3a631c6Yx - результат.

                                                          Сравни это с https://gcc.godbolt.org/z/aa6Eqeze5 по качеству машинного кода.
                                                          Ответить

                                                          • ava PolinaAksenova 05.05.2021 21:15 # 0

                                                            Пока ты там писал примитивную кодогенерацию (ня забыл прописать её в Makefile?), которая ещё и сломается ня строках длиннее четырёх символов — крестовички просто пишут
                                                            switch(ct_hash(key)) {
        case ct_hash("hello"): std::puts("Case Hello!"); break;
        case ct_hash("world"): std::puts("Case World!"); break;
        case ct_hash("123"): std::puts("asdeger!"); break;
        case ct_hash("aa1"): std::puts("1!"); break;
        case ct_hash("aa2"): std::puts("2!"); break;
        case ct_hash("aa3"): std::puts("3!"); break;
        case ct_hash("aa4"): std::puts("4!"); break;
        case ct_hash("aa5"): std::puts("5!"); break;
        case ct_hash("aa6"): std::puts("6!"); break;
        case ct_hash("aa7"): std::puts("7!"); break;
        case ct_hash("aa8"): std::puts("8!"); break;
        case ct_hash("aa9"): std::puts("9!"); break;
        case ct_hash("aa10"): std::puts("10!"); break;
    }

                                                            И сразу же получают оптимальный код.
                                                            https://gcc.godbolt.org
                                                            Ответить

                                                            • ava j123123 05.05.2021 21:24 # 0

                                                              Оптимальный код этим не получится. На строках короче или равных 8 байт (64 бит) можно никакой хэш вообще не делать, а сравнивать через switch и это будет явно быстрее. Если строки длиннее 8 байт, и если первые 8 байт у них зачастую не совпадают, то всё равно можно сравнивать 8 байт через uint64_t и потом дальше уже допроверять остаток. Для оптимального кода нужны какие-то сложные эвристики, возможно даже есть смысл собрать статистику встречаемости таких-то строк и на основе этого заоптимизировать очередность сравнения. Так что до какой-то оптимальности тут очень далеко.
                                                              Ответить

                                                              • ava j123123 05.05.2021 21:31 # 0

                                                                кстати если метки в switch-case идут плотно, т.е.
                                                                case 1: smth1(); break;
case 2: smth2(); break;
case 3: smth3(); break;
case 4: smth4(); break;

                                                                компилятор может сделать табличку поиска, т.е. попросту говоря массив из указателей на функции (или возможно на блоки кода), и в arr[1] будет присвоен указатель на функцию smth1(), в arr[2] будет присвоен указатель на функцию smth2() и так далее. И это будет быстрее хешей и бинарного поиска. Оптимизация хуиты в swich это вообще целая наука. Глупо надеяться на то, что можно сделать всё оптимально, используя какой-то там хэш
                                                                Ответить

                                                                • ava MAKAKA 05.05.2021 21:38 # 0

                                                                  Если метки в свитчах помещаются в целое число данной архитектуры (ну там в 8 байт, например), то хеш наверное и вовсе никогда не нужен:)

                                                                  Но массив указателей это правда круто
                                                                  Ответить

                                                              • ava PolinaAksenova 05.05.2021 21:33 # 0

                                                                Зато соотношение скорости написания и простоты кода к его производительности у C++ вышло няилучшим. Пока сишник будет приделывать в свою билд-систему кодогенерацию ня HTML-шаблонах — крестовички няпишут десять таких свитчей. А если будет боттлнек — тогда уже можня переходить либо к Switcher (в который можня вкрутить любые эвристики), либо к, да, кодогенерации.
                                                                Ответить

                                                • ava MAKAKA 05.05.2021 20:34 # 0

                                                  >strcmp
                                                  ну так где свитч с бинароным поиском по хешу, а где 100500 strcmp
                                                  Ответить

                                                  • ava PolinaAksenova 05.05.2021 20:36 # 0

                                                    Какой бинярный поиск? Switcher с лямбдами — это просто тупой линейный перебор по кейсам со сравнением через ==. Собственно, потому на aaa-aaj он такую бредятину и сгенерировал: каждый cmp WORD PTR [rsi], 24929 — это ошмёток соответствующего execImpl<>().
                                                    Ответить

                                                    • ava j123123 05.05.2021 20:40 # 0

                                                      Бинарный там или не бинарный поиск, какая мне разница? Тут ключ-значение. Пусть оптимально генерирует, раз там оно похоже по каким-то байтикам. Для таких случаев можно написать куда более эффективную реализацию.
                                                      Ответить

                                                      • ava PolinaAksenova 05.05.2021 20:42 # 0

                                                        Так почему же великая сишка даже ня трёх кейсах выдала позорные три вызова strcmp(), хотя код там одиняковый?
                                                        Ответить

                                                    • ava guest6 05.05.2021 20:48 # 0

                                                      Я имел ввиду, что можно сделать супероптимальное говно (свитч по хешам, который затем компилятор превратит в бинарное дерево, если верить Мыщъу), а вы какой-то ужас показываете с серией strcmp

                                                      Можно, кстати, и не по хешам, а просто разбить слова на буковки, и сделать дерево по буковкам же
                                                      Ответить

                                                      • ava PolinaAksenova 05.05.2021 20:50 # 0

                                                        Супероптимальное говно — в https://wandbox.org/permlink/agzUP2JIbCSSzwOR, я там сделала компайл-тайм perfect hashing и лукап за два вычисления хэша от ключа — асимптотически это O(1), быстрее, чем бинярный поиск. Правда, для малого количества ключей оно някнет даже линейному поиску через сравнения, что мы тут и продемонстрировали.
                                                        Ответить

                                                        • ava guest6 05.05.2021 20:57 # 0

                                                          напишити умный кот, который для малого кол-ва ключей будет делать линейный пошук по массиву, а для большого -- превращаться вхеш
                                                          Ответить

                                                          • ava PolinaAksenova 05.05.2021 21:00 # 0

                                                            Здесь представлены варианты Switcher и с хэшами, и с линейным поиском. Объедини их — и готово (¬‿¬ )!
                                                            Ответить

                                                      • ava PolinaAksenova 05.05.2021 20:58 # 0

                                                        > свитч по хешам, который затем компилятор превратит в бинарное дерево, если верить Мыщъу
                                                        У меня в реальном коде используется имення такой свитч. И да, компилятор действительня превращает его в бинярное дерево:
                                                        void func(std::string_view key)
{
    switch(ct_hash(key)) {
        case ct_hash("hello"): std::puts("Case Hello!"); break;
        case ct_hash("world"): std::puts("Case World!"); break;
        case ct_hash("123"): std::puts("asdeger!"); break;
        case ct_hash("aa1"): std::puts("1!"); break;
        case ct_hash("aa2"): std::puts("2!"); break;
        case ct_hash("aa3"): std::puts("3!"); break;
        case ct_hash("aa4"): std::puts("4!"); break;
        case ct_hash("aa5"): std::puts("5!"); break;
        case ct_hash("aa6"): std::puts("6!"); break;
        case ct_hash("aa7"): std::puts("7!"); break;
        case ct_hash("aa8"): std::puts("8!"); break;
        case ct_hash("aa9"): std::puts("9!"); break;
        case ct_hash("aa10"): std::puts("10!"); break;
    }
}
                                                        ...
movabs  rcx, 620444549055354499
        cmp     rax, rcx
        je      .L4
        movabs  rcx, -1793442995417202535
        cmp     rdx, rcx
        ja      .L5
        movabs  rcx, 620444549055354496
        cmp     rax, rcx
        je      .L6
        movabs  rcx, -1793446293952087168
        cmp     rdx, rcx
        jbe     .L22
        movabs  rdx, 620444549055354497
        cmp     rax, rdx
        je      .L11
        add     rdx, 1
        cmp     rax, rdx
        jne     .L23
        mov     edi, OFFSET FLAT:.LC7
        jmp     puts
...

                                                        https://gcc.godbolt.org/z/9jzYYcvha

                                                        Проверки ня коллизии выкинуты для няглядности.
                                                        Ответить

                                            • ava j123123 05.05.2021 20:26 # 0

                                              При таких данных https://gcc.godbolt.org/z/aa6Eqeze5 результирующий код получается уже совсем неадекватным. А ведь всего-то надо понять, что первые две буковки у нас "aa" и потом проверить третью буковку.
                                              Ответить

                              • ava j123123 05.05.2021 18:59 # 0

                                https://wasm.in/blogs/identifikacija-switch-case-break.106/ кстати рекомендую вот, по оптимизации поиска соответствия значениям из switch
                                https://wasm.in/archive/pub/9/pic/p33.gif

                                Если крестовым говнометапрограммированием нельзя просто понабрасывать меток case в этот switch и дать компилятору делать свое дело, нужно как-то ручками нагенерировать кучу if() хреней оптимальным образом (занимаясь работой компилятора).
                                Ответить

                                • ava MAKAKA 05.05.2021 19:15 # 0

                                  Охуенная мысль руками построить двоичное дерево из ифоф, чтобы искать нужную ветку в свитче не за N, воу

                                  Нет уж, лучше руками написать свитч, и пусть ебется компилятор, ведь он умел это еще в 2002-м году.

                                  Интересно другое: один свитч на 20 веточек получается оптимальнее, чем 20 ифэлсов.
                                  Ответить

                                  • ava bormand 05.05.2021 19:16 # 0

                                    > один свитч на 20 веточек получается оптимальнее, чем 20 ифэлсов

                                    Потому что одна ошибка предсказания дешевле чем пять, лол.
                                    Ответить

                                    • ava MAKAKA 05.05.2021 19:21 # 0

                                      да)

                                      Но замечание Криса в том, что если ты заранее знаешь все возможные варианты, то ты просто ложишь их в двоичное дерево, и потом можешь по ним скакать за логорифм.

                                      Можно кстати посчитать от них хеши, и сделать хетаблицу.
                                      Ответить

                                  • ava j123123 05.05.2021 19:25 # 0

                                    > Интересно другое: один свитч на 20 веточек получается оптимальнее, чем 20 ифэлсов.

                                    Иногда компиляторы могут 20 ифелсоф распознать как switch и заоптимизировать его по аналогичной схеме.
                                    Ответить

                                • ava PolinaAksenova 05.05.2021 19:16 # 0

                                  > https://wasm.in/archive/pub/9/pic/p33.gif
                                  Это нязывается "бинарный поиск".
                                  Ответить

                                  • ava j123123 05.05.2021 19:23 # 0

                                    Есть еще ньюанс. После x86 инструкции "cmp" мы можем сразу понять по флагам, больше, меньше или равно. Получается троичное дерево.


                                    https://konyakov.ru/pubs/books/kris-kaspersky-r_i_p/kris-kaspersky-27.pdf
                                    > Балансировка логического дерева

                                    > Учитывая, что x86 процессоры все три операции сравнения <, =, > совмещают в одной машинной команде, двоичное логическое дерево можно преобразовать в троичное,тогда новых гнезд для его балансировки добавлять не нужно. Простейший алгоритм, называемый методом отрезков,работает так: сортируем все числа по возрастанию и делимполучившийся отрезок пополам. Число, находящееся по-середине (в нашем случае это 11), объявляем вершинойдерева, а числа, расположенные слева от него, – его левы-ми ветвями и подветвями (в нашем случае это 0, 3, 4 и 7).Остальные числа (22, 96, 98, 666, 777) идут направо.
                                    Ответить

                                    • ava bormand 05.05.2021 19:26 # 0

                                      Ну вот только бранча сразу на 3 стороны у "x86" нету. И вместо относительно дешёвого сравнения с константой мы получим по джва условных перехода на каждом уровне дерева.

                                      Х.з., это точно хороший хак? Пруфы пирфоманса есть?
                                      Ответить

                                      • ava j123123 05.05.2021 19:32 # 0

                                        > Х.з., это точно хороший хак? Пруфы пирфоманса есть?

                                        Я думаю что это от процессора зависит сильно. Ну вообще можно побенчмаркать конечно.

                                        Если какой-то 8-битный говноконтроллер без префетчей, там вполне норм будет
                                        cmp(reg0, reg1)
goto_if_gr l1
goto_if_ls l2

##а тут код, который выполняется если reg0 == reg1

goto end

l1:
##тут код, который выполняется если reg0 > reg1
goto end

l2:
##тут код, который выполняется если reg0 < reg1

end:
                                        Ответить

      • ava ASD_77 05.05.2021 17:15 # 0

        насколько я помню switch это не код а асм команда. там нет поиска по бинарнику.
        Ответить

        • ava PolinaAksenova 05.05.2021 17:20 # 0

          Нет, компилятор умеет разворачивать switch() в бинярный поиск при няличии достаточного количества кейсов: https://godbolt.org/z/3fEej91nj . А вот если кейсы лежат достаточня близко друг к другу, тогда компилятор генерирует простую проверку границ и прыжок по таблице.
          Ответить

      • ava MAKAKA 05.05.2021 17:19 # 0

        если это constexpr то чому enumы не сделать?
        Ответить

        • ava PolinaAksenova 05.05.2021 17:21 # 0

          По условиям задачи строка, по которой нядо сделать switch, приходит к ням в рантайме — из std::cin, няпример.
          Ответить

          • ava MAKAKA 05.05.2021 17:24 # +1

            но тогда может совпать хеш
            о, бля, у вам там целый тредик про это
            изхвини
            Ответить

            • ava PolinaAksenova 05.05.2021 17:25 # +1

              Для этого после каждого case нядо делать рантайм-сравнение строки с ключом.
              Ответить

              • ava MAKAKA 05.05.2021 17:32 # +1

                ну да, совпадение хеша бывает раз в стол лет, можно и сравнить

                вообще свищ по строкам -- штука не однозначная, в реальном мире у нее мало полезных кейсов (кроме разве что literal types в TS) и скриптушне

                интересно, на кой черт ее завезли в джавы и C#?
                Ответить

                • ava ASD_77 05.05.2021 18:36 # +1

                  не поверишь - такое случается сплош и рядом особенно со словами в uppercase
                  Ответить

                  • ava PolinaAksenova 05.05.2021 18:39 # 0

                    Используй нярмальный 64-битный хэш, которому на uppercase глубоко няплевать.
                    Ответить

                  • ava MAKAKA 05.05.2021 18:44 # +3

                    напомнило


                    LM-хеш вычисляется следующим образом:

                    * Пароль пользователя приводится к верхнему регистру.
                    * Пароль дополняется нулями или обрезается до 14 байтов.
                    * Получившийся пароль разделяется на две части по 7 байтов.
                    * Эти значения используются для создания двух ключей DES, по одному для каждой 7-байтовой половинки, при этом 7 байтов рассматриваются как битовый поток и после каждых 7 битов вставляется ноль. Так создаются 64 бита, необходимые для ключа DES.
                    * Каждый из этих ключей используется для DES-шифрования ASCII-строки «KGS!@#$%», в результате получаются два 8-байтовых шифрованных значения.
                    * Данные шифрованные значения соединяются в 16-байтовое значение, являющееся LM-хешем.
                    Ответить

                    • ava bormand 05.05.2021 18:51 # +2

                      > или обрезается до 14 байтов

                      Как вообще можно было додуматься обрезать пароли? Почему бы честно не сказать юзеру, что его пароль слишком длинный?
                      Ответить

                      • ava MAKAKA 05.05.2021 18:58 # +1

                        А в верхний регистр переводить?

                        В 1993-м году о безопасности даже в большом Интернете не думали (finger в inetd наружу торчал), а уж в опенспейсовых кубиках офисов и подавно.
                        Ответить

                        • ava CEHT9I6PbCKuu_nemyx 01.09.2021 20:38 # 0

                          В те годы было несколько публичных сервисов для проверки валидности адресов е-мейлов по протоколу «LDAP». В «Windows» даже остались копролиты той эпохи в клиентских программах («MS Mail», «Windows Mail» и во всяких «Аутглюках»).

                          Эти сервисы закрылись после того, как ими воспользовались спамеры. Удобня: раньше можно было брутить е-мейлы для спам-баз без отправки писем.

                          «Виста» 2006-го года шла со списком таких сервисов, хотя они уже не работали.
                          Ответить

                        • ava CEHT9I6PbCKuu_nemyx 01.09.2021 20:45 # +1

                          Ещё мне понравились протоколы «SMTP after POP3» и «POP3 after SMTP». Если тебя авторизовали по одному протоколу, то ты в течение нескольких минут можешь с того же айпишника воспользоваться другим протоколом, не логинясь повторно.

                          Задепрекейтили их только после того, как стало много NAT'ов.
                          Ответить

                          • ava Desktop 01.09.2021 20:48 # 0

                            а в чём был смысл?))
                            Ответить

                          • ava guest6 01.09.2021 20:48 # +1

                            >POP3 after SMTP
                            Это зачем?

                            POP3 умел AUTH из коробки, а SMTP не умел.
                            Его туда завезли относительно недавно (точнее фреймворк SASL)

                            https://datatracker.ietf.org/doc/html/rfc4954

                            Как было публичным почтовикам разрещать пользователю посылку пписем?

                            Только через POP before SMTP.

                            За натом можно было помочь соседу, конечно.
                            Но всё таки легитимный юзер и сраный спамер редко сидят в одной локалке
                            Ответить

                            • ava CEHT9I6PbCKuu_nemyx 01.09.2021 20:53 # 0

                              Да, кстати, в «Опере» 1996-го года был только анонимный SMTP-клиент. Это потом «опен релеи» запретили.
                              Ответить

                            • ava CEHT9I6PbCKuu_nemyx 01.09.2021 20:56 # 0

                              А ещё не было ни SPF, ни DKIM. Можно было хоть Президентом подписываться.
                              Ответить

                            • ava CEHT9I6PbCKuu_nemyx 01.09.2021 21:01 # 0

                              А ещё в RFC были поля From: и Sender: для легальной отправки писем с чужого ящика. Одно из этих полей означало автора текста, другое — с чьей машины отправлено письмо.
                              Ответить

      • ava 3.14159265 01.09.2021 15:02 # 0

        Именно поэтому я за «Си» и против питухешей.

        bagor:                                  # @bagor
        mov     rax, qword ptr [rdi]
        ret
say:                                    # @say
        push    rbx
        mov     rbx, rdi
        mov     edi, offset .L.str
        mov     rsi, rbx
        xor     eax, eax
        call    printf
        mov     rax, qword ptr [rbx]
        movabs  rcx, 448647162223
        cmp     rax, rcx
        jle     .LBB1_1
        movabs  rcx, 448647162224
        cmp     rax, rcx
        je      .LBB1_5
        movabs  rcx, 491495317858
        cmp     rax, rcx
        je      .LBB1_10
        movabs  rcx, 107161303805803
        cmp     rax, rcx
        jne     .LBB1_11
        mov     edi, offset .L.str.10
        pop     rbx
        jmp     puts                            # TAILCALL
.LBB1_1:
        movabs  rcx, 418414092652
        cmp     rax, rcx
        je      .LBB1_9
        movabs  rcx, 418447849843
        cmp     rax, rcx
        jne     .LBB1_11
        mov     edi, offset .L.str.6
        pop     rbx
        jmp     puts                            # TAILCALL
.LBB1_5:
        mov     edi, offset .L.str.2
        pop     rbx
        jmp     puts                            # TAILCALL
.LBB1_10:
        mov     edi, offset .L.str.8
        pop     rbx
        jmp     puts                            # TAILCALL
.LBB1_9:
        mov     edi, offset .L.str.4
        pop     rbx
        jmp     puts                            # TAILCALL
.LBB1_11:
        mov     edi, offset .L.str.11
        pop     rbx
        jmp     puts                            # TAILCALL
main:                                   # @main
        push    rax
        mov     edi, offset .L.str.5
        call    say
        mov     edi, offset .L.str.9
        call    say
        mov     edi, offset .L.str.1
        call    say
        mov     edi, offset .L.str.12
        call    say
        xor     eax, eax
        pop     rcx
        ret
        Ответить

    • ava Soul_re@ver 05.05.2021 11:42 # +1

      Какой паттерн-матчинг :). А по значением нескольких полей объектов сопоставлять умеет?
      Ответить

      • ava ASD_77 05.05.2021 11:55 # 0

        не знаю по каким полям но вот так легко делает
        function test5()
{
		let a = 10;
		let b = 20;
	        switch (30) 
		{                                            
		    case a + b: {
        	        print("cool. working.");                          
			break;
		   }                                          
	        }
}
        Ответить

    • ava 3.14159265 01.09.2021 14:47 # +1

      > А ваш С такое прокомпилирует?
      Запросто.

      https://ideone.com/dB8clW
      #include <stdio.h>
#include <stdint.h> 

uint64_t bagor(void *ptr){
     return *(uint64_t*)ptr;
 }
#define SWITCH(ptr) uint64_t Switch = (bagor(ptr)); if (0){}
#define CASE(ptr) else if (Switch == bagor(ptr))
#define DEF else

void say(const char* who){
	printf("%8s says: ",who); 
	SWITCH(who) 
    CASE("pituh") { 
        puts("kokoko"); 
    }
    CASE("lalka"){
         puts("azaza");
    }
    CASE("syoma"){
         puts("rus-nya");
    }    
    CASE("bagor"){
         puts("hhhrghh");
    }
    CASE("korova"){
         puts("mootools");
    }
    DEF{
        puts("dunno, lol");
    }
}
int main()
{
	say("syoma");
	say("korova");
	say("pituh");
	say("neznayka");
	
    return 0;
}
      Output:
   syoma says: rus-nya
  korova says: mootools
   pituh says: kokoko
neznayka says: dunno, lol
      Ответить

      • ava CEHT9I6PbCKuu_nemyx 01.09.2021 14:56 # +1

        Сначала жертве обрезают пароль до восьми символов.

        Затем оставшееся место добивают нулями.
        Ответить

        • ava 3.14159265 01.09.2021 15:07 # +1

          Ну можно сравнить первые 8, а если обломались сделать strcmp.

          Как видим в компайл-тайме всё оптимизируется в константы
          https://gcc.godbolt.org/z/7xPEabYYx
          Ответить

        • ava 3.14159265 01.09.2021 16:23 # +2

          Добавил strcmp.

          Теперь работает на длинных строках, однако короткие по-прежнему оптимизируются в mov/cmp/je.

          Также сделал SWITCH более «бейсиковским» и добавил поддержку break.
          https://ideone.com/a4Ni8C
          #include <stdio.h>
#include <stdint.h> 
#include <string.h>

#define haszero(v) (((v) - 0x0101010101010101UL) & ~(v) & 0x8080808080808080UL)

uint64_t bagor(const char *ptr){
    uint64_t * p64 = (uint64_t*)ptr;
     return haszero(* (p64)) 
        ? * (p64)
        : -1
     ;
}


#define SWITCH(ptr)                     \
    do{                                 \
    uint64_t Switch = (bagor(ptr));     \
    const char * SwitchKey = ptr;       \
    if (0){ 
    
#define CASE(ptr) } else if (-1 != Switch                       \
                ?    Switch == bagor(ptr)                       \
                :    0 == strcmp(SwitchKey, ptr)                \
                 ){

#define DEFAULT } else {
#define ENDCASE } } while(0);

void say(const char who[8]){
    printf("%8s says: ",who); 
    SWITCH(who) 
    CASE("pituh") 
        puts("kokoko"); 
    CASE("lalka")
         puts("azaza");
    CASE("syoma")
         puts("rus-nya");
    CASE("bagor")
         puts("hhhrghh");
    CASE("korova")
         puts("mootools");
         break;
         puts("unreachable");
    CASE("Stripper Penetrator\0\0")
         puts("vanished");
    DEFAULT
        puts("dunno, lol");
    ENDCASE
    
}
int main()
{
    say("syoma");
    say("korova");
    say("pituh");
    say("neznayka");
    say("Stripper Penetrator");    

    return 0;
}
          Ответить

          • ava CEHT9I6PbCKuu_nemyx 01.09.2021 17:21 # 0

            Почему-то последний случай кого-то напоминает...
            Ответить

          • ava PolinaAksenova 01.09.2021 19:50 # +3

            Это специальняя паралимпиада о свитчах по строкам? Можня выпускать своих участниц?

            https://govnokod.ru/27392#comment625532

            В той ветке даже решение с идеальным хэшированием есть <(￣︶￣)>!
            Ответить

            • ava 3.14159265 01.09.2021 19:55 # +3

              > Это специальняя паралимпиада о свитчах по строкам? Можня выпускать своих участниц?

              Мы няк раз ждали девочек-волшебниц: Полиняшу и Бормандяшу.
              Ответить

    • ava 3.14159265 01.09.2021 15:58 # 0

      Говно?
      #define haszero(v) (((v) - 0x0101010101010101UL) & ~(v) & 0x8080808080808080UL)

uint64_t ct_hash(const uint64_t *ptr)
{
    uint64_t val = 14695981039346656037ull;
    
    for (size_t i=0;;++i) {
        val ^= ptr[i];
        val *= 1099511628211ull;
        if haszero(ptr[i]) {
            return val;
        }
    }
}

uint64_t barop(const char *ptr){
    uint64_t * p64 = (uint64_t*)ptr;
     return haszero(* (p64)) 
        ? * (p64)
        : ct_hash(p64)
     ;
}
      Ответить

      • ava CEHT9I6PbCKuu_nemyx 01.09.2021 20:03 # +1

        Кокококонстанты знакомые:
        https://govnokod.ru/27287#comment617046

        Мне кажется, я их видел на ГК несколько лет назад.
        Ответить

        • ava 3.14159265 01.09.2021 20:05 # +2

          Честно спиздил с начала треда и портировал на Сишку чтобы посмотреть асм-выхлоп.

          https://govnokod.ru/27392#comment625532

          Мне всё покоя не даёт случай, если в 64-битное сравение подсунут строку с мусором.
          char * str = "syoma\0\0bagor";
          В остальном пример с strcmp работает замечательно, лучше хеша.
          Ответить

          • ava CEHT9I6PbCKuu_nemyx 01.09.2021 20:12 # 0

            Вот тут много похожей питушни:
            http://graphics.stanford.edu/~seander/bithacks.html
            Ответить

            • ava 3.14159265 01.09.2021 20:18 # +1

              Все эти BSR, LZCNT и __builtin_clz мне известны.

              Я хотел посчитать количество ведущих нулей и сравнить.

              Но, во-первых, это непортабельность на big-endian.

              Во-вторых, не поможет с "syoma\0\0z" == "syoma"
              Хотя технически строки одинаковы.

              Придётся при каждом неравенстве звать strcmp (прощай пирформанс).

              Похоже без магии девочек-волшебниц мне ня обойтись
              Ответить

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