8 ms·

I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not oka

by dcow 5y ago

I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on a show than a practical solution to the task at hand. The worst case performance for a dynamic array is O(n), but the amortized performance is constant. They aren't the same thing. You may be a different, more mature, engineer nowadays. But, when I encounter the type of persona your story describes I tend to respond with strong no’s irrespective of whether you have since written a textbook.

lmilcin 5y ago
Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). Linked lists have a lot of huge downsides that are not easily captured in their naive big-O characterization. Big-O does not tell anything about how efficient things are. Two algorithms can have same big-O complexity yet hugely different costs. For example, you can easily parallelize operations on array lists but you can't do that on linked list where to get to next node you need to dereference a pointer. Even without this, you get bonus from prefetching data to cache when searching through array list or when doing things like moving data. Speculative dereferencing pointers is nowhere close to just regular prefetch. Array lists are denser in memory than linked lists (because of additional pointers). This means that a lot of things works just more efficiently -- cache, memory transfers, prefetching, less need to resolve TLBs, etc. Inserting into array list at the end is as fast as into linked list (after taking account for amortized cost), but what not many people appreciate is that finding an insertion place and inserting within array list is also the same cost or even better than in linked list. That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. Actually, it costs more than copying the same size of array list.
- deleted 5y ago
  [deleted]
- dcow 5y ago
  I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything. Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you already have a reference to the insertion point you can avoid the walk, c) cache coherence is only important of you are actually iterating over the list, etc.
  - whatshisface 5y ago
    I have never ever seen a linked list in a game, anywhere, serving any purpose.
    - dcow 5y ago
      Here’s one: https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20cb4902f2dc53a0c20a96/source/enet/include/enet/list.h https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20c...
    - areyousure 5y ago
      Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/q3map/qbsp.h#L92 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
      - lmilcin 5y ago
        He is still probably technically right. "I have never seen (...)"
        dcow 5y ago
fulafel 5y ago
Games work with time budgets of many milliseconds per frame, relatively long timescales from a cpu pov. It is rare to prefer predictable per iteration latency in loops over higher throughput unless the deferred batch of work is quite big. But of course this can compound in some cases, eg you have thousands of these arrays being extended in lockstep and they all trigger the extra work at the same time...
- Dylan16807 5y ago
  If the arrays are big enough for growing them to mess up your time budget, then it's quite likely that a linked list would already be failing.
  - deleted 5y ago
    [deleted]
  - fulafel 5y ago
    Yep, and the associated dynamic memory allocation for LL nodes will still have latency spikes from the malloc implementation so its worst case latency is still bad.
