15 ms·

Drop millions of allocations by using a linked list

223 points by jcn 12y ago

jammyrose 12y ago
i never knew this, thanks.
steipete 12y ago
Ruby people discovering algorithms ducks
- perdunov 12y ago
  Really. Every time I whine publicly how web programming people aren't familiar with even basic CS, I get a slap. But really, I should move to web programming. I'll be an expert computer scientist there, probably.
  - deleted 12y ago
    [deleted]
  - aidos 12y ago
    Annnndddd.... what reaction do you expect? "Oh, please come and do web development so we can bask in the glow of your self-righteousness and infinite knowledge of computers." /snark (apologies for being offensive, but good lord, what a silly statement - unless I missed the joke) I stand before you as a counterpoint to your foolish generalisation, and guess what, I know plenty of other people that don't fit your stereotype either. I'm not saying there's not an element of truth to your statement. See, here's the thing. People throughout the software (or any) industry have different collections of knowledge. There are an endless number of things to learn and each one of us is different and brings a different set of skills to the table. To be great at web development you spend years learning the subtleties of developing for a vast domain of different platforms. There are bugs in the platforms decades old that I know the intimate details of and have workarounds for especially constructed to fit in with the other bugs in the other platforms we deal with. And that's a tiny facet of what you need to know. You know what would really happen when you came over to web development? You'd find that a lot of the skills as a computer scientist aren't altogether useful. You wouldn't be an expert computer scientist. You'd be a junior developer, probably.
    - Swizec 12y ago
      I keep repeating myself on Hacker News, but once more, we've found the difference between Software Engineer and Computer Scientist. One makes things work, the other is a mathematician. Why do we keep conflating the two?
      - TickleSteve 12y ago
        Because you cant be good at either without having an element of the other. Ideally, they overlap.
        Swizec 12y ago
        Ideally they do overlap. But we don't call people who design bridges physicists even though they know a shitload of physics. Our field is maturing. These difference are only going to become more important.
      - robmccoll 12y ago
        You should be careful with the term engineer. By definition, engineering is the application of scientific and mathematical knowledge to solving practical problems. Without knowing and understanding the science and math behind computing and software, one can hardly claim to be a software engineer.
        FLUX-YOU 12y ago
        The title is cheap in the US and in some companies (cough) they slap it on every position that directly touches the product.
        Dewie 12y ago
        So many programmers have this weird inferiority complex when it comes to the term "engineer". Not you, but those who think that most programming can never be called "engineering" because people don't die if you introduce a software bug[1] (as if the only kinds of modern "engineers" have to do with immediately safety-critical things). I prefer the plain "programmer" myself, but I don't see the big deal unless "engineer" is a protected title wherever that person lives. [1] Note that I said "most programming".
  - ICWiener 12y ago
    Slap. Stop whining.
  - robmccoll 12y ago
    That's a bit strongly worded, but I also see the pattern of people who came into computing from the Web direction rediscovering basic principles of computing and computer science. Similarly, the NoSQL community seems to slowly be discovering why traditional relational databases work the way they do, why supplying correct and durable replicated storage with high performance is difficult, and why some of the features that NoSQL threw out along side SQL itself in the name of simplicity and performance are actually quite useful and occasionally important.
  - raverbashing 12y ago
    I was going to post the photoshopped joke, but this gets more to the gist of it http://stackoverflow.com/questions/3811678/add-two-variables-using-jquery http://stackoverflow.com/questions/3811678/add-two-variables... Edit: found it https://plus.google.com/u/0/+DougTyrrell/posts/br3kqg6Vet6 https://plus.google.com/u/0/+DougTyrrell/posts/br3kqg6Vet6
  - drinchev 12y ago
    When I was in my early teenage years I was already making some development efforts on Pascal, VisualBasic and later on I switched to linux and started doing Perl CGI web apps. Back in time when I had to choose if I want to do CS degree I was already paid as a web developer and doing what I was going to study for. Then I asked some friends that were actually studying CS and they told me that they have a very tight schedule with work in the following disciplines : FORTRAN, ASM, C, C++ . I told them that's too low-level for me and probably I will not use it for my work so I decided to go into completely different sphere ( I graduated law ). Now I'm not the best programmer lived on the planet, but certainly I still do what I love and I'm paid for web development as high as a senior person, because of my experience - not CS degree. So... If you think you can make benefit to web development, why don't you start with a simple open source contribution to any of the existing projects and reduce Wirth's law [1] a bit with some low-level skills. But for something more complicated, please consider some experience first in that specific area. [1] http://en.wikipedia.org/wiki/Wirth%27s_law http://en.wikipedia.org/wiki/Wirth%27s_law
  - manish_gill 12y ago
    I'm a web dev who has a degree in CS. Do you think I'm a unicorn? Of course not. Stop generalising.
  - matthewmacleod 12y ago
    Good, you deserve a slap for being self-satisfied about it. There are loads of fully competent and skilled web developers out there with great, in-depth CS knowledge, and publicly berating them achieves nothing. Web development is interesting, because it tends to mix in people from a lot of different backgrounds — in particular, some of them come through the design side, and move down the stack. That's good, because it demonstrates the accessibility and flexibility of the stack; it's bad because it can result in suboptimal solutions to common problems.
  - thaumaturgy 12y ago
    You probably wouldn't do that well in web development, because it's too different from embedded or systems programming. You probably have the luxury of specializing in one particular language, and maybe a handful of processor architectures. You probably rely on one or a few libraries, and know them backwards and forwards. You probably have your own personal repository of code and tactics that you go back to often. In other words, your knowledge of programming is probably narrow and deep. Web developers usually don't get that luxury. Top web developers today have to be fluent in a minimum of two programming languages (javascript and a backend language like Python, Ruby, PHP...), use several different fast prototyping approaches (css compilers and wacky templating systems), have a good working general knowledge of everything from the web browser to the web server, and cope with an environment in which at least one of those parts is changing on almost a daily basis. Web development is shallow and very, very broad. I prefer systems programming but I've worked as a web developer off and on for several years now. I have a lot of respect for any web developer that's really good at it. They aren't lesser programmers at all, and I suspect a lot of them, if they decided to do it, could kick the pants off of most systems programmers.
