c++ - lenguaje - ¿Por qué las funciones de cadena estándar son más rápidas que mis funciones de cadena personalizadas?

leer cadena de caracteres en c

Question

Decidí encontrar las velocidades de 2 funciones:

• strcmp - La función de comparación estándar definida en string.h
• xstrcmp: una función que tiene los mismos parámetros y hace lo mismo, solo que la creé.

Aquí está mi función xstrcmp:

int xstrlen(char *str)
{
    int i;
    for(i=0;;i++)
    {
        if(str[i]==''/0'')
            break;
    }
    return i;
}

int xstrcmp(char *str1, char *str2)
{
    int i, k;
    if(xstrlen(str1)!=xstrlen(str2))
        return -1;
    k=xstrlen(str1)-1;
    for(i=0;i<=k;i++)
    {
        if(str1[i]!=str2[i])
            return -1;
    }
    return 0;
}

No quería depender de strlen, ya que quiero que todo esté definido por el usuario.

Entonces, encontré los resultados. strcmp hizo 364 comparaciones por milisegundo y mi xstrcmp hizo solo 20 comparaciones por milisegundo (¡por lo menos en mi computadora!)

¿Alguien puede decir por qué esto es así? ¿Qué hace la función xstrcmp para hacerse tan rápido?

Answer 1

Aparte de los problemas en su código (que ya se han señalado), - al menos en gcc-C-libs, las funciones str y mem son más rápidas por un margen en la mayoría de los casos porque sus patrones de acceso a la memoria son muy altos optimizado

Ya hubo algunas discusiones sobre el tema de SO.

Answer 2

Implementación más rápida de strlen:

//Return difference in addresses - 1 as we don''t count null terminator in strlen.
int xstrlen(char *str)
{
    char* ptr = str;
    while (*str++);
    return str - ptr - 1;
}

//Pretty nifty strcmp from here:
//http://vijayinterviewquestions.blogspot.com/2007/07/implement-strcmpstr1-str2-function.html
int mystrcmp(const char *s1, const char *s2)
{
    while (*s1==*s2)
    {
        if(*s1==''/0'')
            return(0);
        ++s1;
        ++s2;
    }
    return(*s1-*s2);
}

Haré el otro después si tengo tiempo. También debe tener en cuenta que la mayoría de ellos se realizan en lenguaje ensamblador o utilizando otros medios optimizados que serán más rápidos que la mejor implementación de Stright C que puede escribir.

Answer 3

Prueba esto:

int xstrlen(const char* s){
  const char* s0 = s;
  while(*s) s++;
  return(s - s0);
}

int xstrcmp(const char* a, const char* b){
  while(*a && *a==*b){a++; b++;}
  int del = *a - *b;
  if (del < 0) return -1;
  else if (del > 0) return 1;
  else return 0;
}

Esto probablemente podría acelerarse con un poco de bucle desenrollado.

Answer 4

Strcmp y otras rutinas de la biblioteca están escritas en ensamblado, o código C especializado, por ingenieros experimentados y utilizan una variedad de técnicas.

Por ejemplo, la implementación del ensamblaje podría cargar cuatro bytes a la vez en un registro y comparar ese registro (como un entero de 32 bits) con cuatro bytes de la otra cadena. En algunas máquinas, la implementación del ensamblaje puede cargar ocho bytes o incluso más. Si la comparación muestra que los bytes son iguales, la implementación pasa a los siguientes cuatro bytes. Si la comparación muestra que los bytes son desiguales, la implementación se detiene.

Incluso con esta simple optimización, hay una serie de problemas que deben abordarse. Si las direcciones de cadena no son múltiplos de cuatro bytes, es posible que el procesador no tenga una instrucción que cargue cuatro bytes (muchos procesadores requieren cargas de cuatro bytes para usar direcciones alineadas a múltiplos de cuatro bytes). Dependiendo del procesador, la implementación podría tener que usar cargas no alineadas más lentas o escribir un código especial para cada caso de alineación que haga cargas alineadas y desplace bytes en los registros para alinear los bytes que se compararán.

Cuando la implementación carga cuatro bytes a la vez, debe asegurarse de que no carga bytes más allá del carácter nulo de terminación si esos bytes pueden causar una falla de segmento (error porque intentó cargar una dirección que no es legible).

