4 ms·

> If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a

> If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. It takes almost no time at all to do that, depending on the size of the elements. But you have a starting assumption there that the vector must always be stored sorted. Challenge that assumption. If insertion is perfectly balanced with traversal it may be true, but that's also rarely the case. It's fairly trivial to instead track if the vector is already sorted or not & sort when sorted access is actually needed. > Besides, linked lists aren't that bad if the nodes are close enough in memory (read: consecutive) Which doesn't really happen outside of a controlled benchmark. If the linked list is stored in a single consecutive allocation, then resizing has observable side effects (eg, pointers to elements become invalidated). You can do things like allocate chunks at a time so that some elements are consecutive, but you won't have all elements consecutive or close in memory.

titzer 5y ago
>> you need to copy 500 of them > It takes almost no time at all to do that, Uh, 500 loads and dependent stores, at minimum, in the best case hitting L1 cache, which is 3 cycles. So you are talking about 1500 cycles to....avoid a single cache line miss due to chasing a linked list pointer? A miss to main memory is 100-200 cycles, maximum. More likely you are going to L2/L1 which is 12-50 cycles. So no, in no circumstances would I expect copying 500 elements to be faster than chasing a single pointer. > Challenge that assumption. You don't get to pick the application behavior. If it needs to a do a lot of inserts and traversals, it just does. >> are close enough in memory (read: consecutive) > Which doesn't really happen outside of a controlled benchmark. There is no supporting information for this statement at all. Of course a list created all at once using a bump-pointer allocator is going to be consecutive. And a (moving) garbage collector is going to dynamically reorganize the nodes of a list, generally in a breadth-first way, depending on the marking algorithm. That can result in the nodes of the list being laid out consecutively after compacting, no matter where they were originally organized. Memory behavior of programs is complicated. I find it surprising that we're having a conversation that we can't or shouldn't use linked lists now because vectors are universally better, or we can lazy sort or some other crazy workaround. I'm not sure what motivates this whole line of argumentation. Sometimes lists are just the best damn thing.
- atq2119 5y ago
  > 500 loads and dependent stores, at minimum, in the best case hitting L1 cache, which is 3 cycles. So you are talking about 1500 cycles This is absolutely not how modern CPUs work, and I think you misunderstood where the dependencies are. All the load/store pairs are independent from each other, which means they can be executed in parallel. Which means that this code is throughput limited. Modern CPUs tend to have at least 2 load/store ports, so we're talking a throughout of one copy per cycle, or 500 cycles for the entire operation (plus warm-up time). Furthermore, this is a pure memmove in many cases, which means a real memmove implementation that has been optimised using vector instructions can be used. Now you're talking about moving 32 bytes per cycle, or 4 array entries if they're pointer-sized, which brings us down to 125 cycles plus warm-up. Which is on the order of a miss to memory...
  - titzer 5y ago
    Great, now we're talking! I realized in the background that yes, there aren't dependencies between the copies...if the regions of memory don't overlap. But they do overlap, especially if you are just moving them over one element, so the simple analysis doesn't hold. But you're right that's it's just a memmove, so there is an optimized vector implementation (which, incidentally, is probably going to have relatively large setup costs for 500 elements). And oops, now your vectors are 1 million entries. I appreciate the discussion. It's a bit of a rathole for something that you shouldn't be optimizing if you can completely avoid it by using the right data structure for your needs.
    - kllrnohj 5y ago
      > And oops, now your vectors are 1 million entries. As soon as you traverse that linked list of 1 million entries, oops. In fact, here, I put together a quick benchmark. It inserts in the middle of the list and then traverses it (since, after all, ordering is irrelevant if there's no traversal). https://paste.ofcode.org/7Buz2Mua9xna55TC3uFaQp https://paste.ofcode.org/7Buz2Mua9xna55TC3uFaQp Test system is a Ryzen 3700x. I tried to avoid all amounts of compiler optimizations and believe I succeeded, but by all means happy to take a review of the above. Would love to see you do a similar test in whatever runtime you want, especially one with that juicy super-amazing compacting GC that makes linked-lists so fast. At 100 elements vector wins (40ns vs 160ns). At 1000 elements vector wins (~300ns vs. ~1000ns). At 10,000 elements vector wins (~2700ns vs. 12,000ns). At 100,000 elements guess what? Vector still wins (29us vs. 130us). You are either vastly underestimating how slow linked-list traversal is or vastly overestimating how expensive memmove is. But you did say 1 million entries so let's give that a shot: Vector size 1000000 took 286,123ns (Vector at 1 million is only twice as slow as a linked list at 100,000, linked lists aren't off to a strong start here...) Linked-list size 1000000 took 2,670,542ns Oh my god it's a bloodbath. Vector wins by 10x. Still. At 1 million entries the O(N) insert structure is still faster than the O(1) insert one. And the gap is getting bigger! And this is the basically best case for linked lists of inserting in the middle happens equally as often as traversal, I'll point out. If traversal is rare obviously a lazy sort would crush these vector results, and if traversal is common the linked lists results get that much worse. Now really these results shouldn't actually be that surprising if you really dig into it. After all, the vector version of this is storing (and therefore traversing) 4MB of data. That's all 1 million ints really is, it's not very big. Now sure you can store bigger things, but much bigger and you're probably storing a vector of pointers instead which only bumps that to 8MB of data. The linked list version, on the other hand, is storing 2 pointers + an int for each node. That's 20MB of data total. So resizing the vector involves a read of 2MB of data, a write of 2MB of data, and a traversal of 4MB of data - 8MB total. Simply traversing the linked list is hitting 20MB of data - over double the amount of memory bandwidth utilized. That's a big difference. In fact on my system at 1 million entries that happened to be the difference between the vector version comfortably fitting in L3 with loads of room to spare (especially since the resize made part of it nice & hot) vs. the linked-list version not coming close to fitting (specs on this CPU claim 32MB of L3, but it's really 16MBx2 - hitting the far L3 isn't much slower than hitting main memory). So more data to hit and it's pointer chasing? Modern CPUs just really hate that. Like a lot. Since I don't intend to cheat at happening to have sufficient L3 for the use case you laid out (combined with the benchmark naturally keeping this hot), I also tried adjusting it. I changed the containers to hold intptr's instead, and hit it with 10 million entries. Neither one comes close to fitting in L3 now. Still 80MB of data for the vector vs. 240MB for the linked list but maybe not having that copy and with both of them thrashing L3 the linked list might finally show something to redeem it. Vector size 10,000,000 took 3,680,111ns Linked-list size 10,000,000 took 26,460,333ns That's a big fucking oof right there. > I appreciate the discussion. It's a bit of a rathole for something that you shouldn't be optimizing if you can completely avoid it by using the right data structure for your needs. And a linked list is rarely the right data structure, so yes you should avoid trying to optimize for that without measuring.

titzer 5y ago

>> you need to copy 500 of them > It takes almost no time at all to do that, Uh, 500 loads and dependent stores, at minimum, in the best case hitting L1 cache, which is 3 cycles. So you are talking about 1500 cycles to....avoid a single cache line miss due to chasing a linked list pointer? A miss to main memory is 100-200 cycles, maximum. More likely you are going to L2/L1 which is 12-50 cycles. So no, in no circumstances would I expect copying 500 elements to be faster than chasing a single pointer. > Challenge that assumption. You don't get to pick the application behavior. If it needs to a do a lot of inserts and traversals, it just does. >> are close enough in memory (read: consecutive) > Which doesn't really happen outside of a controlled benchmark. There is no supporting information for this statement at all. Of course a list created all at once using a bump-pointer allocator is going to be consecutive. And a (moving) garbage collector is going to dynamically reorganize the nodes of a list, generally in a breadth-first way, depending on the marking algorithm. That can result in the nodes of the list being laid out consecutively after compacting, no matter where they were originally organized. Memory behavior of programs is complicated. I find it surprising that we're having a conversation that we can't or shouldn't use linked lists now because vectors are universally better, or we can lazy sort or some other crazy workaround. I'm not sure what motivates this whole line of argumentation. Sometimes lists are just the best damn thing.

atq2119 5y ago
> 500 loads and dependent stores, at minimum, in the best case hitting L1 cache, which is 3 cycles. So you are talking about 1500 cycles This is absolutely not how modern CPUs work, and I think you misunderstood where the dependencies are. All the load/store pairs are independent from each other, which means they can be executed in parallel. Which means that this code is throughput limited. Modern CPUs tend to have at least 2 load/store ports, so we're talking a throughout of one copy per cycle, or 500 cycles for the entire operation (plus warm-up time). Furthermore, this is a pure memmove in many cases, which means a real memmove implementation that has been optimised using vector instructions can be used. Now you're talking about moving 32 bytes per cycle, or 4 array entries if they're pointer-sized, which brings us down to 125 cycles plus warm-up. Which is on the order of a miss to memory...
- titzer 5y ago
  Great, now we're talking! I realized in the background that yes, there aren't dependencies between the copies...if the regions of memory don't overlap. But they do overlap, especially if you are just moving them over one element, so the simple analysis doesn't hold. But you're right that's it's just a memmove, so there is an optimized vector implementation (which, incidentally, is probably going to have relatively large setup costs for 500 elements). And oops, now your vectors are 1 million entries. I appreciate the discussion. It's a bit of a rathole for something that you shouldn't be optimizing if you can completely avoid it by using the right data structure for your needs.
  - kllrnohj 5y ago
    > And oops, now your vectors are 1 million entries. As soon as you traverse that linked list of 1 million entries, oops. In fact, here, I put together a quick benchmark. It inserts in the middle of the list and then traverses it (since, after all, ordering is irrelevant if there's no traversal). https://paste.ofcode.org/7Buz2Mua9xna55TC3uFaQp https://paste.ofcode.org/7Buz2Mua9xna55TC3uFaQp Test system is a Ryzen 3700x. I tried to avoid all amounts of compiler optimizations and believe I succeeded, but by all means happy to take a review of the above. Would love to see you do a similar test in whatever runtime you want, especially one with that juicy super-amazing compacting GC that makes linked-lists so fast. At 100 elements vector wins (40ns vs 160ns). At 1000 elements vector wins (~300ns vs. ~1000ns). At 10,000 elements vector wins (~2700ns vs. 12,000ns). At 100,000 elements guess what? Vector still wins (29us vs. 130us). You are either vastly underestimating how slow linked-list traversal is or vastly overestimating how expensive memmove is. But you did say 1 million entries so let's give that a shot: Vector size 1000000 took 286,123ns (Vector at 1 million is only twice as slow as a linked list at 100,000, linked lists aren't off to a strong start here...) Linked-list size 1000000 took 2,670,542ns Oh my god it's a bloodbath. Vector wins by 10x. Still. At 1 million entries the O(N) insert structure is still faster than the O(1) insert one. And the gap is getting bigger! And this is the basically best case for linked lists of inserting in the middle happens equally as often as traversal, I'll point out. If traversal is rare obviously a lazy sort would crush these vector results, and if traversal is common the linked lists results get that much worse. Now really these results shouldn't actually be that surprising if you really dig into it. After all, the vector version of this is storing (and therefore traversing) 4MB of data. That's all 1 million ints really is, it's not very big. Now sure you can store bigger things, but much bigger and you're probably storing a vector of pointers instead which only bumps that to 8MB of data. The linked list version, on the other hand, is storing 2 pointers + an int for each node. That's 20MB of data total. So resizing the vector involves a read of 2MB of data, a write of 2MB of data, and a traversal of 4MB of data - 8MB total. Simply traversing the linked list is hitting 20MB of data - over double the amount of memory bandwidth utilized. That's a big difference. In fact on my system at 1 million entries that happened to be the difference between the vector version comfortably fitting in L3 with loads of room to spare (especially since the resize made part of it nice & hot) vs. the linked-list version not coming close to fitting (specs on this CPU claim 32MB of L3, but it's really 16MBx2 - hitting the far L3 isn't much slower than hitting main memory). So more data to hit and it's pointer chasing? Modern CPUs just really hate that. Like a lot. Since I don't intend to cheat at happening to have sufficient L3 for the use case you laid out (combined with the benchmark naturally keeping this hot), I also tried adjusting it. I changed the containers to hold intptr's instead, and hit it with 10 million entries. Neither one comes close to fitting in L3 now. Still 80MB of data for the vector vs. 240MB for the linked list but maybe not having that copy and with both of them thrashing L3 the linked list might finally show something to redeem it. Vector size 10,000,000 took 3,680,111ns Linked-list size 10,000,000 took 26,460,333ns That's a big fucking oof right there. > I appreciate the discussion. It's a bit of a rathole for something that you shouldn't be optimizing if you can completely avoid it by using the right data structure for your needs. And a linked list is rarely the right data structure, so yes you should avoid trying to optimize for that without measuring.