- jph 12y ago
  Java had the same kind of issue for years. In Java and Ruby, the standard library uses an object `+` operator to mean concatenation (not numeric addition), and the implementation did immediate data copies, rather than doing reference linking and copy-on-write (or immutability).
  - tr352 12y ago
    But in Java this happens only with strings doesn't it?
    - bcg1 12y ago
      Sort of... technically only the '+' operator only applies to strings... however it is essentially the same issue as the pull request, from what I can gather (I assume the issue comes from allocating a new array with size length+1 and copying the original each time a record is added). Same thing happens with java.util.ArrayList.add() and its cousins though, and from my experience people rarely use the constructor specifying an initial capacity, so the default gets used even if it is would obviously be woefully small (default is 10 BTW, in case you're curious & lazy :). Also one might argue that the problem is actually much worse with strings, because string concatenation is so common and the syntactic sugar of the '+' operator for strings encourages the "wrong" way.
      - this_user 12y ago
        Java's JIT compiler optimises string concatenation by substituting a StringBuilder and has been doing so for a while. As to using the wrong data type, that's really the programmer's fault. If you don't allocate enough capacity or use another data type (e.g. LinkedList) if you don't know the required capacity, you are doing a bad job.
        bcg1 12y ago
        To nitpick, Java's JIT compiler compiles Java bytecodes to machine code, but I know that javac does to the type of optimization that you are describing. There are plenty of scenarios though where it can't/won't do that optimization ... and if you are using the binary version of a library compiled without that optimization I'm pretty sure you're out of luck, especially if the method you're calling is not JIT'd. I'm not really trying to knock any particular language or runtime here, the point I was trying to make is that nearly every language I've used has quirks that encourage convenience over optimization, and that just because you're coding in language foo, it doesn't mean you're off the hook when it comes to being intentional about the choice between them.
- DiabloD3 12y ago
  Not sure why parent is getting downvoted, there is a serious problem in the Ruby community that very few of them have read GoF, TAoCP, and/or K&R.
  - matthewmacleod 12y ago
    Because it's smug and adds nothing to the conversation. I don't see any evidence that the Ruby community suffers more than any other development community from this sort of thing — that is, the ones where high performance is not the biggest concern, of course.
  - Ao7bei3s 12y ago
    Stop jumping to conclusions, and stop throwing around buzzwords. GoF is a (somewhat C++-centric) book about design patterns that's completely unrelated to the discussion at hand, may not be the best resource to learn about design patterns and has nothing to do with CS. TAoCP is more like an encyclopedia; actually reading through even one chapter takes a significant amount of effort (if you want to get anything out of it). Try it. (Yes, I've worked with it.) K&R is a 27 years old, thoroughly outdated book about C. There are better options[1]. [1] Try the 16 years old book "Expert C Programming" by Peter van Linden, which is excellent, even though outdated too.
    - bcg1 12y ago
      +10 if I could, re "Expert C Programming"; excellent read, even if you aren't a C programmer
- WickyNilliams 12y ago
  Um... isn't this a data structure not an algorithm?
  - picks_at_nits 12y ago
    Programs = Data Structures + Algorithms, and it is often the case that there are deep relationships between the data structures and the algorithms. For example, any linear recursive algorithm that deals with the head of a list and the tail/rest/butHead of a list is optimized for a linked list implementation. So... to understand a linked list, you really need to be familiar with algorithms that bisect list sin this manner, and the reverse: To understand algorithms that bisect lists in this manner, you have to be familiar with a linked list. So... Yes it’s a data structure, but it’s joined at the hip to the algorithms that operate best on it.
    - WickyNilliams 12y ago
      I know, I was intentionally curt in my reply because snark is best solved with more snark </snark>
- randomdata 12y ago
  Except the linked list implementation was added to the project in 2013[1], and is presumably used elsewhere in the program. This only fixes a couple of bugs using that same mechanism. https://github.com/rubygems/rubygems/blob/800f2e63bc6174b5b4dea5528110b09d89fe3dd1/lib/rubygems/util/list.rb https://github.com/rubygems/rubygems/blob/800f2e63bc6174b5b4...
- dang 12y ago
  > Ruby people discovering algorithms ducks This was not a good comment to post to HN. When you toss a Molotov cocktail into an HN thread and "duck", here is what we are going to get: web programming people aren't familiar with even basic CS I stand before you as a counterpoint to your foolish generalisation Oh cute, a web dev. You've just reinvented 1975 [...] Would you like a pat on the head? Stop whining your comment is bullshit you deserve a slap For any large group like "Ruby people" or "web programming people", HN has many users who either identify with being part of that group or identify with not being part of it. Given the numbers, there will always be a few who are having a bad day or feeling defensive or what have you, enough to respond angrily when someone posts a slur. Then their counterparts feel attacked, and down the whole thing goes. Social padding prevents disputes like this from turning ugly, but we don't have that on HN. Even when you know another user from their comment history, that's not much information. Imagination fills in the gaps and then we imagine the other in the worst light. That's why the community here is fragile. To be a good community member, please don't post things that could easily set the thread on fire. If after editing them out, your comment has nothing substantive left, please don't post it.
  - steveklabnik 12y ago
    Thank you.
