Re[9]: а как же Larrabee?
От: thesz Россия http://thesz.livejournal.com
Дата: 22.07.09 10:12
Оценка: +1 :)
Здравствуйте, Andrei F., Вы писали:

AF>Здравствуйте, thesz, Вы писали:


T>>Весьма объёмная часть от проекта. Отличающаяся по объёму от всего проекта в константу раз, а, значит, имеющая ту же сложность O(размер_проекта).

T>>Иными словами — дерево всего проекта.

AF>Вот за что я не люблю теоретиков.


И за что конкретно ты не любишь конкретно кого?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: а как же Larrabee?
От: thesz Россия http://thesz.livejournal.com
Дата: 22.07.09 10:18
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, thesz, Вы писали:


T>>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.

CC>Параллелить можно по-разному.
CC>Можно каждый цикл параллелить, а можно логический блок.
CC>Можно пытаться ускорить разбор одного файла, как ты предлагаешь. А можно обработать одновременно несколько файлов, как сделано производителями компиляторов (микрософт и интел)

Итак, мы большую часть времени работаем с одним файлом. Большим файлом, на мег (реальный пример).

Как обработка нескольких файлов сможет ускорить нам компиляцию нашего большого файла?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[11]: а как же Larrabee?
От: thesz Россия http://thesz.livejournal.com
Дата: 22.07.09 10:22
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, thesz, Вы писали:


T>>>>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.

WH>>>1)Где ты видел проект из одного файла?
T>>После препроцессора он становится одним файлом.
CC> Нет!
CC>Если у тебя есть 1.cpp и 2.сpp то после препроцессора у тебя все равно 2 файла. И тот самый разбор исходника будет происходить уже после препроцессора.

Если у меня 1.cc, включающий в себя 2.h, то после препроцессора он станет 1.i и будет включать в себя оба.

Объём заголовочных файлов сравним с объёмом файлов с исходниками.

WH>>>Еще раз читай про IncrediBuild и то как он работает. Сборку реальных проектов ускоряет капитально. Сам видел.

T>>Да и make -n тоже, вроде, как.

make -j N
make --jobs=N

CC>Он тоже умеет раскидывать компиляцию по разным компам и ядрам проца?


Он несколько процессов запускает.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[12]: а как же Larrabee?
От: CreatorCray  
Дата: 22.07.09 11:57
Оценка:
Здравствуйте, thesz, Вы писали:

T>>>>>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.

WH>>>>1)Где ты видел проект из одного файла?
T>>>После препроцессора он становится одним файлом.
CC>> Нет!
CC>>Если у тебя есть 1.cpp и 2.сpp то после препроцессора у тебя все равно 2 файла. И тот самый разбор исходника будет происходить уже после препроцессора.
T>Если у меня 1.cc, включающий в себя 2.h, то после препроцессора он станет 1.i и будет включать в себя оба.

Еще раз: Где ты видел проект из одного файла? Из одного .cpp файла?
Такой сценарий никто даже и не рассматривает.

WH>>>>Еще раз читай про IncrediBuild и то как он работает. Сборку реальных проектов ускоряет капитально. Сам видел.

T>>>Да и make -n тоже, вроде, как.
CC>>Он тоже умеет раскидывать компиляцию по разным компам и ядрам проца?
T>Он несколько процессов запускает.
Это придумано уже давно.
Но колво процессов на конкретно взятой девелоперской машине в первую очередь ограничено колвом ядер проца.
У меня на старой работе колво задействованных в компиляции через Incredibuild ядер доходило до 30.
Прирост скорости получался почти линейный.
Так что IB все таки для не-одного-девелопера все таки лучше
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[10]: а как же Larrabee?
От: CreatorCray  
Дата: 22.07.09 11:57
Оценка:
Здравствуйте, thesz, Вы писали:

T>Итак, мы большую часть времени работаем с одним файлом. Большим файлом, на мег (реальный пример).

Уточни пожалуйста, чтож это за проект такой, который состоит из одного файла исходников в метр толщиной.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[13]: а как же Larrabee?
От: thesz Россия http://thesz.livejournal.com
Дата: 22.07.09 12:30
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, thesz, Вы писали:


T>>>>>>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.

