¿Cuál es el fundamento de las cadenas terminadas nulas?

Por mucho que me gusten C y C ++, no puedo dejar de pensar en la elección de las cadenas terminadas nulas:

  • Longitudes prefijadas (es decir, Pascal) existían antes de C
  • Las cadenas con prefijo de longitud hacen que varios algoritmos sean más rápidos al permitir la búsqueda de longitud de tiempo constante.
  • Las cadenas con prefijo de longitud hacen que sea más difícil provocar errores de desbordamiento del búfer.
  • Incluso en una máquina de 32 bits, si permite que la cadena tenga el tamaño de la memoria disponible, una cadena con prefijo de longitud solo tiene tres bytes más que una cadena con terminación nula. En máquinas de 16 bits, este es un byte único. En máquinas de 64 bits, 4 GB es un límite razonable de longitud de cadena, pero incluso si desea expandirlo al tamaño de la palabra máquina, las máquinas de 64 bits suelen tener una memoria amplia, lo que hace que los siete bytes adicionales sean un argumento nulo. Sé que el estándar C original fue escrito para máquinas locamente pobres (en términos de memoria), pero el argumento de la eficiencia no me vende aquí.
  • Prácticamente todos los demás lenguajes (es decir, Perl, Pascal, Python, Java, C #, etc.) usan cadenas con prefijo de longitud. Estos lenguajes normalmente superan a C en los puntos de referencia de manipulación de cadenas porque son más eficientes con las cadenas.
  • C ++ rectificó esto un poco con la plantilla std::basic_string , pero las matrices de caracteres simples que esperan cadenas terminadas nulas aún son omnipresentes. Esto también es imperfecto porque requiere asignación de montón.
  • Las cadenas terminadas en nulo tienen que reservar un carácter (a saber, nulo), que no puede existir en la cadena, mientras que las cadenas con prefijo de longitud pueden contener nulos incorporados.

Varias de estas cosas han salido a la luz más recientemente que C, por lo que tendría sentido que C no las conociera. Sin embargo, varios eran simples mucho antes de que C llegara a ser. ¿Por qué se han elegido cadenas terminadas nulas en lugar de la prefijación de longitud obviamente superior?

EDITAR : Como algunos pidieron datos (y no me gustaron los que ya proporcioné) en mi punto de eficiencia anterior, se derivan de algunas cosas:

  • Concat utiliza cadenas terminadas nulas requiere O (n + m) complejidad de tiempo. El prefijo de longitud a menudo requiere solo O (m).
  • La longitud usando cadenas terminadas nulas requiere O (n) complejidad de tiempo. El prefijo de longitud es O (1).
  • La longitud y el concat son, con mucho, las operaciones de cuerda más comunes. Hay varios casos en que las cadenas terminadas nulas pueden ser más eficientes, pero ocurren con mucha menos frecuencia.

De las respuestas a continuación, estos son algunos casos en los que las cadenas con terminación nula son más eficientes:

  • Cuando necesite cortar el inicio de una cadena y necesita pasarla a algún método. No se puede hacer esto en tiempo constante con el prefijo de longitud, incluso si se permite destruir la cadena original, porque el prefijo de longitud probablemente deba seguir las reglas de alineación.
  • En algunos casos en los que solo está recorriendo la cadena carácter por carácter, es posible que pueda guardar un registro de la CPU. Tenga en cuenta que esto funciona solo en el caso de que no haya asignado dinámicamente la cadena (porque entonces tendría que liberarla, necesitando usar el registro de la CPU que guardó para mantener el puntero que originalmente obtuvo de malloc y sus amigos).

Ninguno de los anteriores es casi tan común como la longitud y el concat.

Hay uno más afirmado en las respuestas a continuación:

  • Tienes que cortar el final de la cuerda

pero este es incorrecto; es la misma cantidad de tiempo para cadenas terminadas en nulo y cadenas con prefijo de longitud. (Las cadenas terminadas en nulo solo tienen un nulo en donde desea que esté el nuevo extremo, los prefijos de longitud solo restan del prefijo).

De la boca del caballo

Ninguno de BCPL, B o C admite datos de caracteres fuertemente en el idioma; cada uno trata cadenas muy parecidas a vectores de enteros y complementa las reglas generales con unas pocas convenciones. Tanto en BCPL como en B, una cadena literal denota la dirección de un área estática inicializada con los caracteres de la cadena, empaquetada en celdas. En BCPL, el primer byte empaquetado contiene la cantidad de caracteres en la cadena; en B, no hay conteo y las cadenas terminan con un carácter especial, que B deletrea *e . Este cambio se realizó parcialmente para evitar la limitación en la longitud de una cuerda causada por mantener el recuento en una ranura de 8 o 9 bits, y en parte porque el mantenimiento del recuento parecía, en nuestra experiencia, menos conveniente que usar un terminador.

Dennis M Ritchie, Desarrollo del lenguaje C

C no tiene una cadena como parte del lenguaje. Una ‘cadena’ en C es solo un puntero a char. Entonces tal vez estás haciendo la pregunta incorrecta.

“¿Cuál es la razón para dejar de lado un tipo de cadena?” Podría ser más relevante. Para eso, señalaría que C no es un lenguaje orientado a objetos y solo tiene tipos de valores básicos. Una cadena es un concepto de nivel superior que debe implementarse de alguna manera combinando valores de otros tipos. C está en un nivel inferior de abstracción.

a la luz de la furiosa borrasca a continuación:

Solo quiero señalar que no estoy tratando de decir que esta es una pregunta estúpida o mala, o que la forma C de representar cadenas es la mejor opción. Estoy tratando de aclarar que la pregunta sería más sucinta si se tiene en cuenta el hecho de que C no tiene ningún mecanismo para diferenciar una cadena como un tipo de datos de una matriz de bytes. ¿Es esta la mejor opción a la luz del procesamiento y la capacidad de memoria de las computadoras actuales? Probablemente no. Pero en retrospectiva siempre es 20/20 y todo eso 🙂

La pregunta se realiza como una Length Prefixed Strings (LPS) frente a zero terminated strings (SZ) , pero sobre todo expone los beneficios de las cadenas con prefijo de longitud. Eso puede parecer abrumador, pero para ser honesto, también deberíamos considerar los inconvenientes de LPS y las ventajas de SZ.

Según tengo entendido, la pregunta puede incluso entenderse como una forma sesgada de preguntar “¿Cuáles son las ventajas de Cadenas Terminadas en Cero?”.

Ventajas (veo) de cadenas terminadas en cero:

  • muy simple, no es necesario introducir nuevos conceptos en el lenguaje, pueden ser útiles las matrices de caracteres / punteros de char.
  • el lenguaje central solo incluye azúcar sintáctica mínima para convertir algo entre comillas dobles a un montón de caracteres (realmente un montón de bytes). En algunos casos, puede usarse para inicializar cosas que no están relacionadas con el texto. Por ejemplo, el formato de archivo de imagen xpm es una fuente de C válida que contiene datos de imagen codificados como una cadena.
  • por cierto, puede poner un cero en un literal de cadena, el comstackdor también agregará otro al final del literal: "this\0is\0valid\0C" . ¿Es una cadena? o cuatro cuerdas? O un montón de bytes …
  • Implementación plana, sin indirección oculta, sin entero oculto.
  • no hay asignación de memoria oculta involucrada (bueno, algunas funciones infames no estándar como strdup realizan la asignación, pero eso es principalmente una fuente de problemas).
  • ningún problema específico para hardware pequeño o grande (imagina la carga de administrar 32 bits de longitud de prefijo en microcontroladores de 8 bits, o las restricciones de limitar el tamaño de cadena a menos de 256 bytes, que era un problema que tuve con Turbo Pascal hace eones).
  • la implementación de la manipulación de cadenas es solo un puñado de funciones de biblioteca muy simples
  • eficiente para el uso principal de cadenas: texto constante leído secuencialmente desde un inicio conocido (principalmente mensajes para el usuario).
  • el cero de terminación ni siquiera es obligatorio, todas las herramientas necesarias para manipular caracteres como un grupo de bytes están disponibles. Al realizar la inicialización de la matriz en C, incluso puede evitar el terminador NUL. Solo establece el tamaño correcto. char a[3] = "foo"; es válido C (no C ++) y no pondrá un cero final en a.
  • coherente con el punto de vista de Unix “todo es archivo”, incluidos “archivos” que no tienen una longitud intrínseca como stdin, stdout. Debe recordar que las primitivas de lectura y escritura abiertas se implementan a un nivel muy bajo. No son llamadas a la biblioteca, sino llamadas al sistema. Y la misma API se usa para archivos binarios o de texto. Las primitivas de lectura de archivo obtienen una dirección de buffer y un tamaño y devuelven el nuevo tamaño. Y puede usar cadenas como el búfer para escribir. Usar otro tipo de representación de cadena implicaría que no puede usar fácilmente una cadena literal como el búfer de salida, o tendría que hacer que tenga un comportamiento muy extraño al convertirlo en char* . A saber, no devolver la dirección de la cadena, sino devolver los datos reales.
  • muy fácil de manipular datos de texto leídos desde un archivo en el lugar, sin copia inútil del búfer, simplemente inserte ceros en los lugares correctos (bueno, no realmente con C moderna porque las cadenas de comillas dobles son matrices de const hoy por lo general guardadas en datos no modificables) segmento).
  • anteponer algunos valores int de cualquier tamaño implicaría problemas de alineación. La longitud inicial debe estar alineada, pero no hay ninguna razón para hacer eso para los datos de los personajes (y de nuevo, forzar la alineación de las cadenas implicaría problemas al tratarlos como un grupo de bytes).
  • la longitud se conoce en tiempo de comstackción para cadenas literales constantes (sizeof). Entonces, ¿por qué alguien querría almacenarlo en memoria anteponiéndolo a datos reales?
  • en cierto modo, C lo hace como (casi) todos los demás, las cadenas se ven como matrices de caracteres. Como C no administra la longitud de la matriz, la longitud lógica no se gestiona para las cadenas. Lo único sorprendente es que se agregó 0 elementos al final, pero eso es solo a nivel del lenguaje central al escribir una cadena entre comillas dobles. Los usuarios pueden llamar perfectamente a las funciones de manipulación de cadenas que pasan la longitud, o incluso usar memcopy simple en su lugar. SZ son solo una instalación. En la mayoría de los demás lenguajes, se administra la longitud de la matriz, es lógico que sea lo mismo para las cadenas.
  • en los tiempos modernos, de todos modos, los juegos de caracteres de 1 byte no son suficientes y, a menudo, tiene que lidiar con cadenas codificadas de unicode, donde el número de caracteres es muy diferente del número de bytes. Implica que los usuarios probablemente querrán algo más que “solo el tamaño”, pero también otras informaciones. Mantener la longitud no da nada (particularmente ningún lugar natural para almacenarlos) con respecto a estas otras piezas de información útiles.

