8 ms·

Never create Ruby strings longer than 23 characters

• wtn 15y ago
  Link-bait title… Author directly contradicts the title in the tl;dr at the end.
  • phzbOx 15y ago
    The way wtn said it might be a bit provocative, but here's the last paragraph of the post: """ I don’t think you should refactor all your code to be sure you have strings of length 23 or less. That would obviously be ridiculous. The 50% speed increase sounds impressive, but actually the time differences I measured were insignificant until I allocated 100,000s or millions of strings – how many Ruby applications will need to create this many string values? And even if you do need to create many string objects, the pain and confusion caused by using only short strings would overwhelm any performance benefit you might get. """ So, basically, "Never create Ruby strings longer than 23 characters" is not true at all. In some specific cases, it might be true. A more accurate title might have been "Why ruby strings with more than 23 characters are handled differently." (Or something similar) But then, it was an interesting post and I enjoyed it; so it doesn't really matter I guess.
• dpeck 15y ago
  Terrible title, but the content is quite good. Ruby programmers, at least here, should have enough foundations to be able to understand these "deep" dives into the interpreters, and the more you understand the hows and whys of the tools you build on the better your end product will eventually be
  • endgame 15y ago
    Language enthusiasts in general, not just Ruby programmers will enjoy this article, I think. In any case, I got to see a cool little optimisation that I hadn't thought of before.
    • pat_shaughnessy 15y ago
      Thanks a lot for the nice comments, guys! Sorry about the "link bait" - I really was just so surprised that the limit was 23, such a strange number, that I just had to put it in the title of the post. I didn't expect it to end up on HN.
• rodw 15y ago
  I'll admit to only having skimmed much of this article, but that's a lot of words to say this: "It turns out that the MRI Ruby 1.9 interpreter is optimized to handle strings containing 23 characters or less more quickly than longer strings." The rest of the article seems to back that some with benchmarking numbers that suggest allocating a 23 character string is about 50% faster than allocating a 24 character string, which in this particular test worked out to about 200 milliseconds difference in the time it takes to allocate 1 MILLION strings, which makes the time savings about 0.2 picoseconds (200 nanoseconds) per allocation if I remember my SI units right.
  • gjm11 15y ago
    200ms / 1million = 200 nanoseconds, yes, but that's 0.2 microseconds. If you really want it in picoseconds, it's 200000 of those.
  • aaronblohowiak 15y ago
    It is also a nice introduction to C for rubyists -- it explains the basic ruby c object model and how different kinds of strings are laid out in memory and the implications that has on performance. Ultimately, the author shares your conclusion.
• jeffremer 15y ago
  Link bait titles irk me. Nevertheless nice post on some of the MRI internals.
• parfe 15y ago
  Unicode of course takes up more space and fills up your buffer sooner. Looks like the jump happens after 8 chars. Benchmark.bm do |bench| run("と", bench) run("がと", bench) run("りがと", bench) run("ありがと", bench) run("ありがとあ", bench) run("ありがとあり", bench) run("ありがとありが", bench) run("ありがとありがと", bench) run("ありがとありがとあ", bench) run("ありがとありがとあり", bench) run("ありがとありがとありと", bench) run("ありがとありがとありがと", bench) end user system total real 2 chars 0.210000 0.000000 0.210000 ( 0.212420) 3 chars 0.200000 0.000000 0.200000 ( 0.199957) 4 chars 0.200000 0.000000 0.200000 ( 0.199356) 5 chars 0.200000 0.000000 0.200000 ( 0.199142) 6 chars 0.200000 0.000000 0.200000 ( 0.198047) 7 chars 0.190000 0.000000 0.190000 ( 0.198984) 8 chars 0.190000 0.000000 0.190000 ( 0.196917) 9 chars 0.250000 0.000000 0.250000 ( 0.245808) 10 chars 0.240000 0.000000 0.240000 ( 0.247153) 11 chars 0.250000 0.000000 0.250000 ( 0.248083) 12 chars 0.250000 0.000000 0.250000 ( 0.247753) 13 chars 0.240000 0.000000 0.240000 ( 0.250674) Grabbed those unicode chars from http://blog.trydionel.com/2010/03/23/some-unicode-tips-for-ruby/ http://blog.trydionel.com/2010/03/23/some-unicode-tips-for-r... no clue what that says.
  • chaosfox 15y ago
    ありがとう -> thanks, note you are missing the う on the end.
    • parfe 15y ago
      You're welcome. That's what I get for checking up on my limited unicode knowledge before posting, and then just C&Ping. Thanks.
  • pat_shaughnessy 15y ago
    Cool! Thanks for taking the time to test this - while the idea of testing with unicode chars occurred to me while writing the post, I didn't have time to get to it...
  • microtherion 15y ago
    Yes, hiragana are from an unicode range that encodes to 3 UTF-8 characters each, so ruby appears to use UTF-8. ありがと is "arigato".
