4 ms·

> Your "go to" data structures should be hash tables about 70% of the time and vectors about 30% of the time. I literally just wrote a comment elsewhere about

> Your "go to" data structures should be hash tables about 70% of the time and vectors about 30% of the time. I literally just wrote a comment elsewhere about how hash tables are obscenely overused and cause measurable performance degradation in many situations.

bsder 7y ago
That may be. However, the number of times I see people hit a bug because they fenceposted or flat out overflowed a fixed size array VASTLY outnumbers the times I have seen people have to redo their underlying data structure because it just wasn't fast enough.
- banachtarski 7y ago
  We're just in different fields. The OP of the post was a graphics engineer, as am I. We drink to celebrate when we shave off a millisecond haha.
  - Impossible 7y ago
    I've shaved 10 microseconds in large refactors and been told that's great ship it. Other fields might say that wasn't nearly enough to justify the code churn (performance vs. "programmer productivity" argument). A millisecond is a lifetime and can mean the difference between shipping and not shipping in some products.
    - banachtarski 7y ago
      Odd that we feel differently about hash tables then.
      - Impossible 7y ago
        I didn't mention how I feel about hash tables (I'm not OP), but I think we feel the same? I definitely agree that arrays (potentially vector style growable arrays) should be a programmer's go to data structure, both for simplicity and performance. For my use cases I'd probably swap array and hash table usage with OP (70% array and 30% hash) but really it's probably more like 90, 10. Computing hash functions and resolving collisions can be very fast with the right hash table implementation, but it's absolutely not free. There is a reason why Lua tables can implement array like access and memory usage, even if from a language standpoint a Lua table looks like a hash table with some fancy features.
        banachtarski 7y ago
        Ah didn't realize you weren't OP. I think any programmer that operates in the realms of microseconds probably would understand the overhead of both the hash function overhead as well as the coherency issue. I'm not a lua programmer but I remember studying the LuaJIT source pretty extensively.

bsder 7y ago

That may be. However, the number of times I see people hit a bug because they fenceposted or flat out overflowed a fixed size array VASTLY outnumbers the times I have seen people have to redo their underlying data structure because it just wasn't fast enough.

banachtarski 7y ago
We're just in different fields. The OP of the post was a graphics engineer, as am I. We drink to celebrate when we shave off a millisecond haha.
- Impossible 7y ago
  I've shaved 10 microseconds in large refactors and been told that's great ship it. Other fields might say that wasn't nearly enough to justify the code churn (performance vs. "programmer productivity" argument). A millisecond is a lifetime and can mean the difference between shipping and not shipping in some products.
  - banachtarski 7y ago
    Odd that we feel differently about hash tables then.
    - Impossible 7y ago
      I didn't mention how I feel about hash tables (I'm not OP), but I think we feel the same? I definitely agree that arrays (potentially vector style growable arrays) should be a programmer's go to data structure, both for simplicity and performance. For my use cases I'd probably swap array and hash table usage with OP (70% array and 30% hash) but really it's probably more like 90, 10. Computing hash functions and resolving collisions can be very fast with the right hash table implementation, but it's absolutely not free. There is a reason why Lua tables can implement array like access and memory usage, even if from a language standpoint a Lua table looks like a hash table with some fancy features.
      - banachtarski 7y ago
        Ah didn't realize you weren't OP. I think any programmer that operates in the realms of microseconds probably would understand the overhead of both the hash function overhead as well as the coherency issue. I'm not a lua programmer but I remember studying the LuaJIT source pretty extensively.