WH>>>>>1)Где ты видел проект из одного файла?
T>>>>После препроцессора он становится одним файлом.
CC>>> Нет!
CC>>>Если у тебя есть 1.cpp и 2.сpp то после препроцессора у тебя все равно 2 файла. И тот самый разбор исходника будет происходить уже после препроцессора.
T>>Если у меня 1.cc, включающий в себя 2.h, то после препроцессора он станет 1.i и будет включать в себя оба.

CC>Еще раз: Где ты видел проект из одного файла? Из одного .cpp файла?

CC>Такой сценарий никто даже и не рассматривает.

Вот, смотри. У нас есть объём всего проекта, V. Количество информации в заголовочных файлах этого проекта будет kV, k<1 и зависит от среднего стиля кодирования (количества взаимозависимостей). Средний *.cc будет использовать только определённый процент q от общего количества всех заголовочных файлов, итого, к .cc (который имеет размер v не зависящий от размера проекта) добавился код. Общий объём одного .cc и всех нужных ему файлов составит v+kV. Сложность обработки будет O(V), если ты понимаешь, что такое сложность.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: а как же Larrabee?
От: CreatorCray  
Дата: 22.07.09 12:46
Оценка:
Здравствуйте, thesz, Вы писали:

"Ты не зюзюкай, ты рукой махни" (С)

Сколько LOC у вас приходится на .h и на .cpp файлы?
Или у вас в .h шаблоны на шаблонах?
Про PCH опять таки забыли.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[15]: а как же Larrabee?
От: thesz Россия http://thesz.livejournal.com
Дата: 22.07.09 12:59
Оценка: :)
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, thesz, Вы писали:


CC>"Ты не зюзюкай, ты рукой махни" (С)

CC>Сколько LOC у вас приходится на .h и на .cpp файлы?

Я на плюсах не пишу. Под рукой у меня исходников нет.

CC>Или у вас в .h шаблоны на шаблонах?


Достаточно классов с отдельными методами.

CC>Про PCH опять таки забыли.


И что, результат чтения PCH нам уже не надо хранить?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Закат GPU?
От: thesz Россия http://thesz.livejournal.com
Дата: 22.07.09 13:51
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, thesz, Вы писали:


T>>SHA-1 большого сообщения.

WH>Опять таки если не зацикливаться на конкретном алгоритме то см md6.

Вот ещё возражение против MD6: бОльший расход памяти по сравнению с обычными подсчётами контрольных сумм. У MD4/5/SHA он O(1), у MD6 он O(log(размер_сообщения)).

Не для всякого применения подойдёт, поскольку может не влезть в некоторые микроконтроллеры.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[10]: Закат GPU?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 23.07.09 06:36
Оценка:
Здравствуйте, thesz, Вы писали:

T>>>SHA-1 большого сообщения.

WH>>Опять таки если не зацикливаться на конкретном алгоритме то см md6.

T>Вот ещё возражение против MD6: бОльший расход памяти по сравнению с обычными подсчётами контрольных сумм. У MD4/5/SHA он O(1), у MD6 он O(log(размер_сообщения)).


Это не единственный вариант. Цитирую каноническое описание Ривеста (оно в википедии первой ссылкой):

Since the standard MD6 mode requires storage proportional to the height of the tree, there is an alternative low-storage variant mode obtained by adjusting the optional parameter L that decreases both the storage requirements and the parallelizability; setting L = 0 results in a Merkle-Damgard-like sequential mode of operation.


T>Не для всякого применения подойдёт, поскольку может не влезть в некоторые микроконтроллеры.


Для микроконтроллеров сделают реализацию при L == 0 и память будет требоваться линейно.
The God is real, unless declared integer.
Re[16]: а как же Larrabee?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 23.07.09 06:55
Оценка:
Здравствуйте, thesz, Вы писали:

CC>>Про PCH опять таки забыли.

T>И что, результат чтения PCH нам уже не надо хранить? ;)

Надо. Но в тех случаях, когда (по твоим формулам) V станет заметным (сотни, тысячи и больше), сработают два фактора:
1) (менее существенный) k за счёт предкомпиляции уменьшится на порядок или больше. в результате, омикрон-оценки потеряют смысл — они хороши только на асимптотике, с противоположного конца константы оказывают больше влияния.
2) (более существенный) сложность проекта будет заставлять разбивать его на отдельные части (библиотеки, плагины...), в результате получится что-то вроде v + k * V' + k * W, где V' — сколько осталось заголовков на часть, W — общих заголовков используемых других частей.

