5

¿Por qué se necesitaría todo el código en la fuente de strlen en este enlace para medir la longitud de una cadena? https://code.woboq.org/userspace/glibc/string/strlen.c.html ¿Por qué algo como esto no sería más eficiente o preferible que la fuente original eliminada?

size_t strlen(char *str) {
    size_t size = 0;
    for(; str[size] != '\0'; size++);
    return size;
}
3
  • 1
    por favor responda en inglés porque solo pregunto aquí porque me expulsaron del sitio normal el 17 nov. 2019 a las 0:39
  • 1
    Bienvenido, las respuestas que recibas aquí serán enteramente en español pues el idioma oficial del sitio, checa Cómo preguntar y de paso has el recorrido de bienvenida
    – BetaM
    el 17 nov. 2019 a las 0:40
  • ¿Por qué te expulsaron del sitio normal? Quizás porque era una pregunta duplicada... Aqui tienes otras versiones: 1 2 3
    – abulafia
    el 17 nov. 2019 a las 11:44

1 respuesta 1

4

¿Por qué se necesitaría todo el código en la fuente de strlen en este enlace para medir la longitud de una cadena?

El propio comentario de la función es ya una declaración de intenciones:

Return the length of the null-terminated string STR. Scan for the null terminator quickly by testing four bytes at a time.

Es decir, esta función comprueba 4 u 8 bytes en cada iteración, mientras que tu versión únicamente comprueba 1.

Lo primero que hace (el primer bucle) es procesar uno a uno los bytes que procedan hasta tener una alineación de palabra. Esto lo hace porque leer secuencias de bytes si los mismos no están alineados es bastante costoso, Este bucle, por tanto, no ejecutará más de 3 iteraciones en 32 bits y 7 en 64 bits. Lo más habitual es que no se llegue a ejecutar, ya que salvo que se haga a propósito, las variables suelen estar alineadas.

A continuación pasa a leer la cadena de caracteres como si fuesen int. Esto le permite leer 4 u 8 bytes cada vez. Dado que el final de la cadena puede estar en cualquiera de esos bytes, usa unas máscaras especiales para localizar aquellas secuencias que puedan contener un terminador de cadena.

Una vez localizada una secuencia con posibles terminadores de cadena, se procesan esos bytes de forma individual.

Habría que ejecutar tests para tener métricas pero sí, yo diría que la versión del enlace debería ser más rápida que tu versión.

No hay que dejarse llevar por la primera impresión. Que una función tenga mucho código no quiere decir que sea ineficiente... a modo de ejemplo, tu bucle se ejecutará size + 1 veces, mientras que el de la función lo hará 4 veces menos ...

De hecho, he probado ambas versiones del código con el siguiente código:

scanf("%d %s", &length, cadena);
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC_RAW, &start);

for( int i=0; i<1e8; i++ )
{
    if( strlen(cadena) != length )
    { puts("ERROR"); break; }
}

clock_gettime(CLOCK_MONOTONIC_RAW, &end);

uint64_t delta_us = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_nsec - start.tv_nsec) / 1000;
printf("%lu us\n",delta_us);

Este fragmento de código me mide cuantos microsegundos tarda en ejecutarse el bucle. Pues bien, para una entrada con 10 caracteres he obtenido los siguientes tiempos:

tu version: 3186447 us
glibc     : 2228053 us

Vemos que la diferencia es de únicamente 1 segundo. Si ampliamos a 20 caracteres:

tu version: 5965255 us
glibc     : 2713137 us

Ahora la versión de glibc es el doble de rápida que tu versión.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.