tshaddox 5y ago
If the question was about constant time complexity but the questioners had a secret additional requirement that they refused to share, that's a flaw in the questioning. If the questioners had that additional secret requirement and understood amortized analysis, then they should have at least given a hint at their secret requirement by saying something like "your proposal does indeed deliver amortized constant time complexity, but what could the potential downsides be of this approach?" If the commenter is giving an accurate description of what happened in the interview, then the questioners were absolutely the ones being stubborn or ignorant. (And, incidentally, I'm pretty sure that dynamic arrays are going to come out ahead in practice even with the secret "tight loop" requirement.)
munificent 5y ago
> for being stubborn and drunk on ego. I think you would have a hard time finding someone who knows me describe me that way. Maybe the way I related the anecdote here doesn't present me well. I am pretty meek and easily flustered. I don't think I was any more confident back then than I am now which is, alas, not very. > The fact that you were unable to incorporate this into the conversation In this case, it was an interview with three other engineers simultaneously (a truly cursed interview format), so it was hard to incorporate much of anything into the conversation. It felt much like I imagine a thesis examination where the three of them were in charge of pacing and questions. (Also, it was ten years ago, so I'm sure my memory has faded. What I recall was them asking me how I'd do some sort of growable collection. I said I'd probably do a dynamic array. I mean, that is the way 99% of growable collections are done today—look at Java's ArrayList and C#'s List. This is a company that does strictly PC games and I was hiring for a tools position. Dynamic arrays are the right solution most of the time in that context. They asked what the complexity was. I said something like "Constant time, across multiple appends." They didn't seem to get that and asked what the worst case was. I was some appends are O(n) but amortized across a series of them, it's constant. When I tried to clarify, they said they wanted to move on. I think in their minds I was hopelessly lost and they wanted to get to the next question so that I didn't embarrass myself further. I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for. My impression was that they had never heard of amortized analysis at all, and thought I was confusing average case and worst case analysis (which I was not). From their perspective, I can see how I looked lost or wrong. Overall, they had a superior tone that I found off-putting. (For comparison, I didn't get that impression from any of the interviews I had at Google the very next day. My Google interviewers were all kind, engaging, and really fun to talk to.)
- dcow 5y ago
  You may be entirely correct in your analysis. There are definitely a fair share of toxic interview setups and interviewers out there. What I found off putting about the way you presented the story was the bit at the end where you gloated about your current employment status and achievements as if they missed out on some great mind. It gives the impression that in your view, your intellectual prowess was more important than being a good candidate and potential teammate. While that of course may just be the way it came off, that was my perception. So it drove me to present the alternate, less charitable, interpretation where the interviewers did in fact understand amortized complexity and simply didn't find it suitable. > I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for. This is the type of conversation I tend to enjoy during interview problem solving because IMO it most accurately reflects the type of conversation you'd actually have with teammates when building a system. I also might try to bait this topic by specifying O(1) worst case insertion up front and watch for how the candidate interprets the requirement, what type of questions are asked, etc. If you started implementing an array backed thing I might stop you early and prompt the insertion analysis specifically. However, in my experience people tend to discuss an overview of the solution before writing any code which is a great point to iron out any clear non-starters or missing requirements. > Overall, they had a superior tone that I found off-putting. Fair. It's a two way street after all. Even if they were entirely fine and it was all a comms misunderstanding, sometimes personalities just don't gel. Glad you found success the next day!
op00to 5y ago
Interviews are about shows, not boring answers.
- bunfunton 5y ago
  This is so true. It’s about putting as many good vibes and good feelings into the interview as possible while also seeming competent. “Do I want to work with this guy?”
lwansbrough 5y ago
> I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. This flippant remark followed by the egotistical follow up is the kind of art I read hacker news for, thank you.
chakkepolja 5y ago
If they were not dumb, they would've explained him why amortized complexity is not suitable measure for their application. If they were not dumb, they would definitely understand what he was saying and not sit clueless.
animal531 5y ago
I'll add the really correct but stubborn answer. It's a game, why are we allocating memory? Working in for example Unity I need to not ever allocate anything per frame if I can help it (and then knowing other gotchas such as that foreach and/or getting the .Count on a list will also cause memory to be allocated).

by dcow 5y ago

lmilcin 5y ago

Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). Linked lists have a lot of huge downsides that are not easily captured in their naive big-O characterization. Big-O does not tell anything about how efficient things are. Two algorithms can have same big-O complexity yet hugely different costs. For example, you can easily parallelize operations on array lists but you can't do that on linked list where to get to next node you need to dereference a pointer. Even without this, you get bonus from prefetching data to cache when searching through array list or when doing things like moving data. Speculative dereferencing pointers is nowhere close to just regular prefetch. Array lists are denser in memory than linked lists (because of additional pointers). This means that a lot of things works just more efficiently -- cache, memory transfers, prefetching, less need to resolve TLBs, etc. Inserting into array list at the end is as fast as into linked list (after taking account for amortized cost), but what not many people appreciate is that finding an insertion place and inserting within array list is also the same cost or even better than in linked list. That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. Actually, it costs more than copying the same size of array list.

deleted 5y ago
[deleted]
dcow 5y ago
I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything. Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you already have a reference to the insertion point you can avoid the walk, c) cache coherence is only important of you are actually iterating over the list, etc.
- whatshisface 5y ago
  I have never ever seen a linked list in a game, anywhere, serving any purpose.
  - dcow 5y ago
    Here’s one: https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20cb4902f2dc53a0c20a96/source/enet/include/enet/list.h https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20c...
  - areyousure 5y ago
    Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/q3map/qbsp.h#L92 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
    - lmilcin 5y ago
      He is still probably technically right. "I have never seen (...)"
      - dcow 5y ago

fulafel 5y ago

Games work with time budgets of many milliseconds per frame, relatively long timescales from a cpu pov. It is rare to prefer predictable per iteration latency in loops over higher throughput unless the deferred batch of work is quite big. But of course this can compound in some cases, eg you have thousands of these arrays being extended in lockstep and they all trigger the extra work at the same time...

Dylan16807 5y ago
If the arrays are big enough for growing them to mess up your time budget, then it's quite likely that a linked list would already be failing.
- deleted 5y ago
  [deleted]
