Продолжение: mozilla/firefox и аллокатор из openbsd

> Так ведь даже опционально его не включить -- он на BSD-лицензии.

смотря какая BSD, если как в FreeBSD, не надо перечислять кучу людей,
которые писали код, то она совместима с GPL.

>Я всё время думал, почему бы не сделать так же, как openbsd'шники, но >выделять/освобождать память

может сначала узнать что такое медленее/быстрее померить, а потом если действительно медленно, а не отставание на 1% что-то менять?

Сейчас сделал простейший замер на время выделения и освобождения страницы 4096 байт, для mmap/munmap и sbrk/madvise получаются идентичные результаты. А именно:

andrei@superblin:~/prog/alloc$ ./mmap-sbrk
time (cycles): mmap -- 3096.6, munmap -- 1844.98
time (cycles): sbrk -- 2954.61, madvise -- 1239.96

Программа:

#include <sys/mman.h>
#include <asm/timex.h>
#include <asm/msr.h>

#define MMAP(size) \
mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
-1, (off_t)0)
#define SIZE 4096
#define iter 10000

int main()
{
cycles_t c1,c2,t_mmap=0,t_munmap=0,t_sbrk=0,t_madvise=0;
double *ptr;
int i;

for(i=1;i<=iter;i++)
{
rdtscll(c1);
ptr=MMAP(SIZE);
ptr[100]=1.;
rdtscll(c2);
t_mmap+=c2-c1;

rdtscll(c1);
munmap(ptr,SIZE);
rdtscll(c2);
t_munmap+=c2-c1;

rdtscll(c1);
ptr=sbrk(SIZE);
ptr[100]=1.;
rdtscll(c2);
t_sbrk+=c2-c1;

rdtscll(c1);
madvise(ptr,SIZE,MADV_DONTNEED);
rdtscll(c2);
t_madvise+=c2-c1;
}

printf("time (cycles): mmap -- %g, munmap -- %g\n",(double)t_mmap/iter,(double)t_munmap/iter);
printf("time (cycles): sbrk -- %g, madvise -- %g\n",(double)t_sbrk/iter,(double)t_madvise/iter);

return 0;
}

Лучше так:

#include <stdio.h>
#include <unistd.h>
#include <sys/mman.h>
#include <asm/timex.h>
#include <asm/msr.h>

#define MMAP(size) \
mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
-1, (off_t)0)
#define PS 4096
#define SIZE (PS*NP)
#define iter 100000

int main(int argc, char**argv)
{
int NP;
if(argc!=2)
NP=1;
else
NP=atoi(argv[1]);
cycles_t c1,c2,t_mmap=0,t_munmap=0,t_sbrk=0,t_madvise=0;
char *ptr;
int i,k;

printf("results of creating region with size %d*%d:\n",PS,NP);
for(i=1;i<=iter;i++)
{
rdtscll(c1);
ptr=MMAP(SIZE);
for(k=0;k<NP;k++)
ptr[k*PS+1]='1';
rdtscll(c2);
t_mmap+=c2-c1;

rdtscll(c1);
munmap(ptr,SIZE);
rdtscll(c2);
t_munmap+=c2-c1;

rdtscll(c1);
ptr=sbrk(SIZE);
for(k=0;k<NP;k++)
ptr[k*PS+1]='1';
rdtscll(c2);
t_sbrk+=c2-c1;

rdtscll(c1);
madvise(ptr,SIZE,MADV_DONTNEED);
rdtscll(c2);
t_madvise+=c2-c1;
sbrk(-SIZE);

}

printf("time (cycles): mmap -- %g, munmap -- %g\n",(double)t_mmap/iter,(double)t_munmap/iter);
printf("time (cycles): sbrk -- %g, madvise -- %g\n",(double)t_sbrk/iter,(double)t_madvise/iter);

return 0;

И получаются результаты:

andrei@superblin:~/prog/alloc$ ./mmap-sbrk 1
results of creating region with size 4096*1:
time (cycles): mmap -- 2922.05, munmap -- 1862.85
time (cycles): sbrk -- 3235.74, madvise -- 1242.55
andrei@superblin:~/prog/alloc$ ./mmap-sbrk 2
results of creating region with size 4096*2:
time (cycles): mmap -- 5211.34, munmap -- 2322.15
time (cycles): sbrk -- 5545.87, madvise -- 1643.61
andrei@superblin:~/prog/alloc$ ./mmap-sbrk 4
results of creating region with size 4096*4:
time (cycles): mmap -- 9857.77, munmap -- 3105.45
time (cycles): sbrk -- 10106, madvise -- 2480.98
andrei@superblin:~/prog/alloc$ ./mmap-sbrk 8
results of creating region with size 4096*8:
time (cycles): mmap -- 18821.8, munmap -- 4883.43
time (cycles): sbrk -- 19305.9, madvise -- 4287.83
andrei@superblin:~/prog/alloc$ ./mmap-sbrk 16
results of creating region with size 4096*16:
time (cycles): mmap -- 38981.6, munmap -- 7929.79
time (cycles): sbrk -- 39207.2, madvise -- 7232.62
andrei@superblin:~/prog/alloc$ ./mmap-sbrk 32
results of creating region with size 4096*32:
time (cycles): mmap -- 78791.5, munmap -- 14373.3
time (cycles): sbrk -- 79155.4, madvise -- 13782.5

Т.е. (в данном случае) mmap и sbrk с одинаковой скоростью выделяют память.

sbrk даже чуть медленнее, чем mmap!

Уря, оставил на ночь огнелиса а он практически ничего и не съел ;-)

