6 ms·

I was flabbergasted that someone was asked implement a linked list in Ruby. My initial reaction was 'That is an incredibly stupid thing to do.' My slightly mor

I was flabbergasted that someone was asked implement a linked list in Ruby. My initial reaction was 'That is an incredibly stupid thing to do.' My slightly more in depth reaction was "Isn't that what mutable arrays are for?" And my final reaction was, "Maybe I'm missing something." At which point I tried to figure out the benefits of a linked list over a ruby array. I wasn't able to come up with a good reason to use a linked list in Ruby, but maybe someone could enlighten me.

kenjackson 15y ago
Linked lists and arrays typically have different perf characteristics (although I don't know how Ruby arrays work). For example if I give you an element of an array/linked list and tell you to insert a new element adjacent to it -- a linked list is a constant time insertion, whereas arrays are typically O(n).
- tptacek 15y ago
  That's a sensible point, but interpreter and runtime overhead crushes any cost savings you might get from adjusting links instead of the whole array backing store. (Ruby arrays, at least in MRI, are basically STL vectors). 1000 inserts to the middle of a 1,000,000 element Ruby array happens so quickly you can barely perceive the delay. The same insert pattern to a basic Ruby linked list sets my machine on fire.
  - kenjackson 15y ago
    Wow, that sounds painful. So do people not use things like graphs or trees in Ruby due to perf? I actually used to do Python development -- about 13 or so years ago, but had to quit due to perf just being abysmal for applications intended for customers (and started focusing on C++). Is Ruby today similarly bad for apps that make heavy use of data structures like trees/graphs as Python more than a decade ago? EDIT: Updated to remove the term 'toy-apps'
    - tptacek 15y ago
      I'd respond to this, but the "toy apps" wording makes me think this conversation will be unproductive.
      - kenjackson 15y ago
        Updated to remove the term.
        tptacek 15y ago
        Well, to start with, the issue here isn't that Ruby doesn't efficiently support the "modify-in-the-middle" access pattern. It's just that Ruby does this with the Array class. Similarly, even if you intend to insert into the middle, you still probably still want to use NSMutableArray in Objective C. Even on fairly large graphs --- say, graphs at the scale of basic blocks in a program, but (obviously) not on the scale of "recommendation graph at Amazon" --- you shouldn't be burning huge numbers of cycles seeking through reference links. In naive reference-link implementations, Ruby sorely increases the constant factors for graph analysis, but computing a minimum cost spanning tree isn't going to kill you (especially because the intermediate data structures you'd use to do it would be native-code Arrays and Hashes). On the other hand, linked lists more or less pessimize Ruby, forcing it to do nothing but expensive interpreter looping, pointer chasing, and object management. Having said all that, for serious work, I'd keep my data structures outboard, probably in Redis. Other people would probably answer "just write a graph library in C; for instance, you could write a C wrapper around void-star-specialized boost::graph", then bridge it to Ruby with FFI. Ruby is as good at C for I/O bound problem subsets. This is a lot of problems, and so having a language as pleasant to write in as Ruby is a win (you could say the same for Node.js and maybe even Python). It is obviously not the only language you'll ever need, though.
    - jrockway 15y ago
      The key to understanding languages whose runtimes interpret an optree is to realize that all performance depends on the number of ops. When you implement a linked list in pure Ruby, that's a lot of operations that the runtime has to keep track of. When you insert into an array, the actual work is done (in C) in a single operation. Less bookkeeping, less overhead. If you implement both arrays and linked lists in pure Ruby, you'll see the performance you expect. If you implement arrays in C and linked lists in Ruby, the array will probably be faster for any workload. (But implement the linked list in C, and you'll see the performance you expect again. It's computer science, not magic.)
tptacek 15y ago
Linked lists are overused even in C, where they have a natural expression. The reason to use a list instead of an array is that it's cheap to insert/delete anywhere into a list, but expensive to do so in the middle of an array. There's probably no expression of a list in Ruby where insertion is cheaper than inserting into an array. Perhaps if your "list" is a secondary Fixnum index on a larger pool of objects? At any rate, that's no longer a "linked list". I think it's a silly question. I hope the expected answer is, "why would I ever do that?"
tedunangst 15y ago
My first guess would be that a FIFO queue is more efficient as a list than an array, but maybe there's something weird about ruby that makes that untrue. I'd love to hear why.
- tptacek 15y ago
  Unless you have an extraordinarily clever implementation of "linked list in Ruby" (in which case this is still a terrible interview question), no. Arrays are more efficient for every reasonable access pattern. If the links of your list are references to Ruby objects (which every online "linked list in ruby" page uses), they're not so much "more efficient" as they are "tractable" compared to linked-list's "intractable".
  - tedunangst 15y ago
    Looks like you're right, interpreter time dominates unless I use rbx, and it's still not a big win for linked lists. But the meaning of your last sentence escapes. Linked lists are tractable compared to intractable linked lists? Antecedent mismatch?
    - tptacek 15y ago
      Probably. All I meant to say is that on MRI, you might as well give up on reference-based linked lists; they just don't work at scale. In rbx, you're saying 1000.times { list.insert(500000, 666) } actually beats 1000.times { array.insert(500000, 666) } I really should be taking rbx way more seriously.
      - tedunangst 15y ago
        Something like that. rbx takes about 0.5 secs to start up, but after that it generally runs in the neighborhood of 10x faster, assuming you're spending enough time in actual ruby code to make that possible.
        15y ago