• jbooth 15y ago
  This article should really have the word "stack" in it someplace.
  • skatenerd 15y ago
    Not knowing much C, I was confused about why malloc() wouldn't get called for the RString structure. This is elucidating: http://www.cs.usfca.edu/~wolber/SoftwareDev/C/CStructs.htm http://www.cs.usfca.edu/~wolber/SoftwareDev/C/CStructs.htm Particularly this part: "// automatic allocation, all fields placed on stack"
    • metageek 15y ago
      Even if you're not putting the RString struct on the stack, the embedded string optimization means calling malloc() just once instead of twice.
      • ori_b 15y ago
        You can allocate the string with one malloc: RString *s = malloc(sizeof(RString) + length); /* allocate 'length' bytes extra memory past the end of 's' */ s->data = s + 1; /* to the extra memory past the start of the string struct */
        • teaspoon 15y ago
          Ruby strings are mutable, so you need to be able to free s->data without freeing the RString itself.
          • ori_b 15y ago
            s = realloc(s, sizeof(RString));
            • charliesome 15y ago
              MRI objects are not relocatable so that won't work if realloc has to move the structure in memory
• gte910h 15y ago
  I have this sinking feeling reading that article took more time than I'll ever save by knowing this. Computers go unimaginably fast now. Really. Humans can't intuitively comprehend how fast it is. I doubt that this fact will save perceptible time for more than a dozen of its readers.
  • jamesgeck0 15y ago
    Except in the most egregious cases, how many optimization articles ever save you more time than it takes you to read them? As you say, computers are unimaginably fast.
    • gte910h 15y ago
      Indeed. I am just continually amazed at the lack of caution people make when expressing these sentiments "Never use a ruby string longer than 23 characters!!!"....or you'll just take a slightly less infinitesimal amount of time.
      • artursapek 15y ago
        I think the title is meant to be a hook.
    • JoeAltmaier 15y ago
      so premature optimization in code is evil for more than one reason. First, it obfuscates the code. Second, the slowest processor around is the wetware, and it aint getting any faster. Making it simpler to understand/explain/write/compile/debug will save geometrically more time than it saves in almost every case.
  • lgeek 15y ago
    Okay, knowledge of this specific optimisation wouldn't be that useful except in some very unlikely scenarios. Nevertheless, I found this to be an interesting read about some Ruby MRI internals. But I have to disagree with your attitude toward optimisations. Algorithmic improvements (and implementation optimisations, but generally less so) can improve performance by many orders of magnitude. Sure, sometimes it just doesn't matter, but there are plenty of cases when you should pay attention to this. For example: any web service that runs on more than a couple of servers. At some point, it will be cheaper to spend more time writing efficient software than to add hardware. Another example: mobile devices. Can you make your software 20% faster? Great, that means 20% more battery life. I have a recent example which left a strong impression on myself. I have implemented a bot which plays Kalah[1] for a school project. I've used C and I've optimised the program as much as reasonable in a week or so. After I was done, I've looked on the web for a strong implementation to play against. I've found a bot implemented in Ruby. To my surprise, my implementation was about 4 orders of magnitude faster. A friend implemented the same thing (including algorithmic optimisations) in Java. Guess what, his was still 2 orders of magnitude slower than mine. TLDR: Yeah, most of the time computers are fast enough. But if you have hotspots, it often pays off to optimise that code. [1] http://en.wikipedia.org/wiki/Kalah http://en.wikipedia.org/wiki/Kalah
