Qual é a razão para sequências terminadas em null?

Por mais que eu ame C e C ++, não posso deixar de coçar minha cabeça na escolha de strings terminadas com nulo:

  • Comprimento de cadeias prefixadas (ou seja, Pascal) existia antes de C
  • As cadeias prefixadas de comprimento tornam vários algoritmos mais rápidos, permitindo uma consulta de duração constante.
  • Seqüências prefixadas de comprimento tornam mais difícil causar erros de saturação de buffer.
  • Mesmo em uma máquina de 32 bits, se você permitir que a cadeia seja do tamanho da memory disponível, uma cadeia de comprimento prefixada terá apenas três bytes mais largos do que uma cadeia terminada com nulo. Em máquinas de 16 bits, este é um byte único. Em máquinas de 64 bits, 4 GB é um limite de comprimento de string razoável, mas mesmo se você quiser expandi-lo para o tamanho da palavra da máquina, as máquinas de 64 bits geralmente têm memory suficiente tornando os sete bytes extras um argumento nulo. Eu sei que o padrão C original foi escrito para máquinas insanamente pobres (em termos de memory), mas o argumento da eficiência não me vende aqui.
  • Praticamente todas as outras linguagens (por exemplo, Perl, Pascal, Python, Java, C #, etc) usam strings com comprimento prefixado. Essas linguagens geralmente vencem C nos benchmarks de manipulação de strings porque são mais eficientes com strings.
  • C ++ corrigiu isso um pouco com o modelo std::basic_string , mas os arrays de caracteres simples que esperam sequências de caracteres terminadas com valores nulos ainda são abrangentes. Isso também é imperfeito porque requer alocação de heap.
  • Seqüências terminadas em nulos precisam reservar um caractere (a saber, nulo), que não pode existir na cadeia, enquanto cadeias prefixadas com comprimento podem conter nulos incorporados.

Várias dessas coisas vieram à tona mais recentemente do que C, então faria sentido que C não soubesse delas. No entanto, vários eram bem claros antes de C aparecer. Por que seqüências terminadas em null foram escolhidas em vez do prefixo de comprimento obviamente superior?

EDIT : Uma vez que alguns pediu fatos (e não gostou dos que eu já forneci) no meu ponto de eficiência acima, eles resultam de algumas coisas:

  • Concat usando cadeias terminadas com nulo requer complexidade de tempo O (n + m). O prefixo de comprimento geralmente requer apenas O (m).
  • Comprimento usando cadeias terminadas com nulo requer complexidade de tempo O (n). O prefixo de comprimento é O (1).
  • Comprimento e concat são de longe as operações de string mais comuns. Existem vários casos em que as sequências terminadas com valores nulos podem ser mais eficientes, mas estas ocorrem com menor frequência.

A partir das respostas abaixo, há alguns casos em que as sequências terminadas com valores nulos são mais eficientes:

  • Quando você precisar cortar o início de uma string e precisar passá-la para algum método. Você não pode fazer isso em tempo constante com prefixos de comprimento, mesmo se tiver permissão para destruir a string original, porque o prefixo de comprimento provavelmente precisa seguir as regras de alinhamento.
  • Em alguns casos em que você está apenas passando o caractere de string por caractere, você pode salvar um registrador de CPU. Note que isto funciona somente no caso de você não ter alocado dinamicamente a string (porque você teria que liberá-la, precisando usar o registro da CPU que você salvou para manter o ponteiro que você obteve originalmente de malloc e amigos).

Nenhuma das opções acima é quase tão comum quanto o comprimento e a concatitude.

Há mais um afirmado nas respostas abaixo:

  • Você precisa cortar o final da string

mas este é incorreto – é a mesma quantidade de tempo para sequências com terminação nula e comprimento prefixado. (As strings terminadas em Null apenas colocam um valor nulo onde você deseja que a nova extremidade seja, e os prefixadores de comprimento apenas subtraem do prefixo.)

Da boca do cavalo

Nenhum dos BCPL, B ou C suporta dados de caracteres fortemente na linguagem; Cada um trata cadeias de caracteres muito parecidas com vetores de inteiros e complementa regras gerais por algumas convenções. Tanto no BCPL quanto no B, uma string literal indica o endereço de uma área estática inicializada com os caracteres da string, compactada nas células. No BCPL, o primeiro byte compactado contém o número de caracteres na string; em B, não há contagem e strings são terminadas por um caractere especial, que B soletra *e . Essa mudança foi feita parcialmente para evitar a limitação do comprimento de uma string causada pela retenção da contagem em um slot de 8 ou 9 bits, e em parte porque manter a contagem pareceu, em nossa experiência, menos conveniente do que usar um terminador.

Dennis M Ritchie, Desenvolvimento da Linguagem C

C não tem uma string como parte da linguagem. Uma ‘string’ em C é apenas um ponteiro para char. Então talvez você esteja fazendo a pergunta errada.

“Qual é a razão para deixar de fora um tipo de string” pode ser mais relevante. Para isso, gostaria de salientar que C não é uma linguagem orientada a objects e tem apenas tipos básicos de valor. Uma string é um conceito de nível superior que deve ser implementado de alguma forma combinando valores de outros tipos. C está em um nível inferior de abstração.

à luz da raiva abaixo:

Eu só quero salientar que não estou tentando dizer que esta é uma pergunta estúpida ou ruim, ou que a maneira C de representar strings é a melhor escolha. Eu estou tentando esclarecer que a questão seria mais sucinta se você levar em conta o fato de que C não tem nenhum mecanismo para diferenciar uma string como um tipo de dados de uma matriz de bytes. Esta é a melhor escolha à luz do poder de processamento e memory dos computadores de hoje? Provavelmente não. Mas retrospectiva é sempre 20/20 e tudo o que 🙂

A pergunta é feita como uma Length Prefixed Strings (LPS) versus zero terminated strings (SZ) , mas expõe principalmente os benefícios das strings prefixadas de comprimento. Isso pode parecer esmagador, mas, para ser honesto, devemos também considerar as desvantagens do LPS e as vantagens do SZ.

Pelo que entendi, a questão pode até ser entendida como uma forma tendenciosa de perguntar “quais são as vantagens de Zero Terminated Strings?”.

Vantagens (vejo) de sequências com terminação zero:

  • muito simples, não há necessidade de introduzir novos conceitos na linguagem, char arrays / char pointers podem fazer.
  • a linguagem principal apenas inclui o mínimo de açúcar sintático para converter algo entre aspas duplas para um monte de caracteres (na verdade, um monte de bytes). Em alguns casos, ele pode ser usado para inicializar coisas completamente não relacionadas ao texto. Por exemplo, o formato de arquivo de imagem xpm é uma fonte C válida que contém dados de imagem codificados como uma string.
  • a propósito, você pode colocar um zero em uma string literal, o compilador irá simplesmente adicionar outro no final do literal: "this\0is\0valid\0C" . É uma corda? ou quatro cordas? Ou um monte de bytes …
  • implementação plana, nenhuma indirecção oculta, nenhum inteiro oculto.
  • nenhuma alocação de memory oculta envolvida (bem, algumas funções não padrão infames como strdup executam alocação, mas isso é principalmente uma fonte de problemas).
  • nenhum problema específico para hardware pequeno ou grande (imagine o fardo de gerenciar o comprimento do prefixo de 32 bits em microcontroladores de 8 bits ou as restrições de limitar o tamanho da cadeia a menos de 256 bytes, que era um problema que tive com o Turbo Pascal há eons atrás).
  • implementação de manipulação de string é apenas um punhado de function de biblioteca muito simples
  • eficiente para o uso principal de strings: texto constante lido seqüencialmente a partir de uma partida conhecida (principalmente mensagens para o usuário).
  • o zero final não é obrigatório, todas as ferramentas necessárias para manipular caracteres como um monte de bytes estão disponíveis. Ao executar a boot de array em C, você pode até evitar o terminador NUL. Basta definir o tamanho certo. char a[3] = "foo"; é válido C (não C ++) e não colocará um zero final em a.
  • coerente com o ponto de vista unix “tudo é arquivo”, incluindo “arquivos” que não têm comprimento intrínseco como stdin, stdout. Você deve lembrar que as primitivas de leitura e gravação abertas são implementadas em um nível muito baixo. Eles não são chamadas de biblioteca, mas chamadas de sistema. E a mesma API é usada para arquivos binários ou de texto. As primitivas de leitura de arquivo obtêm um endereço de buffer e um tamanho e retornam o novo tamanho. E você pode usar strings como o buffer para escrever. Usar outro tipo de representação de string implicaria que você não pode facilmente usar uma string literal como o buffer para a saída, ou você teria que fazer com que ela tenha um comportamento muito estranho ao lançá-la para char* . Ou seja, não retornar o endereço da string, mas sim retornar os dados reais.
  • muito fácil de manipular dados de texto lidos de um arquivo in-loco, sem cópia inútil do buffer, basta inserir zeros nos locais certos (bem, não realmente com C moderno como strings entre aspas duplas são arrays const char agora geralmente mantidos em dados não modificáveis segmento).
  • preceder alguns valores int de qualquer tamanho implicaria em problemas de alinhamento. O comprimento inicial deve ser alinhado, mas não há razão para fazer isso para os dados dos caracteres (e, novamente, forçar o alinhamento de strings implicaria em problemas ao tratá-los como um grupo de bytes).
  • length é conhecido em tempo de compilation por strings literais constantes (sizeof). Então, por que alguém iria querer armazená-lo na memory antes de os dados reais?
  • de certa forma, C está fazendo como (quase) todo mundo, strings são vistas como arrays de char. Como o comprimento da matriz não é gerenciado por C, o comprimento lógico não é gerenciado para cadeias de caracteres. A única coisa surpreendente é que 0 item foi adicionado no final, mas isso é apenas no nível da linguagem principal ao digitar uma string entre aspas duplas. Os usuários podem chamar perfeitamente as funções de manipulação de strings passando o comprimento, ou até mesmo usar memcopy simples. SZ são apenas uma facilidade. Na maioria das outras linguagens, o comprimento do array é gerenciado, é lógico que é o mesmo para strings.
  • nos tempos modernos, de qualquer modo, conjuntos de caracteres de 1 byte não são suficientes e você geralmente tem que lidar com sequências unicode codificadas onde o número de caracteres é muito diferente do número de bytes. Isso implica que os usuários provavelmente vão querer mais do que “apenas o tamanho”, mas também outras informações. Manter o comprimento não oferece nada (particularmente nenhum lugar natural para armazená-los) em relação a essas outras informações úteis.

Dito isto, não há necessidade de reclamar no caso raro em que as sequências C padrão são realmente ineficientes. Libs estão disponíveis. Se eu seguisse essa tendência, eu deveria reclamar que o padrão C não inclui nenhuma function de suporte ao regex … mas na verdade todo mundo sabe que não é um problema real, pois há bibliotecas disponíveis para esse propósito. Portanto, quando a eficiência da manipulação de strings é desejada, por que não usar uma biblioteca como bstring ? Ou até mesmo strings C ++?

EDIT : Recentemente, eu tinha um olhar para cordas de D. É interessante o suficiente para ver que a solução escolhida não é um prefixo de tamanho nem uma terminação zero. Como em C, as strings literais entre aspas duplas são apenas curtas para matrizes de char imutáveis, e a linguagem também tem uma palavra-chave string que significa (matriz de char imutável).

Mas os arrays D são muito mais ricos que os arrays C. No caso de matrizes estáticas, o comprimento é conhecido em tempo de execução, portanto não há necessidade de armazenar o comprimento. Compiler tem em tempo de compilation. No caso de matrizes dinâmicas, o comprimento está disponível, mas a documentação D não indica onde é mantida. Por tudo o que sabemos, o compilador pode optar por mantê-lo em algum registro, ou em alguma variável armazenada longe dos dados dos caracteres.

Em matrizes char normais ou strings não literais, não há zero final, portanto o programador tem que colocá-lo se ele quiser chamar alguma function C de D. No caso particular de strings literais, entretanto o compilador de D ainda coloca um zero no fim de cada strings (para permitir fácil conversão para strings C para facilitar a chamada da function C?), mas este zero não faz parte da string (D não o conta no tamanho da string).

A única coisa que me decepcionou um pouco é que as strings devem ser utf-8, mas o comprimento aparentemente ainda retorna um número de bytes (pelo menos é verdade no meu compilador gdc), mesmo quando se usa caracteres multi-byte. Não está claro para mim se é um erro de compilador ou por finalidade. (OK, eu provavelmente descobri o que aconteceu. Para dizer ao compilador de D seu uso de fonts utf-8 você tem que colocar algum ponto de ordem de byte estúpido no começo. Eu escrevo estúpido porque eu sei de não fazer isso, especialmente para UTF- 8 que é suposto ser compatível com ASCII).

Eu acho, tem razões históricas e achei isso na Wikipédia :

Na época em que o C (e os idiomas dos quais ele derivava) foram desenvolvidos, a memory era extremamente limitada, portanto, usar apenas um byte de sobrecarga para armazenar o comprimento de uma string era atraente. A única alternativa popular na época, geralmente chamada de “string Pascal” (embora também usada por versões anteriores do BASIC), usava um byte inicial para armazenar o tamanho da string. Isso permite que a string contenha NUL e fez com que a busca demorasse apenas um access à memory (O (1) (constante) tempo). Mas um byte limita o comprimento a 255. Essa limitação de comprimento era muito mais restritiva que os problemas com a string C, então a string C em geral venceu.

Calavera está certo , mas como as pessoas parecem não entender, vou fornecer alguns exemplos de código.

Primeiro, vamos considerar o que C é: uma linguagem simples, em que todo o código tem uma tradução bastante direta para a linguagem de máquina. Todos os tipos se encheckboxm em registradores e na pilha, e não requer um sistema operacional ou uma grande biblioteca de tempo de execução para executar, uma vez que foram feitos para escrever essas coisas (uma tarefa para a qual é soberbamente adequada, considerando que nem é um concorrente provável até hoje).

Se C tivesse um tipo de string , como int ou char , seria um tipo que não caberia em um registrador ou na pilha, e exigiria alocação de memory (com toda sua infra-estrutura de suporte) para ser manipulada de qualquer forma. Todas as quais vão contra os princípios básicos de C.

Então, uma string em C é:

 char s*; 

Então, vamos supor que isso tenha o prefixo do comprimento. Vamos escrever o código para concatenar duas strings:

 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; } 

