[C][pool based memory allocator]

Я так и понял. Но цифры от твоего теста кажутся сильно завышенными.

Исходники есть, компиляйте, запускайте, объясняйте ваши результаты.

У вас выравнивание отклеилось (4092 % 8 = 4).

Не отклеилось.

P. S. что-то я смотрю, занятия лиспом скатились к сношению битиков, которые скобочными средствами не делаются, вот и приходится возвращаться к истокам?

Я в стартапе работаю, тут все таланты и знания востребованны. В большую корпорацию с их «мы тебя не для инициатив нанимали» ни в жизнь больше не сунусь.

>В usermode? Я лично не в курсе.

Из ring0 само собой. Ты бы еще lgdt из третьего колечка запросил.

она начинает тормозить из-за того, что страниц в этом кэше нет

Во-первых, не страниц, а оттранслированных адресов страниц. Во-вторых, это невероятно сильно зависит от паттерна доступа к памяти. Последовательный одноразовый доступ — фигня, ни на что не влияет; случайный доступ — в среднем фигня; синтетический тест, где мы будем выделять кучу страниц и нарочно бегать по ним, читая по байтику со страницы — фигня, в жизни такого не бывает.

Достаточно аргументированно?

>> В usermode? Я лично не в курсе.

Из ring0 само собой. Ты бы еще lgdt из третьего колечка запросил.

А ты не понял, что речь идет о юзерспейсном приложении?

Во-первых, не страниц, а оттранслированных адресов страниц.

Это очень важная поправка, да.

Достаточно аргументированно?

Я не заметил вообще никаких аргументов - ты говоришь «будет так», не приводя ни объяснений, ни замеров. Да и вообще я говорил не о паттернах доступа, а о размере working set и том, что случается, когда он не влезает в TLB.

>> Я так и понял. Но цифры от твоего теста кажутся сильно завышенными.

Исходники есть, компиляйте, запускайте, объясняйте ваши результаты.

Разве что вечером.

синтетический тест, где мы будем выделять кучу страниц и нарочно бегать по ним, читая по байтику со страницы — фигня, в жизни такого не бывает.

Я могу назвать биржу, где такое «в жизни не бывает» делается ;)

>Не отклеилось.

64-битные данные разве не по 8-байтной границе должны быть выравнены?

Предлагаю более справедливую версию http://pastebin.com/r9dVi3Zc

На 32 битах результаты вроде как одинаковые, но на 64 (на фре с memset вместо MAP_POPULATE), конечно, какой-то ахтунг: различия на порядок. Правда я не уверен, что такой беспредел творится из-за TLB cache miss. Точнее говоря, точно уверен, что не из-за него, а из-за непоследовательного расположения страниц в памяти. Дома попробую на чистой машине запустить.

>Я не заметил вообще никаких аргументов - ты говоришь «будет так», не приводя ни объяснений, ни замеров.

Замеры в рабочее время проводить не буду, но вот тебе объяснение:

1. Последовательный однократный доступ. Число промахов TLB = sizeof(dataset) / sizeof(PAGE). Думаю, очевидно, почему.

2. Случайный доступ. Промахи возникнут только при равномерном случайном доступе к большому числу страниц. Правда при таком жестком паттерне доступа к памяти вероятность попасть на границу страниц... Кхм, невелика (1 / (sizeof(PAGE) / sizeof(OBJECT))), а вероятность попасть на границу со страницей, которой нет в кеше... Ну, математически она вроде еще меньше, чем просто «попасть на границу страницы».

3. Специально спроектированный паттерн. Пример mv на 32 битной архитектуре «исправляется» элементарным удалением «чита» на попадание в одну и ту же строку памяти. На 64 битах наверняка тоже есть какой-то подводный камень, который можно отрыть в интеловских мануалах. То есть, если уж выравнивать, то надо это делать по 64 байтной границе, но это такой оверхед по памяти, что правильнее забить.