chatman 12y ago
Just comes to show how careless Ruby guys were while building this.
- eddd 12y ago
  1. Make it work 2. Optimize
  - rosspanda 12y ago
    From working with Ruby guys its normally 1. Make it work 2. Spin up more AWS boxes
    - pothibo 12y ago
      Nothing's wrong with spinning up more AWS boxes. If it costs 300$ annually to solve a problem that would cost 5k$ in development to fix, I believe it's a wise choice. Yeah, down the line you will eventually have to do optimization, but you will prioritize.
      - rosspanda 12y ago
        A agree somewhat, but I've seen 10 box systems that could run on raspberry pie with good code
        lmm 12y ago
        I've seen them. I've worked on them. But again, where's the cost/benefit?
        nirvdrum 12y ago
        I'm hardly what most environmentalists would call an "environmentalist", but one cost here is the increase in carbon footprint. Of course, to the company the cost/benefit analysis errs on the side of just spinning up more boxes. But from a larger perspective, taking some extra time to make more efficient use of machines could have a drastic impact. Many optimizations don't require months to implement. Many of those are even avoidable with a bit of foresight.
icebraining 12y ago
I'm not very familiar with Ruby; where exactly did the duplication occur in the original code?
- deleted 12y ago
  [deleted]
- barrkel 12y ago
  I believe it's in the Gem::Specification.traverse method here: http://ruby-doc.org/stdlib-1.9.3/libdoc/rubygems/rdoc/Gem/Specification.html#method-i-traverse http://ruby-doc.org/stdlib-1.9.3/libdoc/rubygems/rdoc/Gem/Sp... The 'trail' parameter, an array, was implicitly duplicated by applying the '+' operator on each recursion through a dependency.
  - weavie 12y ago
    trail = trail + [self] That + operator looks so innocent, so seductively simple..
kilotaras 12y ago
I'm torn on this one. It's a great performance improvement, but on the other hand I would expect this way sooner than after almost 4 years of usage.
- vidarh 12y ago
  It's because the main bottleneck for most apps that uses lots of gems is elsewhere (the load path grows with each extra gem, meaning a simple 'require' gets more and more expensive the more gems your app uses).
jph 12y ago
Great pull request. Ruby makes it easy to duplicate data by calling `.dup` or `+`, and this does help with state isolation. But duplication is an expensive operation. Ruby's standard libraries don't have much support for immutability, or deep cloning, or copy on write, or linking concatenation. There's no standard library way to ask for a snapshot of an object. So in the early days for Ruby, an idiom was: if you're writing a method that takes a list, and you need to be sure your list doesn't change out from under you, then duplicate it, get it working, and if it becomes a bottleneck then optimize it.
cranium 12y ago
All your tests passed, nothing broken, a small bit of code for tremendous optimization,... I can feel the satisfaction!
shiggerino 12y ago
Nobody show this to Bjarne Stroustrup https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo
- kaeluka 12y ago
  AFAICT, this performance bug is not at all related to the linked-list vs. vector issue.
  - rakoo 12y ago
    Yes it does: vectors are good for random access, linked-lists are good for doing stuff in the front/back of the list. The performance bug we have here is solved by finding a way to insert stuff at the front/back (and also going through each item in the list); there is no need for random access.
    - kaeluka 12y ago
      If I remember Bjarne's talk correctly, vectors (in C++) are even fast at inserting because they have densely packed representation which rhymes well with modern computer architecture. Inserting in a linked list is slow, as walking the list to find the element at which to insert will already incur O(N) cache misses, whereas in vectors it's only O(1) cache misses. Moving the elements in the vector one to the right is fast due to computer architecture dealing well with predictable patterns. The allocations here (ruby) are reduced because the implementation of appending is horribly slow in the first place, using defensive cloning (I'm taking jph's word here).
      - herewego 12y ago
        Yes, but FWIW most linked list implementations have a reference or pointer to the tail, making appends not O(n), but O(1). However, there is a threshold, depending on use case, where a small vector being resized multiple times larger than the original will be faster than many linked list appends. Point being, either can accel depending on use case.
    - 12y ago
mjs 12y ago
Are there any profiling tools that would have found this? Flame graphs showing the time spent in traverse, perhaps? It seems like this should have been trivially detectable, since the difference is so dramatic.
mbrock 12y ago
Semi-related: does anyone know why installing gems is so ridiculously slow? What is the thing doing? Downloading tarballs, yes, but then? It's a dynamic language; there is no compilation or verification! Why can I install Ruby packages using apt almost immediately, when gem/bundle install takes half a coffee break? I'm growing more impatient with the years. I have measured out my life with slow software. We talk about saving developer time with dynamic languages, but, as Flight of the Conchords sang, the sneakers don't seem to get much cheaper; what are your overheads?
- ishtu 12y ago
  gem: --no-document --verbose in your ~/.gemrc may speed up some things and show slowest steps (where '--no-document' means the same as deprecated '--no-rdoc --no-ri').
