C для индексации цикла: вперед индексирует быстрее в новых центральных процессорах?

Это, вероятно, не имеет большого значения с точки зрения скорости, но я часто пишу:

for (i = n; --i >= 0; ) blah blah

что, как мне кажется, когда-то генерировало более чистую сборку.

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

Нет, мы не можем сказать, что процессорные реализации изменились, чтобы сделать петлю быстрее. И это очень мало связано с самими процессорами.

Это связано с тем, что Вы не указали ни , о каком процессоре идет речь, ни о компиляторе.

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

Если Вы захотите перефразировать вопрос под конкретный процессорный и машинный язык (так как какой машинный язык Вы получаете из компилятора Си зависит полностью от компилятора), Вы можете получить лучший ответ.

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

Направление, в котором Вы должны делать итерации, всегда продиктовано тем, что Вы должны делать. Например, если вам нужно обрабатывать элементы массива в порядке возрастания, вы используете:

for (i = 0; i < 1000; i++) { process (a[i]); }

а не:

for (i = 999; i >= 0; i--) { process (a[999-i]); }

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

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

Мой совет: всегда сначала программируйте на удобочитаемость, а затем нацеливайтесь на любые специфические проблемы с производительностью ("сначала заставьте его работать, потом заставьте его работать быстро").

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

Да. Но с оговоркой. Идея, которая зацикливающая назад, быстрее никогда не применяется ко всем старшим процессорам. Это вещь х86 (как у 8086 по 486, возможно, Pentium, хотя я никак не думаю).

Эта оптимизация никогда не применяется к любой другой архитектуре ЦП, о которой я знаю.

Вот почему.

У 8086 был регистр, который был специально оптимизирован для использования в качестве счетчика петли. Вы помещаете счет цикла в CX, а затем есть несколько инструкций, которые уменьшают Cx, а затем устанавливают коды условий, если он переходит на ноль. На самом деле был префикс инструкций, который вы могли бы поставить перед другими инструкциями (префикс REP), который в основном будет помимо выполнять другую инструкцию до тех пор, пока CX не получится до 0.

в те дни, когда мы подсчитывали инструкции, и инструкции, имели данные, имели значение CX как ваш счетчик петли был способом пойти, а Cx был оптимизирован для подсчета.

Но это было давно время назад. С момента Pentium эти сложные инструкции были более медленными в целом, чем использование большего, и более простые инструкции. (RISC Baby!) Ключевое то, что мы стараемся сделать в эти дни, пытаются положить некоторое время между загрузкой реестра и использование его, потому что трубопроводы могут на самом деле делать несколько вещей за цикл, если вы не пытаетесь использовать один и тот же регистр больше, чем одна вещь за раз.

outdays То, что убивает производительность, не сравнение, это ветвление, а затем только тогда, когда прогнозирование ветвления прогнозирует неправильно.

У меня есть административный проект BOINC (в настоящее время не существует), я немного участвовал в разработке BOINC (и во многих пламенных программах с разработчиками!), есть, по крайней мере, одна функция, которую я реализовал, которая сейчас находится на сервере, и я взломал один или два проекта BOINC, которые не понимают важности "поддержания программного обеспечения до Сейчас я работаю с тремя другими людьми на вилке клиента BOINC. Достаточно ли этого?:)

Если вы не ищете кого-то нанять (намек!), вы должны просто задать конкретные вопросы по SO по фактическим проблемам, которые у вас возникают при настройке сервера BOINC или при разработке приложения или чего-либо еще, вместо того, чтобы «кто-нибудь знал что-нибудь о теме?»

По вопросам, которые вы задавали:

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

Вы должны установить свой собственный сервер с LAMP и BOINC. (Обратите внимание, что SETI @ Home использовал Solaris вместо Linux; и я почти уверен, что вы можете использовать не-Apache веб-серверы, если вы пишете конфигурационный элемент самостоятельно).

Вы создаете приложение, которое использует API BOINC (или изменяете существующее вычислительное приложение, чтобы использовать его), устанавливаете его на сервере, создаете «рабочие единицы» и получаете клиентов для присоединения к вашему проекту. Клиенты загружают работу, обрабатывают ее и загружают обратно.

Завершенная задача проходит через «валидатор» (который вы пишете или используете один из образцов), который проверяет правильность вычислений, и «ассимилятор» (который вы пишете), который делает что-то полезное с результатом; например, анализ выходного файла и помещение данных в реляционную базу данных, или сообщение электронной почты о том, что вы нашли «Ответ жизни», «Вселенная и всё». Или упаковать результаты нескольких работ, и отправить их обратно «ученому».

Какие языки он поддерживает? как он работает со временем выполнения (полагаю, вы сможете предоставить полный, независимый пакет со всеми необходимыми материалами)

Он в основном поддерживает C++. API совместим с C, и существуют производственные проекты, использующие его от Fortran (climateprediction.net - ~ млн линий Fortran).

Я также написал обертку для Python . Приложение Python внутри не имеет большого доступа к API, но его легко добавить. Но это, наверное, плохая идея. Если вам нужен BOINC, это потому, что вам нужно много ЦП времени. И в этом случае вы не будете использовать медленный интерпретируемый язык для начала.

Откуда люди знают, что ваш проект существует

Широко, то же самое, путь они знали бы ваш блог существует: это ваша маркетинговая/SEO проблема;)

Однако вы получаете несколько уникальных вещей, связанных с сообществом:

