6 ms·

Just a thought -- gaming is latency sensitive. Maybe their issue with it wasn't about average performance, but that the once-in-a-while perf hit would be enough

by chaps 5y ago

Just a thought -- gaming is latency sensitive. Maybe their issue with it wasn't about average performance, but that the once-in-a-while perf hit would be enough to cause a bad experience for the person playing the game? I know I'd be frustrated if there was a predictable lag spike while playing a game.

typon 5y ago
Any game engine design worth its salt would: 1. Probably not used linked lists (contiguous layout means better cache efficiency) 2. Would try to understand their data requirements and allocate memory up front as much as possible - doing a similar amortized analysis the OP is suggesting rather than a generic "always have O(1) insertion" at the cost of using an inferior data structure (a linked list)
- BrS96bVxXBLzf5B 5y ago
  Any game engine architect worth her salt would know to not speak so absolutely about cache coherency, and that if you're dealing with a use-case where iteration is massively infrequent but random insertions and removals are likely, you could be better off with the linked list :)
  - typon 5y ago
    Certainly if you design a scenario where linked lists are superior to use, you should use linked lists. Fortunately, these are few and far between in real production software.
munificent 5y ago
No, latency didn't come up. (I agree that could be a reason not to use a dynamic array.) They were hung up on the idea that a dynamic array must be O(n) because at least some of the appends copy.
- 8note 5y ago
  Assuming you can average over all requests imposes that latency does not matter, doesn't it? If you're the interviewee, it's up to you to get that clarification
  - munificent 5y ago
    The question they asked was about its complexity in big-O terms, not so much about its real world performance, at least as I recall.
- deleted 5y ago
  [deleted]
- qu4z-2 5y ago
  You explicitly said they were hung up on the "worst case O(n)" situation, so I suspect they were concerned about the latency. Insertion into a dynamic array has a worst case of O(n) and an average case of O(1), no?

by chaps 5y ago

typon 5y ago

Any game engine design worth its salt would: 1. Probably not used linked lists (contiguous layout means better cache efficiency) 2. Would try to understand their data requirements and allocate memory up front as much as possible - doing a similar amortized analysis the OP is suggesting rather than a generic "always have O(1) insertion" at the cost of using an inferior data structure (a linked list)

BrS96bVxXBLzf5B 5y ago
Any game engine architect worth her salt would know to not speak so absolutely about cache coherency, and that if you're dealing with a use-case where iteration is massively infrequent but random insertions and removals are likely, you could be better off with the linked list :)
- typon 5y ago
  Certainly if you design a scenario where linked lists are superior to use, you should use linked lists. Fortunately, these are few and far between in real production software.

munificent 5y ago

No, latency didn't come up. (I agree that could be a reason not to use a dynamic array.) They were hung up on the idea that a dynamic array must be O(n) because at least some of the appends copy.

8note 5y ago
Assuming you can average over all requests imposes that latency does not matter, doesn't it? If you're the interviewee, it's up to you to get that clarification
- munificent 5y ago
  The question they asked was about its complexity in big-O terms, not so much about its real world performance, at least as I recall.
deleted 5y ago
[deleted]
qu4z-2 5y ago
You explicitly said they were hung up on the "worst case O(n)" situation, so I suspect they were concerned about the latency. Insertion into a dynamic array has a worst case of O(n) and an average case of O(1), no?