- fulafel 5y ago
  Yep, and the associated dynamic memory allocation for LL nodes will still have latency spikes from the malloc implementation so its worst case latency is still bad.

tshaddox 5y ago

If the question was about constant time complexity but the questioners had a secret additional requirement that they refused to share, that's a flaw in the questioning. If the questioners had that additional secret requirement and understood amortized analysis, then they should have at least given a hint at their secret requirement by saying something like "your proposal does indeed deliver amortized constant time complexity, but what could the potential downsides be of this approach?" If the commenter is giving an accurate description of what happened in the interview, then the questioners were absolutely the ones being stubborn or ignorant. (And, incidentally, I'm pretty sure that dynamic arrays are going to come out ahead in practice even with the secret "tight loop" requirement.)

munificent 5y ago

> for being stubborn and drunk on ego. I think you would have a hard time finding someone who knows me describe me that way. Maybe the way I related the anecdote here doesn't present me well. I am pretty meek and easily flustered. I don't think I was any more confident back then than I am now which is, alas, not very. > The fact that you were unable to incorporate this into the conversation In this case, it was an interview with three other engineers simultaneously (a truly cursed interview format), so it was hard to incorporate much of anything into the conversation. It felt much like I imagine a thesis examination where the three of them were in charge of pacing and questions. (Also, it was ten years ago, so I'm sure my memory has faded. What I recall was them asking me how I'd do some sort of growable collection. I said I'd probably do a dynamic array. I mean, that is the way 99% of growable collections are done today—look at Java's ArrayList and C#'s List. This is a company that does strictly PC games and I was hiring for a tools position. Dynamic arrays are the right solution most of the time in that context. They asked what the complexity was. I said something like "Constant time, across multiple appends." They didn't seem to get that and asked what the worst case was. I was some appends are O(n) but amortized across a series of them, it's constant. When I tried to clarify, they said they wanted to move on. I think in their minds I was hopelessly lost and they wanted to get to the next question so that I didn't embarrass myself further. I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for. My impression was that they had never heard of amortized analysis at all, and thought I was confusing average case and worst case analysis (which I was not). From their perspective, I can see how I looked lost or wrong. Overall, they had a superior tone that I found off-putting. (For comparison, I didn't get that impression from any of the interviews I had at Google the very next day. My Google interviewers were all kind, engaging, and really fun to talk to.)

dcow 5y ago
You may be entirely correct in your analysis. There are definitely a fair share of toxic interview setups and interviewers out there. What I found off putting about the way you presented the story was the bit at the end where you gloated about your current employment status and achievements as if they missed out on some great mind. It gives the impression that in your view, your intellectual prowess was more important than being a good candidate and potential teammate. While that of course may just be the way it came off, that was my perception. So it drove me to present the alternate, less charitable, interpretation where the interviewers did in fact understand amortized complexity and simply didn't find it suitable. > I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for. This is the type of conversation I tend to enjoy during interview problem solving because IMO it most accurately reflects the type of conversation you'd actually have with teammates when building a system. I also might try to bait this topic by specifying O(1) worst case insertion up front and watch for how the candidate interprets the requirement, what type of questions are asked, etc. If you started implementing an array backed thing I might stop you early and prompt the insertion analysis specifically. However, in my experience people tend to discuss an overview of the solution before writing any code which is a great point to iron out any clear non-starters or missing requirements. > Overall, they had a superior tone that I found off-putting. Fair. It's a two way street after all. Even if they were entirely fine and it was all a comms misunderstanding, sometimes personalities just don't gel. Glad you found success the next day!

op00to 5y ago

Interviews are about shows, not boring answers.

bunfunton 5y ago
This is so true. It’s about putting as many good vibes and good feelings into the interview as possible while also seeming competent. “Do I want to work with this guy?”

lwansbrough 5y ago

> I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. This flippant remark followed by the egotistical follow up is the kind of art I read hacker news for, thank you.

chakkepolja 5y ago

If they were not dumb, they would've explained him why amortized complexity is not suitable measure for their application. If they were not dumb, they would definitely understand what he was saying and not sit clueless.

animal531 5y ago

I'll add the really correct but stubborn answer. It's a game, why are we allocating memory? Working in for example Unity I need to not ever allocate anything per frame if I can help it (and then knowing other gotchas such as that foreach and/or getting the .Count on a list will also cause memory to be allocated).