I'm somehow disappointed (quite unreasonably, of course) that the code uses plain old zero-terminated C strings instead of something more exotic. One of the fun things about assembly is that you get to reinvent basic language features on the fly -- calling conventions, data layout, strings, everything.
https://github.com/torvalds/linux/blob/fb65d872d7a8dc629837a...
(Hence the need for the strncpy_from_user()-function: https://github.com/torvalds/linux/blob/fb65d872d7a8dc629837a...)
If you null-terminate a length-prefixed string, what if there's a null in the middle of the string?
(1) Allow inconsistency, and go with the length prefix in case of inconsistency. You could allow null bytes in the middle, treating it as a normal length-prefixed string, but then why do you null-terminate the string? (Is it so that you can still pass the string to functions that will choke on embedded nulls? Why would you do that?) This is just asking for kernel bugs.
(2) Allow inconsistency and go with the position of the first null byte in the case of inconsistency. If the length prefix is inconsistent with the position of the first null byte, you could go with the position of the first null byte, but then why even have the length prefix?
(3) Disallow inconsistency. You could disallow embedded nulls, but then the length prefix is just there as a place to cache strlen calls? If you're defining a syscall interface and requiring the length and first null to be consistent, then you need to run strlen anyway in order to sanity check what userspace gave you... why not simplify the external interface to just be either null-terminated or length-prefixed?
The length prefix is the only thing you use, ordinarily. The only time the null comes into play is if you've already had a bug.
Think of it like a stack protector.
... but one that doesn't terminate execution, but instead hides your bugs. In most use cases, I'd prefer to find my bugs in the majority of cases, rather than to hide the bugs except for corner cases.
The original 1984 Elite computer game is famous for its huge galaxy full of planets. Each of them had individual names and descriptions such as "Lave is most famous for its vast rain forests and the Laveian tree grub."
Yet those strings were never stored as plain strings. The game had to run in 32kB of memory, so almost all strings were stored in a tokenized form and expanded using a pseudo-random number generator:
http://wiki.alioth.net/index.php/Random_number_generator
That article shows how the planet description strings were stored and reconstructed on the fly. The base representation for the aforementioned description of planet Lave was only a handful of bytes: "\x8F is \x97"
So I think Elite is a pretty good example of an application written in assembly that didn't have anything like a generic string type.
push rax ; save our registers
push rdi
push rsi
mov rsi, location ; get the pointer to the right place
mov rdi, destination
beginning:
mov rax, [rsi] ; copy contents to the register so we can compare
test rax, rax ; compare our source to itself, if it's zero, it'll set a flag
jz done ; we're done
movsb ; copy the byte, increment the rsi and rdi registers
jmp beginning
done:
pop rsi ; restore our registers
pop rdi
pop rax
push rcx ; using a different register here
push rdi
push rsi
mov rsi, location ; same as before
mov rcx, length ; moving our length into the counter register
mov rdi, destination
cld ; okay our first change. Clearing the direction flag so the copy
; goes from the first byte to the end
rep movsb ; it'll repeat cx times the movsb command, and then carry on
pop rsi ; restoring our registers
pop rdi
pop rcx
e.g. a really basic example for a web server would be splitting up a URL into a path and query string: both strings can use the underlying URL without any copying.
In fact the best, alignment-sensitive solution I've never seen written. It would load 2 large words, shift them to target alignment if needed, store, load, repeat. This would guarantee aligned fetch/store and still do whole-bus operations.
I've waited to see an instruction to do this in any machine ever (why do we have to hand-code this kind of thing, when the processor chip KNOWS the best way to get it done?) I've waited 20 years.
It's hard to do this safely for strcpy/strcmp because you might read past the end of the buffer when trying to test against a null terminator. memcmp/memcpy and length-prefixed blocks let you use a Duff's-Device-like construct to test only the last word byte-by-byte.
I've waited to see an instruction to do this in any machine ever (why do we have to hand-code this kind of thing, when the processor chip KNOWS the best way to get it done?) I've waited 20 years.
Look up "enhanced REP MOVSB"; this link may also be interesting reading: https://software.intel.com/en-us/forums/topic/275765
REP STOS (memset) has also gotten the same boost throughout the generations of x86, and if the trend continues I'd expect REP CMPS and LODS to get the same treatment. These string instructions are tiny (1-2 bytes) and yet very powerful; their greatest advantage is that they don't take up the astoundingly large amount of space in the icache that some extremely micro-optimised routines (i.e. ridiculous amounts of loop unrolling) do.
Java IIRC also uses a length-oriented format for string constants in .class files. [1] It's been a while since I wrote a .java to MIPS asm compiler in C++ from scratch (don't ask).
This is because real-world strings may contain 0 to N NULs and escaping them is too much of a PITA for serialized formats, so it's easier and common to do things like TYPE LENGTH DATA de/serialization. For modern, efficient binary de/ser, check out binc and msgpack [2,3].
0: http://math.uww.edu/~harrisb/courses/cs171/strings.html
1: https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.ht...
http://en.m.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuf...
Basically eliminates a null in a byte stream so it can be used as a terminator.
I think even counting number of UTF-8 code points in a string is faster in UTF-8 than in UTF-16, if you're allowed to use SSE2/AVX2/AVX-512, because all UTF-8 sequences start with a byte that has highest bit 0, all other bytes in the sequence have highest bit 1.
So just SIMD vector compare [1] to find all "positive" bytes (highest bit == 0), which gives you a nice mask. Then move the mask to a general purpose register [2] and popcount [3] it. 16/32/64 (SSE2/AVX2/AVX-512) bytes processed at a time, no branches other than loop control branch.
You can use the same idea to quickly scan UTF-8 string to approximately right position to retrieve a given (random) code point index. Still O(n), but with 10-50x smaller constant factor. If that's not enough, you can simply pre-index every n-th code point (say, every 64/128/256th) in a separate array for larger UTF-8 strings. That gives you constant time random access.
[1]: http://www.felixcloutier.com/x86/PCMPGTB:PCMPGTW:PCMPGTD.htm...
[2]: http://www.felixcloutier.com/x86/PMOVMSKB.html
[3]: http://www.felixcloutier.com/x86/POPCNT.html
Note: UTF-8 code points start either 0xxxxxxx or 11xxxxxx. Regardless of this the basic idea should work, just need to do two compares and to bitwise-or the masks. At the end, AVX-512 of course would use mask-register (k0-k7) and AVX2 would probably need to convert the mask in two parts, once for both 128-bit register halves.
Note 2: Thinking about it a bit more, I think it's enough to check if signed bytes are greater or equal than -64 (0xc0)! This covers bit patterns from 11000000 (-64) to 01111111 (127); all the sequences that can start a sequence. So no two compares and bitwise-or needed after all.
It basically counts continuation bytes (which all start 10xxxxxx) and substracts, rather than trying to count characters.
Additionally, if you know how many bytes are in the string, you can remove the check for the null terminator.
Only tested with long 30 MB strings.
Edit: Now at 26%. But it can still be improved more. Both benchmarks are with hot cache.
new_strlen_utf8 12352856 clock cycles
cp_strlen_utf8 47544818 clock cycles
Edit 3: Ended up at 35% (2.9x) execution time for 64-bit and 18% (5.5x) for 32-bit. My version is as fast in 32 and 64-bit, but cp_strlen_utf8 benefits quite a bit from 64-bit mode. Probably memory bandwidth limited at this point, but I didn't profile yet. In any case, it does utf-8 code point strlen at 16 GB/s at this point. CPU is i5-4430 CPU @ 3.00GHz, two memory channels @1600 MHz.
[1]: http://www.daemonology.net/blog/2008-06-05-faster-utf8-strle...
> but UTF-16 captures really a very large share of actually used code points.
That most characters[1] in use are a single code unit in UTF-16 is meaningless to code that needs to index[2] into a UTF-16 by code point (or grapheme): the only correct way to accomplish this in a typical UTF-16 string implementation is O(n).
[1]: I love emoji, and they are outside the BMP.
[2]: I think you'll find that most code does not need to index into a string. (Though languages that lack iterators on strings will make writing the code without indexing difficult.)
next, your claim that UTF-8 is not well suited for a general purpose string implementation because it is a variable length encoding and therefore addressing a character becomes a linear time operation is incoherrent: UTF-16 is a variable length encoding just as well. come out and say that you want to be lazy and pretend surrogate pairs don't exist.
Actually today it might be hard to understand what indexing is, even if you store your string in UCS-32 encoding. There are graphical symbols that may occupy variable number of UCS-32 items. And they are used out there (e.g. flags).
Encoding of an opaque byte array is a different story. E.g. Python 2's unicode vs string.
Bad for storing data in .text, but still a neat hack that shaved whole tens of bytes off the program size.