Outra alternativa seria usar uma estrutura para definir uma string:

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

Nesse ponto, toda a manipulação de strings exigiria duas alocações a serem feitas, o que, na prática, significa que você passaria por uma biblioteca para fazer qualquer manipulação dela.

O engraçado é que … estruturas como essa existem em C! Eles simplesmente não são usados ​​para o seu dia-a-dia exibindo mensagens para o manuseio do usuário.

Então, aqui está o ponto que Calavera está fazendo: não há nenhum tipo de string em C. Para fazer qualquer coisa com isso, você teria que pegar um ponteiro e decodificá-lo como um ponteiro para dois tipos diferentes, e então se torna muito relevante o que é o tamanho de uma string, e não pode simplesmente ser deixado como “implementação definida”.

Agora, C pode manipular a memory de qualquer maneira, e as funções mem na biblioteca (em , até!) Fornecem todas as ferramentas que você precisa para manipular memory como um par de ponteiro e tamanho. As chamadas “strings” em C foram criadas com uma única finalidade: mostrar mensagens no contexto de escrever um sistema operacional destinado a terminais de texto. E, para isso, a terminação nula é suficiente.

Obviamente, para desempenho e segurança, você desejará manter o comprimento de uma string enquanto estiver trabalhando com ela, em vez de executar repetidamente strlen ou o equivalente nela. No entanto, armazenar o comprimento em um local fixo logo antes do conteúdo da string é um design incrivelmente ruim. Como Jörgen apontou nos comentários sobre a resposta de Sanjit, ela impede tratar a cauda de uma string como uma string, que por exemplo impossibilita muitas operações comuns como path_to_filename ou filename_to_extension sem alocar nova memory (e incorrer na possibilidade de falha e erro manipulação). E, claro, há o problema de que ninguém pode concordar com quantos bytes o campo de comprimento de string deve ocupar (muitos idiomas “Pascal string” ruins usavam campos de 16 bits ou até mesmo campos de 24 bits que impedem o processamento de strings longas).

