[postgis-devel] Re: Cost of memcmp

[Paul Ramsey]

I think I'm convinced that, thought memcmp is a non-zero cost,
compared to the cost of EVERYTHING ELSE, it's a very small cost. (For
example, I calculated, based on the numbers below, that the memcmp
cost of my standard 8000-overlayed-with-80 test data would be about
40ms, and the current code returns results in about 8000ms. So a 0.5%
performance penalty.)

P.

On Mon, Oct 6, 2008 at 10:17 PM, Paul Ramsey <pramsey at cleverelephant.ca> wrote:
> OK, I should have been a bit more skeptical of those results.. the
> compiler optimized the test out of existence. Here's one that returns
> real answers on the cost of memcmp.
>
> First the results though:
>
> 1000000 ticks per second.
> Compared 1024 bytes (~64 vertices), 1000000 times, took 165666 ticks.
> Compared 2048 bytes (~128 vertices), 1000000 times, took 288141 ticks.
> Compared 4096 bytes (~256 vertices), 1000000 times, took 570401 ticks.
> Compared 8192 bytes (~512 vertices), 1000000 times, took 1112775 ticks.
> Compared 16384 bytes (~1024 vertices), 1000000 times, took 2221507 ticks.
> Compared 32768 bytes (~2048 vertices), 1000000 times, took 4781961 ticks.
> Compared 65536 bytes (~4096 vertices), 1000000 times, took 9576764 ticks.
> Compared 131072 bytes (~8192 vertices), 1000000 times, took 19109345 ticks.
> Compared 262144 bytes (~16384 vertices), 1000000 times, took 38152790 ticks.
>
>
> Then the code:
>
> #include <stdio.h>
> #include <string.h>
> #include <stdlib.h>
> #include <time.h>
>
> clock_t start_time, end_time;
> int i, j, k;
> int loop = 1000000;
> size_t size = 1024;
> char* memseg1;
> char* memseg2;
>
> int expn = 1;
>
> int main() {
>
>  printf("%d ticks per second.\n", CLOCKS_PER_SEC);
>
>  for(j = 0; j < 18; j++ ) {
>
>    memseg1 = malloc(size);
>    memseg2 = malloc(size);
>    memcpy(memseg2, memseg1, size);
>
>    start_time = clock();
>    k = 0;
>    for( i = 0; i < loop; i++ )
>    {
>      if(memcmp(memseg1, memseg2, size))
>      {
>        k++;
>      }
>    }
>    end_time = clock();
>
>    printf("Compared %d bytes (~%d vertices), %d times, took %d
> ticks.\n", size, size / 16, loop, end_time - start_time);
>    size = size * 2;
>    free(memseg1);
>    free(memseg2);
>  }
> }
>
>
>
> On Mon, Oct 6, 2008 at 9:59 PM, Paul Ramsey <pramsey at cleverelephant.ca> wrote:
>> I can't see anything wrong with this test program, but it seems to
>> indicate that the cost of memcmp is basically constant and tiny.
>> Anyone see what I'm doing wrong? If the answer is "no", then we should
>> clearly by moving to a memcmp implementation.
>>
>>
>> #include <stdio.h>
>> #include <string.h>
>> #include <stdlib.h>
>> #include <time.h>
>>
>> clock_t start_time, end_time;
>> int i, j;
>> int loop = 10000000;
>> size_t size = 1024;
>> char* memseg1;
>> char* memseg2;
>>
>> int expn = 1;
>>
>> int main() {
>>
>>  printf("%d ticks per second.\n", CLOCKS_PER_SEC);
>>
>>  for(j = 0; j < 18; j++ ) {
>>
>>    memseg1 = malloc(size);
>>    memseg2 = malloc(size);
>>    memcpy(memseg2, memseg1, size);
>>
>>    start_time = clock();
>>    for( i = 0; i < loop; i++ )
>>    {
>>      if(memcmp(memseg1, memseg2, size)) {}
>>    }
>>    end_time = clock();
>>
>>    printf("Compared %d bytes, %d times, took %d ticks.\n", size,
>> loop, end_time - start_time);
>>    size = size * 2;
>>    free(memseg1);
>>    free(memseg2);
>>  }
>> }
>>
>