A few years ago, I added an optimisation to the GNUstep Objective-C runtime to store tiny strings (up to 8 7-byte ASCII characters) in the pointer and completely eliminate allocation. On some desktop application workloads, these accounted for 20% of total allocations (though not 20% of bytes allocated) and made some operations much faster (string comparison became pointer comparison). Keys in dictionaries and path components were very common to represent in this way. I think Apple picked up the same optimisation.
Strings are one of the most interesting trade-off points in a standard library implementation. Objective-C benefits hugely from some macro-optimisations enabled by the design of NSString as an abstract class but also suffers from missing microoptimisations as a result of not being able to inline common string-manipulation instructions. Getting strings right can make a huge difference to language performance, unfortunately it’s not really clear what ‘right’ means.
Say we ran this workload on a machine with 64 GiB of RAM - that’s not atypical for a server. And say the input file was 100 GiB. We couldn’t even read the whole thing in memory! We’d have to go back to a streaming solution.
You could also mmap() and borrow from the mapped file and let the kernel take care of what’s in RAM and what’s not. Which the author’s blog engine does for content files :)
As for smartstring, it’s recommended for “a key type for a B-tree” (such as BTreeMap), because inline strings greatly improve cache locality.
Hmm!! Oh yeah this is brilliant. So easy to forget that String keys introduce indirection actually. I love how Rust makes you think about this.
oh and for anyone looking for a serious tracing allocator, heaptrack is really good and comes with a GUI
This article has some terrible organizational problems, aka “burying the lede.” I came for insight into string implementations, but after scrolling through page after page about command-line parsing, memory allocators, and a JSON report generator, I still hadn’t seen anything related to the topic. So I gave up and went on to something else. I can imagine how this might all come together into something that’s actually about string optimizations, but I’d probably have to understand all the context he’s been building up.
If I were the author I’d move most of this stuff into appendices, or at least lead with the string stuff and then explain how he got there.
Objective-C can store strings of various lengths inside tagged pointers, keeping them in registers or on the stack instead of heap allocation them, the maximum length depending on the characters used. Swift’s recent String refactors have managed to cram even more string into registers.
It’s super convenient that Rust has &str (pointer + length, immutable) and types can auto-dereference to it. This works as the lowest common denominator for strings, so using a custom small string type is practical.
This is in contrast with languages like ObjC or Swift, where there is one blessed string type. That type has to be everything for everyone, and needs to support small strings, large strings, fast appends, searches, and everything in between, because any other string type would be a second-class citizen.
Yeah, it’s a very clever solution for a type that needs to do a good job for many very different workloads, given that ObjC already pays the cost of dynamic dispatch on every call.
I just want to say: this blog, fasterthanli.me, is so amazing. I’ve learned so much from his posts and the content just keeps coming. Hoping he’ll eventually do a comparison article (like the ones he does with C and Go) but with Zig.
Glad I waited to post the above comment until after I read the article, I recently watched this talk about allocators so it’s a great time (for me..) for seeing how Rust expresses these patterns (I am much more familiar with Rust than Zig, I’m interested in the latter for seamless C interop but I came to Rust from Haskell so the lower parts have not been very clear to me).
A few years ago, I added an optimisation to the GNUstep Objective-C runtime to store tiny strings (up to 8 7-byte ASCII characters) in the pointer and completely eliminate allocation. On some desktop application workloads, these accounted for 20% of total allocations (though not 20% of bytes allocated) and made some operations much faster (string comparison became pointer comparison). Keys in dictionaries and path components were very common to represent in this way. I think Apple picked up the same optimisation.
Strings are one of the most interesting trade-off points in a standard library implementation. Objective-C benefits hugely from some macro-optimisations enabled by the design of NSString as an abstract class but also suffers from missing microoptimisations as a result of not being able to inline common string-manipulation instructions. Getting strings right can make a huge difference to language performance, unfortunately it’s not really clear what ‘right’ means.
You could also
mmap()and borrow from the mapped file and let the kernel take care of what’s in RAM and what’s not. Which the author’s blog engine does for content files :)Hmm!! Oh yeah this is brilliant. So easy to forget that
Stringkeys introduce indirection actually. I love how Rust makes you think about this.oh and for anyone looking for a serious tracing allocator, heaptrack is really good and comes with a GUI
This article has some terrible organizational problems, aka “burying the lede.” I came for insight into string implementations, but after scrolling through page after page about command-line parsing, memory allocators, and a JSON report generator, I still hadn’t seen anything related to the topic. So I gave up and went on to something else. I can imagine how this might all come together into something that’s actually about string optimizations, but I’d probably have to understand all the context he’s been building up.
If I were the author I’d move most of this stuff into appendices, or at least lead with the string stuff and then explain how he got there.
Objective-C can store strings of various lengths inside tagged pointers, keeping them in registers or on the stack instead of heap allocation them, the maximum length depending on the characters used. Swift’s recent String refactors have managed to cram even more string into registers.
https://www.mikeash.com/pyblog/friday-qa-2015-07-31-tagged-pointer-strings.html
It’s super convenient that Rust has
&str(pointer + length, immutable) and types can auto-dereference to it. This works as the lowest common denominator for strings, so using a custom small string type is practical.This is in contrast with languages like ObjC or Swift, where there is one blessed string type. That type has to be everything for everyone, and needs to support small strings, large strings, fast appends, searches, and everything in between, because any other string type would be a second-class citizen.
Did you know that
NSStringis a class cluster? It has a number of private subclasses which function as alternate implementations.Yeah, it’s a very clever solution for a type that needs to do a good job for many very different workloads, given that ObjC already pays the cost of dynamic dispatch on every call.
I just want to say: this blog, fasterthanli.me, is so amazing. I’ve learned so much from his posts and the content just keeps coming. Hoping he’ll eventually do a comparison article (like the ones he does with C and Go) but with Zig.
Glad I waited to post the above comment until after I read the article, I recently watched this talk about allocators so it’s a great time (for me..) for seeing how Rust expresses these patterns (I am much more familiar with Rust than Zig, I’m interested in the latter for seamless C interop but I came to Rust from Haskell so the lower parts have not been very clear to me).