- richthegeek 12y ago
  Not that I install gems very often (Node.JS is my primary platform) but I find that the majority of the time is installing the different docs. Check the difference between "gem install sass" and "gem install sass --no-rdoc --no-ri" and be amazed.
  - shawabawa3 12y ago
    Which as far as I'm concerned is a bug. I don't even know how to view gem documentation, and I've never wanted or needed to. --no-document should be the default They could make it download the docs on first view
- ing33k 12y ago
  imo resolving dependencies is one of the factor
- tobeportable 12y ago
  U can also run with option -j4 to get 4 workers doing the task; u can also add it to your global config : bundle config --global jobs 4
- 12y ago
rfrey 12y ago
I'm really surprised by the amount of smugness in the comments here. A bit of good-natured teasing, followed by a wheelbarrow full of "ruby-devs" this and "web-devs" that. Take off your Hats of Superior Coding. Any one of us, regardless of honorific titles, could have made this mistake, and you know it. Being steeped in CS Fundamentals does not immunize you against bugs. Congratulations to tenderlove for finding the bug. Remember the details - it'll be a great war story in a few years.
- ryanjshaw 12y ago
  Is this even a bug or just a case of "in version 0.1 we'll do this quick & dirty", i.e. unaddressed technical debt? I make a point to keep track of all technical debt in my projects so that I have an easy way to quickly identify opportunities for improvements when there is spare capacity, and also so that technical debt isn't left unaddressed.
  - mkopinsky 12y ago
    How do you keep track of the technical debt? Ticket system?
    - bglusman 12y ago
      Shameless plug: https://github.com/bglusman/debt_ceiling https://github.com/bglusman/debt_ceiling
    - kybernetyk 12y ago
      //TODO: //FIXME: ;)
      - evincarofautumn 12y ago
        Wink all you like, but I get a lot of value from greppable, well written fixmes directly in the source they pertain to. If I’m working on a feature and I discover some odd misbehaviour, there is often a comment right there in the source, explaining precisely what I need to do next.
bcg1 12y ago
I'm not a ruby dev, so I guess maybe my perspective is not that great on this particular issue... but hats off to the dev with the fix, indeed this is how free software collaboration is supposed to work in my opinion. Even the dev with the fix wasn't rude about the original problem, he seemed pretty humble about it actually. If you think the Ruby guys are such shitty programmers you should be able to dive into their codebases and find the plethora of problems to show them what's up... so either give them a pull request or STFU ;)
- skj 12y ago
  Clearly that would require becoming adept with Ruby, which would require actually looking at Ruby code. That's a bit of a show-stopper.
- michaelfeathers 12y ago
  > Even the dev with the fix wasn't rude about the original problem, he seemed pretty humble about it actually. The Ruby community is very good interpersonally from my experience. It's a culture that I think comes from this: http://en.wikipedia.org/wiki/MINASWAN http://en.wikipedia.org/wiki/MINASWAN
  - nevinera 12y ago
    Unfortunately, the rails community are the visible minority, and they follow DHH's example more than Matz's.
    - thekaleb 12y ago
      David Heinemeier Hansson[1] for anybody else that was confused about what "DHH" referred to. [1]: http://en.wikipedia.org/wiki/David_Heinemeier_Hansson http://en.wikipedia.org/wiki/David_Heinemeier_Hansson
    - thinkbohemian 12y ago
      Tenderlove, the super nice guy who submitted that PR is on Rails core. Too bad to hear he's part of the evil visible minority that you just made up in your head.
jokoon 12y ago
I still can't see the real usefulness of linked lists, the idea of having a data container that doesn't have a transparent indexing algorithm sounds ill-advised. Linked lists should be named "linked graphs" instead. There is so much relevant science to learn about CPU caches, than there is about using a container which is based on nested pointer indirections.
- agentultra 12y ago
  The only thing I can think of is when your algorithm is building the sequence of items whose length cannot be precalculated. For lists of a certain size you might be able to save over the amortized cost of calling realloc on an array. Just have to follow the data and watch how its used and build your program to provide the simplest flow.
- noselasd 12y ago
  Note that the links in a linked can be in-line with the contained data (aka. intrusive pointers). Albeit quite uncommon, they don't need to be pointers/references at all, but indexes.
- jdmichal 12y ago
  If you're going to change the name, "unary trees" makes a lot more sense. "Linked graph" does not imply the 1-child-per-node linearity requirement of a linked list.
noir_lord 12y ago
It's always nice when a small change is a big win. This reminds me of the gc_disable() PR that reduced composer install times by half a few months back.
- Someone1234 12y ago
  Here's an article on the composer change: http://blog.ircmaxell.com/2014/12/what-about-garbage.html http://blog.ircmaxell.com/2014/12/what-about-garbage.html
voidhorse 12y ago
Good job, tenderlove, that's a nice performance boost. Personally, I really dislike Ruby's syntax, though I haven't spent a huge amount of time with it (because I dislike the syntax). The use of bracers and other lexical markers makes code a lot clearer and faster to decipher, imo, than a bunch of def and ends. (I know that () are optional in Ruby, can you also use {} if you desire? Again, not 100% familiar with the language features. Just know some standard rails implementations of the language). Maybe it just hasn't 'clicked' with me yet, but bleh. The dynamic typing doesn't help its case in my book either. That's my personal preference, and why I try to avoid using ruby, even for the web backed by rails despite it's popularity. Then again, if you need to get a web project up and running quickly rails is never a bad choice (in my experience).
- swah 12y ago
  Related: https://twitter.com/tenderlove/status/576389996019462144 https://twitter.com/tenderlove/status/576389996019462144