Dicho esto, no es necesario quejarse en el raro caso en que las cadenas estándar de C sean de hecho ineficientes. Libs están disponibles. Si siguiera esa tendencia, debería quejarme de que el estándar C no incluye ninguna función de soporte de expresiones regulares … pero realmente todo el mundo sabe que no es un problema real, ya que hay bibliotecas disponibles para ese fin. Entonces, cuando se quiere eficiencia en la manipulación de cadenas, ¿por qué no utilizar una biblioteca como bstring ? O incluso cadenas de C ++?

EDITAR : Recientemente eché un vistazo a las cuerdas D. Es lo suficientemente interesante como para ver que la solución elegida no es un prefijo de tamaño ni una terminación cero. Al igual que en C, las cadenas literales encerradas entre comillas dobles son muy cortas para matrices de caracteres inmutables, y el lenguaje también tiene una palabra clave de cadena que significa eso (matriz de caracteres inmutables).

Pero las matrices D son mucho más ricas que las matrices en C. En el caso de las matrices estáticas, la longitud se conoce en tiempo de ejecución, por lo que no es necesario almacenar la longitud. El comstackdor lo tiene en tiempo de comstackción. En el caso de matrices dinámicas, la longitud está disponible, pero la documentación D no indica dónde se guarda. Por lo que sabemos, el comstackdor podría elegir mantenerlo en algún registro, o en alguna variable almacenada lejos de los datos de los caracteres.