Такое наблюдение, _не мое_.

На машине c 64M RAM, linux 2.4.*, X.org 6.8 (?), IceWM:

Firefox 1.0.* c openbsd-malloc пользовали ~2 суток с перерывами: открывали/закрывали до ~30 вкладок (форум на Invision power board), писали сообщения, редактировали, сливали темы, открывали посторонние ссылки, короче чистили форум. Ощутимый своп начался к концу вторых суток (RSS ~ 35M при VSZ ~ 50M вроде как) после просмотра "плохо написанного сайта". До этого момента было комфортно.

По субъективным оценкам того же человека, Firefox 1.0.* под Windows 2000 на _той же_ машине забивает в том же режиме память через несколько часов. Тормоза начинаются после одноразового открывания тех же 20-30 вкладок, даже если закрыть потом.

Все субъективно и с чужих слов.

Реально, эта библиотека рулит, терминал теперь отдаёт память при закрытии табов, раньше еле по 3 метра с таба возвращал!

Чтобы понять, можно ли улучшить результаты openbsd-malloc для firefox, надо по крайней мере снять статистику, сколько аллокаций и деаллокаций осуществляется для каждого размера[байт]. Как это сделать для первого -- с malloc всё очевидно, а вот для free (и для realloc) можно знать размер освобождаемого ею куска в лучшем случае только с точностью до множителя 2 (в openbsd-malloc)... Так что тут снятие статитстики будет геморройным -- нужно извращаться. Надо посмотреть dlmalloc/glibc-malloc (как он работает, я пока не представляю), может, там это можно сделать просто...

Под АМД64 выводит следующие предупреждения при сборке: OpenBSD_malloc_Linux.c: In function `calloc': OpenBSD_malloc_Linux.c:1931: warning: left shift count >= width of type OpenBSD_malloc_Linux.c: In function `ispowerof2': OpenBSD_malloc_Linux.c:1944: warning: left shift count >= width of type

OpenBSD_malloc_Linux.c: In function `calloc':
OpenBSD_malloc_Linux.c:1931: warning: left shift count >= width of type
OpenBSD_malloc_Linux.c: In function `ispowerof2':
OpenBSD_malloc_Linux.c:1944: warning: left shift count >= width of type

Но работает или нет?

>Так что тут снятие статитстики будет геморройным -- нужно извращаться

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

Работает, память отдаёт ;-)

Эээ, я может чего-то не понимаю, но чтобы найти этот конец, надо как раз и знать размер куска. :) Может, лучше в начале? :)

Точна! Знач так... выделяем на 4 байта больше... но указатель возвращаем на "начало+4", соответственно, когда приходит указатель в функцию free мы просто сичтаем "указатель-4", и узнаём размер куска... хм а что... интересно ;)

Вот только о существовании aligned кусков забыли -- а их на 4 байта смещать нельзя...

А вообще-то ништяк. Просто надо это использовать на машине с более старыми gtk/glib, т.е. где posix_memalign не используется. В общем, всем спасибо, буду втыкать :)

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

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

Тогда я хочу об этом знать поподробнее. Кто-то тут тормозит (возможно, что я).

В openbsd-malloc на каждой странце куски имеют определённый размер (он хранится в струтуре pginfo): 16 для аллокаций 1-16 байт, 32 для 17-32, 64 для 33-64, ..., 2048 для 1025-2048; бОльшие аллокации размещаются на отдельных mmap'нутых областях. Можно было бы помещать в конец этих кусков/областей. Понятно?

