10 ms·

It's strange the extent to which programming interview questions reflect an 80s view of the cost of operations, particularly the overabundance of linked list an

It's strange the extent to which programming interview questions reflect an 80s view of the cost of operations, particularly the overabundance of linked list and binary tree questions. Cache misses ain't free and memory scans are relatively cheap after you do the initial lookup.

deleted 11y ago
[deleted]
chipsy 11y ago
I think most such interview questions are informed by CS curricula, which also have only changed modestly since 1980(some new languages and tools). The elaborate pointer chasing structures available then have basically sufficed and are in many instances less useful new.
trsohmers 11y ago
Yep! The big thing people don't realize that it is memory operations that are the biggest cost in terms of both time and energy. While it takes ~100 picojoules to do a double precision floating point operation on a Ivy Bridge Intel processor, it takes 4200 picojoules to move the 64 bits from DRAM to your registers. Most people assume that the huge power usage is because you need to move data from off the chip, but the reality (and surprising fact to most people) is that over 60% (~2500 picojoules) of the energy usage of moving the data is consumed by the on chip cache hierarchy. That doesn't mean the SRAM caches themselves, but all the additional logic that makes it hardware managed (TLBs, etc) that give you functionality like virtual memory translations, cache coherency, etc. Getting rid of all of that cruft that has been added since the 80s to make programmers lives easier would actually reduce power consumption and latency significantly... My startup is working on that problem by removing all of that additional logic from the hardware and instead having it managed at compile time. The best thing though would be having programmers really think about locality when writing their programs though.
- shadowfox 11y ago
  > My startup is working on that problem by removing all of that additional logic from the hardware and instead having it managed at compile time. Maybe a naive question. How do you foresee your approach with this succeeding given the failure of Itanium's similar approach?
  - trsohmers 11y ago
    There are two (major) things that we are addressing with the compiler. The first is the traditional VLIW problem, which is the same problem Itanium faced, and the second is doing fully software managed memory, which no (non academic) architectures have attempted to solve with a compiler. 1) As for the traditional VLIW problem, the simplified explanation of why it is difficult for most systems is because it is difficult to know exactly when a functional unit will actually receive/have access to a piece of data (either due to data hazards, latency due to the memory system, or many other factors). We solve this at the hardware level by being the first architecture to be able to guarantee latency between any location in memory. Once you can guarantee this in hardware, your compiler has a lot more information to be able to make decisions with and does not need to needlessly insert nops that hurt performance. 2)When it comes to software memory management, we have some new proprietary techniques for determining memory usage at compile time plus runtime tools. For obvious reasons I can't go into too much detail on how they work, but we will be publishing on it in the near future. To summarize, we think that the reason others have never made a "sufficiently smart compiler" is because the hardware never gave enough data to the compiler and vice versa. We decided to have virtual memory (which we think is unnecessary) and instead opted for having all of our cores have access to a shared memory space, which simplifies both the hardware and makes memory mapping easier for the compiler. Hardware features that guarantee the latency for both operating and moving data along with the entire system being non blocking is what really gives our compiler the information necessary to efficiently pipeline things.
    - pjc50 11y ago
      fully software managed memory This is going to be interesting from a security point of view. It also sounds like users will need a new OS to take advantage of this?
TillE 11y ago
Nobody ever used a linked list for performance. And it's not reasonable to abandon trees and graphs and everything just for the sake of cache locality. Algorithm first, CPU optimization second. Especially because you can control allocation very easily with something like an object pool, which will minimize cache misses.
- adrianN 11y ago
  You basically shouldn't use vanilla _binary_ trees ever. b-trees with appropriate node sizes provide much better cache locality without sacrificing any of the nice properties trees have. They are easier to implement too. You don't have to go full van Emde Boas layout trickery to get most of the benefits.
sklogic 11y ago
Would you really prefer to be asked to write a cache-friendly hash map on a whiteboard?
- fiatmoney 11y ago
  It's not really that hard. Open addressing + linear probing + magic value for deletions is something you can implement in 15 minutes if you know how hashmaps work. Of course "cache friendly" is relative; any hashmap has pseudorandom memory accesses as a core part of its design so again, array scans will beat it below a certain number of elements.

