recorrer - comparar palabras en c++

¿Por qué reimplementar strlen como loop+resta? (2)

¿Por qué reimplementar strlen como loop + resta?

Sospecho que la respuesta real es que el programador se sintió así, pero otra posible justificación / racionalización es que el bucle está en línea (independientemente de si strlen30 sí lo es), mientras que en muchos sistemas, strlen es una llamada de función fuera de línea (por ejemplo, Linux / GCC). Si la gran mayoría de las cadenas son vacías o cortas (a pesar del tratamiento "especial" de las largas), eso puede producir un leve golpe de rendimiento para el caso común. Esa posibilidad por sí sola puede ser suficiente para obtener un toque de clave de programador feliz. Para cadenas más largas, yo esperaría que la biblioteca strlen sea generalmente óptima (lo que permite su falta de conocimiento de la longitud específica de la aplicación de las cadenas).

Es posible que algunos sistemas ni siquiera se beneficien de esta strlen ya que strlen proporciona su propio sistema, o un híbrido en línea / fuera de línea con una rápida verificación en línea para ver si hay cadenas vacías de un carácter, tal vez de dos caracteres y luego una llamada.

Inspirado en esta pregunta sobre el siguiente código de SQLite3:

static int strlen30(const char *z){ const char *z2 = z; while( *z2 ){ z2++; } return 0x3fffffff & (int)(z2 - z); }

eso va acompañado de un mensaje de confirmación que dice que esta función ayuda con los desbordamientos int .

Estoy particularmente interesado en esta parte:

const char *z2 = z; while( *z2 ){ z2++; }

Para mí, este bucle avanza z2 hasta que z2 apunta al terminador nulo. Entonces z2-z produce la longitud de la cadena.

¿Por qué no usar strlen() para esta parte y reescribir así?

return 0x3fffffff & (int)(strlen(z));

¿Por qué usar loop + resta en lugar de strlen() ? ¿Qué puede hacer loop + resta que strlen() no puede?

No puedo decirle la razón por la que tuvieron que volver a implementarlo y por qué eligieron int lugar de si size_t es el tipo de devolución. Pero sobre la función:

/* ** Compute a string length that is limited to what can be stored in ** lower 30 bits of a 32-bit signed integer. */ static int strlen30(const char *z){ const char *z2 = z; while( *z2 ){ z2++; } return 0x3fffffff & (int)(z2 - z); }

Referencias estándar sobre truncamiento, tipos, desbordamiento

La norma dice en (ISO / IEC 14882: 2003 (E)) 3.9.1 Tipos Fundamentales , 4 .:

Los enteros sin signo, declarados sin firmar, obedecerán las leyes del módulo aritmético 2 ⁿ donde n es el número de bits en la representación del valor de ese tamaño particular de entero. 41)
...
⁴¹⁾ : Esto implica que la aritmética sin signo no se desborda porque un resultado que no puede ser representado por el tipo de entero sin signo resultante se reduce en módulo el número que es mayor que el valor más grande que puede ser representado por el tipo de entero sin signo resultante

Esa parte del estándar no define el comportamiento de desbordamiento para enteros con signo. Si nos fijamos en 5. Expresiones , 5 .:

Si durante la evaluación de una expresión, el resultado no está definido matemáticamente o no está en el rango de valores representables para su tipo, el comportamiento no está definido, a menos que dicha expresión sea una expresión constante (5.19), en cuyo caso el programa está enfermo. -formado. [Nota: la mayoría de las implementaciones existentes de C ++ ignoran los desbordamientos de enteros. El tratamiento de la división por cero, formando un resto utilizando un divisor cero, y todas las excepciones de punto flotante varían entre las máquinas, y generalmente es ajustable por una función de biblioteca. ]

Hasta ahora para el desbordamiento.

En cuanto a restar dos punteros a elementos de matriz, 5.7 Operadores aditivos , 6 .:

Cuando se restan dos punteros a elementos del mismo objeto de matriz, el resultado es la diferencia de los subíndices de los dos elementos de matriz. El tipo del resultado es un tipo de integral con signo definido por la implementación; este tipo será el mismo que se define como ptrdiff_t en el encabezado (18.1). [...]

Mirando a 18.1 :

El contenido es el mismo que el encabezado de la biblioteca de Standard C stddef.h

Así que echemos un vistazo al estándar C (aunque solo tengo una copia de C99), 7.17 Definiciones comunes :

Los tipos utilizados para size_t y ptrdiff_t no deben tener un rango de conversión de entero mayor que el de int. Con signo a menos que la implementación admita objetos lo suficientemente grandes como para que sea necesario.

No hay ninguna otra garantía sobre ptrdiff_t . Luego, el Anexo E (aún en ISO / IEC 9899: TC2) da la magnitud mínima para int. Largo con signo, pero no un máximo:

#define LONG_MAX +2147483647

Ahora, ¿cuáles son los máximos para int , el tipo de retorno para sqlite - strlen30() ? Vamos a omitir la cita de C ++ que nos reenvía al estándar C una vez más, y veremos en C99, Anexo E, el máximo mínimo para int :

#define INT_MAX +32767

Resumen sobre la parte de truncamiento

Por lo general, ptrdiff_t no es más grande que el signed long , que no es más pequeño que 32 bits.
int solo se define para tener al menos 16 bits de longitud.
Por lo tanto, restar dos punteros puede dar un resultado que no se ajuste al int de su plataforma.
Recordamos desde arriba que para los tipos firmados, un resultado que no se ajusta produce un comportamiento indefinido.
strlen30 aplica en modo bit a bit o sobre el resultado de resta-puntero:

| 32 bit | ptr_diff |10111101111110011110111110011111| // could be even larger & |00111111111111111111111111111111| // == 3FFFFFFF<sub>16</sub> ---------------------------------- = |00111101111110011110111110011111| // truncated

Eso evita el comportamiento indefinido al truncar el resultado de la resta del puntero a un valor máximo de 3FFFFFFF ₁₆ = 1073741823 ₁₀ .

No estoy seguro de por qué eligieron exactamente ese valor, porque en la mayoría de las máquinas, solo el bit más significativo indica la firmeza . Podría haber tenido sentido en comparación con el estándar elegir el INT_MAX mínimo, pero 1073741823 es un poco extraño sin saber más detalles (aunque, por supuesto, hace perfectamente lo que dice el comentario sobre su función: truncar a 30 bits y evitar el desbordamiento).

"¿Por qué no usar strlen () para esta parte?"

y reescribirlo así:

return 0x3fffffff & (int)(strlen(z));

Mi conjetura es que querían evitar una posible indirección. Otra ventaja podría ser menos dependencias en la biblioteca estándar, lo que puede ser útil si escribe una aplicación no alojada.

Por cierto, como se desprende de las referencias anteriores, (int)(strlen(z)) podría generar un comportamiento indefinido si el máximo para ptrdiff_t> INT_MAX , así que (int)(0x3fffffff & strlen(z)) sería mejor.