1. Си / Говнокод #12379

    +135

    1. 001
    2. 002
    3. 003
    4. 004
    5. 005
    6. 006
    7. 007
    8. 008
    9. 009
    10. 010
    11. 011
    12. 012
    13. 013
    14. 014
    15. 015
    16. 016
    17. 017
    18. 018
    19. 019
    20. 020
    21. 021
    22. 022
    23. 023
    24. 024
    25. 025
    26. 026
    27. 027
    28. 028
    29. 029
    30. 030
    31. 031
    32. 032
    33. 033
    34. 034
    35. 035
    36. 036
    37. 037
    38. 038
    39. 039
    40. 040
    41. 041
    42. 042
    43. 043
    44. 044
    45. 045
    46. 046
    47. 047
    48. 048
    49. 049
    50. 050
    51. 051
    52. 052
    53. 053
    54. 054
    55. 055
    56. 056
    57. 057
    58. 058
    59. 059
    60. 060
    61. 061
    62. 062
    63. 063
    64. 064
    65. 065
    66. 066
    67. 067
    68. 068
    69. 069
    70. 070
    71. 071
    72. 072
    73. 073
    74. 074
    75. 075
    76. 076
    77. 077
    78. 078
    79. 079
    80. 080
    81. 081
    82. 082
    83. 083
    84. 084
    85. 085
    86. 086
    87. 087
    88. 088
    89. 089
    90. 090
    91. 091
    92. 092
    93. 093
    94. 094
    95. 095
    96. 096
    97. 097
    98. 098
    99. 099
    100. 100
    #include <stdio.h>
    #include <malloc.h>
    #include <sys/time.h>
    #include <pthread.h>
    
    #define MAXPRIME 10000001
    char sieve[MAXPRIME];
    
    typedef struct {
        int id, min, max, step;
        unsigned long long result;
    } Task;
    
    void primes() {
        printf("Searching prime numbers ...\n");
        sieve[0] = sieve[1] = 1;
        for (int i=2; i<MAXPRIME; i++)
            sieve[i] = 0;
        int i = 2;
        while (1) {
            while (i<MAXPRIME && sieve[i])
                i++;
            if (i >= MAXPRIME)
                break;
            for (int j=i*2; j<MAXPRIME; j+=i)
                sieve[j] = 1;
            i++;
        }
    }
    
    double utime() {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec / 1000000.0;
    }
    
    unsigned long long calc(int thread, int min, int max, int step) {
        unsigned long long sum = 0;
        double start = utime();
        int nextshow = max+1;
        for (int n=max; n>=min; n-=step) {
            if (!sieve[n]) {
                sum += 1;
                continue;
            }
            if (n <= nextshow && n > min) {
                double elapsed = utime() - start, eta = elapsed/(max-n)*(n-min);
                printf("Thread %d: current=%d elapsed=%lfs eta=%lfh\n", thread, n, elapsed, eta/3600);
                nextshow = n < 10000 ? 0 : n - 10000;
            }
            int b;
            asm("movl %1, %%ecx\n"
                "1: dec %%ecx\n"
                "movl %%ecx, %%eax\n"
                "imull %%eax\n"
                "idivl %1\n"
                "cmpl %%ecx, %%edx\n"
                "jnz 1b\n"
                "movl %%ecx, %0"
                : "=g"(b)
                : "r"(n)
                : "%eax", "%ecx", "%edx");
            sum += b;
        }
        return sum;
    }
    
    void * thread(void *arg) {
        Task *task = arg;
        printf("Thread %d: working from %d to %d step %d\n", task->id, task->min, task->max, task->step);
        task->result = calc(task->id, task->min, task->max, task->step);
        printf("Thread %d: partial result is %llu\n", task->id, task->result);
        return NULL;
    }
    
    int main() {
        primes();
    
        int threads = 4;
        int max = 10000000;
        pthread_t tid[10];
        Task tasks[10];
    
        for (int i=0; i<threads; i++) {
            tasks[i].id = i;
            tasks[i].min = 1;
            tasks[i].max = max-i;
            tasks[i].step = threads;
            pthread_create(&tid[i], NULL, thread, &tasks[i]);
        }
    
        unsigned long long sum = 0;
        for (int i=0; i<threads; i++) {
            pthread_join(tid[i], NULL);
            sum += tasks[i].result;
        }
    
        printf("Result: %llu\n", sum);
        return 0;
    }

    Мое ужасное решение вот этой задачки: http://projecteuler.net/problem=407

    В день, когда математика упорно не желает вспоминаться...
    на помощь приходят брутальные и бессердечные ассемблер и мультитрединг.

    model name: Pentium(R) Dual-Core CPU E5400 @ 2.70GHz
    real 286m45.890s
    user 545m44.926s

    Запостил: bormand, 01 Января 2013

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

    • Пишу из кофе неподалёку от пляжа Мериса, острова Шри-Ланка. Тут перебои с Интернетом какие-то, но мне пофиг. С Новым Годом!
      Ответить
      • >Пишу из кофе неподалёку от пляжа Мериса, острова Шри-Ланка.
        ЗАВИДОВАТ

        >Тут перебои с Интернетом
        А, нет, отпустило.
        Ответить
        • Ничего на свету лучше нету,
          Чем сто мегабитов интернету!
          Ответить
        • > >Тут перебои с Интернетом
          > А, нет, отпустило.
          Это в основном из-за будущей жены. Она говорит, что я часто хожу на сранные сайты, например говнокод. Она считает его очень странным почему-то и говорит, чтобы я больше туда не ходил. Говорит, что у меня какая-то зависимость и что это очень плохо. Она ведь не права? Может мне её бросить?
          Ответить
          • Какой жены, тебе же семь лет? Или уже восемь, но всё равно.
            Ответить
          • беги от неё!
            Ответить
          • >перебои с Интернетом
            >из-за будущей жены

            100Mbps-женщина перебивает интернет.

            И вообще, не нужно себя обманывать. Если ты один раз свозил девушку на Шри-Ланку на НГ, это еще не значит, что она будет тебе готовить и стирать носки. Тут без ожерелья с брелянтами не обойтись.
            Ответить
            • > Тут без ожерелья с брелянтами не обойтись.

              беги от неё!
              Ответить
              • Я сам так не делаю, только ему советую.
                Ответить
              • Тарас сегодня подозрительно прав. Уже второй раз подряд.
                Ответить
      • Только вот ip твой ну никакая не Шри-Ланка.
        Ответить
        • А он вайфай из дома ловит. Потому и проблемы с интернетом...
          Ответить
          • так он может через vpn сидит из домашнего инета
            Ответить
    • админ мудак! неужели так трудно сделать ссылки кликабельными?
      Ответить
      • Старая школа
        Ответить
      • Неужели трудно поставить аддон или выделять? Чай, не в линксах сидишь.
        И, вообще, мы тут привыкли к хардкору, а ты тут лезешь со своим херомуставом в нашу часть.
        Ответить
        • Это написано специально для админа! Какого ты лезешь вообще? Хардкорщик хренов...
          Ответить
          • Может быть, я на самом деле виртуал админа? Или нет, rat4. Совсем запутался, короче, не помню. Помню - чей-то.
            Ответить
      • Одно из преимуществ регистрации: у зарегистрированных пользователей ссылки кликабельны и они могут читать
        скрытый текст:
        Для просмотра скрытого текста - войдите или зарегистрируйтесь.
        Ответить
        • А можно порог хайда снизить, а то я тоже не вижу?
          Ответить
          • Ньюфаг... Парни, а классный анекдот модер затравил скрытым текстом, да?

            А король-то голый...
            Ответить
            • >классный анекдот
              Не анекдот это, а реальный случай. К сожалению.
              Ответить
          • Ну хоть ссылки-то работают? Подозреваю всё дело в кукисах.
            Ответить
            • Ссылки-то работают. У меня же id < 2k. А кукис браузером я уже два раза почистил.
              Ответить
              • А что id, в формуле рассчёта кармы не учитывается id. В пункте 2.4.5 правил дана же формула. Если ссылки не работают, могу скинуть в личку.
                Ответить
          • Ссылки кликабельны только при карме >= 100. Так написано в правилах.
            Ответить
            • Ну да. Там и про отображение скрытых текстов написано.
              Ответить
            • >кликабельны только при карме >= 100.
              Это само собой. Оно сохраняется в куках.
              Когда карма превысила порог а ссылки не работают, то нужно просто почистить куки.
              Потому иногда проблемы с сессиями. Пользователя может разлогинить. Например когда карма упала ниже порога.

              Да что там. Вновь прибывшим даже писать комментарии неделю нельзя. Оттуда же.
              Ответить
              • Ещё пообсуждать чутка, и родятся правила поведения ГК 2.0
                Ответить
        • $регистрации
          fixed
          Но ссылки когда есть сессия, работают, да.
          Ответить
      • gopher://jgw.mdns.org/I/PICS/matchbook.jpg
        Ответить
    • @siteDevs: добавьте возможность поставить шрифтом выбранного говнокода Comic Sans, ибо ваистену!
      Ответить
    • И что? Этот асмовысер сколько % производительности прибавляет?
      Ответить
      • Если сравнивать с тем что там было до этого:
        for (int b=n-1; ; --b) {
            long long lb = b;
            if ((lb*lb) % n == b) {
                sum += b;
                break;
            }
        }
        то асм быстрее в 2.8 раза. Гцц вместо дива какого-то хуя втыкает вызов __moddi3, который и убивает всю производительность. А ждать 15 часов вместо 5 меня не особо прикалывало, вот и переписал на асме.
        Ответить
        • Не понимаю, почему втыкается этот __moddi3, судя по докам он нужен для деления 64-битных на 64-битные на 32-битной платформе. Но тут то я делю на 32-битное число, поэтому должен проканать и обычный div/idiv...
          Ответить
          • Щас у себя посмотрел. Если собирать под 32 бит, то он вставляет __moddi3 и прочую вакханалию.
            Если 64 бит. То
            imulq	%rax, %rax
            	movslq	-40(%rbp), %rcx
            	cqto
            	idivq	%rcx
            	movslq	-60(%rbp), %rax
            	cmpq	%rax, %rdx
            	jne	LBB2_13

            5 часов ждать не стал, как побыстрее оценить?)
            Searching prime numbers ...
            Thread 0: working from 1 to 10000000 step 4
            Thread 0: current=10000000 elapsed=0.000001s eta=infh
            Thread 1: working from 1 to 9999999 step 4
            Thread 1: current=9999999 elapsed=0.000001s eta=infh
            Thread 2: working from 1 to 9999998 step 4
            Thread 2: current=9999998 elapsed=0.000001s eta=infh
            Thread 3: working from 1 to 9999997 step 4
            Thread 3: current=9999997 elapsed=0.000001s eta=infh
            Thread 0: current=9990000 elapsed=37.571820s eta=10.426179h
            Thread 2: current=9989998 elapsed=45.755806s eta=12.697232h
            Thread 3: current=9989997 elapsed=47.328907s eta=13.133766h
            Thread 1: current=9989999 elapsed=49.395768s eta=13.707323h
            Thread 0: current=9980000 elapsed=74.303516s eta=10.299292h
            Thread 2: current=9979998 elapsed=90.654717s eta=12.565747h
            Thread 3: current=9979997 elapsed=95.896572s eta=13.292325h
            Thread 1: current=9979999 elapsed=98.456737s eta=13.647195h
            Ответить
            • Ну вот eta часов 10-13, значит где-то за 5 управится, у меня примерно в этом районе и показывало. Быстрее или медленнее той асмовставки оно всяко не будет работать, т.к. количество делений по идее будет таким же, а все остальное - копейки.

              > Если 64 бит. То
              Хороший код получился. Давно хотел сменить ось на 64битную. Видимо настало время.
              Ответить
              • > Давно хотел сменить ось на 64битную. Видимо настало время.
                да, срочно переходим на UTCv6, где в сутках 64 часа
                Ответить
        • А так?
          (int)((((long long) b)*((long long) b))%n);

          Я точно знаю что гцц правильно делает
          (int)((((long long) b)*((long long) b))>>32);

          так что может ты записал не так?
          Ответить
          • Ну вот со сдвигом 100% получается. А делить не хочет. Я и signed и unsigned во всех сочетаниях поперевтыкал. Все равно этот __moddi3 или __umoddi3, в который делителем приходит 64 битное число, у которого в старших разрядах намертво забит 0.
            Ответить
            • С делением да, странно. Делитель пробовал по-разному делать, и в int и в long long?
              Эх а вот в Форте есть готовый оператор */ для такой фигни - умножить и поделить, имея промежуточный результат двойной длины.
              А в Аде есть фиксированная запятая, она тут как-то должна помочь, мне кажется.
              Ответить
              • > Делитель пробовал по-разному делать, и в int и в long long?
                Да, конечно.

                > в Форте есть готовый оператор */ для такой фигни
                Да, именно такой функции и не хватает. Можно конечно ее запилить в виде макроса на асме под важные платформы, а на остальных оставить костылик с кастом в int64 перед умножением.
                Ответить
          • P.S. Понятно, что в стандартах c/c++ написано, что перед операцией оба операнда приводятся к одному типу. Но в данном случае компилеру заведомо известно, что число 32битное, и он мог бы сгенерить сокращенный код без полноценного 64битного деления... хбз почему так не сделали, может быть я еще что-то упускаю..
            Ответить

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