deleted 11y ago

[deleted]

chipsy 11y ago

I think most such interview questions are informed by CS curricula, which also have only changed modestly since 1980(some new languages and tools). The elaborate pointer chasing structures available then have basically sufficed and are in many instances less useful new.

trsohmers 11y ago

Yep! The big thing people don't realize that it is memory operations that are the biggest cost in terms of both time and energy. While it takes ~100 picojoules to do a double precision floating point operation on a Ivy Bridge Intel processor, it takes 4200 picojoules to move the 64 bits from DRAM to your registers. Most people assume that the huge power usage is because you need to move data from off the chip, but the reality (and surprising fact to most people) is that over 60% (~2500 picojoules) of the energy usage of moving the data is consumed by the on chip cache hierarchy. That doesn't mean the SRAM caches themselves, but all the additional logic that makes it hardware managed (TLBs, etc) that give you functionality like virtual memory translations, cache coherency, etc. Getting rid of all of that cruft that has been added since the 80s to make programmers lives easier would actually reduce power consumption and latency significantly... My startup is working on that problem by removing all of that additional logic from the hardware and instead having it managed at compile time. The best thing though would be having programmers really think about locality when writing their programs though.

shadowfox 11y ago
> My startup is working on that problem by removing all of that additional logic from the hardware and instead having it managed at compile time. Maybe a naive question. How do you foresee your approach with this succeeding given the failure of Itanium's similar approach?
- trsohmers 11y ago
  There are two (major) things that we are addressing with the compiler. The first is the traditional VLIW problem, which is the same problem Itanium faced, and the second is doing fully software managed memory, which no (non academic) architectures have attempted to solve with a compiler. 1) As for the traditional VLIW problem, the simplified explanation of why it is difficult for most systems is because it is difficult to know exactly when a functional unit will actually receive/have access to a piece of data (either due to data hazards, latency due to the memory system, or many other factors). We solve this at the hardware level by being the first architecture to be able to guarantee latency between any location in memory. Once you can guarantee this in hardware, your compiler has a lot more information to be able to make decisions with and does not need to needlessly insert nops that hurt performance. 2)When it comes to software memory management, we have some new proprietary techniques for determining memory usage at compile time plus runtime tools. For obvious reasons I can't go into too much detail on how they work, but we will be publishing on it in the near future. To summarize, we think that the reason others have never made a "sufficiently smart compiler" is because the hardware never gave enough data to the compiler and vice versa. We decided to have virtual memory (which we think is unnecessary) and instead opted for having all of our cores have access to a shared memory space, which simplifies both the hardware and makes memory mapping easier for the compiler. Hardware features that guarantee the latency for both operating and moving data along with the entire system being non blocking is what really gives our compiler the information necessary to efficiently pipeline things.
  - pjc50 11y ago
    fully software managed memory This is going to be interesting from a security point of view. It also sounds like users will need a new OS to take advantage of this?

TillE 11y ago

Nobody ever used a linked list for performance. And it's not reasonable to abandon trees and graphs and everything just for the sake of cache locality. Algorithm first, CPU optimization second. Especially because you can control allocation very easily with something like an object pool, which will minimize cache misses.

adrianN 11y ago
You basically shouldn't use vanilla _binary_ trees ever. b-trees with appropriate node sizes provide much better cache locality without sacrificing any of the nice properties trees have. They are easier to implement too. You don't have to go full van Emde Boas layout trickery to get most of the benefits.

sklogic 11y ago

Would you really prefer to be asked to write a cache-friendly hash map on a whiteboard?

fiatmoney 11y ago
It's not really that hard. Open addressing + linear probing + magic value for deletions is something you can implement in 15 minutes if you know how hashmaps work. Of course "cache friendly" is relative; any hashmap has pseudorandom memory accesses as a core part of its design so again, array scans will beat it below a certain number of elements.