Практические способности человека заставляют поддерживать V на низком уровне (реально — не более сотни включаемых файлов среднего размера, 10-50K), иначе приближается путаница между включениями; её можно отодвинуть жесточайшей дисциплиной, но не устранить совсем.
The God is real, unless declared integer.
Re[11]: Закат GPU?
От: thesz Россия http://thesz.livejournal.com
Дата: 23.07.09 06:59
Оценка:
Здравствуйте, netch80, Вы писали:

N>Здравствуйте, thesz, Вы писали:


N>Это не единственный вариант. Цитирую каноническое описание Ривеста (оно в википедии первой ссылкой):


N>

N>Since the standard MD6 mode requires storage proportional to the height of the tree, there is an alternative low-storage variant mode obtained by adjusting the optional parameter L that decreases both the storage requirements and the parallelizability; setting L = 0 results in a Merkle-Damgard-like sequential mode of operation.


T>>Не для всякого применения подойдёт, поскольку может не влезть в некоторые микроконтроллеры.

N>Для микроконтроллеров сделают реализацию при L == 0 и память будет требоваться линейно.

То есть, микроконтроллеры будут понимать не все варианты входных потоков. Это усложняет жизнь, хотя и немного.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[12]: Закат GPU?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 23.07.09 07:00
Оценка:
Здравствуйте, thesz, Вы писали:

T>>>Не для всякого применения подойдёт, поскольку может не влезть в некоторые микроконтроллеры.

N>>Для микроконтроллеров сделают реализацию при L == 0 и память будет требоваться линейно.
T>То есть, микроконтроллеры будут понимать не все варианты входных потоков. Это усложняет жизнь, хотя и немного.

Этой реплики я не понял. Того, что они будут понимать входной поток данных как последовательность байт, вполне достаточно для вычисления хэша, пусть и чуть медленнее. Или ты о чём?
The God is real, unless declared integer.
Re[13]: Закат GPU?
От: thesz Россия http://thesz.livejournal.com
Дата: 23.07.09 08:40
Оценка:
Здравствуйте, netch80, Вы писали:

N>Здравствуйте, thesz, Вы писали:


T>>>>Не для всякого применения подойдёт, поскольку может не влезть в некоторые микроконтроллеры.

N>>>Для микроконтроллеров сделают реализацию при L == 0 и память будет требоваться линейно.
T>>То есть, микроконтроллеры будут понимать не все варианты входных потоков. Это усложняет жизнь, хотя и немного.

N>Этой реплики я не понял. Того, что они будут понимать входной поток данных как последовательность байт, вполне достаточно для вычисления хэша, пусть и чуть медленнее. Или ты о чём?


L — это параметр алгоритма. Вычисления по MD6-256-L0 не равны вычислениям MD6-256-L64.

У нас на одной из работ был криптомодуль собственной разработки на аналоге 8051. MD5 он умел, программной памяти хватало, а вот MD6-256-L64 он бы не смог.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: Закат GPU?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 23.07.09 10:14
Оценка:
Здравствуйте, thesz, Вы писали:

N>>>>Для микроконтроллеров сделают реализацию при L == 0 и память будет требоваться линейно.

T>>>То есть, микроконтроллеры будут понимать не все варианты входных потоков. Это усложняет жизнь, хотя и немного.
N>>Этой реплики я не понял. Того, что они будут понимать входной поток данных как последовательность байт, вполне достаточно для вычисления хэша, пусть и чуть медленнее. Или ты о чём?
T>L — это параметр алгоритма. Вычисления по MD6-256-L0 не равны вычислениям MD6-256-L64.

Таки да — есть подтверждение тому в тексте документа.

T>У нас на одной из работ был криптомодуль собственной разработки на аналоге 8051. MD5 он умел, программной памяти хватало, а вот MD6-256-L64 он бы не смог.


Ну, 8051 по нынешним меркам уже за гранью добра и зла.:) Хотя местами есть звери и послабее, но это уже в ситуации, где нормальную микруху вообще не поставишь.
The God is real, unless declared integer.
Re[15]: Закат GPU?
От: thesz Россия http://thesz.livejournal.com
Дата: 23.07.09 11:38
Оценка:
Здравствуйте, netch80, Вы писали:

N>Здравствуйте, thesz, Вы писали:


N>>>>>Для микроконтроллеров сделают реализацию при L == 0 и память будет требоваться линейно.

T>>>>То есть, микроконтроллеры будут понимать не все варианты входных потоков. Это усложняет жизнь, хотя и немного.
N>>>Этой реплики я не понял. Того, что они будут понимать входной поток данных как последовательность байт, вполне достаточно для вычисления хэша, пусть и чуть медленнее. Или ты о чём?
T>>L — это параметр алгоритма. Вычисления по MD6-256-L0 не равны вычислениям MD6-256-L64.

N>Таки да — есть подтверждение тому в тексте документа.


Да это следует из обычной логики. Равенство a+(b+(c+d)) и ((a+b)+(c+d)) ослабляет криптостойкость функция сжатия, как я понимаю.

T>>У нас на одной из работ был криптомодуль собственной разработки на аналоге 8051. MD5 он умел, программной памяти хватало, а вот MD6-256-L64 он бы не смог.


N>Ну, 8051 по нынешним меркам уже за гранью добра и зла. Хотя местами есть звери и послабее, но это уже в ситуации, где нормальную микруху вообще не поставишь.


Заметная часть AVR, MicroChip, ADSP21xx.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[4]: dmitriy_k
От: dmitriy_k  
Дата: 03.08.09 08:56
Оценка: -1
Здравствуйте, thesz, Вы писали:

T>>>На компиляции с помощью одного ядра современный Core 2 будет рвать Лараби, как Тузик грелку.

M>>Это очевидно, но в том то и дело что ядер будет много.
T>Если у нас 90% (обработка) может быть выполнено произвольно параллельно, а 10% (анализ) не может быть выполнено параллельно, то производительность упрётся в эти 10%. Тогда-то и вылезет ILP и out-of-order.
А вот тут могут уже всплыть алогоритмы которые мягко говоря неоэффиктивны последовательно, но если у нас _много_ процессоров — то могут дать лучщий эффект — не смотря на то что общие количество процессоро-часов — больше
dmitriy_k
Re[5]: dmitriy_k
От: thesz Россия http://thesz.livejournal.com
Дата: 03.08.09 12:42
Оценка:
Здравствуйте, dmitriy_k, Вы писали:

_>Здравствуйте, thesz, Вы писали:


T>>>>На компиляции с помощью одного ядра современный Core 2 будет рвать Лараби, как Тузик грелку.

M>>>Это очевидно, но в том то и дело что ядер будет много.
T>>Если у нас 90% (обработка) может быть выполнено произвольно параллельно, а 10% (анализ) не может быть выполнено параллельно, то производительность упрётся в эти 10%. Тогда-то и вылезет ILP и out-of-order.
_>А вот тут могут уже всплыть алогоритмы которые мягко говоря неоэффиктивны последовательно, но если у нас _много_ процессоров — то могут дать лучщий эффект — не смотря на то что общие количество процессоро-часов — больше

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

Потрудись в следующий раз читать то, на что отвечаешь.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[10]: а как же Larrabee?
От: Sinclair Россия https://github.com/evilguest/
Дата: 04.08.09 02:58
Оценка:
Здравствуйте, thesz, Вы писали:
T>Как обработка нескольких файлов сможет ускорить нам компиляцию нашего большого файла?
Очень просто. Типичный C++ исходник — это 95% заголовки, 5% собственно исходник.
В итоге, парсинг уникального для проекта кода занимает смешное, по сравнению с библиотечными заголовками, время. В частности, поэтому системы, в которых нет заголовков (pascal, java, C#) рвут плюсы по скорости компиляции в кровавые ошмётки.

Поэтому первая же идея, которая приходит в голову — скормить на вход компилятору несколько .cpp файлов — скорее всего, в них будут использоваться более-менее одни и те же хидеры, и на их повторном разборе можно очень сильно сэкономить. Вторая идея, которая приходит в голову — это реализовать предкомпилированные хидеры, но там есть несколько нюансов, из-за которых это сделать сложнее и дороже, чем повторное использование результатов разбора.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: Закат GPU?
От: Lorenzo_LAMAS  
Дата: 05.08.09 09:08
Оценка:
GN>Да! Где же Duke Nukem Forever???

Пару месяцев назад окончательно R.I.P. вроде как.
Of course, the code must be complete enough to compile and link.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.