64-битные данные разве не по 8-байтной границе должны быть выравнены?

Нет, на 4 байта достаточно.

Предлагаю более справедливую версию http://pastebin.com/r9dVi3Zc

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

На 32 битах результаты вроде как одинаковые, но на 64 (на фре с memset вместо MAP_POPULATE), конечно, какой-то ахтунг: различия на порядок. Правда я не уверен, что такой беспредел творится из-за TLB cache miss. Точнее говоря, точно уверен, что не из-за него, а из-за непоследовательного расположения страниц в памяти. Дома попробую на чистой машине запустить.

Результаты и процессор огласил бы, чтоль...

Я в стартапе работаю, тут все таланты и знания востребованны. В большую корпорацию с их «мы тебя не для инициатив нанимали» ни в жизнь больше не сунусь.

Эх, знать бы только, какие задачи востребованы. Где может пролиться денежный дождь или хотя бы прокапать?.. [тут личное было вырезано] Значит, тебя временно нагрузили сями. Кстати, а почему плюсы не используешь? В бусте есть готовый пул, правда не знаю, насколько он хорош, и подходит ли под твои требования.

>Нет, на 4 байта достаточно.

gcc с тобой не согласен.

$ cat align.c
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>

struct sample {
    char        c;
    uint64_t    u;
};

int main()
{
    printf("uint64_t align: %u\n", (unsigned)offsetof(struct sample, u));
    return 0;
}
// EOF
$ gcc -Wall -o align align.c && ./align 
uint64_t align: 8

>В первом случае данные попадают на границу строчек кэша.

Как и в случае с границой страницы. По-моему, все честно.

>Результаты и процессор огласил бы, чтоль...

Результаты:

$ gcc -Wall 1.c -O2 && ./a.out
 123853392
 128473736

Процессор (P IV 3.2GHz, HT):

processor	: 0
vendor_id	: GenuineIntel
cpu family	: 15
model		: 4
model name	: Intel(R) Pentium(R) 4 CPU 3.20GHz
stepping	: 9
cpu MHz		: 3200.112
cache size	: 1024 KB
physical id	: 0
siblings	: 2
core id		: 0
cpu cores	: 1
apicid		: 0
initial apicid	: 0
fdiv_bug	: no
hlt_bug		: no
f00f_bug	: no
coma_bug	: no
fpu		: yes
fpu_exception	: yes
cpuid level	: 5
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc pebs bts pni dtes64 monitor ds_cpl cid cx16 xtpr
bogomips	: 6400.22
clflush size	: 64
power management:

processor	: 1
......

Какой у вас DE? А то как то подозрительно...

gcc с тобой не согласен.

Он со мной во многом не согласен (вернее, я с ним), поэтому кое-что пишу на ассемблере.

На c2d разницы между выравниванием на 4/8 байт нет.

Процессор (P IV 3.2GHz, HT):

Ясно, на П4 результаты совсем другие могут быть.

Эх, знать бы только, какие задачи востребованы. Где может пролиться денежный дождь или хотя бы прокапать?..

Биржи, инвестиционные банки - основные источники денежных туч.

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

Да надо было... Я что-то объём задачи недооценил, много общей шелухи пришлось писать. Надо было вообще на лиспе писать, с вынесением тормозных делов в библиотеку.

Надо было вообще на лиспе писать, с вынесением тормозных делов в библиотеку.

Собственно, при мысли писать тесткейсы на сях мне стало совсем грустно, поэтому быстро состряпал прослойку для лиспа и написал тесты на нём =)

>Он со мной во многом не согласен (вернее, я с ним), поэтому кое-что пишу на ассемблере.

Боюсь, что с тобой не согласен и Intel в том числе:

Assembly/Compiler Coding Rule 45. (H impact, H generality) Align data on natural operand size address boundaries. If the data will be accessed with vector instruction loads and stores, align the data on 16-byte boundaries. For best performance, align data as follows:
• Align 8-bit data at any address.
• Align 16-bit data to be contained within an aligned 4-byte word.
• Align 32-bit data so that its base address is a multiple of four.
• Align 64-bit data so that its base address is a multiple of eight.
• Align 80-bit data so that its base address is a multiple of sixteen.
• Align 128-bit data so that its base address is a multiple of sixteen.

Взято из раздела 3.6.3 вот этого замечательного мануала: http://www.intel.com/Assets/PDF/manual/248966.pdf

Боюсь, что с тобой не согласен и Intel в том числе

Да пусть не соглашается. На его же нехалеме и амдшном феноме 8/4 пофигу. На корке плохо, но корка широко известна своей регрессией в плане выравниваний.

>Да пусть не соглашается. На его же нехалеме и амдшном феноме 8/4 пофигу.

libastral.so подсказывает, что пофигу может быть только 32-разрядным приложениям, которые в любом случае разбивают 64-битные переменные на 2 32-битных.

К сожалению 64-битного нехалема нет под рукой, так что реквестирую пруфкод или не было.

А по теме аллокаторов что-то вспомнился мне memcached тем, что он для хранения ключей реализует свой slab аллокатор:

$ ls memcached-1.4.5/slabs.*
memcached-1.4.5/slabs.c  memcached-1.4.5/slabs.h

libastral.so подсказывает, что пофигу может быть только 32-разрядным приложениям, которые в любом случае разбивают 64-битные переменные на 2 32-битных.

У нас 32-разрядных систем или 32-разрядных приложений нет.

К сожалению 64-битного нехалема нет под рукой, так что реквестирую пруфкод или не было.

Модифицируйте код выше по топику. Я проверял, если что.

> $ ./123

39282342

258812631

фигассе. не, я знал, что медленнее, но что бы так...

static void test(void *p)
{
volatile uint64_t* ptr = p;
uint64_t t1, t2;
int i;

t1 = rdtsc();
for (i = 0; i < 1000000; ++i)
*ptr = 1;
t2 = rdtsc();

printf(«%ld\n», t2 - t1);
}

int main()
{
char *tmp;

tmp = mmap(0, 4096 * 2, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE, -1, 0);
assert(tmp != MAP_FAILED);

test(tmp + 4);
test(tmp + 4096 - 4);

return 0;
}

./a.out
3633388
285297694

и без всякого вымывания tlb/cache. удивлен.

из теста idle следует, что при записи через page boundary, ни tlb, ни cache не влияют на деградацию производительности. интересно, что если заменить 64-битную запись на две 32-битные (каждая из которых не пересекает границу страницы), то с производительностью все в порядке (правда, получается в 2 раза медленее, чем test(tmp+4), но этого и следовало ожидать).

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

тестил на 64 битах на c2d.

У меня на 32 корке (первой) наоборот - первый тест медленнее второго. Почему такое поведение?

> ни tlb, ни cache не влияют

да нет, они, конечно влияют. просто я исключил misses.

я не знаю, насколько в _данном_ случае у нас tlb виноват.
а cache, он же на x86 (не помню, как правильно называется)
physically indexed. те во втором случае мы две записи делаем.

но все равно, не ожидал такой разницы.

> те во втором случае мы две записи делаем.

на моем ноуте L1_CACHE_BYTES=64, соответственно

test(tmp + 4);
test(tmp + 64 - 4);
test(tmp + 4096 - 4);

печатает

9828907
120168510
2698714678

(ессно, результаты не стабильны)

/usr/src/lib/libc/stdlib/malloc.c

начиная с 7.0 и слаб, и лицензия кошерная

начиная с 7.0 и слаб, и лицензия кошерная

фря?

> Я могу назвать биржу, где такое «в жизни не бывает» делается ;)

могу добавить одну сильно известную компанию

так точно в своё время выдирали и прикручивали к 6-й (не в libc, а у себя), на линуксе программы с таким malloc запускаются

// pppp