4 ms·

Even more important than learning how to vectorize is learning the basics of computer architecture: register, caches, pipelining, branch prediction, and supersc

Even more important than learning how to vectorize is learning the basics of computer architecture: register, caches, pipelining, branch prediction, and superscalar execution. One of the common interview questions I ask is computing the sum of an array of doubles. Barely 1% of applicants can even get the basics correctly such as having multiple partial sums. Once you do the work such that your code actually allows execution to happen in parallel, then leveraging superscalar and simd happens automatically.

listenallyall 3y ago
Is asking a question that fewer than 1% of applicants "can even get the basics correct" -- which implies that only a tiny fraction of 1% actually provide a fully complete and correct answer -- a good use of either the applicants' or the interviewer's time? Is it effective in distinguishing candidates, or are you only seeking 1 success (fewer, actually) per 100?
- mgaunard 3y ago
  1% success rate is typical when interviewing developers. Also they get asked multiple exercises, not doing great at one is not eliminatory. Being able to quickly identify whether an individual is exceptionally good is very important to ensure the employer can fast-track them and be responsive quickly enough that he doesn't accept another offer.
  - preseinger 3y ago
    cpu cache line optimization is relevant to a superminority of programming contexts if you're working in those contexts then it's all fine, but it's important to acknowledge that most software development is bottlenecked by concerns far above this level of concern
    - mgaunard 3y ago
      [flagged]
dragontamer 3y ago
> One of the common interview questions I ask is computing the sum of an array of doubles. Barely 1% of applicants can even get the basics correctly such as having multiple partial sums. Ehhh... I've got multiple hats from my college classes. Yes, optimizations say that multiple partial sums is fastest. But... my floating-point analysis classes has my brain yelling "cancellation error". The only way to minimize cancellation error is to sort the numbers from biggest to smallest, and then separate them from positives-and-negatives. You add the numbers from smallest to largest in magnitude, only matching signs, and then finally combine them at the end. The only two partial sums you should be keeping are "positive numbers" and "negative numbers", and everything else needs to be folded together to minimize rounding and cancellation errors. -------- You know. For stability and minimization of errors. There's other, faster, methods to possibly be employed. But optimization of partial sums is probably the last thing I'm thinking if I see "float" or "double". If things are "int" or "long", I'll have a higher chance of actually thinking (and caring) about optimization, because stability/cancellation error isn't a thing with int or long.
- mgaunard 3y ago
  The reason you need multiple sums is because there is a loop dependency which causes every iteration to stall and prevents pipelining and saturating the multiple compute units of your superscalar processor. Yes, floating-point isn't associative, so the results aren't numerically equivalent, and that is why you need to do that optimization yourself since the compiler isn't allowed to do it for you. As per the exercise, there is no information about the distribution of the data, so there is no indication that any order would be any better than another for numerical stability. If you care about stability you'd implement a kahan sum, which isn't really affected by changing the order of the sum so that you can parallelize it.
  - dragontamer 3y ago
    Kahan summing doesn't fix cancellation error. It just extends the precision by another 53-bits or so. The only way you fix cancellation error is summing the positives in one variable, and the negatives in another, and do a big cancellation at the end. Anyway, my overall point is not to criticize Kahan summing or other techniques. My point is that these techniques are incompatible with optimizations. The faster way is often times a less stable operation.

listenallyall 3y ago

Is asking a question that fewer than 1% of applicants "can even get the basics correct" -- which implies that only a tiny fraction of 1% actually provide a fully complete and correct answer -- a good use of either the applicants' or the interviewer's time? Is it effective in distinguishing candidates, or are you only seeking 1 success (fewer, actually) per 100?

mgaunard 3y ago
1% success rate is typical when interviewing developers. Also they get asked multiple exercises, not doing great at one is not eliminatory. Being able to quickly identify whether an individual is exceptionally good is very important to ensure the employer can fast-track them and be responsive quickly enough that he doesn't accept another offer.
- preseinger 3y ago
  cpu cache line optimization is relevant to a superminority of programming contexts if you're working in those contexts then it's all fine, but it's important to acknowledge that most software development is bottlenecked by concerns far above this level of concern
  - mgaunard 3y ago
    [flagged]

dragontamer 3y ago

> One of the common interview questions I ask is computing the sum of an array of doubles. Barely 1% of applicants can even get the basics correctly such as having multiple partial sums. Ehhh... I've got multiple hats from my college classes. Yes, optimizations say that multiple partial sums is fastest. But... my floating-point analysis classes has my brain yelling "cancellation error". The only way to minimize cancellation error is to sort the numbers from biggest to smallest, and then separate them from positives-and-negatives. You add the numbers from smallest to largest in magnitude, only matching signs, and then finally combine them at the end. The only two partial sums you should be keeping are "positive numbers" and "negative numbers", and everything else needs to be folded together to minimize rounding and cancellation errors. -------- You know. For stability and minimization of errors. There's other, faster, methods to possibly be employed. But optimization of partial sums is probably the last thing I'm thinking if I see "float" or "double". If things are "int" or "long", I'll have a higher chance of actually thinking (and caring) about optimization, because stability/cancellation error isn't a thing with int or long.

mgaunard 3y ago
The reason you need multiple sums is because there is a loop dependency which causes every iteration to stall and prevents pipelining and saturating the multiple compute units of your superscalar processor. Yes, floating-point isn't associative, so the results aren't numerically equivalent, and that is why you need to do that optimization yourself since the compiler isn't allowed to do it for you. As per the exercise, there is no information about the distribution of the data, so there is no indication that any order would be any better than another for numerical stability. If you care about stability you'd implement a kahan sum, which isn't really affected by changing the order of the sum so that you can parallelize it.
- dragontamer 3y ago
  Kahan summing doesn't fix cancellation error. It just extends the precision by another 53-bits or so. The only way you fix cancellation error is summing the positives in one variable, and the negatives in another, and do a big cancellation at the end. Anyway, my overall point is not to criticize Kahan summing or other techniques. My point is that these techniques are incompatible with optimizations. The faster way is often times a less stable operation.