kendallpark 12y ago
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%" --Donald Knuth
airblade 12y ago
So many armchair critics! It's very easy to pontificate in hindsight when somebody else has done the hard work of actually finding something that can be improved.

223 points by jcn 12y ago

jammyrose 12y ago

i never knew this, thanks.

steipete 12y ago

Ruby people discovering algorithms ducks

perdunov 12y ago
Really. Every time I whine publicly how web programming people aren't familiar with even basic CS, I get a slap. But really, I should move to web programming. I'll be an expert computer scientist there, probably.
- deleted 12y ago
  [deleted]
- aidos 12y ago
  Annnndddd.... what reaction do you expect? "Oh, please come and do web development so we can bask in the glow of your self-righteousness and infinite knowledge of computers." /snark (apologies for being offensive, but good lord, what a silly statement - unless I missed the joke) I stand before you as a counterpoint to your foolish generalisation, and guess what, I know plenty of other people that don't fit your stereotype either. I'm not saying there's not an element of truth to your statement. See, here's the thing. People throughout the software (or any) industry have different collections of knowledge. There are an endless number of things to learn and each one of us is different and brings a different set of skills to the table. To be great at web development you spend years learning the subtleties of developing for a vast domain of different platforms. There are bugs in the platforms decades old that I know the intimate details of and have workarounds for especially constructed to fit in with the other bugs in the other platforms we deal with. And that's a tiny facet of what you need to know. You know what would really happen when you came over to web development? You'd find that a lot of the skills as a computer scientist aren't altogether useful. You wouldn't be an expert computer scientist. You'd be a junior developer, probably.
  - Swizec 12y ago
    I keep repeating myself on Hacker News, but once more, we've found the difference between Software Engineer and Computer Scientist. One makes things work, the other is a mathematician. Why do we keep conflating the two?
    - TickleSteve 12y ago
      Because you cant be good at either without having an element of the other. Ideally, they overlap.
      - Swizec 12y ago
        Ideally they do overlap. But we don't call people who design bridges physicists even though they know a shitload of physics. Our field is maturing. These difference are only going to become more important.
    - robmccoll 12y ago
      You should be careful with the term engineer. By definition, engineering is the application of scientific and mathematical knowledge to solving practical problems. Without knowing and understanding the science and math behind computing and software, one can hardly claim to be a software engineer.
      - FLUX-YOU 12y ago
        The title is cheap in the US and in some companies (cough) they slap it on every position that directly touches the product.
      - Dewie 12y ago
        So many programmers have this weird inferiority complex when it comes to the term "engineer". Not you, but those who think that most programming can never be called "engineering" because people don't die if you introduce a software bug[1] (as if the only kinds of modern "engineers" have to do with immediately safety-critical things). I prefer the plain "programmer" myself, but I don't see the big deal unless "engineer" is a protected title wherever that person lives. [1] Note that I said "most programming".
- ICWiener 12y ago
  Slap. Stop whining.
- robmccoll 12y ago
  That's a bit strongly worded, but I also see the pattern of people who came into computing from the Web direction rediscovering basic principles of computing and computer science. Similarly, the NoSQL community seems to slowly be discovering why traditional relational databases work the way they do, why supplying correct and durable replicated storage with high performance is difficult, and why some of the features that NoSQL threw out along side SQL itself in the name of simplicity and performance are actually quite useful and occasionally important.
- raverbashing 12y ago
  I was going to post the photoshopped joke, but this gets more to the gist of it http://stackoverflow.com/questions/3811678/add-two-variables-using-jquery http://stackoverflow.com/questions/3811678/add-two-variables... Edit: found it https://plus.google.com/u/0/+DougTyrrell/posts/br3kqg6Vet6 https://plus.google.com/u/0/+DougTyrrell/posts/br3kqg6Vet6
- drinchev 12y ago
  When I was in my early teenage years I was already making some development efforts on Pascal, VisualBasic and later on I switched to linux and started doing Perl CGI web apps. Back in time when I had to choose if I want to do CS degree I was already paid as a web developer and doing what I was going to study for. Then I asked some friends that were actually studying CS and they told me that they have a very tight schedule with work in the following disciplines : FORTRAN, ASM, C, C++ . I told them that's too low-level for me and probably I will not use it for my work so I decided to go into completely different sphere ( I graduated law ). Now I'm not the best programmer lived on the planet, but certainly I still do what I love and I'm paid for web development as high as a senior person, because of my experience - not CS degree. So... If you think you can make benefit to web development, why don't you start with a simple open source contribution to any of the existing projects and reduce Wirth's law [1] a bit with some low-level skills. But for something more complicated, please consider some experience first in that specific area. [1] http://en.wikipedia.org/wiki/Wirth%27s_law http://en.wikipedia.org/wiki/Wirth%27s_law
- manish_gill 12y ago
  I'm a web dev who has a degree in CS. Do you think I'm a unicorn? Of course not. Stop generalising.
- matthewmacleod 12y ago
  Good, you deserve a slap for being self-satisfied about it. There are loads of fully competent and skilled web developers out there with great, in-depth CS knowledge, and publicly berating them achieves nothing. Web development is interesting, because it tends to mix in people from a lot of different backgrounds — in particular, some of them come through the design side, and move down the stack. That's good, because it demonstrates the accessibility and flexibility of the stack; it's bad because it can result in suboptimal solutions to common problems.
