2 ms·
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
by 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.
- tptacek 15y agoCan you show me your list implementation? I just installed rbx and tried this; the Array implementation ran in single-digit seconds, but I gave up and CTR-C'd the list one (which works fine for smaller lists).
- tedunangst 15y agoWhy do I get the sinking feeling I'm about to embarrass myself by implementing a linked list wrong? Anyway, here's the test case I used, where I'm emulating a FIFO. class Link attr_accessor :next, :v end i = 2000 j = 10000 k = 100 if true p "linked list" j.times { head = Link.new tail = head i.times { n = Link.new n.v = 12 tail.next = n tail = n } (i-k).times { n = head head = head.next } } else p "array" j.times { arr = [] i.times { n = Link.new n.v = 13 arr << n } (i-k).times { n = arr.pop } } end
- tptacek 15y agoMy test was: 1. Make a 1,000,000 node linked list of integers (I used doubly linked lists but I don't think it matters). 2. 1,000 times, insert into the middle of the list; I wrote a trivial O(n) stateless insert and called it with an offset of 500,000 1,000 times. 3. Make a 1,000,000 element Array of integers --- I just did "1000000.times.map". 4. 1,000 times call "insert" with an index of 500,000. Step (2) takes so long I kill the process. Step (4) takes a barely perceptible amount of time. (Both in Rubinius). It looks to me like: * You're using much smaller data structures than I am * Your "Array" case is still building Link objects, so still incurs the object management overhead * You're inserting at the head of the list every time, which doesn't incur seek time. But inserts at the head or tail of a contiguous array don't need to seek or reallocate either.
- tedunangst 15y agoIf you have to seek into the list, of course it's going to suck, that's not a good application for a list. Your test would blow just as bad in C. I'm not sure that says anything interesting about lists vs arrays in ruby in particular. I am using the same data structure, I guess it would be a little smaller without the next attr. Still seems fair. Building an array of objects is going to require allocating them. I build hand rolled linked lists by directly linking the objects of interest. Calling the class Link may have been a misnomer, it could have been called AnyClass. It's easy to insert at the tail of an array (I'm actually inserting at the tail of the list, btw), but popping from the front means having to shift everything down. That's what makes the FIFO case interesting. If we're going to prove that ruby is too slow for linked lists to be viable, we need to be testing a scenario where linked lists generally are viable.
- tptacek 15y agoThe most naive possible C implementation takes 2.5 seconds to run this same test. I just tried it. The point of a list is "insert and delete from the middle", so I don't know how to respond to the idea that actually inserting and deleting from the middle of the list is a bad benchmark. It's difficult to respond to your last point about FIFOs for a different reason. Popping 1000 times from a 1,000,000 Array is so fast that I'd have to write code to benchmark it. And Ruby doesn't even optimize for that case; in real code, I'd use a ring buffer so that pops are just pointer adds. Ruby is, to the best of my knowledge, actually copying every single time. Copies are just way way way faster than you seem to expect them to be.
- barrkel 15y agoThe reason manipulating linked lists in the middle is faster than arrays is so you can save the O(n) work of moving elements. But you lose that if you still do O(n) worth of seeking. There is no big-O difference between inserting and deleting in the middle of an array and a plain linked list, if the linked list is forced to seek. I'm sure this is as obvious to you as it is to me, but perhaps the perspective it comes from explains why people are thinking that your described operations on the list are a dodgy benchmark for judging linked lists vs arrays; absent constant factors, they should perform the same. (And yes, for reasonable input on modern machines, the constant factors will dominate.)