memcmp ведь быстрее, чем strncmp?
Быстрее. strncmp сравнивает побайтно, и с дополнительной проверкой на конец строки.
Ну вот я об этом.
Никак не побайтно.
Скорее всего обе функции упираются в memory bandwidth.
Скорее всего обе функции упираются в memory bandwidth.
Скорее всего обе функции упираются в memory bandwidth.Конечно от частного случая зависит, но в среднем сильно чаще эти функции упираться будут в производительность CPU, а не в memory bandwidth, что легко посчитать.
Допустим, strncmp читает сразу по 4 или 8 байт - как терминальный ноль отлавливать? Может как-то и реально, но это в любом случае сложнее, чем memcmp, где этого делать не надо.
Мелкософтовская реализация crt
Мелкософтовская реализация crt
int __cdecl strncmp
(
const char *first,
const char *last,
size_t count
)
{
size_t x = 0;
if (!count)
{
return 0;
}
/*
* This explicit guard needed to deal correctly with boundary
* cases: strings shorter than 4 bytes and strings longer than
* UINT_MAX-4 bytes .
*/
if( count >= 4 )
{
/* unroll by four */
for (; x < count-4; x+=4)
{
first+=4;
last +=4;
if (*(first-4) == 0 || *(first-4) != *(last-4
{
return(*(unsigned char *first-4) - *(unsigned char *last-4;
}
if (*(first-3) == 0 || *(first-3) != *(last-3
{
return(*(unsigned char *first-3) - *(unsigned char *last-3;
}
if (*(first-2) == 0 || *(first-2) != *(last-2
{
return(*(unsigned char *first-2) - *(unsigned char *last-2;
}
if (*(first-1) == 0 || *(first-1) != *(last-1
{
return(*(unsigned char *first-1) - *(unsigned char *last-1;
}
}
}
/* residual loop */
for (; x < count; x++)
{
if (*first == 0 || *first != *last)
{
return(*(unsigned char *)first - *(unsigned char *)last);
}
first+=1;
last+=1;
}
return 0;
}
Как ты такие вещи считаешь? ИМХО все теоретические подсчеты такого рода _очень_ приблизительны.
Как ты такие вещи считаешь?По клокам. Как ты обосновываешь свою версию?
ИМХО все теоретические подсчеты такого рода _очень_ приблизительны.Если разница идёт на порядки, то теоретические подсчеты на простой задаче типа озвученной уже не приблизительны.
По клокам. Как ты обосновываешь свою версию?
Кодом.
http://pastebin.com/fABeYjEE
Intel(R) Core(TM) i5-2500K CPU @ 3.30GHz
0.144907
0.156303
0.152920
Все три цифры чертовски похожи на бенчмарки из интернета. Да, memcmp слегка выигрывает.
Кодом меряешь нагрузку на memory bandwidth или как это понимать? А с IO и энергопотреблением так тоже можешь?По клокам. Как ты обосновываешь свою версию?Кодом.
Да, memcmp слегка выигрывает.Ну то есть ограничение всё же не в memory bandwidth, поскольку на тестах с одинаковой нагрузкой на чтение из памяти разная производительность.
Кодом меряешь нагрузку на memory bandwidth или как это понимать? А с IO и энергопотреблением так тоже можешь?
Ну да, бенчмарком, а как еще? В теории можно что угодно насчитать. Вот у тебя двумя сообщениями выше порядки фигурировали там где их явно нет
Ну то есть ограничение всё же не в memory bandwidth, поскольку на тестах с одинаковой нагрузкой на чтение из памяти разная производительность.
А хз. Разные реализации memcpy ведь тоже разную скорость дают, с похожим разбросом. Может быть там в основном в память, но с небольшими затыками - например на каждую кеш-линию, или что-то в этом роде.
жуть какая. Это всё человек написал? 
Ну да, бенчмарком, а как еще?Ок, запускаешь ты бенчмарк на чтение памяти, и что, на бенчмарке получилость столько же, сколько на memcmp? Или как ты сравниваешь memcmp с бенчмарком?
Вот у тебя двумя сообщениями выше порядки фигурировали там где их явно нетНу как так нет, если клоки в штуках в секунду меряются, их запросто можно сравнивать между собой.
Так выровняй данные по странице, померяй бенчмарком (хм-хм) или там валгриндом, посчитай выполненные инструкции честно, и посмотри, что однотредовый memcmp не упирается в память.Ну то есть ограничение всё же не в memory bandwidth, поскольку на тестах с одинаковой нагрузкой на чтение из памяти разная производительность.А хз. Разные реализации memcpy ведь тоже разную скорость дают, с похожим разбросом. Может быть там в основном в память, но с небольшими затыками - например на каждую кеш-линию, или что-то в этом роде.
PS, написал тест и проверил у себя, что время выполнения 100 раз memcmp (в подавляющем большинстве инструкции repz cmpsb) сравнения двух 536866816 байтных кусков памяти с тронутыми страницами обратно пропорционально зависит от частоты процессора:
| частота, GHz | время выполнения, c | штуки, в миллиардах | Мбайт пополам в секунду |
| 2.7 | 44.211592524 | 119.371299814 | 1158.05847408 |
| 2.2 | 53.893048858 | 118.564707488 | 950.02250679 |
| 2.0 | 59.696896444 | 119.393792888 | 857.65948357 |
| 1.8 | 65.477249749 | 117.859049548 | 781.94502015 |
| 1.6 | 74.363381555 | 118.981410488 | 688.50566373 |
| 1.4 | 84.256964605 | 117.959750447 | 607.66026422 |
Впрочем, это было и так очевидно.
С удовольствием прочту объяснение этого феномена через достигнутый потолок memory bandwidth, что-нибудь вроде того, что когда достигнут потолок, то memory bandwidth линейно зависит от частоты процессора
Ок, запускаешь ты бенчмарк на чтение памяти, и что, на бенчмарке получилость столько же, сколько на memcmp? Или как ты сравниваешь memcmp с бенчмарком?
Я выше давал ссылку на исходник.
Может быть ты про какой-то embedded говоришь? У меня плохо укладывается в голове как можно клоки считать в штуках когда на дворе 2013 год, суперскаляры и прочая фигня.
Да, и как ты добился repz cmpsb? У меня значительно круче:
0.00 : 13a67b: mov %rcx,%rdx
0.17 : 13a67e: xchg %ax,%ax
0.56 : 13a680: movdqa (%rdi,%rdx,1%xmm0
1.77 : 13a685: pcmpistri $0x1a%rsi,%rdx,1%xmm0
9.87 : 13a68c: lea 0x10(%rdx%rdx
3.35 : 13a690: jbe 13a6c0 <__nss_hosts_lookup+0x13d0>
1.47 : 13a692: sub $0x10,%r11
0.00 : 13a696: jbe 13b534 <__nss_hosts_lookup+0x2244>
0.45 : 13a69c: movdqa (%rdi,%rdx,1%xmm0
29.36 : 13a6a1: pcmpistri $0x1a%rsi,%rdx,1%xmm0
43.37 : 13a6a8: lea 0x10(%rdx%rdx
1.87 : 13a6ac: jbe 13a6c0 <__nss_hosts_lookup+0x13d0>
4.25 : 13a6ae: sub $0x10,%r11
Я выше давал ссылку на исходник.
Может быть ты про какой-то embedded говоришь?Да нет, обыкновенный generic i686, собственно поэтому и repz cmpsb, а не инструкция из SSE4.2.
У меня плохо укладывается в голове как можно клоки считать в штуках когда на дворе 2013 год, суперскаляры и прочая фигня.Сложнее, но всё равно считается. В этой задаче основное время идёт на выполнение лишь нескольких инструкций, что просчитывается.
$ ./testУ меня на generic i686 не упирается. memcpy не очень хороший референсный пример, так как хочется сравнивать лишь с чтением из памяти, что должно быть значительно быстрее.
0.870109
1.188038
0.193335
При этом сам мой медленный memcpy у меня тоже не упирается в память, что легко проверяется изменением частоты CPU:
| 2.7 GHz | 9.675454478 с | 26.1237270906 штук |
| 2.2 GHz | 11.539442963 c | 25.3867745186 штук |
| 1.8 GHz | 13.822094812 c | 24.8797706616 штук |
| 1.0 GHz | 24.226097764 c | 24.2260977640 штук |
в ./sysdeps/ia64/strcmp.S, кстати, написано "Unlike memcmp this function is optimized for mismatches within the first few characters"
раз уж вы тут бенчмарками меряетесь - может проверите есть ли разница на x86_64 ?
раз уж вы тут бенчмарками меряетесь - может проверите есть ли разница на x86_64 ?
Да, memcmp слегка выигрывает.Ну так и должно быть, я полагаю. В нем минус одна зависимость от памяти, должен лучше конвейеризоваться.
а ты когда уменьшаешь частоту CPU у тебя с частотой памяти ничего не происходит?
$ ./testНикаких подобных результатов воспроизвести не получилось.
0.870109
1.188038
0.193335
http://pastebin.com/fABeYjEE
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
Linux 3.2.0-4-amd64 SMP Debian 3.2.51-1 x86_64 GNU/Linux
$ ./kai_test
0.166762
0.160864
0.145566
Это на частоте 3.40, компилировал "g++ -O3". Уменьшение частоты процессора до 1.60 (в два с лишним раза) таки к замедлению приводит, но точно не пропорциональному, как ты репортишь в своих замерах.
$ ./kai_test
0.231044
0.224599
0.209666
Частота менялась с помощью cpufreq, драйвер - acpi-cpufreq. Рандомизация адресного пространства у меня выключена.
Итого, твои результаты не воспроизводятся. Значит либо у тебя сетап отличается чем-то принципиально, либо ты просто гонишь. Поскольку подробностей эксперимента ты не сообщаешь, то нельзя точно сказать, что из этого имеет место быть.
Это всё, конечно, жутко интересно и непонятно, но народ волнует один вопрос: так всё-таки, на сколько процентов memcmp быстрее strncmp?
на 87.9854%
какого рода ответ ты ожидаешь, интересно?
какого рода ответ ты ожидаешь, интересно?
а ты когда уменьшаешь частоту CPU у тебя с частотой памяти ничего не происходит?CPU и память — это независимые устройства.
Это неудивительно, потому что у меня generic 32-bit i686 без SSE4.2 оптимизаций в libc, я об этом писал выше.$ ./testНикаких подобных результатов воспроизвести не получилось.
0.870109
1.188038
0.193335
Итого, твои результаты не воспроизводятся. Значит либо у тебя сетап отличается чем-то принципиально, либо ты просто гонишь. Поскольку подробностей эксперимента ты не сообщаешь, то нельзя точно сказать, что из этого имеет место быть.Какого эксперимента? Я запускал тот же самый тест от , и собственный тупой тест, не думал, что он представляет настолько большой интерес для тебя.
#define _GNU_SOURCE
#include <string.h>
#include <sys/mman.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static unsigned long long now(void) {
struct timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
return ts.tv_nsec + ts.tv_sec * 1000000000ULL;
}
int main(int argc, char **argv)
{
char *p1, *p2;
int count = 100, size = (INT_MAX / 4) & ~(4096 - 1);
volatile int ret;
unsigned long long delta;
p1 = mmap(0, size, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
p2 = mmap(0, size, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (p1 == MAP_FAILED || p2 == MAP_FAILED)
return EXIT_FAILURE;
memset(p1, 'x', size);
memset(p2, 'x', size);
printf("size: %llu \n", (unsigned long long)count * size);
delta = now;
for (; count; count--) {
ret = memcmp(p1, p2, size);
//memcpy(p1, p2, size);
}
delta = now - delta;
printf("delta: %f\n", (double)delta / 1000000000);
munmap(p2, size);
munmap(p1, size);
return EXIT_SUCCESS;
}
И вот что удивительно, если я параллелю тест от на две коры ноутбука по-честному с set affinity, то получаю такие результаты:
а на одной коре было
$ ./test2
0.500286
0.697225
0.165848
а на одной коре было
$ ./testR/W memcpy подвинулся на 16%, две другие медленные прибавили по 70%, то есть на одной коре memory bandwidth достигнут не был. Так вопрос остался открыт, почему можно утверждать, что memory bandwidth достигнут, например, теперь на двух корках.
0.870109
1.188038
0.193335
generic 32-bit i686 без SSE4.2 оптимизаций в libcНо это же сферический конь в вакууме. В glibc, например, оптимизации включаются в рантайме (через IFUNC и чтобы собрать без них надо сильно постараться.
Так яснее?
0007ec60 <memcmp>:
7ec60: 56 push %esi
7ec61: 89 fa mov %edi,%edx
7ec63: 8b 74 24 08 mov 0x8(%esp%esi
7ec67: 8b 7c 24 0c mov 0xc(%esp%edi
7ec6b: 8b 4c 24 10 mov 0x10(%esp%ecx
7ec6f: fc cld
7ec70: 31 c0 xor %eax,%eax
7ec72: f3 a6 repz cmpsb %es:(%edi%ds:(%esi)
7ec74: 74 04 je 7ec7a <memcmp+0x1a>
7ec76: 19 c0 sbb %eax,%eax
7ec78: 0c 01 or $0x1,%al
7ec7a: 5e pop %esi
7ec7b: 89 d7 mov %edx,%edi
7ec7d: c3 ret
0007d5b0 <strncmp>:
7d5b0: 55 push %ebp
7d5b1: 57 push %edi
7d5b2: 56 push %esi
7d5b3: 83 ec 04 sub $0x4,%esp
7d5b6: 8b 6c 24 1c mov 0x1c(%esp%ebp
7d5ba: 8b 54 24 14 mov 0x14(%esp%edx
7d5be: 8b 4c 24 18 mov 0x18(%esp%ecx
7d5c2: 83 fd 03 cmp $0x3,%ebp
7d5c5: 0f 86 a5 00 00 00 jbe 7d670 <strncmp+0xc0>
7d5cb: 89 ee mov %ebp,%esi
7d5cd: c1 ee 02 shr $0x2,%esi
7d5d0: eb 6d jmp 7d63f <strncmp+0x8f>
7d5d2: 8d b6 00 00 00 00 lea 0x0(%esi%esi
7d5d8: 80 7c 24 03 00 cmpb $0x0,0x3(%esp)
7d5dd: 74 79 je 7d658 <strncmp+0xa8>
7d5df: 0f b6 42 01 movzbl 0x1(%edx%eax
7d5e3: 0f b6 79 01 movzbl 0x1(%ecx%edi
7d5e7: 88 44 24 03 mov %al,0x3(%esp)
7d5eb: 89 f8 mov %edi,%eax
7d5ed: 38 44 24 03 cmp %al,0x3(%esp)
7d5f1: 75 65 jne 7d658 <strncmp+0xa8>
7d5f3: 80 7c 24 03 00 cmpb $0x0,0x3(%esp)
7d5f8: 74 5e je 7d658 <strncmp+0xa8>
7d5fa: 0f b6 42 02 movzbl 0x2(%edx%eax
7d5fe: 0f b6 79 02 movzbl 0x2(%ecx%edi
7d602: 88 44 24 03 mov %al,0x3(%esp)
7d606: 89 f8 mov %edi,%eax
7d608: 38 44 24 03 cmp %al,0x3(%esp)
7d60c: 75 4a jne 7d658 <strncmp+0xa8>
7d60e: 80 7c 24 03 00 cmpb $0x0,0x3(%esp)
7d613: 74 43 je 7d658 <strncmp+0xa8>
7d615: 0f b6 42 03 movzbl 0x3(%edx%eax
7d619: 83 c2 04 add $0x4,%edx
7d61c: 0f b6 79 03 movzbl 0x3(%ecx%edi
7d620: 83 c1 04 add $0x4,%ecx
7d623: 88 44 24 03 mov %al,0x3(%esp)
7d627: 89 f8 mov %edi,%eax
7d629: 38 44 24 03 cmp %al,0x3(%esp)
7d62d: 75 29 jne 7d658 <strncmp+0xa8>
7d62f: 80 7c 24 03 00 cmpb $0x0,0x3(%esp)
7d634: 74 22 je 7d658 <strncmp+0xa8>
7d636: 83 ee 01 sub $0x1,%esi
7d639: 0f 84 89 00 00 00 je 7d6c8 <strncmp+0x118>
7d63f: 0f b6 02 movzbl (%edx%eax
7d642: 0f b6 39 movzbl (%ecx%edi
7d645: 88 44 24 03 mov %al,0x3(%esp)
7d649: 89 f8 mov %edi,%eax
7d64b: 38 44 24 03 cmp %al,0x3(%esp)
7d64f: 74 87 je 7d5d8 <strncmp+0x28>
7d651: 8d b4 26 00 00 00 00 lea 0x0(%esi,%eiz,1%esi
7d658: 0f b6 44 24 03 movzbl 0x3(%esp%eax
7d65d: 81 e7 ff 00 00 00 and $0xff,%edi
7d663: 83 c4 04 add $0x4,%esp
7d666: 5e pop %esi
7d667: 29 f8 sub %edi,%eax
7d669: 5f pop %edi
7d66a: 5d pop %ebp
7d66b: c3 ret
7d66c: 8d 74 26 00 lea 0x0(%esi,%eiz,1%esi
7d670: 31 ff xor %edi,%edi
7d672: c6 44 24 03 00 movb $0x0,0x3(%esp)
7d677: 85 ed test %ebp,%ebp
7d679: 74 dd je 7d658 <strncmp+0xa8>
7d67b: 0f b6 02 movzbl (%edx%eax
7d67e: 0f b6 39 movzbl (%ecx%edi
7d681: 88 44 24 03 mov %al,0x3(%esp)
7d685: 89 f8 mov %edi,%eax
7d687: 38 44 24 03 cmp %al,0x3(%esp)
7d68b: 75 cb jne 7d658 <strncmp+0xa8>
7d68d: 83 ed 01 sub $0x1,%ebp
7d690: 31 f6 xor %esi,%esi
7d692: 80 7c 24 03 00 cmpb $0x0,0x3(%esp)
7d697: 75 27 jne 7d6c0 <strncmp+0x110>
7d699: eb bd jmp 7d658 <strncmp+0xa8>
7d69b: 90 nop
7d69c: 8d 74 26 00 lea 0x0(%esi,%eiz,1%esi
7d6a0: 0f b6 44 32 01 movzbl 0x1(%edx,%esi,1%eax
7d6a5: 0f b6 7c 31 01 movzbl 0x1(%ecx,%esi,1%edi
7d6aa: 83 c6 01 add $0x1,%esi
7d6ad: 88 44 24 03 mov %al,0x3(%esp)
7d6b1: 89 f8 mov %edi,%eax
7d6b3: 38 44 24 03 cmp %al,0x3(%esp)
7d6b7: 75 9f jne 7d658 <strncmp+0xa8>
7d6b9: 80 7c 24 03 00 cmpb $0x0,0x3(%esp)
7d6be: 74 98 je 7d658 <strncmp+0xa8>
7d6c0: 39 ee cmp %ebp,%esi
7d6c2: 75 dc jne 7d6a0 <strncmp+0xf0>
7d6c4: eb 92 jmp 7d658 <strncmp+0xa8>
7d6c6: 66 90 xchg %ax,%ax
7d6c8: 83 e5 03 and $0x3,%ebp
7d6cb: 90 nop
7d6cc: 8d 74 26 00 lea 0x0(%esi,%eiz,1%esi
7d6d0: eb a5 jmp 7d677 <strncmp+0xc7>
Нет, еще хуже стало.
Меня интересовало где этот код работает в наши дни. Какой-то BSD?
Меня интересовало где этот код работает в наши дни. Какой-то BSD?
Во, у меня кажется получилось!
Это я взял тулчейн под i586 с uClibc в качетсве рантайма. (конфиг i586-geode-linux-uclibc для crosstool-NG). Итого, если взять рантайм, оптимизированный под размер (порой в ущерб производительности и скомпилировать под железо 15-летней давности, то программа получится CPU-bound. Очень полезное знание.
$ ./kai_test.x86
0.673270
0.973881
0.145393
Это я взял тулчейн под i586 с uClibc в качетсве рантайма. (конфиг i586-geode-linux-uclibc для crosstool-NG). Итого, если взять рантайм, оптимизированный под размер (порой в ущерб производительности и скомпилировать под железо 15-летней давности, то программа получится CPU-bound. Очень полезное знание.
Причём код, который показывает , даже по размеру оптимальным назвать никак нельзя. Я там вижу что-то напоминающее четырежды раскрученный цикл.
Оставить комментарий
apl13
Ня?