4 ms·

Remember that this code was written a long time ago. It is seriously only recently that I have seen widespread discussion about how poorly linked lists perform

Remember that this code was written a long time ago. It is seriously only recently that I have seen widespread discussion about how poorly linked lists perform in practice despite how theoretically nice they are. Back in the olden days at least a few things were different compared to today: 1) your only point of reference and authority was academic writing that stressed theory over practice. Blogs weren't around yet. So, you didn't have any random blogs with hard measurements showing that in practice brute force often wins over elegance. 2) Back then, the memory/ALU gap wasn't quite as drastic as it is today. 3) Available memory was drastically smaller than it is today. Therefore, if you had a list with a length that was highly variable, the obvious go-to container was a linked list. The idea of using an dynamic array of objects or pointers seemed highly wasteful from a memory fragmentation and copying point of view. Today processors spend most of their time stalling on memory and only dreaming of the opportunity to copy a large, linear chunk of data. It's only now that the performance penalty for random access has exceeded 50:1 for over 10 years that general programming public has started to take the problem seriously.

Retric 12y ago
Until recently main memory was close to CPU speeds and RAM cache was pointless. The issue is the speed of light means the distance between RAM chips and the CPU limits you to MHz* speeds which is not an issue for a 286, but CPU's kept getting faster even if the Speed of light is fixed. *At 1GHz light can do a six inch round trip, electricity is significantly slower than that. SDRAM is fairly high latency but cheaper and as the best case is not all that fast it's considered a good tradeoff. Adding cache increases latency even further, but tends to make CPU's faster on average.
- hengheng 12y ago
  > electricity is significantly slower As a rule of thumb, most signals travel at half the vacuum speed (√ε_r for FR4 is 2.15), with a slight variation due to the copper trace shape. So, 150 mm/ns or 6 inch/ns one-way. I love how we can say nowadays "That's not all that much, is it."
  - Rapzid 12y ago
    Man, what ever happened to those fibre interconnects and micro transmitters Intel was working on? http://www.bit-tech.net/news/bits/2010/07/28/intel-claims-optical-computing-milestone/1 http://www.bit-tech.net/news/bits/2010/07/28/intel-claims-op...
- jjoonathan 12y ago
  I don't think speed of light is a limiting factor yet (if it will ever be) for DRAM: even as memory bus speeds have been increasing, tCAS/tRCD/tRP/tRAS/etc, the number of clock cycles it takes a RAM card to actually perform the commands sent to it, have been increasing too. For a DDR RAM "speed" of, say, 1866 MHz you have an actual clock of 933MHz and typical timings of roughly tCAS=tRCD=tRAS=9 to tCAS=tRCD=tRAS=11 (measured in cycles of the actual clock). If you're lucky and the correct memory row is already open, then you'll wait 10ns for a memory request to complete, but you will regularly wind up waiting 20 or 30ns if you need to open or precharge+open a row -- and that's assuming that there are no refresh cycles blocking the request. This adds up to a lot of inches when you multiply by 6in/ns, not to mention a lot of CPU die area to optimally order memory requests & refreshes (you can have one in-flight per bank). You're right that light should be the limiting factor, though. It has long seemed to me that we need to undergo a DRAM->SRAM shift analogous to the HDD->SDD shift. Drop the capacities a bit (factor of ~6 from 6 transistors/cell vs 1 transistor/cell?) in exchange for speed. I'm sure there's a reason why it's not happening (energy efficiency?), but I'm an industry outsider and have no idea what it is. If anyone reading this does, I'd love to hear.
  - Retric 12y ago
    At 933 MHz light can make a round trip of Google: "1 / (966* 1 million) / 2 * speed of light * 1 second in inches" = 6.109 inches. The physical path from a CPU to the furthest part of ram on a desktop PC is about 2-3 times that so by the laws of physics your going to need to wait more than 2 cycle before you even consider that electricity is ~1/2 the speed of light. So, ~1/2 of your total latency (~5 or 6 of 10 cycles) is just waiting electricity to travel down wires. Anyway, my point is when physics puts hard limits in place cost / benefit trade-offs tend to be centered around that limit. http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law Note: This is purely a discussion about latency which is what matters for Linked List access. You can send a lot of data as part of a single request cycle, but that adds to your effective latency.
    - jjoonathan 12y ago
      > The physical path from a CPU to the furthest part of ram on a desktop PC is [1-1.5ft] That doesn't seem right. http://www.bhphotovideo.com/bnh/controller/home?O=&sku=1088740&is=REG&Q=&A=details http://www.bhphotovideo.com/bnh/controller/home?O=&sku=10887... Looks like it might be 1ns away at .5c, which is 10% of the minimum latency and 3% of maximum (excluding refresh) latency -- and those are latencies I took off a top-of-the-line gaming RAM (my own computer is 11-11-11). It also looks like the RAM could trivially be moved closer if there were an advantage to doing so (e.g. square, stacked layout). My point is not that the limits aren't physical, it's that the limiting physical factors are currently in silicon designs, not FR4 layouts.

