C 实现可以使用长度前缀字符串 "under the hood" 吗？

Question

读完这个问题后：我开始想知道，究竟是什么阻止了 C 实现为分配在堆栈或堆并将它们用作 "string prefix" 来存储其元素的数量 N?

那么，如果第N个字符是'[=15=]'，N - 1表示字符串长度。

我相信这可以极大地提高 strlen 或 strcat 等函数的性能。

如果程序广泛使用非 0 终止的 char 数组，这可能会导致额外的内存消耗，但这可以通过编译器标志打开或关闭常规 "count-until-you-reach-'[=15=]'" 编译代码例程。

这样的实施可能会遇到哪些障碍？ C标准是否允许这样做？这项技术会导致哪些我没有考虑到的问题？

还有...这真的做过吗？

Answer 1

可以存储分配的长度。 malloc 实现确实做到了这一点（或者至少有一些实现）。

但是，您不能合理地存储分配中存储的任何字符串的长度，因为用户可以随心所欲地更改内容；保持最新的长度是不合理的。此外，用户可能会在字符数组的中间某处开始字符串，或者甚至可能不会使用数组来保存字符串！

Answer 2

如果有用的话，没有什么能从根本上阻止您在您的应用程序中执行此操作（其中一条评论指出了这一点）。但是，会出现两个问题：

您必须重新实现所有的字符串处理函数，并具有 my_strlen、my_strcpy 等，并添加字符串创建函数。这可能很烦人，但这是一个有限的问题。
你必须阻止人，在为系统编写时，有意或自动地将关联的字符数组视为“普通”C 字符串，并且在他们身上使用通常的功能。您可能必须确保此类用法会立即中断。

这意味着，我认为，将重新实现的“C 字符串”走私到现有程序中是不可行的。

类似

typedef struct {
    size_t len;
    char* buf;
} String;
size_t my_strlen(String*);
...

可能有效，因为类型检查会阻碍 (2)（除非有人决定“为了效率”而破解某些东西，在这种情况下你无能为力）。

当然，除非并且直到您证明字符串管理是代码中的瓶颈并且这种方法可证明改进了一些东西，否则您不会这样做....

Answer 3

Then, if the N-th character is '[=12=]', N - 1 would signify the string length.

实际上，不，这就是为什么这个建议行不通的原因。

如果我用 0 覆盖字符串中的字符，我就有效地截断了字符串，随后对字符串 的 strlen 调用必须 return 截断的长度。（这通常由应用程序完成，包括 (f)lex 生成的每个扫描器，以及 strtok 标准库函数。等等。）

此外，对字符串的内部字节调用 strlen 是完全合法的。

例如（仅用于演示目的，尽管我敢打赌您可以找到与此几乎相同的常用代码。）

/* Split a string like 'key=value...' into key and value parts, and
 * return the value, and optionally its length (if the second argument
 * is not a NULL pointer). 
 * On success, returns the value part and modifieds the original string
 * so that it is the key.
 * If there is no '=' in the supplied string, neither it nor the value
 * pointed to by plen are modified, and NULL is returned.
 */
char* keyval_split(char* keyval, int* plen) {
  char* delim = strchr(keyval, '=');
  if (delim) {
    if (plen) *plen = strlen(delim + 1)
    *delim = 0;
    return delim + 1;
  } else {
    return NULL;
  }
}

Answer 4

这种方法有几个问题。首先，您将无法创建任意长的字符串。如果你只保留 1 个字节的长度，那么你的字符串最多只能有 255 个字符。您当然可以使用更多字节来存储长度，但是有多少？ 2？ 4？

如果您尝试连接两个都在其大小限制边缘的字符串（即，如果您使用 1 个字节的长度并尝试将两个 250 个字符的字符串相互连接，会发生什么情况）？您是否只是根据需要向长度添加更多字节？

其次，您将此元数据存储在何处？它必须以某种方式与字符串相关联。这类似于 Dennis Ritchie 运行在他用 C 实现数组时遇到的问题。最初，数组对象存储一个指向数组第一个元素的显式指针，但是当他将 struct 类型添加到语言，他意识到他不希望元数据使 struct 对象在内存中的表示变得混乱，因此他摆脱了它并引入了在大多数情况下数组表达式转换为指针表达式的规则。

您可以创建一个新的聚合类型，例如

struct string
{
  char *data;
  size_t len;
};

但是你将无法使用 C 字符串库来操作该类型的对象；实现仍然必须支持现有接口。

您可以将长度存储在字符串的前导字节或字节中，但是您保留了多少？您可以使用可变数量的字节来存储长度，但现在您需要一种方法来区分长度字节和内容字节，并且您不能通过简单地取消引用指针来读取第一个字符。 strcat 之类的函数必须知道如何绕过长度字节，如果长度字节数发生变化，如何调整内容等。

以 0 结尾的方法有其缺点，但它也更容易实现并且使操作字符串更容易。

Answer 5

标准库中的字符串方法定义了语义。如果生成包含各种值的 char 数组，并将指针传递给数组或其一部分，则其行为根据 NUL 字节定义的方法必须以与定义相同的方式搜索 NUL 字节按标准。

可以定义自己的字符串处理方法，使用更好的字符串存储形式，并简单地假装标准库中与字符串相关的函数不存在，除非必须将字符串传递给 fopen.这种方法的最大困难是，除非使用不可移植的编译器功能，否则不可能使用内联字符串文字。而不是说：

ns_output(my_file, "This is a test"); // ns -- new string

有人会说得更像：

MAKE_NEW_STRING(this_is_a_test, "This is a test");
ns_output(my_file, this_is_a_test);

其中宏 MAKE_NEW_STRING 将创建一个匿名类型的联合，定义一个名为 this_is_a_test 的实例，并适当地初始化它。由于很多字符串都是不同的匿名类型，类型检查将要求字符串是包含已知数组类型成员的联合，并且应该为期望字符串的代码提供该成员的指针，可能使用类似：

#define ns_output(f,s) (ns_output_func((f),(s).stringref))

可以定义类型以避免需要 stringref 成员并让代码只接受 void*，但 stringref 成员本质上会执行静态鸭子-typing（只有具有 stringref 成员的东西才能被赋予这样的宏）并且还可以允许对 stringref 本身的类型进行类型检查。

如果可以接受这些约束，我认为可以编写出在几乎所有方面都比零终止字符串更高效的代码；问题是这些优势是否值得麻烦。

C 实现可以使用长度前缀字符串 "under the hood" 吗？

Can a C implementation use length-prefixed-strings "under the hood"?

c

compiler-construction

c-strings

null-terminated

compiler-optimization