DannoHung 15y ago
Non-mutable linked lists have advantageous memory/copying properties.
brown9-2 15y ago
I think you are looking at this from the wrong angle. Just because it made a good interview question (for the interviewer) doesn't mean it's something you'd actually want to use in everyday practice.
- kamaal 15y ago
  Why would you ask questions to a candidate which have nothing to do with his job? Will you ask a marathon runner to prove his worth by asking him how quickly he can sprint?

kenjackson 15y ago

Linked lists and arrays typically have different perf characteristics (although I don't know how Ruby arrays work). For example if I give you an element of an array/linked list and tell you to insert a new element adjacent to it -- a linked list is a constant time insertion, whereas arrays are typically O(n).

tptacek 15y ago
That's a sensible point, but interpreter and runtime overhead crushes any cost savings you might get from adjusting links instead of the whole array backing store. (Ruby arrays, at least in MRI, are basically STL vectors). 1000 inserts to the middle of a 1,000,000 element Ruby array happens so quickly you can barely perceive the delay. The same insert pattern to a basic Ruby linked list sets my machine on fire.
- kenjackson 15y ago
  Wow, that sounds painful. So do people not use things like graphs or trees in Ruby due to perf? I actually used to do Python development -- about 13 or so years ago, but had to quit due to perf just being abysmal for applications intended for customers (and started focusing on C++). Is Ruby today similarly bad for apps that make heavy use of data structures like trees/graphs as Python more than a decade ago? EDIT: Updated to remove the term 'toy-apps'
  - tptacek 15y ago
    I'd respond to this, but the "toy apps" wording makes me think this conversation will be unproductive.
    - kenjackson 15y ago
      Updated to remove the term.
      - tptacek 15y ago
        Well, to start with, the issue here isn't that Ruby doesn't efficiently support the "modify-in-the-middle" access pattern. It's just that Ruby does this with the Array class. Similarly, even if you intend to insert into the middle, you still probably still want to use NSMutableArray in Objective C. Even on fairly large graphs --- say, graphs at the scale of basic blocks in a program, but (obviously) not on the scale of "recommendation graph at Amazon" --- you shouldn't be burning huge numbers of cycles seeking through reference links. In naive reference-link implementations, Ruby sorely increases the constant factors for graph analysis, but computing a minimum cost spanning tree isn't going to kill you (especially because the intermediate data structures you'd use to do it would be native-code Arrays and Hashes). On the other hand, linked lists more or less pessimize Ruby, forcing it to do nothing but expensive interpreter looping, pointer chasing, and object management. Having said all that, for serious work, I'd keep my data structures outboard, probably in Redis. Other people would probably answer "just write a graph library in C; for instance, you could write a C wrapper around void-star-specialized boost::graph", then bridge it to Ruby with FFI. Ruby is as good at C for I/O bound problem subsets. This is a lot of problems, and so having a language as pleasant to write in as Ruby is a win (you could say the same for Node.js and maybe even Python). It is obviously not the only language you'll ever need, though.
  - jrockway 15y ago
    The key to understanding languages whose runtimes interpret an optree is to realize that all performance depends on the number of ops. When you implement a linked list in pure Ruby, that's a lot of operations that the runtime has to keep track of. When you insert into an array, the actual work is done (in C) in a single operation. Less bookkeeping, less overhead. If you implement both arrays and linked lists in pure Ruby, you'll see the performance you expect. If you implement arrays in C and linked lists in Ruby, the array will probably be faster for any workload. (But implement the linked list in C, and you'll see the performance you expect again. It's computer science, not magic.)

tptacek 15y ago

Linked lists are overused even in C, where they have a natural expression. The reason to use a list instead of an array is that it's cheap to insert/delete anywhere into a list, but expensive to do so in the middle of an array. There's probably no expression of a list in Ruby where insertion is cheaper than inserting into an array. Perhaps if your "list" is a secondary Fixnum index on a larger pool of objects? At any rate, that's no longer a "linked list". I think it's a silly question. I hope the expected answer is, "why would I ever do that?"

tedunangst 15y ago

My first guess would be that a FIFO queue is more efficient as a list than an array, but maybe there's something weird about ruby that makes that untrue. I'd love to hear why.

tptacek 15y ago
Unless you have an extraordinarily clever implementation of "linked list in Ruby" (in which case this is still a terrible interview question), no. Arrays are more efficient for every reasonable access pattern. If the links of your list are references to Ruby objects (which every online "linked list in ruby" page uses), they're not so much "more efficient" as they are "tractable" compared to linked-list's "intractable".
- tedunangst 15y ago
  Looks like you're right, interpreter time dominates unless I use rbx, and it's still not a big win for linked lists. But the meaning of your last sentence escapes. Linked lists are tractable compared to intractable linked lists? Antecedent mismatch?
  - tptacek 15y ago
    Probably. All I meant to say is that on MRI, you might as well give up on reference-based linked lists; they just don't work at scale. In rbx, you're saying 1000.times { list.insert(500000, 666) } actually beats 1000.times { array.insert(500000, 666) } I really should be taking rbx way more seriously.
    - tedunangst 15y ago
      Something like that. rbx takes about 0.5 secs to start up, but after that it generally runs in the neighborhood of 10x faster, assuming you're spending enough time in actual ruby code to make that possible.
      - 15y ago

DannoHung 15y ago

Non-mutable linked lists have advantageous memory/copying properties.

brown9-2 15y ago

I think you are looking at this from the wrong angle. Just because it made a good interview question (for the interviewer) doesn't mean it's something you'd actually want to use in everyday practice.

kamaal 15y ago
Why would you ask questions to a candidate which have nothing to do with his job? Will you ask a marathon runner to prove his worth by asking him how quickly he can sprint?