analyse af kodestump

Jeg lytter lige med - det virker pænt indviklet ;-)

Ja, tænk at gøre det så besværligt at tælle længden på et char array.

Vedligeholdelsesvenligt er det ihvertfald ikke !
:-)

Ja man skulle tro at man bare kunne tælle mens man løber det igennem indtil man støder på '\0'

Det må være en virkelig optimeret algoritme

Den er faktisk rimelig hurtig.

Kode:

#include <stdlib.h>

static const unsigned long magic = 0x01010101;

size_t strlen1(const char *s)
{
  const char *t = s;
  unsigned long word;

  if (!s) return 0;

  /* Byte compare up until word boundary */
  for (; ((unsigned long) t & 3); t++)
    if (!*t) return t - s;

  /* Word compare */
  do {
    word = *((unsigned long *) t); t += 4;
    word = (word - magic) &~ word;
    word &= (magic << 7);
  } while (word == 0);

#if BYTE_ORDER == LITTLE_ENDIAN
  /* word & 0x80808080 == word */
  word = (word - 1) & (magic << 10);
  word += (word << 8) + (word << 16);
  t += word >> 26;
#else
  if ((word & 0x80800000) == 0) {
    word <<= 16;
    t += 2;
  }
  if ((word & 0x80000000) == 0) t += 1;
#endif
  return ((const char *) t) - 4 - s;
}

size_t strlen2(const char *s)
{
  int ix = 0;
  while(s[ix]) ix++;
  return ix;
}

size_t strlen3(const char *s)
{
  char *p = (char *)s;
  while(*p) p++;
  return (p-s);
}

#include <stdio.h>
#include <string.h>
#include <time.h>

#define N 100000000