En arreglos de caracteres normales o cadenas no literales no hay un cero final, por lo tanto, el progtwigdor tiene que ponerlo él mismo si quiere llamar a alguna función C de D. En el caso particular de cadenas literales, sin embargo, el comstackdor D todavía pone un cero en el fin de cada cadena (para permitir el envío fácil a las cadenas C para facilitar la llamada a la función C?), pero este cero no es parte de la cadena (D no cuenta en el tamaño de la cadena).

Lo único que me decepcionó un poco es que las cadenas se supone que son utf-8, pero la longitud aparentemente aún devuelve una cantidad de bytes (al menos es cierto en mi comstackdor gdc) incluso cuando se utilizan caracteres multi-byte. No está claro si se trata de un error del comstackdor o por propósito. (OK, probablemente me he enterado de lo que pasó.) Para decir al comstackdor D que tu fuente usa utf-8 debes poner una marca de orden de bytes estúpida al principio. Escribo estúpido porque sé que no hay editor haciendo eso, especialmente para UTF- 8 que se supone que es compatible con ASCII).

Creo que tiene razones históricas y encontró esto en wikipedia :

En el momento en que se desarrollaron C (y los idiomas de los que se deriva), la memoria era extremadamente limitada, por lo que usar solo un byte de sobrecarga para almacenar la longitud de una cuerda era atractivo. La única alternativa popular en ese momento, generalmente llamada “cadena de Pascal” (aunque también se usaba en versiones anteriores de BASIC), usaba un byte principal para almacenar la longitud de la cadena. Esto permite que la cadena contenga NUL y hace que la búsqueda de la longitud necesite solo un acceso a la memoria (O (1) (constante)). Pero un byte limita la longitud a 255. Esta limitación de longitud era mucho más restrictiva que los problemas con la cadena C, por lo que la cadena C en general ganó.

