На международном симпозиуме параллельных и распределенных вычислений будет представлена (http://news.ncsu.edu/releases/wmssolihinthreads/) новая техника (http://www.ece.ncsu.edu/arpers/Papers/MMT_IPDPS10.pdf) организации управления памятью, позволяющая добиться заметного повышения производительности стандартных приложений при их работе на многоядерных процессорах. При этом повышение производительности заметно в программах для которых в обычных условиях достаточно трудно распараллелить операции, например, в браузерах и текстовых процессорах.Суть техники в выделении функций динамического распределения памяти в отдельный поток MMT (Memory Management Thread), работающий параллельно и не блокирующий работу основного приложения. В настоящий момент разработчиками подготовлен прототип динамической библиотеки, подменяющей стандартные функции распределения памяти (malloc, free) и не требующей модификации приложения.
Измерение производительности различных программ, в зависимости от...
URL: http://news.ncsu.edu/releases/wmssolihinthreads/
Новость: http://www.opennet.ru/opennews/art.shtml?num=26107
это будет в ядре?
ядро то тут причом?
На какой ОС? На виндовс?)
Да на любой.
>На какой ОС? На виндовс?)От них дождешься =)
Там если явно самому в своей программе накодить.А на любой нормальной ОС, где можно подсовывать разные реализации malloc, возможно все перевести на ту реализацию, которая больше нравится.
> Там если явно самому в своей программе накодить.Да, как бы не сверх проблема. На C++ (в первом приближении!), пишете обертку и перегружаете глобальный оператор new. STL, по дефолту, использует глобальный оператор, но позволяет указать одним из параметров шаблона свой аллокатор (еще один путь)...
Ну а "чисто" на C, под вындос вряд ли сейчас кто пишет, впрочем, там можно по шаманить с опциями линкера, попытаться заставить его слинковать нужную либу и использовать именно нужную ф-цию. Когда-то давно читал, что new из библиотек VS6 пользует malloc (понятия не имею, как сейчас), т.ч. данный путь может оказаться универсальным.Ну а шарписты, видимо, в пролете...
>> Там если явно самому в своей программе накодить.
>
>Да, как бы не сверх проблема.Согласен.
Свой код - своя вольница.Но я про то, что в нормальных ОС можно задавать реализацию malloc для всех программ.
Я имею в виду для всех уже скомпиленных программ.
Ну кроме статически скомпиленных)А попробуйте такой же трюк проделать в винде.
Я так понимаю, там и статическая компиляция практикуется куда чаще.
>Но я про то, что в нормальных ОС можно задавать реализацию malloc
>для всех программ.
>Я имею в виду для всех уже скомпиленных программ.
>Ну кроме статически скомпиленных)Ну, согласно закону Мерфи -- "Если высказывание может быть не понято, непременно найдется тот, кто его не поймет!" ((С) как-то так :-), ну а я человек маленький и законопослушный... :-)
Вобщем, извиняюсь, не так понял.
new то тут причем?
вызвал я скажем strdup-где тут new? все идет от malloc и собратьев, даже new!
>new то тут причем?
>вызвал я скажем strdup-где тут new?Я же написал -- "в первом приближении", я же не предлагал, как нихрена не делая, поиметь кучу выгод, так только МММ в свое время делала, где она теперь, Вы (думаю) в курсе...
Вместо char*, пользуйте std::string, там используется new, или, вообще, свой аллокатор указать можно...>все идет от malloc и собратьев,
>даже new!"Анатомия C Run-Time, или Как сделать программу немного меньшего размера" ( http://www.rsdn.ru/article/cpp/crt.xml ):
"Обычно C/C++-программа опирается на мощную поддержку С Run-Time Library - библиотека времени исполнения языка C, далее - CRT; более редкое название - RTL (Run-Time Library). Многим функциям этой библиотеки для правильной работы требуется дополнительная инициализация (CRT startup code). В частности, для вывода текста на консоль с помощью функции printf необходимо, чтобы дескриптор стандартного вывода stdout был предварительно связан с устройством вывода операционной системы (например, стандартным выводом и консолью Win32). То же самое справедливо и для функций работы с кучей - таких, как malloc для C и оператора new для C++.
...
А сам код CRT находится в динамической библиотеке MSVCRT.DLL в системном каталоге Windows. Эта многопоточная библиотека используется и некоторыми бесплатными компиляторами C/C++ для Windows, например, MinGW."Пишите свою dll, где делаете форвардинг всех ф-ций на оригинал, кроме malloc/free, ну и еще чего-нить, навроде realloc... При линковке линкуете со своей либой.
По мойму, не так уж и офигенно сложно...
Интересно в PDF-е и в новости написано про прототип динамической библиотеки! Кто нибудь видел link на эту библиотеку?
исходники в студию!
Искал исходники, но пока не нашел. Есть только пара презентаций:
1. http://www4.ncsu.edu/~dtiwari2/Papers/ESPIPP_Presen_WACI_ASP...
2. http://www4.ncsu.edu/~dtiwari2/Papers/MMT_MEDEA_PRESENTATION...
Это будет хорошо дополнять ZFS prefetch и другие техники файлового кэширования. Правда, при этом, оперативка будет загружена на 100% (однако, память на то и покупается, чтобы использоваться не на 20%, а на полную свою длину).
Да, жависты любят эту ересь нести. Только память всегда гораздо лучше пустить под дисковые кэши, чем под забитие бесполезным мусором, как в случае с java.
Главное чтобы не запатентовали.
Чето я не понял за счет чего ускорение. malloc все равно будет ждать завершения выделения памяти в этом потоке
> Чето я не понял за счет чего ускорение. malloc все равно будет ждать завершения выделения памяти в этом потокеАналогично, какая разница в каком потоке выполняется код malloc, если ему всё равно нужно блокироваться от конкурентных запросов?
По сути, для начал использования памяти, достаточно получить указатель
на начало сегмента.int A[ULONG_LONG_MAX];
int *prt;if ( (pid = fork()) == 0 ) {
ptr = super_malloc(ULONG_LONG_MAX);
exit 0;
}
if ( pid > 0 ) {memcpy(ptr, A, ULONG_LONG_MAX * sizeof (int));
}
......
В общем, пока второй делает маллоку, первый начинает её юзать.
Если ядро дробит память на страницы, то по мере доступности всего
запрашиваемого размера, можно ставить мутексы, спинлоки.
Но тогда уже memcpy должен отрабатывать ожидание в очереди на выделение.
Начинаю патентовать... :)
Заголвок должен быть "Новая техника управления памятью позволяет ускорить плохо распараллеливаемые программы с интенсивным выделением и освобождением памяти на 19%. А то можно подумать, что изобрели какой-то мегаускорятель программ...
Да все просто, делаете отдельный обьект , в который кидаете запросы на выделение памяти.
Выполнение происходит в отдельном потоке, вот вам и прирост. Поидее так и надо было делать изначально.
Ага. А как узнать насколько заранее нужно послать запрос на выделение памяти, что бы он успел ее выделить к тому моменту, когда она понадобится?
полный бред! поток, которому необходима память всё равно будет ожидать окончания выделения памяти другим потоком и не продолжится, пока память не будет выделена
Поток с выделением будет выполнятся на другом ядре(процессоре) ,
а поток из которого был запрос на выделение будет ждать , не занимая ядро(процессор).
>Поток с выделением будет выполнятся на другом ядре(процессоре) ,
>а поток из которого был запрос на выделение будет ждать , не
>занимая ядро(процессор).И откуда тут выигрыш по сравнению с обычным подходом?
потому что запрос будет неблокирующий
Специально для особо одарённых танкистов: http://www.ece.ncsu.edu/arpers/Papers/MMT_IPDPS10.pdfПростейший подход к многопоточному выделению/освобождению памяти приводит к замедлению выделения/освобождения памяти в несколько раз. В представленном решении приведены техники по преодолению замедляющих факторов.
Моё мнение: большинство из этих техник, а также более продвинутые техники, способны дать выигрыш гораздо больший при организации программы без многопоточности.
>> потому что запрос будет неблокирующийв пдфке вроде говорят, что интерфейс malloc/free они не ломали. Откуда возьмется неблокирующий malloc?
а вы внимательней почитайте
Очевидно, что некоторое приближение к неблокирующему malloc-у можно получить только посредством preallocation и организации нескольких "маленьких куч" - по одной на поток; или если потоков много больше чем процессорных ядер - то можно организовать несколько "коммунальных" куч с диспетчеризацией malloc-ов по правилу "round robin". Получается почти-неблокирующий-malloc. Коллеги в tbsoft когда-то экспериментировали с такими аллокаторами и достигли заметных успехов.
> потому что запрос будет неблокирующийРешение предлагается как drop-in замена обычному malloc. Вопрос - что вернет ваш "неблокирующий malloc"?
>> потому что запрос будет неблокирующий
>
>Решение предлагается как drop-in замена обычному malloc. Вопрос - что вернет ваш
>"неблокирующий malloc"?указатель на начало сегмента памяти.
:)
и когда он выдалять будет и в каком порядке?если он к моменту возвращения еще не все выделил - то мы ведь можем не с начала заюзать сегмент, а с конца или с середины.
>и когда он выделять будет и в каком порядке?В пространстве пользователя это должны быть линейные адреса.
А как их сегментирует ядро это уже второй вопрос.>
>если он к моменту возвращения еще не все выделил - то мы
>ведь можем не с начала заюзать сегмент, а с конца или
>с середины.Живой, классический пример, - поезд рельсоукладчик, сам кладёт - сам едет,
или даже танк, сам за собой дорогу тащит. :)В С99 сделали же динамические массивы ...
for ( i = 0; i < LIMIT; i++) {
int A[i] = i+i;
}
в с нет ниаких сегментов памяти
>в с нет ниаких сегментов памятиЕщё один... иди всю Википедию выучи или хотя бы Ожегова, тогда возвращайся.
И причем тут язык...
---
Сегмент (от лат. segmentum — отрезок, полоса, от лат. seco — режу, рассекаю) — часть чего-либо.* В математике
o Сегмент, или отрезок — множество точек прямой, включающее свои концы.
o Сегмент (геометрия) — плоская фигура, заключённая между кривой и её хордой. Как частный случай: круговой сегмент.
o Сегмент (стереометрия) — часть тела, ограниченная плоскостью и отсекаемой ею частью поверхности. Как частный случай: шаровой сегмент.
o Сегмент (математический анализ) — множество всех вещественных чисел, удовлетворяющих неравенствам a≤x≤b, где a<b.
o Полусегмент — множество всех вещественных чисел x, удовлетворяющих неравенствам a≤x<b {или a<x≤b}
* Сегмент памяти — в информатике одна из единиц адрсесации в некоторых моделях памяти.
* Сегмент (биология) — части тела, похожие по строению и расположенные последовательно вдоль продольной оси тела.
* Сегмент (ботаника) — часть листовой пластинки рассечённого листа.
* Сегмент сети (в информатике) — узлы сети, подключённые к одному маршрутизирующему устройству (коммутатор, маршрутизатор) и работающие по одному физическому протоколу.
* Сегмент рынка (в экономике)
* Семисегментный индикатор в электронике.
И во что это выльется? Я так могу sbrk вместо маллока использовать.
в то, что можно начать использовать до конца не выделенную память. По аналогии с CoW
С выделением памяти действительно непонятно, но вот free() должно выноситься в отдельный тред без проблем.
Поддерживаю.
Ну это уже, наверно, во всех сборщиках мусора реализовано.
ну пускай вот в glibc добавят, чтож...
Спорно, т.к. приведенный метод ускорения будет в каких-то случаях немного ускорять, а в каких-то очень замедлять выделение/освобождение пямяти.
Нда?! И в каких он будет замедлять?
>Нда?! И в каких он будет замедлять?Если не использовать preallocation, то во всех. А если использовать, то оно будет жрать лишнюю память. Лучше просто головой подумать, перед тем как в inner loop маллочить четыре байта.
И хорошо еще, если ядро свободное найдется на работу потока выделения/освобождения памяти. Потому как если не найдется, то, наверно:
1) память в лучшем случае будет освобождаться с задержкой, что грозит либо большим перерасходом памяти, либо выделение памяти станет нереально медленным.
2) выделение памяти во многих случаях станет оооччень медленным по многим причинам.
>И хорошо еще, если ядро свободное найдется на работу потока выделения/освобождения памяти.
>Потому как если не найдется, то, наверно:
>1) память в лучшем случае будет освобождаться с задержкой, что грозит либо
>большим перерасходом памяти, либо выделение памяти станет нереально медленным.
>2) выделение памяти во многих случаях станет оооччень медленным по многим причинам.
>Могу предположить, что все ядра, кроме первого, обычно загружены чуть меньше.
Исходя из той же идеи, что далеко не все программы ещё true smp =)
Ну и сам по загрузке ядер вижу такую картину.
Что на сервере, что на десктопе.И можно сделать вывод, что такая фишка с выделением памяти будет эффективна до тех пор, пока не научатся равномерно эффективно загружать все ядра.
Т.е. она будет эффективна ещё очень долго)
>>И хорошо еще, если ядро свободное найдется на работу потока выделения/освобождения памяти.
>>Потому как если не найдется, то, наверно:
>>1) память в лучшем случае будет освобождаться с задержкой, что грозит либо
>>большим перерасходом памяти, либо выделение памяти станет нереально медленным.
>>2) выделение памяти во многих случаях станет оооччень медленным по многим причинам.
>>
>
>Могу предположить, что все ядра, кроме первого, обычно загружены чуть меньше.
>Исходя из той же идеи, что далеко не все программы ещё true
>smp =)Предлагаешь замутить sleep(), wait(), delay() и т.п., c поддержкой SMP
Если процесс спит, так пущай спит на всех процах сразу?
>Предлагаешь замутить sleep(), wait(), delay() и т.п., c поддержкой SMP
>Если процесс спит, так пущай спит на всех процах сразу?=)
Я просто указываю на то, что нет true smp.
Да и не думаю, что будет.
Из этого и исходит мое предположение, что ещё долгое время первое ядро будет более нагружено, чем остальные.
Особенно на десктопе.
вот мой десктоп (коре квад) секундное измерение:
cpu 0 usage: 0%
cpu 1 usage: 2%
cpu 2 usage: 28%
cpu 3 usage: 7%[dv@dvpc ~]$ uname -r
2.6.31.12-server-3mnb
Хотя средняя загрузка процессора не велика, но это не означает, что на каждом участке веремени есть хотя бы одно свободное ядро. Т.е. при небольшом количестве ядер ситуация, когда в конкретный момент времени загружены все ядра велика, что означает огромный лаг (по меркам процессорного времени) при выделении и освобождении памяти, т.е. пауза до тех пор, пока планировщик потоков не даст время потоку выделения/освобождения памяти, а потом, пока планировщик потоков не даст время потоку, которому требовалась память. В Win у вас может уйти на такую операцию 15+15=30 мс (нехилый такой лаг). А если операция выделения/освобождения памяти слишком частые (что говорит лишь о кривой архитектуре программы), то лаги могут быть не только наблюдаемые визуально, но и нехило досаждающие. Не думаю, что вам будет приятно листать страницу в браузере во время упаковки каких-то данных многопоточным 7zip'ом.Ну, а если у вас процессор свободен, то никакие ускорения malloc вам не нужны. Тем более 19% для malloc/free, о которых идет речь в данной новости, т.к. в лучшем случае в конечном счете вы получите пару процентов улучшения общей производительности, и то не факт.
>Хотя средняя загрузка процессора не велика, но это не означает, что на
>каждом участке веремени есть хотя бы одно свободное ядро. Т.е. при
>небольшом количестве ядер ситуация, когда в конкретный момент времени загружены все
>ядра велика, что означает огромный лаг (по меркам процессорного времени) при
>выделении и освобождении памяти, т.е. пауза до тех пор, пока планировщик
>потоков не даст время потоку выделения/освобождения памяти, а потом, пока планировщик
>потоков не даст время потоку, которому требовалась память. В Win у
>вас может уйти на такую операцию 15+15=30 мс (нехилый такой лаг).Если переход с текущей реализации на предлагаемую может вызвать такие лаги, то напрашивается вопрос - а в текущей реализации нет таких лагов?
>[оверквотинг удален]
>>каждом участке веремени есть хотя бы одно свободное ядро. Т.е. при
>>небольшом количестве ядер ситуация, когда в конкретный момент времени загружены все
>>ядра велика, что означает огромный лаг (по меркам процессорного времени) при
>>выделении и освобождении памяти, т.е. пауза до тех пор, пока планировщик
>>потоков не даст время потоку выделения/освобождения памяти, а потом, пока планировщик
>>потоков не даст время потоку, которому требовалась память. В Win у
>>вас может уйти на такую операцию 15+15=30 мс (нехилый такой лаг).
>
>Если переход с текущей реализации на предлагаемую может вызвать такие лаги, то
>напрашивается вопрос - а в текущей реализации нет таких лагов?В текущей реализации таких лагов нет, т.к. память выделяется/освобождается в том же потоке, которому она требуется, а описанная возможная ситуация (когда поток выделения/освобождения памяти имеет наивысший приоритет в системе, и других потоков с таким приоритетом в системе нет) возникает исключительно из-за многопоточности. Сейчас ядро любой ОС учитывает ситуации одновременного обращения к нему нескольких потоков, которые требуют выделить/освободить для них память или другие объекты ядра.
>В текущей реализации таких лагов нет, т.к. память выделяется/освобождается в том же
>потоке, которому она требуется, а описанная возможная ситуация (когда поток выделения/освобождения
>памяти имеет наивысший приоритет в системе, и других потоков с таким
>приоритетом в системе нет) возникает исключительно из-за многопоточности. Сейчас ядро любой
>ОС учитывает ситуации одновременного обращения к нему нескольких потоков, которые требуют
>выделить/освободить для них память или другие объекты ядра.Т.е. лаги могут быть, если много программ одновременно потребуют память?
Кстати, в винде такое врядли будет реализовываться, так что на её лаги пофиг)
> Using the new technique, when a memory-management function needs to be performed, “the computational thread notifies the memory-management thread – effectively telling it to allocate data storage and to notify the computational thread of where the storage space is located,” says Devesh Tiwari, a Ph.D. student at NC State and lead author of the paper. “By the same token, when the computational thread no longer needs certain data, it informs the memory-management thread that the relevant storage space can be freed.”Бгыгы, и что, computational thread не заблокирована на это время? Бред какой-то.
>Бгыгы, и что, computational thread не заблокирована на это время? Бред какой-то. >Это _академический опен-сорс такой. Диссертация про коня в вакууме, потом, если повезёт, закрытые тесты-реализации-бенчмарки (как щас вижу - на win* или *BSD) с ещё более громкими заголовками, потом продажа венчурным капиталистам =>профит. А ускоряет оно маллок в глибц, не ускоряет... __Так_и_не_обещал_же_никто.__
не исключено
>Это _академический опен-сорс такой. Диссертация про коня в вакууме, потом, если повезёт, закрытые тесты-реализации-бенчмарки (как щас вижу - на win* или *BSD) с ещё более громкими заголовками, потом продажа венчурным капиталистам =>профит. А ускоряет оно маллок в глибц, не ускоряет... __Так_и_не_обещал_же_никто.__На win* или *nux. На BSD как раз самых эффективный аллокатор из существующих.
>>Это _академический опен-сорс такой
>>закрытые тесты-реализации-бенчмарки (как щас вижу - на win* или *BSD)
>>__Так_и_не_обещал_же_никто.__
>На win* или *nux. На BSD как раз самых эффективный аллокатор из существующих.Так-так!? Что зироты BSD имеют сказать за борьбу с академ-пен-сорсом и мировой иссследовательскай наукай?!
http://www.google.ru/search?q=tcmalloc
чем не понравился им?
>http://www.google.ru/search?q=tcmalloc
>чем не понравился им?Возможно, лицензией.
А может просто, своя велосипеда ближе к телу)
>http://www.google.ru/search?q=tcmalloc
>чем не понравился им?О, это такая клёвая хрень...
# svn checkout http://google-perftools.googlecode.com/svn/trunk/ google-perftools
# cd google-perftools
# ./autogen.sh
# ./configure
# make
# make check
...
...
======================================
8 of 25 tests failed
Please report to opensource@google.com
======================================
make[1]: *** [check-TESTS] Ошибка 1
make[1]: Leaving directory `/usr/src/google-perftools'
make: *** [check-am] Ошибка 2
# LD_PRELOAD=./.libs/libtcmalloc.so firefox
Ошибка сегментирования
звучит заманчиво
но не поверю пока сам не попробую
Прогресс такой прогресс. Сначала напридумывают языков с динамической типизацией, сборщиками мусора, безграничными строками. Ересь. Для критических приложений есть С, каждый поток со своим стеком, стоимость выделения минимальна. Размером управляется железом. Да, может не так оптимально, но память физически жрётся приемлемо. malloc/free в хорошо спроектированной программе нужны в начале и конце обработки. Всё остальное от лукавого.