• anrope 15y ago
  Cool dip into Ruby internals. If you roll your own ruby, instead of redoing all your strings, you could just change RSTRING_EMBED_LEN_MAX. This would cause more wasted memory if you have a lot of short strings (0 < len << RSTRING_EMBED_LEN_MAX), and probably isn't worth it since there isn't much performance improvement. The most confusing part of this article was the actual RString struct implementation. Are the anonymous unions and structs used to control structure padding and alignment?
  • minimax 15y ago
    The "aux" union contains either the reference count or the string capacity. The idea must be that shared strings are immutable so the capacity is not meaningful. Conversely, if the string is not shared, the reference count is not meaningful. The outer "as" union either contains the 24 byte char array or the 24 byte (len + ptr + aux) heap string information.
  • pat_shaughnessy 15y ago
    Thanks! Cool idea about recompiling with a new value for RSTRING_EMBED_LEN_MAX - never thought of that! Yes, the inner unions/structs are used to tell the C compiler exactly where the different data values should go. They are in fact not anonymous: e.g. "heap" and "aux" - the names appear right after the closing brace.
  • barrkel 15y ago
    Values in interpreters written in C are frequently implemented as (manually) discriminated unions - i.e. unions that share a field at the start to indicate the type and contents of the remainder - because that's a handy way of implementing the polymorphism required for a straightforward interpreter. It's pretty much necessary to use structs inside unions in order to have a more than one field per layout; the struct is just grouping, so it doesn't need a type name. So without looking at any of MRI source, I'd be willing to guess that most, if not all, of its structures representing Ruby values start with a field of type RBasic, and that type contains information necessary to distinguish and interpret the remainder of the value.
    • 15y ago
• tptacek 15y ago
  Interesting deep dive; but remember that calling :+ to append to strings is a pessimization (in both Ruby and Python); :join'ing a list of 2 strings is about as fast as :+'ing them together, but :join'ing 3 strings is about twice as fast.
  • monochromatic 15y ago
    I thought I remembered reading somewhere that Python optimizes this so that both forms are basically equivalent, performance-wise. At least in relatively recent versions of Python.
    • masklinn 15y ago
      It's a bit more complex, it's implementation-specific, it's definitely a hack and it's not very reliable: * It's a CPython-only optimization * It does not work if the first member of the concatenation is an interned string (such as a literal string, so `s = s + "abc"` may trigger the optimization but `s = "abc" + s` will never do so) * It only works if there's a single reference to the string in the system. * It only works for the shapes `s = s + s1` and `s += s1` and no other[0], including (excluding?) `s = s + s1 + s2` or `someFunction(s + s1)` The way it works is that, when it sees `s = s + "abc"` or `s += "abc"` and there's a single reference to `s` (this one), CPython will call `realloc(3)` on the string's internal buffer (technically it calls `_PyString_Resize` which calls `PyObject_Realloc` unless you've compiled python --without-pymalloc then it calls a macro over realloc(3), but you get the point) instead of allocating a brand new string. And it does not work on unicode objects in CPython 2 (only str, it works on both str and bytes in CPython 3). Interestingly, this optimization was introduced by Armin Rigo[1], one of the lead Pypy devs for which this CPython optimization is an issue (it leads developers to use more string concatenation, which pypy can not really optimize as it does not use refcounting semantics)[2] [0] http://bugs.python.org/issue980695#msg46258 http://bugs.python.org/issue980695#msg46258 [1] http://bugs.python.org/issue980695 http://bugs.python.org/issue980695 [2] https://bugs.pypy.org/issue814 https://bugs.pypy.org/issue814 (nb: pypy's bug tracker displays the oldest comment at the bottom) PS: I don't think I've noted how much HN's comment-editing "facilities" suck today. They really, really suck. What's a man got to do for markdown support in order to make formatted comments readable?