int main()
{
  int i;
  time_t t1,t2;
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen("abcdefgijhklmopqrstuvwxyz0123456789");
  t2 = time(NULL);
  printf("builtin %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen1("abcdefgijhklmopqrstuvwxyz0123456789");
  t2 = time(NULL);
  printf("special %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen2("abcdefgijhklmopqrstuvwxyz0123456789");
  t2 = time(NULL);
  printf("simple array %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen3("abcdefgijhklmopqrstuvwxyz0123456789");
  t2 = time(NULL);
  printf("simple pointer %d\n",t2-t1);
  return 0;
}

output:

builtin 1
special 8
simple array 26
simple pointer 23

Det der gør den hurtig er at den minimerer tilgangen til RAM.

De to simple funktioner jeg laver henter en byte af gangen fra memory
og skal derfor have fat i memory X gange.

Den specielle henter longs fra memory og skal derfor kun hente fra
memory X/4 gange.

[word kører rundt i registre]

Sejt nok! Nu mangler vi bare at forstå algoritmen ;-)

Til at illustere min pointe så har jeg lavet en ny variant:

#include <stdlib.h>

static const unsigned long magic = 0x01010101;

size_t strlen1(const char *s)
{
  const char *t = s;
  unsigned long word;

  if (!s) return 0;

  /* Byte compare up until word boundary */
  for (; ((unsigned long) t & 3); t++)
    if (!*t) return t - s;

  /* Word compare */
  do {
    word = *((unsigned long *) t); t += 4;
    word = (word - magic) &~ word;
    word &= (magic << 7);
  } while (word == 0);

#if BYTE_ORDER == LITTLE_ENDIAN
  /* word & 0x80808080 == word */
  word = (word - 1) & (magic << 10);
  word += (word << 8) + (word << 16);
  t += word >> 26;
#else
  if ((word & 0x80800000) == 0) {
    word <<= 16;
    t += 2;
  }
  if ((word & 0x80000000) == 0) t += 1;
#endif
  return ((const char *) t) - 4 - s;
}

size_t strlen2(const char *s)
{
  int ix = 0;
  while(s[ix]) ix++;
  return ix;
}

size_t strlen3(const char *s)
{
  char *p = (char *)s;
  while(*p) p++;
  return (p-s);
}

size_t strlen4(const char *s)
{
  char *p = (char *)s;
  long l;
  while(((int)p)%4!=0)
  {
      if(!*p) return (p-s);
      p++;
  }
  for(;;) {
      l = *(long *)p;
      if(!(l & 0x000000FF)) return (p-s);
      if(!(l & 0x0000FF00)) return (p-s+1);
      if(!(l & 0x00FF0000)) return (p-s+2);
      if(!(l & 0xFF000000)) return (p-s+3);
      p+=4;
  }
}

#include <stdio.h>
#include <string.h>
#include <time.h>

#define N 100000000
#define S "abcdefgijhklmopqrstuvwxyz0123456789"

int main()
{
  int i;
  time_t t1,t2;
  printf("%d\n",strlen(S));
  printf("%d\n",strlen1(S));
  printf("%d\n",strlen2(S));
  printf("%d\n",strlen3(S));
  printf("%d\n",strlen4(S));
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen(S);
  t2 = time(NULL);
  printf("builtin %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen1(S);
  t2 = time(NULL);
  printf("special %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen2(S);
  t2 = time(NULL);
  printf("simple array %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen3(S);
  t2 = time(NULL);
  printf("simple pointer %d\n",t2-t1);
  t1 = time(NULL);
  for(i=0;i<N;i++) strlen4(S);
  t2 = time(NULL);
  printf("my special %d\n",t2-t1);
  return 0;
}

output:

35
35
35
35
35
builtin 0
special 9
simple array 26
simple pointer 21
my special 11

my special begynder at ligne special en lille smule i kode og
en masse i performance.

Imponerende nok - det kræver vidst lidt nærmere kendskab til maskinarkitektur...

Jeg har stadigvæk ikke forklaret hvad de laver med 0x01010101 ...

if (!s) return 0;

fanger den tomme streng.

  for (; ((unsigned long) t & 3); t++)
    if (!*t) return t - s;

tester 0-3 bytes op til en adresse der er et multipla af 4.

  do {
    word = *((unsigned long *) t); t += 4;
    word = (word - magic) &~ word;
    word &= (magic << 7);
  } while (word == 0);

processer 4 byte ad gange så længe der ikke er nogen nul bytes
i den pågældende long.

#include <stdio.h>

void test(int v)
{
  int v2 = v;
  v2 = (v2 - 0x01010101) & ~v2;
  v2 = v2 & 0x80808080;
  printf("%08X %08X\n",v,v2);
  return;
}

int main()
{
  test(0x12345678);
  test(0x00345678);
  test(0x12345600);
  return 0;
}

outputter:

12345678 00000000
00345678 80000000
12345600 00000080

word = (word - 1) & (magic << 10);
  word += (word << 8) + (word << 16);
  t += word >> 26;

udregner position af den nul byte.

#include <stdio.h>

void test(int v)
{
  int offset;
  int v2 = v;
  v2 = (v2 - 0x01010101) & ~v2;
  v2 = v2 & 0x80808080;
  printf("%08X %08X\n",v,v2);
  if(v2!=0)
  {
      offset = (v2 - 1) & 0x04040400;
      offset = offset + (offset << 8) + (offset << 16);
      offset = offset >> 26;
      printf("%d\n",offset);
  }
  return;
}

int main()
{
  test(0x12345678);
  test(0x00345678);
  test(0x12005678);
  test(0x12340078);
  test(0x12345600);
  return 0;
}

outputter:

12345678 00000000
00345678 80000000
3
12005678 00800000
2
12340078 00008000
1
12345600 00000080
0

Men at forklare de konstanter og matematiske logik ligger vist udover
mine matematiske evner.

Hvis vi nøjes med at se på en unsigned char kan det ret let vises at der for:
(word - 1) &~ word;
kun er en værdi af word der resulterer i at MSB (bit 7) er sat i resultatet, denne værdi er 0.
Linien  word &= (magic << 7) tester efterfølgende for om MSB er sat.

At det netop er 0 der resulterer i at MSB er sat i resultatet, skyldes at der for 0 sker en "overflow" når man trækker 1 fra.

Der er nogle relevante sider:

http://www.ugcs.caltech.edu/~wnoise/base2.html

http://nemesis.sourceforge.net/browse/mod/venimpl/c/str/strlen.c.html

http://ftp.linux.org.uk/pub/linux/libc/t/libc/sysdeps/m68k/strlen.c

Finno - så var der mening med galskaben !

:-)

Jeg savner nogle svar

Så hvis Arnelog Bertel lige vil være så venlig ?

svar

Det er værd at bemærke at sådan noget er meget CPU og compiler specifikt.

Mine resulateter fra i aftes er på en Athlon XP 2000+ uden specielle
switches.

På en 750 MHz Pemntium III for jeg uden specielle switches:

builtin 1
special 27
simple array 38
simple pointer 37
my special 38

men med -O6 får jeg:

builtin 1
special 6
simple array 12
simple pointer 11
my special 10

Det kunne egentlig være sjovt at se hvordan den indbyggede metode er kodet !

Den må ligge i msvcrt.dll (har du ikke brugt Windows?) - men det kan man jo ikke lige umiddelbart se koden til.

Hvad med på en Linux maskine - hvad giver den (jeg har ikke lige adgang til en med compiler på) ?

Den indbyggede bruger formentlig en processor specifik instruktion !

Operativ-systemet burde ikke netyde noget for denne her problem-stilling.

GCC (som jeg har brugt) burde give samme resultat på en given
CPU uanset om den kører Windows eller Linux.

Mere specifikt vil man på x86 bruge:
  repne scasb
se mere her:
  http://www.int80h.org/strlen/

Det var det jeg var ude efter - altså hvordan den indbyggede funktion fungerer.

Det kunne være sjovt at få den asm instruktion til at spille..

Men så skal der jo konverteres fra Intel -> AT&T syntaks. Det kræver vist et større research arbejde at få til at virke (jeg kan få det til at compile - men det virker ikke).

Andre links:

http://www.linuxbin.com/src/string_8h.php (hæsligt farve valg på siden)

http://www.snippets.org/snippets/portable/STRECPY+ASM.php3

Det ser spændende ud.

Men du har ret - et farveladekursus ville gøre godt for ham som har sammensat de farver !

Det vil jeg kigge lidt nærmere på de kommende dage - hvis jeg får tid..

Tak for hjælpen.

Lidt flere resultater:

Athlon XP 2000+ med -O6:

builtin 0
special 2
simple array 6
simple pointer 5
my special 3

Alpha 433 MHz no switches:

builtin 0
special 19
simple array 30
simple pointer 31
my special 21

Alpha 433 MHz with /opt=tune=ev56:

builtin 0
special 19
simple array 22
simple pointer 22
my special 19

Pentium 200 MHz (scaled with 1/10) no switches:

builtin 1
special 13
simple array 21
simple pointer 18
my special 11

Pentium 200 MHz (scaled with 1/10) med -O6:

builtin 0
special 4
simple array 7
simple pointer 7
my special 5