Ладно, забей на это, всё равно писать размер в начало гораздо проще, никто не спорит.

Ну это уже для конкретного типа аллокатора... Тады конечно.

Вспомнил, что я же про аналогичную фигню у Кнута читал. :) Эх дырявая голова...

>Вспомнил, что я же про аналогичную фигню у Кнута читал.

Интересно, а где именно? Я просто думаю, может все алгоритмы работы алокаторов уже изобретены и не надо заново открывать велосипед...

>Ну это уже для конкретного типа аллокатора... Тады конечно.

Алокатор openbsd проще, чем glibc'шный, так что с ним это проще сделать по-любому.

В первом томе вестимо. А насчёт

> все алгоритмы работы алокаторов уже изобретены

можешь даже не сомневаться. :)

Такс, падает мплайер под амд64.

Пытался проиграть файл матрёшки со звуком ворбис, свалился в decode_audio.

А только что xfwm4 свалился :-(

> Пытался проиграть файл матрёшки...

> anonymous (*) (29.06.2006 2:06:27)

Это ты чё за порнуху на ночь глядя там смотришь? ^_~

Если не трудно:

1. Проверь, компилируется ли теперь без ворнингов (я слегка поменял там константы)

2. Напиши, какие программы работают и не работают под amd64 с аллокатором (для моего успокоения :))

Это не порнуха, а хентай ;-)

> 1. Проверь, компилируется ли теперь без ворнингов (я слегка поменял там константы)

Собралось без предупреждений, спасибо.

> 2. Напиши, какие программы работают и не работают под amd64 с аллокатором (для моего успокоения :))

mplayer на этом файле всё так же валится!

Ночью запустил иксы под ним, в mplayer глюк возник и через некоторое время xfwm4 отвалил :-( А так вроде и терминал и огнелис пахали.

Пока точно проверить не могу, 64-битная тачка дома, я по удалёнке на ней сижу.

amd64, firefox не отдает память вообще.

firefox-1.5.0.4
gcc-4.1.1
glibc-2.4
gtk+-2.8.19
pango-1.12.2
cairo-1.0.4

Ой! Проверил, используется ли openbsd-алокатор? http://www.linux.org.ru/jump-message.jsp?msgid=1452045#1454796

используется.

Запустил свою сессию в 5 окон и в 200 табов сумарно, отожрал ff сразу 100 метров, открыл еще одно окно и в нем кучу табов, отожрал 120 метров, закрыл окно... фиг...

Хех... щас вот не полинился... и провёл так сказать "боевые испытания"...

Тест нумбер 1: запускаем ФФ с "аллокатор из openbsd"...

VIRT RES
~90 Mb ~35 Mb - после старта...
-------------------
~160 Mb ~90 Mb - после открытия 3х окон, с общей суммой вкоадок ~350
-------------------
~105 Mb ~40 Mb - после закрытия 2х окон... и всех вкладок в оставшемся окне исключая одну вкладку...

Как видим память хоть и не совсем вся, но отдаётся по большей части...

Тест нумбер 2: запускаем ФФ с glibc`шным аллокатором (тоесть как обычно :))...

VIRT RES
~95 Mb ~30 Mb - после старта...
-------------------
~150 Mb ~80 Mb - после открытия 3х окон, с общей суммой вкоадок ~350
-------------------
~150 Mb ~80 Mb - после закрытия 2х окон... и всех вкладок в оставшемся окне исключая одну вкладку...

Как видно... результат для glibc`ишного аллокатора не утешительный :)) в то же время openbsd`шный действительно работает!

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

Кстати, собрал "статистику" по free, какая часть аллокаций освобождается. http://mr.himki.net/conv-alloc-dat. Хотя однозначно сделать вывод, можно ли существенно улучшить поведение дальнейшим разделением разных размеров аллокаций, конечно, нельзя...

Хочу продолжить тему про поведение ФФ в винде. Есть разница между поведением ФФ и сеамонкей(все программы последних версий). Если ФФ в 2003 сервер не отдает память с закрытием вкладок, то сеамонкей отдает. При примерно 40 октрытых вкладках, сеамонкей отжирал памяти около 300 Мбт, с закрытием вкладок разнер потребляемой памяти сократился до 70 Мбт

Поведение программ относительно памяти как видим разительно отличается, хотя считается, что у них общая база кода