Calavera tiene razón , pero como la gente no parece entender su punto, le daré algunos ejemplos de código.

Primero, consideremos qué es C: un lenguaje simple, donde todo el código tiene una traducción bastante directa al lenguaje de la máquina. Todos los tipos encajan en los registros y en la stack, y no requiere un sistema operativo o una gran biblioteca de tiempo de ejecución para ejecutar, ya que estaba destinado a escribir estas cosas (una tarea que es muy adecuada, teniendo en cuenta que ni siquiera es un competidor probable hasta el día de hoy).

Si C tuviera un tipo de string , como int o char , sería un tipo que no encaja en un registro o en la stack, y requeriría la asignación de memoria (con toda su infraestructura de soporte) para ser manejada de cualquier manera. Todo lo cual va en contra de los principios básicos de C.

Entonces, una cadena en C es:

 char s*; 

Entonces, asummos que esto fue con prefijo de longitud. Vamos a escribir el código para concatenar dos cadenas:

 char* concat(char* s1, char* s2) { /* What? What is the type of the length of the string? */ int l1 = *(int*) s1; /* How much? How much must I skip? */ char *s1s = s1 + sizeof(int); int l2 = *(int*) s2; char *s2s = s2 + sizeof(int); int l3 = l1 + l2; char *s3 = (char*) malloc(l3 + sizeof(int)); char *s3s = s3 + sizeof(int); memcpy(s3s, s1s, l1); memcpy(s3s + l1, s2s, l2); *(int*) s3 = l3; return s3; } 

Otra alternativa sería usar una estructura para definir una cadena:

 struct { int len; /* cannot be left implementation-defined */ char* buf; } 

En este punto, toda la manipulación de cadenas requerirá dos asignaciones, lo que, en la práctica, significa que pasarás por una biblioteca para manejarlo.

Lo gracioso es … estructuras así existen en C! Simplemente no se utilizan para su visualización diaria de mensajes para el manejo del usuario.

Entonces, aquí está el punto que está haciendo Calavera: no hay ningún tipo de cadena en C. Para hacer algo con él, debe tomar un puntero y decodificarlo como un puntero a dos tipos diferentes, y luego se vuelve muy relevante cuál es el tamaño de una cadena, y no puede simplemente dejarse como “implementación definida”.

Ahora, C puede manejar la memoria de todos modos, y las funciones de la memoria en la biblioteca (en , ¡incluso!) Proporcionan todas las herramientas que necesita para manejar la memoria como un par de puntero y tamaño. Las llamadas “cadenas” en C se crearon con un solo propósito: mostrar mensajes en el contexto de escribir un sistema operativo destinado a terminales de texto. Y, para eso, la terminación nula es suficiente.