- thaumaturgy 12y ago
  You probably wouldn't do that well in web development, because it's too different from embedded or systems programming. You probably have the luxury of specializing in one particular language, and maybe a handful of processor architectures. You probably rely on one or a few libraries, and know them backwards and forwards. You probably have your own personal repository of code and tactics that you go back to often. In other words, your knowledge of programming is probably narrow and deep. Web developers usually don't get that luxury. Top web developers today have to be fluent in a minimum of two programming languages (javascript and a backend language like Python, Ruby, PHP...), use several different fast prototyping approaches (css compilers and wacky templating systems), have a good working general knowledge of everything from the web browser to the web server, and cope with an environment in which at least one of those parts is changing on almost a daily basis. Web development is shallow and very, very broad. I prefer systems programming but I've worked as a web developer off and on for several years now. I have a lot of respect for any web developer that's really good at it. They aren't lesser programmers at all, and I suspect a lot of them, if they decided to do it, could kick the pants off of most systems programmers.
jph 12y ago
Java had the same kind of issue for years. In Java and Ruby, the standard library uses an object `+` operator to mean concatenation (not numeric addition), and the implementation did immediate data copies, rather than doing reference linking and copy-on-write (or immutability).
- tr352 12y ago
  But in Java this happens only with strings doesn't it?
  - bcg1 12y ago
    Sort of... technically only the '+' operator only applies to strings... however it is essentially the same issue as the pull request, from what I can gather (I assume the issue comes from allocating a new array with size length+1 and copying the original each time a record is added). Same thing happens with java.util.ArrayList.add() and its cousins though, and from my experience people rarely use the constructor specifying an initial capacity, so the default gets used even if it is would obviously be woefully small (default is 10 BTW, in case you're curious & lazy :). Also one might argue that the problem is actually much worse with strings, because string concatenation is so common and the syntactic sugar of the '+' operator for strings encourages the "wrong" way.
    - this_user 12y ago
      Java's JIT compiler optimises string concatenation by substituting a StringBuilder and has been doing so for a while. As to using the wrong data type, that's really the programmer's fault. If you don't allocate enough capacity or use another data type (e.g. LinkedList) if you don't know the required capacity, you are doing a bad job.
      - bcg1 12y ago
        To nitpick, Java's JIT compiler compiles Java bytecodes to machine code, but I know that javac does to the type of optimization that you are describing. There are plenty of scenarios though where it can't/won't do that optimization ... and if you are using the binary version of a library compiled without that optimization I'm pretty sure you're out of luck, especially if the method you're calling is not JIT'd. I'm not really trying to knock any particular language or runtime here, the point I was trying to make is that nearly every language I've used has quirks that encourage convenience over optimization, and that just because you're coding in language foo, it doesn't mean you're off the hook when it comes to being intentional about the choice between them.
DiabloD3 12y ago
Not sure why parent is getting downvoted, there is a serious problem in the Ruby community that very few of them have read GoF, TAoCP, and/or K&R.
- matthewmacleod 12y ago
  Because it's smug and adds nothing to the conversation. I don't see any evidence that the Ruby community suffers more than any other development community from this sort of thing — that is, the ones where high performance is not the biggest concern, of course.
- Ao7bei3s 12y ago
  Stop jumping to conclusions, and stop throwing around buzzwords. GoF is a (somewhat C++-centric) book about design patterns that's completely unrelated to the discussion at hand, may not be the best resource to learn about design patterns and has nothing to do with CS. TAoCP is more like an encyclopedia; actually reading through even one chapter takes a significant amount of effort (if you want to get anything out of it). Try it. (Yes, I've worked with it.) K&R is a 27 years old, thoroughly outdated book about C. There are better options[1]. [1] Try the 16 years old book "Expert C Programming" by Peter van Linden, which is excellent, even though outdated too.
  - bcg1 12y ago
    +10 if I could, re "Expert C Programming"; excellent read, even if you aren't a C programmer
WickyNilliams 12y ago
Um... isn't this a data structure not an algorithm?
- picks_at_nits 12y ago
  Programs = Data Structures + Algorithms, and it is often the case that there are deep relationships between the data structures and the algorithms. For example, any linear recursive algorithm that deals with the head of a list and the tail/rest/butHead of a list is optimized for a linked list implementation. So... to understand a linked list, you really need to be familiar with algorithms that bisect list sin this manner, and the reverse: To understand algorithms that bisect lists in this manner, you have to be familiar with a linked list. So... Yes it’s a data structure, but it’s joined at the hip to the algorithms that operate best on it.
  - WickyNilliams 12y ago
    I know, I was intentionally curt in my reply because snark is best solved with more snark </snark>
randomdata 12y ago
Except the linked list implementation was added to the project in 2013[1], and is presumably used elsewhere in the program. This only fixes a couple of bugs using that same mechanism. https://github.com/rubygems/rubygems/blob/800f2e63bc6174b5b4dea5528110b09d89fe3dd1/lib/rubygems/util/list.rb https://github.com/rubygems/rubygems/blob/800f2e63bc6174b5b4...
dang 12y ago
> Ruby people discovering algorithms ducks This was not a good comment to post to HN. When you toss a Molotov cocktail into an HN thread and "duck", here is what we are going to get: web programming people aren't familiar with even basic CS I stand before you as a counterpoint to your foolish generalisation Oh cute, a web dev. You've just reinvented 1975 [...] Would you like a pat on the head? Stop whining your comment is bullshit you deserve a slap For any large group like "Ruby people" or "web programming people", HN has many users who either identify with being part of that group or identify with not being part of it. Given the numbers, there will always be a few who are having a bad day or feeling defensive or what have you, enough to respond angrily when someone posts a slur. Then their counterparts feel attacked, and down the whole thing goes. Social padding prevents disputes like this from turning ugly, but we don't have that on HN. Even when you know another user from their comment history, that's not much information. Imagination fills in the gaps and then we imagine the other in the worst light. That's why the community here is fragile. To be a good community member, please don't post things that could easily set the thread on fire. If after editing them out, your comment has nothing substantive left, please don't post it.
- steveklabnik 12y ago
  Thank you.

