Implementing ‘strlen’ using SVE
lemire.me
lemire.me
Huh, this is an interesting instruction. Wonder if this will “break” code that expected a read into an unmapped page to fault…
According to some documentation[0], anything after the first element uses the `MemNF` "intrinsic":
if first then
// Mem[] will not return if a fault is detected for the first active element
data = Mem[addr, mbytes, AccType_NORMAL];
first = FALSE;
else
// MemNF[] will return fault=TRUE if access is not performed for any reason
(data, fault) = MemNF[addr, mbytes, AccType_CNOTFIRST];
(value<7:0>, bad) = MemSingleNF[address, 1, acctype, aligned];
if bad then
return (bits(8*size) UNKNOWN, TRUE);
[0]: http://hehezhou.cn/isa/ldff1b_z_p_br.html
[1]: http://hehezhou.cn/isa/shared_pseudocode.html#impl-aarch64.M...
Certainly, “contents of unmapped region” wouldn’t be on the table these days, right?
- Whether subsequent non-faulting elements are loaded as normal, or ignored and treated as also faulting (more relevant for the FF gather variants)
- Whether the faulting elements zero or merge the previous element value of the destination vector
The first one has an awesome typo (I hope, else they're being a bit evil) with a double negative in the text explaining the instruction:
Inactive elements will not not cause a read from Device memory or signal a fault, and are set to zero in the destination vector.
Note the double "not" in the first half. Ouch.
It is a fair assumption these days that no instruction leaves bits in the register "untouched" unless doing so is a core part of what's needed for the instruction to work. On architectures with register renaming (which is all high-performance architectures) it can be surprisingly expensive.
The very least, it forces a dependency on all previous instructions that write that register, and adds another source operand to the instruction. And on most real architectures, this source operand would be required to be present before the instruction itself can start. This is particularly bad for load instructions, if it pushes back when the load can be submitted to cache. This can wipe out all your memory parallelism, and effectively cut your performance to a fraction of what it would othewise be.
The basic mental model you need to have is that every instruction that writes to a register always gets a new register that starts with all bits zeroed. To have anything else, you have to do work.
If you perform a page-crossing load where, say, only elements 0-5 out of 32 elements are loaded, then only elements 0-5 in the predicate register gets set, the loop steps 6 elements instead of 32 elements in this iteration. On the next time around, if you really intended to go past the end, byte 0 of the next page will be in the first element position and goes through normal fault handling.
Lemire's example loop is subtly wrong here, but the version in the SVE slides he links to is fine.
The other advantage is that there’s nothing involved in porting C strings between 8, 16, 32, and 64 bit machines.
Of course, most modern languages will store the length separately (using small string optimization) AND offer a way to convert to a C string (for OS interop).
There’s an argument that taking a substring off a C string a) can be done without allocating a copy b) can be done with pure pointer manipulation. In practice though I’m not sure how critical that case is.
This might work fine in a bank mainframe, but is prohibitively expensive in the minicomputers back in the days.
C is written for Unix. Unix is written with minicomputers in mind. Thus C is somewhat influenced by minicomputers and has to work on their setback in the good ol' days.
You have to think in the historic context.
It causes strictly less indirect access if you store it as part of the string struct, as C++, Go, or Rust do.
It’s more clear today but that’s because we’ve had 20 years of data of various experiments and ideas like small string optimizations on modern architectures that didn’t exist 40+ years ago.
Doesn't seem to be much of an issue in practice, even when strings are 3 words wide (as is the case for C++ and Rust because their strings are mutable[0], Go's strings are not so only 2 words).
Especially as it's a good tradeoff for safety, reliability, gains you performances elsewhere, and allows slicing.
[0] Rust String specifically, &str is immutable and 2 words, C++17 added string_view but I don't know how large it is, or whether it's used much if at all
You can optimize the common case of string data following the header by encoding the fact in a bit of the length field.
E.g. if the length is odd (LSB = 1) then the next word contains the pointer to the string body, otherwise the string body follows the length field. Archs that lack tagged arithmetic would require a shift but at least that skips a memory read for the string data indirection.
Rust supports the same features by storing the length of the string with the pointer. Same thing with other references to dynamically sized memory (slices).
Variable length encodings like varint [1] allows to use 1 byte for small integers and more for large. Zero terminated string will use less memory for large strings, but the difference between 1 (\0) and 3 bytes (varint length) for a 64k string is negligible.
Afaik AmigaOS itself was based on some earlier OS written in B or BCPL language.
PS: Here's some story behind this http://aminet.net/package/dev/misc/BCPL
If you create a C datatype with a length plus characters, now you've got a composite of two types. That's a struct. Most of those excellent properties I describe above are no longer in play. The "length" value is probably wider than the characters after it. Is it going to land on a word boundary? How to copy it around in RAM?
It was a short trip from C code to assembly, and this decision matched the simple elegance of Unix.
Thus the concept of string length itself already depends on different types of string. Unless it is strictly defined like Java and Rust do, you can't be sure what to store in the prefix. And even that makes string interoperability still exceedingly hard.
That's why I have a question though: Why don't people design a "small string" to prepend just one unsigned byte into the string as a fast path to check length? This operation will thus be O(1) if you have a string length less than 255, and if it hits 255/-1, we can determine that it is a long string and fallback to do null check. Other than the stale string issue (which means the actual length does not respect the stoted length) I found no more major issues with that.
Side note: The aforementioned encoding problem gets serious with regards to database collation. Far as I know, Redis used binary collation while other DBMS will need user to determine a default collation, most likely Latin-1.
> There’s an argument that taking a substring off a C string a) can be done without allocating a copy b) can be done with pure pointer manipulation. In practice though I’m not sure how critical that case is.
You can't. What if the original data mutated? To take a substring off a C string without copy in practice, you will at least need a copy-on-write data structure. In some system however this can be done with virtual memory by issuing page fault to redirect to the same source memory. In theory you should use something like a Rope [1] or trie or even some Clojure persistent vector black magic that God knows what the hell is that about [2]
[1]: https://en.wikipedia.org/wiki/Rope_%28data_structure%29?wpro...
[2]: https://hypirion.com/musings/understanding-persistent-vector...
The encoded length. First because it’s necessary, second because it’s C and would not bother with anything else, third because USV length is useless, fourth because grapheme clusters have dependencies on the locale and data files, and are only useful in some cases. And their relation with code units / USVs is irregular (adding USVs can decrease GCs).
> You have the binary length (that is, up to 7 in the emoji example as it could store up to 7 bytes), or you have the canonical length (which is 1 because we have 1 visible emoji symbol).
These numbers aren't really accurate. It depends how you define a "single" emoiji, but there are some that are > 7 utf-8 bytes, and there are some that are > 1 code point. E.g. the rainbow flag is a single graphical symbol that is 14 bytes long and 4 code points
> Far as I know, Redis used binary collation while other DBMS will need user to determine a default collation, most likely Latin-1.
Latin1 is a charset not a collation.
You can replicate the same sort of storage of the string length alongside the buffer itself that other languages have by using structs quite easily.
The devil is in the "just", though. It is actually a hassle to use counted strings when every one else uses ASCIIZ; you sacrifice interoperability for sometimes dubious performance improvements (and sometimes docs because if you're working on a large lib documenting this exhaustively is... exhaustive and boring - and now your users have two issues with your stuff).
Often you can keep track of the length of strings and use the "mem" functions instead of the "str" functions. printf for instance returns the length of the resulting string. The tools to avoid unwanted quadratic behavior are there, the hard part is often to just notice that you "did it again".
char* s = "foo";
But nothing stops you to store strings another way. There is nothing magic in C for this. Just use whatever layout you like.
You "just" need to re-implement any function manipulating strings in all of the C standard library. You can probably re-use the printf family with GCC using a non-standard approach: https://www.gnu.org/software/libc/manual/html_node/Customizi... And you need to write conversion of any library/program/kernel that expects NUL-terminated strings.
And there are libraries that do that, like https://github.com/websnarf/bstrlib (Doc and rationale: https://raw.githubusercontent.com/websnarf/bstrlib/master/bs... ). I've never seen them used in the wild though.