Obviamente, para el rendimiento y la seguridad, querrás mantener la longitud de una cuerda mientras trabajas con ella en lugar de ejecutar repetidamente strlen o su equivalente. Sin embargo, almacenar la longitud en una ubicación fija justo antes de que el contenido de la cadena sea un diseño increíblemente malo. Como Jörgen señaló en los comentarios sobre la respuesta de Sanjit, impide tratar la cola de una cuerda como una cuerda, lo que hace imposible muchas operaciones comunes como path_to_filename o filename_to_extension sin asignar nueva memoria (y incurrir en la posibilidad de falla y error manejo). Y luego, por supuesto, está el problema de que nadie puede acordar cuántos bytes debe ocupar el campo de longitud de cadena (muchos lenguajes malos de “Pascal string” utilizan campos de 16 bits o incluso campos de 24 bits que impiden el procesamiento de cadenas largas).

El diseño de C de dejar que el progtwigdor elija si / dónde / cómo almacenar la longitud es mucho más flexible y poderoso. Pero, por supuesto, el progtwigdor debe ser inteligente. C castiga la estupidez con progtwigs que fallan, se detienen o dan raíz a tus enemigos.

Lazyness, frugalidad de registro y portabilidad teniendo en cuenta la tripa de ensamblaje de cualquier idioma, especialmente C, que está un paso por encima del ensamblaje (heredando así un montón de código heredado de ensamblaje). Usted estaría de acuerdo ya que un carácter nulo sería inútil en esos días ASCII (y probablemente tan bueno como un elemento de control EOF).

veamos en pseudo código

 function readString(string) // 1 parameter: 1 register or 1 stact entries pointer=addressOf(string) while(string[pointer]!=CONTROL_CHAR) do read(string[pointer]) increment pointer 

uso total de 1 registro

caso 2

  function readString(length,string) // 2 parameters: 2 register used or 2 stack entries pointer=addressOf(string) while(length>0) do read(string[pointer]) increment pointer decrement length 

total de 2 registros utilizados

Eso podría parecer miope en ese momento, pero teniendo en cuenta la frugalidad en el código y el registro (que eran PREMIUM en ese momento, el momento en que lo sabes, usan la tarjeta perforada). Por lo tanto, al ser más rápido (cuando la velocidad del procesador se podía contar en kHz), este “Hack” era bastante bueno y portátil para el procesador sin registro con facilidad.

Por el bien de argumento implementaré 2 operaciones de cuerda comunes

 stringLength(string) pointer=addressOf(string) while(string[pointer]!=CONTROL_CHAR) do increment pointer return pointer-addressOf(string) 

complejidad O (n) donde, en la mayoría de los casos, la cadena PASCAL es O (1) porque la longitud de la cuerda está preanclada a la estructura de la cuerda (eso también significaría que esta operación debería realizarse en una etapa anterior).

 concatString(string1,string2) length1=stringLength(string1) length2=stringLength(string2) string3=allocate(string1+string2) pointer1=addressOf(string1) pointer3=addressOf(string3) while(string1[pointer1]!=CONTROL_CHAR) do string3[pointer3]=string1[pointer1] increment pointer3 increment pointer1 pointer2=addressOf(string2) while(string2[pointer2]!=CONTROL_CHAR) do string3[pointer3]=string2[pointer2] increment pointer3 increment pointer1 return string3 

la complejidad O (n) y anteponer la longitud de la cuerda no cambiaría la complejidad de la operación, aunque admito que tomaría 3 veces menos tiempo.

Por otro lado, si usa la cadena PASCAL, debería rediseñar su API para tener en cuenta la longitud de registro y el bit-endianness, la cadena PASCAL obtuvo la conocida limitación de 255 char (0xFF) porque la longitud se almacenó en 1 byte (8bits ), y si quería una cadena más larga (16bits-> cualquier cosa) tendría que tener en cuenta la architecture en una capa de su código, lo que significaría en la mayoría de las API de cadenas incompatibles si desea cadena más larga.

Ejemplo:

Se escribió un archivo con su api de cadena antes de una computadora de 8 bits y luego tendría que leerse en una computadora de 32 bits, ¿qué haría el progtwig perezoso que considera que sus 4 bytes son la longitud de la cadena y luego asignar esa cantidad de memoria luego intenta leer tantos bytes. Otro caso sería PPC 32 byte cadena de lectura (little endian) en un x86 (big endian), por supuesto, si no sabes que uno está escrito por el otro, habría problemas. 1 byte de longitud (0x00000001) se convertiría en 16777216 (0x0100000) que es de 16 MB para leer una cadena de 1 byte. Por supuesto, diría que las personas deberían estar de acuerdo en un estándar, pero incluso el Unicode de 16 bits tiene poca y gran importancia.