chatman 12y ago

Just comes to show how careless Ruby guys were while building this.

eddd 12y ago
1. Make it work 2. Optimize
- rosspanda 12y ago
  From working with Ruby guys its normally 1. Make it work 2. Spin up more AWS boxes
  - pothibo 12y ago
    Nothing's wrong with spinning up more AWS boxes. If it costs 300$ annually to solve a problem that would cost 5k$ in development to fix, I believe it's a wise choice. Yeah, down the line you will eventually have to do optimization, but you will prioritize.
    - rosspanda 12y ago
      A agree somewhat, but I've seen 10 box systems that could run on raspberry pie with good code
      - lmm 12y ago
        I've seen them. I've worked on them. But again, where's the cost/benefit?
        nirvdrum 12y ago
        I'm hardly what most environmentalists would call an "environmentalist", but one cost here is the increase in carbon footprint. Of course, to the company the cost/benefit analysis errs on the side of just spinning up more boxes. But from a larger perspective, taking some extra time to make more efficient use of machines could have a drastic impact. Many optimizations don't require months to implement. Many of those are even avoidable with a bit of foresight.

icebraining 12y ago

I'm not very familiar with Ruby; where exactly did the duplication occur in the original code?

deleted 12y ago
[deleted]
barrkel 12y ago
I believe it's in the Gem::Specification.traverse method here: http://ruby-doc.org/stdlib-1.9.3/libdoc/rubygems/rdoc/Gem/Specification.html#method-i-traverse http://ruby-doc.org/stdlib-1.9.3/libdoc/rubygems/rdoc/Gem/Sp... The 'trail' parameter, an array, was implicitly duplicated by applying the '+' operator on each recursion through a dependency.
- weavie 12y ago
  trail = trail + [self] That + operator looks so innocent, so seductively simple..

kilotaras 12y ago

I'm torn on this one. It's a great performance improvement, but on the other hand I would expect this way sooner than after almost 4 years of usage.

vidarh 12y ago
It's because the main bottleneck for most apps that uses lots of gems is elsewhere (the load path grows with each extra gem, meaning a simple 'require' gets more and more expensive the more gems your app uses).

jph 12y ago

Great pull request. Ruby makes it easy to duplicate data by calling `.dup` or `+`, and this does help with state isolation. But duplication is an expensive operation. Ruby's standard libraries don't have much support for immutability, or deep cloning, or copy on write, or linking concatenation. There's no standard library way to ask for a snapshot of an object. So in the early days for Ruby, an idiom was: if you're writing a method that takes a list, and you need to be sure your list doesn't change out from under you, then duplicate it, get it working, and if it becomes a bottleneck then optimize it.

cranium 12y ago

All your tests passed, nothing broken, a small bit of code for tremendous optimization,... I can feel the satisfaction!

shiggerino 12y ago

Nobody show this to Bjarne Stroustrup https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo

kaeluka 12y ago
AFAICT, this performance bug is not at all related to the linked-list vs. vector issue.
- rakoo 12y ago
  Yes it does: vectors are good for random access, linked-lists are good for doing stuff in the front/back of the list. The performance bug we have here is solved by finding a way to insert stuff at the front/back (and also going through each item in the list); there is no need for random access.
  - kaeluka 12y ago
    If I remember Bjarne's talk correctly, vectors (in C++) are even fast at inserting because they have densely packed representation which rhymes well with modern computer architecture. Inserting in a linked list is slow, as walking the list to find the element at which to insert will already incur O(N) cache misses, whereas in vectors it's only O(1) cache misses. Moving the elements in the vector one to the right is fast due to computer architecture dealing well with predictable patterns. The allocations here (ruby) are reduced because the implementation of appending is horribly slow in the first place, using defensive cloning (I'm taking jph's word here).
    - herewego 12y ago
      Yes, but FWIW most linked list implementations have a reference or pointer to the tail, making appends not O(n), but O(1). However, there is a threshold, depending on use case, where a small vector being resized multiple times larger than the original will be faster than many linked list appends. Point being, either can accel depending on use case.
  - 12y ago

mjs 12y ago

Are there any profiling tools that would have found this? Flame graphs showing the time spent in traverse, perhaps? It seems like this should have been trivially detectable, since the difference is so dramatic.

mbrock 12y ago

Semi-related: does anyone know why installing gems is so ridiculously slow? What is the thing doing? Downloading tarballs, yes, but then? It's a dynamic language; there is no compilation or verification! Why can I install Ruby packages using apt almost immediately, when gem/bundle install takes half a coffee break? I'm growing more impatient with the years. I have measured out my life with slow software. We talk about saving developer time with dynamic languages, but, as Flight of the Conchords sang, the sneakers don't seem to get much cheaper; what are your overheads?

ishtu 12y ago
gem: --no-document --verbose in your ~/.gemrc may speed up some things and show slowest steps (where '--no-document' means the same as deprecated '--no-rdoc --no-ri').
richthegeek 12y ago
Not that I install gems very often (Node.JS is my primary platform) but I find that the majority of the time is installing the different docs. Check the difference between "gem install sass" and "gem install sass --no-rdoc --no-ri" and be amazed.
- shawabawa3 12y ago
  Which as far as I'm concerned is a bug. I don't even know how to view gem documentation, and I've never wanted or needed to. --no-document should be the default They could make it download the docs on first view