Retric 12y ago

Until recently main memory was close to CPU speeds and RAM cache was pointless. The issue is the speed of light means the distance between RAM chips and the CPU limits you to MHz* speeds which is not an issue for a 286, but CPU's kept getting faster even if the Speed of light is fixed. *At 1GHz light can do a six inch round trip, electricity is significantly slower than that. SDRAM is fairly high latency but cheaper and as the best case is not all that fast it's considered a good tradeoff. Adding cache increases latency even further, but tends to make CPU's faster on average.

hengheng 12y ago
> electricity is significantly slower As a rule of thumb, most signals travel at half the vacuum speed (√ε_r for FR4 is 2.15), with a slight variation due to the copper trace shape. So, 150 mm/ns or 6 inch/ns one-way. I love how we can say nowadays "That's not all that much, is it."
- Rapzid 12y ago
  Man, what ever happened to those fibre interconnects and micro transmitters Intel was working on? http://www.bit-tech.net/news/bits/2010/07/28/intel-claims-optical-computing-milestone/1 http://www.bit-tech.net/news/bits/2010/07/28/intel-claims-op...
jjoonathan 12y ago
I don't think speed of light is a limiting factor yet (if it will ever be) for DRAM: even as memory bus speeds have been increasing, tCAS/tRCD/tRP/tRAS/etc, the number of clock cycles it takes a RAM card to actually perform the commands sent to it, have been increasing too. For a DDR RAM "speed" of, say, 1866 MHz you have an actual clock of 933MHz and typical timings of roughly tCAS=tRCD=tRAS=9 to tCAS=tRCD=tRAS=11 (measured in cycles of the actual clock). If you're lucky and the correct memory row is already open, then you'll wait 10ns for a memory request to complete, but you will regularly wind up waiting 20 or 30ns if you need to open or precharge+open a row -- and that's assuming that there are no refresh cycles blocking the request. This adds up to a lot of inches when you multiply by 6in/ns, not to mention a lot of CPU die area to optimally order memory requests & refreshes (you can have one in-flight per bank). You're right that light should be the limiting factor, though. It has long seemed to me that we need to undergo a DRAM->SRAM shift analogous to the HDD->SDD shift. Drop the capacities a bit (factor of ~6 from 6 transistors/cell vs 1 transistor/cell?) in exchange for speed. I'm sure there's a reason why it's not happening (energy efficiency?), but I'm an industry outsider and have no idea what it is. If anyone reading this does, I'd love to hear.
- Retric 12y ago
  At 933 MHz light can make a round trip of Google: "1 / (966* 1 million) / 2 * speed of light * 1 second in inches" = 6.109 inches. The physical path from a CPU to the furthest part of ram on a desktop PC is about 2-3 times that so by the laws of physics your going to need to wait more than 2 cycle before you even consider that electricity is ~1/2 the speed of light. So, ~1/2 of your total latency (~5 or 6 of 10 cycles) is just waiting electricity to travel down wires. Anyway, my point is when physics puts hard limits in place cost / benefit trade-offs tend to be centered around that limit. http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law Note: This is purely a discussion about latency which is what matters for Linked List access. You can send a lot of data as part of a single request cycle, but that adds to your effective latency.
  - jjoonathan 12y ago
    > The physical path from a CPU to the furthest part of ram on a desktop PC is [1-1.5ft] That doesn't seem right. http://www.bhphotovideo.com/bnh/controller/home?O=&sku=1088740&is=REG&Q=&A=details http://www.bhphotovideo.com/bnh/controller/home?O=&sku=10887... Looks like it might be 1ns away at .5c, which is 10% of the minimum latency and 3% of maximum (excluding refresh) latency -- and those are latencies I took off a top-of-the-line gaming RAM (my own computer is 11-11-11). It also looks like the RAM could trivially be moved closer if there were an advantage to doing so (e.g. square, stacked layout). My point is not that the limits aren't physical, it's that the limiting physical factors are currently in silicon designs, not FR4 layouts.