Por supuesto, C también tendría sus problemas, pero se vería muy poco afectado por las cuestiones planteadas aquí.

En muchos sentidos, C era primitivo. Y me encantó.

Era un paso por encima del lenguaje ensamblador, que le proporcionaba casi el mismo rendimiento con un lenguaje que era mucho más fácil de escribir y mantener.

The null terminator is simple and requires no special support by the language.

Looking back, it doesn’t seem that convenient. But I used assembly language back in the 80s and it seemed very convenient at the time. I just think software is continually evolving, and the platforms and tools continually get more and more sophisticated.

Assuming for a moment that C implemented strings the Pascal way, by prefixing them by length: is a 7 char long string the same DATA TYPE as a 3-char string? If the answer is yes, then what kind of code should the compiler generate when I assign the former to the latter? Should the string be truncated, or automatically resized? If resized, should that operation be protected by a lock as to make it thread safe? The C approach side stepped all these issues, like it or not 🙂

Somehow I understood the question to imply there’s no compiler support for length-prefixed strings in C. The following example shows, at least you can start your own C string library, where string lengths are counted at compile time, with a construct like this:

 #define PREFIX_STR(s) ((prefix_str_t){ sizeof(s)-1, (s) }) typedef struct { int n; char * p; } prefix_str_t; int main() { prefix_str_t string1, string2; string1 = PREFIX_STR("Hello!"); string2 = PREFIX_STR("Allows \0 chars (even if printf directly doesn't)"); printf("%d %s\n", string1.n, string1.p); /* prints: "6 Hello!" */ printf("%d %s\n", string2.n, string2.p); /* prints: "48 Allows " */ return 0; } 

This won’t, however, come with no issues as you need to be careful when to specifically free that string pointer and when it is statically allocated (literal char array).

Edit: As a more direct answer to the question, my view is this was the way C could support both having string length available (as a compile time constant), should you need it, but still with no memory overhead if you want to use only pointers and zero termination.

Of course it seems like working with zero-terminated strings was the recommended practice, since the standard library in general doesn’t take string lengths as arguments, and since extracting the length isn’t as straightforward code as char * s = "abc" , as my example shows.

The null termination allows for fast pointer based operations.

“Even on a 32 bit machine, if you allow the string to be the size of available memory, a length prefixed string is only three bytes wider than a null terminated string.”

First, extra 3 bytes may be considerable overhead for short strings. In particular, a zero-length string now takes 4 times as much memory. Some of us are using 64-bit machines, so we either need 8 bytes to store a zero-length string, or the string format can’t cope with the longest strings the platform supports.

There may also be alignment issues to deal with. Suppose I have a block of memory containing 7 strings, like “solo\0second\0\0four\0five\0\0seventh”. The second string starts at offset 5. The hardware may require that 32-bit integers be aligned at an address that is a multiple of 4, so you have to add padding, increasing the overhead even further. The C representation is very memory-efficient in comparison. (Memory-efficiency is good; it helps cache performance, for example.)

One point not yet mentioned: when C was designed, there were many machines where a ‘char’ was not eight bits (even today there are DSP platforms where it isn’t). If one decides that strings are to be length-prefixed, how many ‘char’s worth of length prefix should one use? Using two would impose an artificial limit on string length for machines with 8-bit char and 32-bit addressing space, while wasting space on machines with 16-bit char and 16-bit addressing space.

If one wanted to allow arbitrary-length strings to be stored efficiently, and if ‘char’ were always 8-bits, one could–for some expense in speed and code size–define a scheme were a string prefixed by an even number N would be N/2 bytes long, a string prefixed by an odd value N and an even value M (reading backward) could be ((N-1) + M*char_max)/2, etc. and require that any buffer which claims to offer a certain amount of space to hold a string must allow enough bytes preceding that space to handle the maximum length. The fact that ‘char’ isn’t always 8 bits, however, would complicate such a scheme, since the number of ‘char’ required to hold a string’s length would vary depending upon the CPU architecture.

Many design decisions surrounding C stem from the fact that when it was originally implemented, parameter passing was somewhat expensive. Given a choice between eg

 void add_element_to_next(arr, offset) char[] arr; int offset; { arr[offset] += arr[offset+1]; } char array[40]; void test() { for (i=0; i<39; i++) add_element_to_next(array, i); } 