• adriand 15y ago
  This was interesting and caused me to go off on a neat little tangent too. I was curious about the VALUE declaration in: struct RString { long len; char *ptr; VALUE shared; }; From the Hacker Guide referenced, I found this definition: typedef unsigned long VALUE; This is then casted, when needed, to a pointer to whatever type of struct you are dealing with. How does that work? Well, on a 32-bit machine, if I'm correct in my reading, an unsigned long is 4 bytes in size and can contain these numbers: 0 to 4294967295 That last number is 4 gigabytes, which is the size of byte-addressable memory on a 32-bit machine. So VALUE can point anywhere. Neat!
  • archangel_one 15y ago
    That seems like a slightly dubious choice to me, since unsigned long isn't guaranteed to be as long as a pointer; for example, under Microsoft's 64-bit compiler it's still only 4 bytes, but pointers are obviously 8. Possibly there is some extra preprocessor cleverness to deal with it, or maybe they don't expect it to work under that compiler?
    • jof 15y ago
      Isn't this what C99's uintptr_t type tries to address?
      • archangel_one 15y ago
        Yes, exactly. I'm just a little curious since, without knowing anything about the code at all, unsigned long doesn't seem like a great choice. I'm sure the Ruby devs would know this though so I expect there must be some reason for it.
        • bhousel 15y ago
          Here's the code: https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#L66 https://github.com/ruby/ruby/blob/trunk/include/ruby/ruby.h#... It looks like uintptr_t support is there, just disabled for now.
