5 ms·
Out of curiosity What would you have done for strings?
by maguirre 11y ago
Out of curiosity What would you have done for strings?
- FreeFull 11y agoCould have a pointer, length pair. That's how it's done in some non-C languages.
- bkeroack 11y agoPointer, length, encoding. In 2015, giving me a bag of bytes labeled "string" is about as meaningful as saying it's "music" or "a picture".
- vardump 11y agoIt's 2015. UTF-8 won.
- kinghajj 11y agoIf only Java and NT would get the message...
- danbruc 11y agoUTF-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. UTF-16 would probably be a better choice in most cases.
- vardump 11y agoUTF-16 is also a variable length encoding and addressing a character is a linear time operation. Then again, even UTF-32 can have composed characters, such as ¨a separately forming ä.
- danbruc 11y agoTrue but UTF-16 captures really a very large share of actually used code points. UTF-32 captures all of them but wastes at least 11 bit per code point, more right now because most of the code points are unassigned. It seems a good tradeoff for a lot of use cases and as you mentioned once operating on code points is no longer good enough you will have to face the issue regardless of the encoding.
- vardump 11y agoUTF-8 consumes less space and has pretty much same trade-offs in terms of iteration. No worries about endian (UTF-16LE vs UTF-16BE). Almost all input text is in UTF-8 and so is almost all output text. Conversion back and forth to UTF-16 is just wasted CPU time. 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.html http://www.felixcloutier.com/x86/PCMPGTB:PCMPGTW:PCMPGTD.htm... [2]: http://www.felixcloutier.com/x86/PMOVMSKB.html http://www.felixcloutier.com/x86/PMOVMSKB.html [3]: http://www.felixcloutier.com/x86/POPCNT.html 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.
- dlubarov 11y agoWell now that we have supplementary planes, UTF-16 should also be considered variable-length.
- vbezhenar 11y agoI used Rust and Swift languages a little bit and I must admit that I almost never had to use indexing for characters. Iterating and slicing is enough for most algorithms. 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).
- nothrabannosir 11y agoEncoding of string types can be (and often is) implicit within the context of a program. Encoding of an opaque byte array is a different story. E.g. Python 2's unicode vs string.
- pavlov 11y agoWell, for a HTTP server, I don't have a specific idea... But in general, the fun part would be trying to come up with string representations that are optimized for the particular application. 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 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.
- Raphael_Amiard 11y agoThat is awfully cool stuff, thank you for that ! but to be honest none of that is really specific to assembly. You can do the same thing in C/C++/Ada/Rust/pick your favorite systems language, or even in a higher level language if you don't care so much about data representation.
- mattgodbolt 11y agoIndeed! Full details of the string routine at http://xania.org/201406/elites-crazy-string-format http://xania.org/201406/elites-crazy-string-format if you're interested in quite how mad it was!
- deleted 11y ago[deleted]
- frozenport 11y agoI would argue this has nothing to do with ASM, one could achieve the same compression with any programming language. The bottom of the linked article has a nice, few lines of Python.
- Sanddancer 11y agoAs others have said, have a length field in with the string. This also has advantages other than making buffer overflows a lot harder, such as making string copying faster and easier. For example, let's have a skeletonized view of a normal string copy routine in assembly (disclaimer: my assembly is rusty, so this may not be completely right. void where prohibited): 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 In contrast, with a length parameter, we can do 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 Having the length of strings means you can have much more concise code. It makes loops easier, makes your code cleaner, and in some environments, gives a speed boost.
- JoeAltmaier 11y agoLots to add to that if you want: sanity check the length against external buffer limit; move word/dword/mmx128; consider alignment; not use deprecated movs instruction. 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.
- nostrademons 11y agoYou mean vectorizing memcmp/memcpy to work word-at-a-time instead of byte-at-a-time? Google does this when compiling their binaries, and I think Facebook does too. I thought the latter had open-sourced it with Folly but couldn't find a code pointer. I've heard rumors that LLVM can sometimes vectorize them to use SIMD instructions when available, too. 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.
- ataylor284_ 11y agoI remember one program that had a string print subroutine that took zero args. It just used the return address from the stack to grab the nul-terminated string immediately following the JSR/CALL instruction. It then patched the return address on stack to return just after the nul. Bad for storing data in .text, but still a neat hack that shaved whole tens of bytes off the program size.
- cgabios 11y agoTurbo/Borland Pascal used a NUL-optional string format of length (byte IIRC) followed by data. [0] 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 http://math.uww.edu/~harrisb/courses/cs171/strings.html 1: https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.html#jvms-4.4.7 https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.ht... 2: http://msgpack.org/ http://msgpack.org/ 3: https://github.com/ugorji/binc/blob/master/SPEC.md https://github.com/ugorji/binc/blob/master/SPEC.md
- salgernon 11y agoAnother option for dealing with nuls in a string: http://en.m.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing 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.