versus

 void add_element_to_next(ptr) char *p; { p[0]+=p[1]; } char array[40]; void test() { int i; for (i=0; i<39; i++) add_element_to_next(arr+i); } 

the latter would have been slightly cheaper (and thus preferred) since it only required passing one parameter rather than two. If the method being called didn't need to know the base address of the array nor the index within it, passing a single pointer combining the two would be cheaper than passing the values separately.

While there are many reasonable ways in which C could have encoded string lengths, the approaches that had been invented up to that time would have all required functions that should be able to work with part of a string to accept the base address of the string and the desired index as two separate parameters. Using zero-byte termination made it possible to avoid that requirement. Although other approaches would be better with today's machines (modern compilers often pass parameters in registers, and memcpy can be optimized in ways strcpy()-equivalents cannot) enough production code uses zero-byte terminated strings that it's hard to change to anything else.

PS--In exchange for a slight speed penalty on some operations, and a tiny bit of extra overhead on longer strings, it would have been possible to have methods that work with strings accept pointers directly to strings, bounds-checked string buffers, or data structures identifying substrings of another string. A function like "strcat" would have looked something like [modern syntax]

 void strcat(unsigned char *dest, unsigned char *src) { struct STRING_INFO d,s; str_size_t copy_length; get_string_info(&d, dest); get_string_info(&s, src); if (d.si_buff_size > d.si_length) // Destination is resizable buffer { copy_length = d.si_buff_size - d.si_length; if (s.src_length < copy_length) copy_length = s.src_length; memcpy(d.buff + d.si_length, s.buff, copy_length); d.si_length += copy_length; update_string_length(&d); } } 

A little bigger than the K&R strcat method, but it would support bounds-checking, which the K&R method doesn't. Further, unlike the current method, it would be possible to easily concatenate an arbitrary substring, eg

 /* Concatenate 10th through 24th characters from src to dest */ void catpart(unsigned char *dest, unsigned char *src) { struct SUBSTRING_INFO *inf; src = temp_substring(&inf, src, 10, 24); strcat(dest, src); } 

Note that the lifetime of the string returned by temp_substring would be limited by those of s and src , which ever was shorter (which is why the method requires inf to be passed in--if it was local, it would die when the method returned).

In terms of memory cost, strings and buffers up to 64 bytes would have one byte of overhead (same as zero-terminated strings); longer strings would have slightly more (whether one allowed amounts of overhead between two bytes and the maximum required would be a time/space tradeoff). A special value of the length/mode byte would be used to indicate that a string function was given a structure containing a flag byte, a pointer, and a buffer length (which could then index arbitrarily into any other string).

Of course, K&R didn't implement any such thing, but that's most likely because they didn't want to spend much effort on string handling--an area where even today many languages seem rather anemic.

According to Joel Spolsky in this blog post ,

It’s because the PDP-7 microprocessor, on which UNIX and the C programming language were invented, had an ASCIZ string type. ASCIZ meant “ASCII with a Z (zero) at the end.”

After seeing all the other answers here, I’m convinced that even if this is true, it’s only part of the reason for C having null-terminated “strings”. That post is quite illuminating as to how simple things like strings can actually be quite hard.

Not a Rationale necessarily but a counterpoint to length-encoded

  1. Certain forms of dynamic length encoding are superior to static length encoding as far as memory is concerned, it all depends on usage. Just look at UTF-8 for proof. It’s essentially an extensible character array for encoding a single character. This uses a single bit for each extended byte. NUL termination uses 8 bits. Length-prefix I think can be reasonably termed infinite length as well by using 64 bits. How often you hit the case of your extra bits is the deciding factor. Only 1 extremely large string? Who cares if you’re using 8 or 64 bits? Many small strings (Ie Strings of English words)? Then your prefix costs are a large percentage.

  2. Length-prefixed strings allowing time savings is not a real thing . Whether your supplied data is required to have length provided, you’re counting at compile time, or you’re truly being provided dynamic data that you must encode as a string. These sizes are computed at some point in the algorithm. A separate variable to store the size of a null terminated string can be provided. Which makes the comparison on time-savings moot. One just has an extra NUL at the end… but if the length encode doesn’t include that NUL then there’s literally no difference between the two. There’s no algorithmic change required at all. Just a pre-pass you have to manually design yourself instead of having a compiler/runtime do it for you. C is mostly about doing things manually.

  3. Length-prefix being optional is a selling point. I don’t always need that extra info for an algorithm so being required to do it for a every string makes my precompute+compute time never able to drop below O(n). (Ie hardware random number generator 1-128. I can pull from an “infinite string”. Let’s say it only generates characters so fast. So our string length changes all the time. But my usage of the data probably doesn’t care how many random bytes I have. It just wants the next available unused byte as soon as it can get it after a request. I could be waiting on the device. But I could also have a buffer of characters pre-read. A length comparison is a needless waste of computation. A null check is more efficient.)

  4. Length-prefix is a good guard against buffer overflow? So is sane usage of library functions and implementation. What if I pass in malformed data? My buffer is 2 bytes long but I tell the function it’s 7! Ex: If gets() was intended to be used on known data it could’ve had an internal buffer check that tested compiled buffers and malloc() calls and still follow spec. If it was meant to be used as a pipe for unknown STDIN to arrive at unknown buffer then clearly one can’t know abut the buffer size which means a length arg is pointless, you need something else here like a canary check. For that matter, you can’t length-prefix some streams and inputs, you just can’t. Which means the length check has to be built into the algorithm and not a magic part of the typing system. TL;DR NUL-terminated never had to be unsafe, it just ended up that way via misuse.

  5. counter-counter point: NUL-termination is annoying on binary. You either need to do length-prefix here or transform NUL bytes in some way: escape-codes, range remapping, etc… which of course means more-memory-usage/reduced-information/more-operations-per-byte. Length-prefix mostly wins the war here. The only upside to a transform is that no additional functions have to be written to cover the length-prefix strings. Which means on your more optimized sub-O(n) routines you can have them automatically act as their O(n) equivalents without adding more code. Downside is, of course, time/memory/compression waste when used on NUL heavy strings. Depending on how much of your library you end up duplicating to operate on binary data, it may make sense to work solely with length-prefix strings. That said one could also do the same with length-prefix strings… -1 length could mean NUL-terminated and you could use NUL-terminated strings inside length-terminated.

  6. Concat: “O(n+m) vs O(m)” I’m assuming your referring to m as the total length of the string after concatenating because they both have to have that number of operations minimum (you can’t just tack-on to string 1, what if you have to realloc?). And I’m assuming n is a mythical amount of operations you no longer have to do because of a pre-compute. If so, then the answer is simple: pre-compute. If you’re insisting you’ll always have enough memory to not need to realloc and that’s the basis of the big-O notation then the answer is even more simple: do binary search on allocated memory for end of string 1, clearly there’s a large swatch of infinite zeros after string 1 for us to not worry about realloc. There, easily got n to log(n) and I barely tried. Which if you recall log(n) is essentially only ever as large as 64 on a real computer, which is essentially like saying O(64+m), which is essentially O(m). (And yes that logic has been used in run-time analysis of real data structures in-use today. It’s not bullshit off the top of my head.)

  7. Concat()/Len() again : Memoize results. Fácil. Turns all computes into pre-computes if possible/necessary. This is an algorithmic decision. It’s not an enforced constraint of the language.

  8. String suffix passing is easier/possible with NUL termination. Depending on how length-prefix is implemented it can be destructive on original string and can sometimes not even be possible. Requiring a copy and pass O(n) instead of O(1).

  9. Argument-passing/de-referencing is less for NUL-terminated versus length-prefix. Obviously because you’re passing less information. If you don’t need length, then this saves a lot of footprint and allows optimizations.

  10. You can cheat. It’s really just a pointer. Who says you have to read it as a string? What if you want to read it as a single character or a float? What if you want to do the opposite and read a float as a string? If you’re careful you can do this with NUL-termination. You can’t do this with length-prefix, it’s a data type distinctly different from a pointer typically. You’d most likely have to build a string byte-by-byte and get the length. Of course if you wanted something like an entire float (probably has a NUL inside it) you’d have to read byte-by-byte anyway, but the details are left to you to decide.

TL;DR Are you using binary data? If no, then NUL-termination allows more algorithmic freedom. If yes, then code quantity vs speed/memory/compression is your main concern. A blend of the two approaches or memoization might be best.

gcc accept the codes below:

char s[4] = “abcd”;

and it’s ok if we treat is as an array of chars but not string. That is, we can access it with s[0], s[1], s[2], and s[3], or even with memcpy(dest, s, 4). But we’ll get messy characters when we trying with puts(s), or worse with strcpy(dest, s).