Si los cuatro bytes contienen el carácter nulo de terminación, la implementación debe detectarlo y no continuar comparando otros bytes, incluso si los cuatro actuales son iguales en las dos cadenas.

Muchos de estos problemas requieren instrucciones de montaje detalladas, y el control requerido sobre las instrucciones exactas utilizadas no está disponible en C. Las técnicas exactas utilizadas varían de un modelo de procesador a otro y varían mucho de una arquitectura a otra.

Answer 5

1. algoritmo

Su implementación de strcmp podría tener un mejor algoritmo. No debería haber necesidad de llamar a strlen en absoluto, cada llamada a strlen se repetirá en toda la longitud de la cadena. Puede encontrar implementaciones simples pero efectivas en línea, probablemente el lugar para comenzar sea algo como:

// Adapted from http://vijayinterviewquestions.blogspot.co.uk
int xstrcmp(const char *s1, const char *s2)
{
  for (;*s1==*s2;++s1,++s2)
  {
    if(*s1==''/0'') return(0);
  }
  return(*s1-*s2);
}

Eso no lo hace todo, pero debería ser simple y funcionar en la mayoría de los casos.

2. Optimización del compilador.

Es una pregunta estúpida, pero asegúrate de activar todos los cambios de optimización cuando compiles.

3. Optimizaciones más sofisticadas.

Las personas que escriben bibliotecas a menudo utilizan técnicas más avanzadas, como cargar un int de 4 bytes o de 8 bytes a la vez, y compararlas, y solo comparar bytes individuales si todo coincide. Necesitará ser un experto para saber qué es apropiado para este caso, pero puede encontrar personas que discutan la implementación más eficiente en el desbordamiento de pila (¿enlace?)

Algunas funciones de biblioteca estándar para algunas plataformas pueden ser escritas a mano en ensamblador si el codificador puede saber que hay una implementación más eficiente que la que puede encontrar el compilador. Eso es cada vez más raro ahora, pero puede ser común en algunos sistemas integrados.

4. Linker "trampa" con la librería estándar

Con algunas funciones de biblioteca estándar, el enlazador puede hacer que su programa las llame con menos gastos que las funciones de llamada en su código porque fue diseñado para saber más sobre los aspectos internos específicos de las funciones (¿enlace?) No sé si eso se aplica en este caso, probablemente no, pero es el tipo de cosas en las que tienes que pensar.

5. De acuerdo, de acuerdo, lo entiendo, pero ¿cuándo debo implementar mi propio strcmp?

Fuera de mi cabeza, las únicas razones para hacer esto son:

• Quieres aprender como. Esta es una buena razón.
• Estás escribiendo para una plataforma que no tiene una biblioteca estándar lo suficientemente buena. Esto es muy poco probable.
• La comparación de cadenas ha sido medida como un importante cuello de botella en su código, y usted sabe algo específico acerca de sus cadenas que significa que puede compararlas más eficientemente que un algoritmo ingenuo. (Por ejemplo, a todas las cadenas se les asigna un alineamiento de 8 bytes, o todas las cadenas tienen un prefijo de N bytes). Esto es muy, muy poco probable.

6. Pero ...

OK, ¿POR QUÉ quieres evitar confiar en strlen? ¿Te preocupa el tamaño del código? ¿Sobre la portabilidad de código o de ejecutables?

Si hay una buena razón, abra otra pregunta y puede haber una respuesta más específica. Lo siento si me falta algo obvio, pero confiar en la biblioteca estándar suele ser mucho mejor, a menos que haya algo específico en el que desee mejorar.

Answer 6

if(xstrlen(str1)!=xstrlen(str2))    //computing length of str1
    return -1;                      
k=xstrlen(str1)-1;                  //computing length of str1 AGAIN!

Estás calculando la longitud de str1 DOS VECES. Esa es una de las razones por las que tu función pierde el juego.

Además, su xstrcmp de xstrcmp es muy ingenua en comparación con las definidas en (la mayoría) de las bibliotecas estándar. Por ejemplo, su xstrcmp compara un byte a la vez, cuando en realidad podría comparar varios bytes de una sola vez, aprovechando la alineación adecuada, o puede hacer un pequeño procesamiento previo para alinear los bloques de memoria, antes de la comparación real.