Re:New Grad vs. Senior Dev
by jodrellblank on Saturday March 28, 2020 @03:38PM
(#22713756)
At a guess, some understanding of this article[1] - if a CPU instruction scaled up to human time takes 1 second then a Level 1 cache lookup takes 2 seconds and a main memory lookup takes 4 minutes.
Imagine for the array it's 1 CPU instruction to load a value, 1 to load the next value, 1 to add them, and one to store the result, that would be 4 instructions per sum; ideally the array would stream into the CPU after a single main memory lookup delay up-front, and then be 4 instructions per pair, summed as fast as the CPU can loop.
The linked list at worst needs an imaginary 1 CPU instruction to load a value, 1 to load the pointer value, 1 to reference the pointer, a delay of 2 seconds to get that value from L1 cache - missed, it's not in cache - 240 seconds stalled waiting for main memory, 1 to add, 1 to store the result. Worst case, >240x slower.
The linked list is not guaranteed to be in contiguous memory, but it might be, so the cache might have the right data in it. The linked list is 50% data, 50% metadata, so the cache is half wasted / can hold half as much data, and if the linked list is coming in from a big memory read quickly, half the bandwidth is carrying pointer addresses not data, so the throughput is halved for that, too, and the processor cycles were already able to happen much faster than the main memory bus max speed. If it's not contiguous memory, you don't know in advance where it is to request all the right memory areas at once - not until you read sequentially to the last item pointer and find there are no more.
Maybe if they are both small, both in contiguous memory and go into Level 1 cache after a single main memory delay, it could be only ~2x time, but the more data there is overall, the more chance the linked list will bust the cache or be discontinuous in memory. And on the plain array side, it might be possible to speed up with SIMD/SSE instructions to spend fewer cycles adding and storing per element, which the linked list approach might not be amenable to at all[2], then best case might be ~4x slower, worst case ~500x slower.
Imagine for the array it's 1 CPU instruction to load a value, 1 to load the next value, 1 to add them, and one to store the result, that would be 4 instructions per sum; ideally the array would stream into the CPU after a single main memory lookup delay up-front, and then be 4 instructions per pair, summed as fast as the CPU can loop.
The linked list at worst needs an imaginary 1 CPU instruction to load a value, 1 to load the pointer value, 1 to reference the pointer, a delay of 2 seconds to get that value from L1 cache - missed, it's not in cache - 240 seconds stalled waiting for main memory, 1 to add, 1 to store the result. Worst case, >240x slower.
The linked list is not guaranteed to be in contiguous memory, but it might be, so the cache might have the right data in it. The linked list is 50% data, 50% metadata, so the cache is half wasted / can hold half as much data, and if the linked list is coming in from a big memory read quickly, half the bandwidth is carrying pointer addresses not data, so the throughput is halved for that, too, and the processor cycles were already able to happen much faster than the main memory bus max speed. If it's not contiguous memory, you don't know in advance where it is to request all the right memory areas at once - not until you read sequentially to the last item pointer and find there are no more.
Maybe if they are both small, both in contiguous memory and go into Level 1 cache after a single main memory delay, it could be only ~2x time, but the more data there is overall, the more chance the linked list will bust the cache or be discontinuous in memory. And on the plain array side, it might be possible to speed up with SIMD/SSE instructions to spend fewer cycles adding and storing per element, which the linked list approach might not be amenable to at all[2], then best case might be ~4x slower, worst case ~500x slower.
[1] https://www.prowesscorp.com/computer-latency-at-a-human-scal...
[2] https://stackoverflow.com/questions/10930595/sse-instruction...