• Есть BOINCaholics, которые присоединятся к любому проекту, который приходит, и активно искать их. И расскажите их друзьям и товарищам по команде. Разместите свой проект в сети, включите форумы, получите его ссылку хотя бы с одного веб-сайта, чтобы он появился в Google,и я гарантирую , что в течение нескольких дней появится поток форума с «ATA» в теме (Alpha Testers Anonymous). Я могу даже сказать вам имена пользователей людей, которые будут там, если хотите. Они , которые предсказуемы. (Честно говоря, вы можете найти меня там тоже: D)
• Есть много сайтов статистики, которые собирают кредитную статистику пользователей из нескольких проектов и агрегируют их. Присутствие вашего проекта на одном из этих сайтов - важный способ увидеть его. Но просто экспорт статистики не означает, что вы доберетесь туда; вы должны показать администраторам сайтов статистики, что ваш проект делает что-то полезное (чтобы их мнение) и что ему можно доверять.
• Если вы поддерживаете хорошую связь с вашими пользователями, хорошую стабильность в приложениях и т.д., вы получите больше пользователей через сарафанное радио и, что, возможно, более важно, вы получите ваши существующие пользователи, чтобы остаться и/или дать вам большую долю времени ЦП. Внимательно относитесь к «у вас есть только одна возможность произвести первое впечатление». Не афишируйте свой проект большим при первом запуске, пусть сарафанное радио сначала позаботится о нем, пока он не станет достаточно стабильным.

Конечно, совершенно очевидно, что доля населения мира, владеющего компьютерами, которые являются BOINCaholics, незначительна. И менее 10% вообще используют BOINC. Если вы хотите нацеливаться на широкую аудиторию: вернитесь к обычному маркетингу на веб-сайте, и я не могу помочь вам в этом. Обратите внимание, что в этом случае вам также придется объяснить им, как работает BOINC и как его установить!

и зарегистрироваться для участия?

Они присоединяют проект от своего клиента BOINC (или загружают его сначала, если они не знакомы с BOINC). Они могут создать учетную запись непосредственно из графического интерфейса пользователя BOINC.

Пожалуйста, даже не думайте о том, чтобы попытаться разработать свой собственный проект BOINC, пока вы не используете BOINC самостоятельно в качестве пользователя в течение некоторого времени. Это похоже на создание веб-сайта без опыта использования веб-браузера («Я думаю, что он работает, но как я смотрю на него сейчас?»). Загрузите клиент, найдите классный проект, прикрепите его и посмотрите, как он работает.

Однажды я попытался помочь кому-то создать проект, а затем обнаружил, что у него нет опыта ни с LAMP, ни с BOINC со стороны пользователя. Это был болезненный опыт.

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

Я не могу подробно остановиться на этом; вы должны будете быть более конкретными в отношении того, что будет делать ваш проект, откуда идет «работа», какая обработка должна быть выполнена на стороне сервера, какой язык/среду выполнения/библиотеку использует ваше клиентское приложение и т.д. и тогда я мог бы сказать вам, есть ли у BOINC что-то, что может помочь вам с этим.

... и я думаю, что этого достаточно на данный момент (whew, 3:15 утра!).

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

#include <time.h>
#include <stdio.h>

int main(void)
{
    int i;
    int s;
    clock_t start_time, end_time;
    int centiseconds;

    start_time = clock();
    s = 1;
    for (i = 0; i < 1000000000; i++)
    {
        s = s + i;
    }
    end_time = clock();
    centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC;
    printf("Answer is %d; Forward took %ld centiseconds\n", s, centiseconds);

    start_time = clock();
    s = 1;
    for (i = 999999999; i >= 0; i--)
    {
        s = s + i;
    }
    end_time = clock();
    centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC;
    printf("Answer is %d; Backward took %ld centiseconds\n", s, centiseconds);

    return 0;
}

Составлен с -O9 используя gcc 3.4.4 на Cygwin, работая на «AMD Athlon (TM) 64 Процессора 3500 +» (2 211 МГц) в 32-битном Windows XP:

Answer is -1243309311; Forward took 93 centiseconds
Answer is -1243309311; Backward took 92 centiseconds

(Ответы, различные 1 так или иначе в нескольких повторениях.)

Собранный с-I9, использующим gcc 4.4.1 работы «Intel (R) Atom (TM) CPU N270 1.60 ГГц» (800 МГц и по-видимому только одного ядра, учитывая программу) в 32-битной Ubuntu Linux.

Answer is -1243309311; Forward took 196 centiseconds
Answer is -1243309311; Backward took 228 centiseconds

(Ответы варьировались на 1 в любом случае в нескольких повторениях.)

Глядя на код, прямой цикл переводится в:

; Gcc 3.4.4 on Cygwin for Athlon      ; Gcc 4.4.1 on Ubuntu for Atom
L5:                                .L2:
    addl    %eax, %ebx                 addl    %eax, %ebx
    incl    %eax                       addl    $1, %eax
    cmpl    $999999999, %eax           cmpl    $1000000000, %eax
    jle     L5                         jne     .L2

Назад в:

L9:                                .L3:
    addl    %eax, %ebx                 addl    %eax, %ebx
    decl    %eax                       subl    $1, $eax
    jns     L9                         cmpl    $-1, %eax
                                       jne .L3

Что показывает, если не намного больше, что поведение GCC изменилось между этими двумя версиями!

Вставка старых петель GCC в новый файл asm GCC дает результаты:

Answer is -1243309311; Forward took 194 centiseconds
Answer is -1243309311; Backward took 133 centiseconds

Резюме: на > 5-летнем Athlon петли, генерируемые GCC 3.4.4, имеют одинаковую скорость. На новинку (< 1 год?) Атом, обратная петля значительно быстрее. GCC 4.4.1 имеет небольшой регресс для этого конкретного случая, о котором я лично не беспокоюсь меньше всего, учитывая его пункт. (Я должен был убедиться, что s используется после цикла, потому что в противном случае компилятор полностью исключает вычисления.)

[1] Я никогда не могу вспомнить команду для системной информации...