• jcoder 15y ago
  Robert Anton Wilson would be proud (http://en.wikipedia.org/wiki/23_enigma http://en.wikipedia.org/wiki/23_enigma).
• endgame 15y ago
  Does that maximum length need to be a magic number, or could it be an expression written in terms of `offsetof` and `sizeof`?
  • ars 15y ago
    It could be (and probably should be): sizeof(long) + sizeof(char *) + sizeof(long) But it's possible the DEFINE for RSTRING_EMBED_LEN_MAX is that and not a fixed number. You need the DEFINE since it would be needed elsewhere to check the length of a string before storing it.
• extension 15y ago
  Why would str2=str create a new string? How are RStrings modified when they are referenced by other shared RStrings? Is there any way to create a shared RString other than calling .dup?
  • pat_shaughnessy 15y ago
    Great questions! To be honest I don't have enough knowledge of the MRI internals yet to be able to answer these 100% correctly. Maybe I'll write a follow up post or an update to this one explaining these issues when I have time for more research. But for today: 1. str2 = str doesn't actually create a new string. RString represents a string value, not a string object. So str2=str creates a new RString because that essentially defines what str2's value refers to… Think of RString as an internal pointer to the value that str or str2 is referring to. Sorry - not a good explanation :( 2. How are shared RStrings modified? Not sure yet, but I'm curious to find out. Will let you know on my site somehow. 3. Yes, simply calling str2 = str or in a variety of other ways will do it.
    • ben0x539 15y ago
      I'm 99% sure you're wrong about 1). The internal pointer is the VALUE that is pointing to the struct RString. `str2 = str` will make another VALUE point to the same struct RString. Consider str = "foo" str2 = str str.object_id == str2.object_id #=> true I'm fairly sure that implies that str and str2 share everything including the RString object, so it couldn't really have one of str/str2 have a field that points to the other. I am not sure about 2) and 3) but I'd expect some copy-on-write mechanism based on a flag field in the RBasic struct, and taking substrings might be O(1) thanks to sharing too.
    • charliesome 15y ago
      Here's a better explanation for #1: In Ruby, most classes (including String) are reference types. This is why `str2 = str` doesn't create a new string. It doesn't create a new RString either - str and str2 are both pointers to the same RString struct.
    • flgr 15y ago
• ComputerGuru 15y ago
  I read the title and thought that I was going to see some really stupid design decisions. To the contrary, it's vary clean and smart. It's not that strings over 24 are slow, it's that strings below length 24 have extra optimizations. It's a great article, but I really, really despise the linkbait title.
  • ComputerGuru 15y ago
    s/vary/very/ Sorry! Can't edit it now, either. :$
  • nonrecursive 15y ago
    I work with Pat and kicked around some title ideas with him yesterday. It's interesting to see a title that he created out of a sense of fun and excitement being perceived as linkbait. I can see why that perception would arise, but I hope people think of him as a good writer trying to have fun rather than some dude writing linkbait titles trying to get attention. Some other title ideas: * 23 characters ought to be enough for anybody * 23: How Twitter could have solved their ruby scaling problem
    • gbog 15y ago
      No better. It is becoming a real problem if factual accurate titles don't go through. Imagine, I'm on a phone in China, most articles never load, I have to rely on title and comments to now what we are talking about.
    • ComputerGuru 15y ago
      Heh. I would have gone with "Ruby Optimizations: Why short strings are an order of magnitude faster" or something.
  • kooshball 15y ago
    > It's a great article, but I really, really despise the linkbait title. Generally I feel the same. Although, I think exceptions can be made for articles with real content.
  • 15y ago
• minimax 15y ago
  He's nearly there, but the reason for the number 23 is staring you right in the face. It's not arbitrary. A heap allocated string requires 8 bytes for the length, 8 bytes for the pointer to the string, and 8 bytes for the capacity / reference count. The sum is 24 bytes. So you either use it as a length/pointer/capacity/refcount struct, or save the malloc and use the 24 bytes directly for 23 chars and a NULL terminator.
  • nonrecursive 15y ago
    I think Pat actually points that out: The value of RSTRING_EMBED_LEN_MAX was chosen to match the size of the len/ptr/capa values. That’s where the 23 limit comes from.
    • steve19 15y ago
      I apologize, I accidentally downvoted you instead of upvoting.
  • charliesome 15y ago
    use the 24 bytes directly for 23 chars and a NULL terminator. Ruby strings aren't null terminated though EDIT: So I went and looked at the code, they are null terminated, but as far as I can tell, Ruby doesn't rely on this directly.
    • deleted 15y ago
      [deleted]
    • throw_away 15y ago
      They probably are when they are inlined like this, else, how would you know the length?
      • charliesome 15y ago
        The length is stored in a flag. include/ruby/ruby.h: #define RSTRING_EMBED_LEN(str) \ (long)((RBASIC(str)->flags >> RSTRING_EMBED_LEN_SHIFT) & \ (RSTRING_EMBED_LEN_MASK >> RSTRING_EMBED_LEN_SHIFT)) #define RSTRING_LEN(str) \ (!(RBASIC(str)->flags & RSTRING_NOEMBED) ? \ RSTRING_EMBED_LEN(str) : \ RSTRING(str)->as.heap.len)
• pillbug88 15y ago
  Isn't this just the small string optimization with copy on write?
  • ComputerGuru 15y ago
    No - instead of allocating memory on the heap for the C character array aka "string", Ruby is the text itself directly in the RString object. These short strings would actually NOT have COW optimization because they're structs and cloning one would clone its embedded string as well (as there are no pointers involved in < 24 byte strings).
    • pillbug88 15y ago
      isn't that the definition of the small string optimization? This is how the dinkumware implementation of std::string has behaved for years. The basic form of the structure is a buffer and a pointer. If the pointer is filled in, it points to a heap string and follows cow semantics. Otherwise, the buffer is used, accomplishing the small string optimization. I suppose I should have elaborated more. It just feels like the OP is "discovering" the wheel.
      • ComputerGuru 15y ago
        Absolutely. Keep in mind that the OP is coming from a Ruby background and TFA targets people more familiar with high-level interpreted languages than with C/C++. BTW, I think though I cannot be sure that both the GCC and MSVC std::string implementations use this optimization in release mode, but I gotta dash and don't have time to verify this fact, so take it with a grain of salt, if you will.
• mikehoward 15y ago
  good to know - thanks
• deleted 15y ago
  [deleted]
• dblock 15y ago
  It's too bad that Ruby requires strings to be GC-ed, otherwise you could get away with an even faster stack string up to a certain size. Basically you would do the same thing as RString, but when you declare a string on the stack, there's no malloc unless you need >N chars. https://github.com/dblock/baseclasses/tree/master/String https://github.com/dblock/baseclasses/tree/master/String for an implementation (a bit thick).