ing33k 12y ago
imo resolving dependencies is one of the factor
tobeportable 12y ago
U can also run with option -j4 to get 4 workers doing the task; u can also add it to your global config : bundle config --global jobs 4
12y ago

rfrey 12y ago

I'm really surprised by the amount of smugness in the comments here. A bit of good-natured teasing, followed by a wheelbarrow full of "ruby-devs" this and "web-devs" that. Take off your Hats of Superior Coding. Any one of us, regardless of honorific titles, could have made this mistake, and you know it. Being steeped in CS Fundamentals does not immunize you against bugs. Congratulations to tenderlove for finding the bug. Remember the details - it'll be a great war story in a few years.

ryanjshaw 12y ago
Is this even a bug or just a case of "in version 0.1 we'll do this quick & dirty", i.e. unaddressed technical debt? I make a point to keep track of all technical debt in my projects so that I have an easy way to quickly identify opportunities for improvements when there is spare capacity, and also so that technical debt isn't left unaddressed.
- mkopinsky 12y ago
  How do you keep track of the technical debt? Ticket system?
  - bglusman 12y ago
    Shameless plug: https://github.com/bglusman/debt_ceiling https://github.com/bglusman/debt_ceiling
  - kybernetyk 12y ago
    //TODO: //FIXME: ;)
    - evincarofautumn 12y ago
      Wink all you like, but I get a lot of value from greppable, well written fixmes directly in the source they pertain to. If I’m working on a feature and I discover some odd misbehaviour, there is often a comment right there in the source, explaining precisely what I need to do next.

bcg1 12y ago

I'm not a ruby dev, so I guess maybe my perspective is not that great on this particular issue... but hats off to the dev with the fix, indeed this is how free software collaboration is supposed to work in my opinion. Even the dev with the fix wasn't rude about the original problem, he seemed pretty humble about it actually. If you think the Ruby guys are such shitty programmers you should be able to dive into their codebases and find the plethora of problems to show them what's up... so either give them a pull request or STFU ;)

skj 12y ago
Clearly that would require becoming adept with Ruby, which would require actually looking at Ruby code. That's a bit of a show-stopper.
michaelfeathers 12y ago
> Even the dev with the fix wasn't rude about the original problem, he seemed pretty humble about it actually. The Ruby community is very good interpersonally from my experience. It's a culture that I think comes from this: http://en.wikipedia.org/wiki/MINASWAN http://en.wikipedia.org/wiki/MINASWAN
- nevinera 12y ago
  Unfortunately, the rails community are the visible minority, and they follow DHH's example more than Matz's.
  - thekaleb 12y ago
    David Heinemeier Hansson[1] for anybody else that was confused about what "DHH" referred to. [1]: http://en.wikipedia.org/wiki/David_Heinemeier_Hansson http://en.wikipedia.org/wiki/David_Heinemeier_Hansson
  - thinkbohemian 12y ago
    Tenderlove, the super nice guy who submitted that PR is on Rails core. Too bad to hear he's part of the evil visible minority that you just made up in your head.

jokoon 12y ago

I still can't see the real usefulness of linked lists, the idea of having a data container that doesn't have a transparent indexing algorithm sounds ill-advised. Linked lists should be named "linked graphs" instead. There is so much relevant science to learn about CPU caches, than there is about using a container which is based on nested pointer indirections.

agentultra 12y ago
The only thing I can think of is when your algorithm is building the sequence of items whose length cannot be precalculated. For lists of a certain size you might be able to save over the amortized cost of calling realloc on an array. Just have to follow the data and watch how its used and build your program to provide the simplest flow.
noselasd 12y ago
Note that the links in a linked can be in-line with the contained data (aka. intrusive pointers). Albeit quite uncommon, they don't need to be pointers/references at all, but indexes.
jdmichal 12y ago
If you're going to change the name, "unary trees" makes a lot more sense. "Linked graph" does not imply the 1-child-per-node linearity requirement of a linked list.

noir_lord 12y ago

It's always nice when a small change is a big win. This reminds me of the gc_disable() PR that reduced composer install times by half a few months back.

Someone1234 12y ago
Here's an article on the composer change: http://blog.ircmaxell.com/2014/12/what-about-garbage.html http://blog.ircmaxell.com/2014/12/what-about-garbage.html

voidhorse 12y ago

Good job, tenderlove, that's a nice performance boost. Personally, I really dislike Ruby's syntax, though I haven't spent a huge amount of time with it (because I dislike the syntax). The use of bracers and other lexical markers makes code a lot clearer and faster to decipher, imo, than a bunch of def and ends. (I know that () are optional in Ruby, can you also use {} if you desire? Again, not 100% familiar with the language features. Just know some standard rails implementations of the language). Maybe it just hasn't 'clicked' with me yet, but bleh. The dynamic typing doesn't help its case in my book either. That's my personal preference, and why I try to avoid using ruby, even for the web backed by rails despite it's popularity. Then again, if you need to get a web project up and running quickly rails is never a bad choice (in my experience).

swah 12y ago
Related: https://twitter.com/tenderlove/status/576389996019462144 https://twitter.com/tenderlove/status/576389996019462144

kendallpark 12y ago

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%" --Donald Knuth

airblade 12y ago

So many armchair critics! It's very easy to pontificate in hindsight when somebody else has done the hard work of actually finding something that can be improved.