O projeto de C de deixar o programador escolher se / onde / como armazenar o comprimento é muito mais flexível e poderoso. Mas é claro que o programador tem que ser inteligente. C pune a estupidez com programas que falham, param, ou dão raiz aos seus inimigos.

Preguiça, registre a frugalidade e a portabilidade considerando o conjunto de linguagens de assembly, especialmente C, que é um passo acima da assembly (herdando, portanto, muito código de legado de assembly). Você concordaria que um caractere nulo seria inútil naqueles dias ASCII (e provavelmente tão bons quanto um caractere de controle de EOF).

vamos ver no 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 

registo total 2 usado

Isso pode parecer míope naquela época, mas considerando a frugalidade no código e no registro (que eram PREMIUM naquele momento, quando você sabe, eles usam cartão perfurado). Assim, sendo mais rápido (quando a velocidade do processador pode ser contada em kHz), esse “Hack” foi muito bom e portátil para registrar o processador com menos facilidade.

Por causa do argumento eu implementarei 2 operações de string comuns

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

complexidade O (n) onde, na maioria dos casos, a cadeia PASCAL é O (1) porque o comprimento da cadeia é pré-pendente para a estrutura de cadeia (isso também significaria que essa operação teria que ser executada em um estágio 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 

complexidade O (n) e prepending o comprimento da string não mudaria a complexidade da operação, enquanto eu admito que levaria 3 vezes menos tempo.

Por outro lado, se você usar cadeia PASCAL você teria que redesenhar sua API para levar em conta o comprimento do registro e bit-endianness, PASCAL string tem a limitação bem conhecida de 255 caracteres (0xFF) porque o tamanho foi armazenado em 1 byte (8bits ), e você queria uma string mais longa (16bits-> qualquer coisa) você teria que levar em conta a arquitetura em uma camada do seu código, o que significaria, na maioria dos casos, APIs de strings incompatíveis se você quisesse uma string mais longa.

Exemplo:

Um arquivo foi escrito com sua API de seqüência de caracteres em um computador de 8 bits e, em seguida, teria que ser lido em um computador de 32 bits, o que o programa faria considerando que seus 4 bytes são o comprimento da seqüência e alocar esse lote de memory então tente ler muitos bytes. Outro caso seria PPC 32 byte string read (little endian) em um x86 (big endian), claro que se você não souber que um é escrito pelo outro, haverá problemas. Comprimento de 1 byte (0x00000001) seria 16777216 (0x0100000) que é 16 MB para ler uma cadeia de 1 byte. É claro que você diria que as pessoas devem concordar com um padrão, mas até mesmo um unicode de 16 bits tem pouca ou grande força.

É claro que C também teria seus problemas, mas seria muito pouco afetado pelas questões levantadas aqui.

De muitas maneiras, C era primitivo. E eu adorei.

It was a step above assembly language, giving you nearly the same performance with a language that was much easier to write and maintain.

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).