Efficient alternate representations for lists of characters (strings).

[UWN]

Consider to add an internal string data type as an alternate representation for lists of characters:

Complete strings

The tagged value is a byte-aligned pointer to a null-terminated sequence of UTF-8 characters on the heap (copy stack). This means that the full address-space of 32/64 bits cannot be used but some (1 or two) bits less than that. In many systems this is not a problem since the operating systems already makes similar assumptions anyway.

A list of n characters [C1, ..., CN] would thus occupy between n+1 and n+8 bytes, depending on alignment, whereas the naive representation as a list of chars would take n · (3 · 8) bytes.

In this manner, the "tail" of the strings can be rapidly (constantly) computed which is key for fast parsing with DCGs. Note that SWI7's built-in string requires for sub_string(String, 1, _, 0, Tail) time and space proportional to the length of String.

Then, all operations from unification upwards need to be able to handle both lists of chars and that string type. That is indeed the more challenging part.

Partial strings

This would take the idea one step further. Instead of representing a list of known characters, a partial list of known characters would be represented compactly. E.g. Xs0 = [a,b,c,d|Xs] would be represented as a null-terminated string "abcd" plus padding to the next word which represents Xs. This would make library(pio) very fast!

Just as a remark: Strings that contain the null-character can still be represented as a regular lists of characters.

[mthom]

Should there be a specialized syntactic form for the introduction of partial strings? Something like X = diff_string("abc"), so that X unifies against [a,b,c|Y] (but Y remains free) maybe?

[UWN]

if you want to have something special for it, then use a built-in predicate. Like list_to_compactlist/2 or the like. But not a special functor as diff_string/1.

[UWN]

But most of the time there will be built-ins (like those for library(pio)) that will generate compact representations. Or think of atom_chars/2, number_chars/2.

Another option is to produce a compact representation during garbage collection. But rather leave this for a much later phase.

[bakaq]

Ok, from what I was able to understand by reading this, #95 and the source code at different points in time, it seems that Scryer once did implement partial strings as intended (inline in the heap) using RawBlock. But after redoing the heap representation in 0404c3b it fell back into allocating the strings in the atom table instead of in the heap. The new representation is really nice, but I think it has to be changed again to enable inline heap partial strings.

Ideally we could just interpret a pointer into the heap as either a HeapCellValue or a str buffer, but I don't even know if it is actually "allowed" (in the sense of Undefined Behavior) to do something like this in Rust. It certainly isn't in C¹, because of strict aliasing. I need to research this better.

A better way may be to represent a HeapCellValue as an enum of the current representation and [u8; 8], and then implement a bazillion traits to make it actually work as intended. This would be a big architectural change, but way more safe, if it is possible.

Footnotes

1. Actually, this would be legal in C because you can alias any type by char* if I remember correctly. ↩

[mthom]

Partial strings were never allocated in the heap, no.. pointers in the heap owned string instances that were allocated with the global allocator.