3 ms·

Pay a log(n) slowdown and you have arrays in all their glory (and more!) https://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-Sequence.html https:/

• poorlyknit 4y ago
  If we really need to we can just actually use arrays tho: https://hackage.haskell.org/package/primitive-0.7.4.0/docs/Data-Primitive-ByteArray.html#v:ByteArray https://hackage.haskell.org/package/primitive-0.7.4.0/docs/D... That's what I meant: You can mostly use tree-like log(n) data structures rather nicely but you'll have to isolate your mutating code into stuff like PrimMonad, see: https://hackage.haskell.org/package/primitive-0.7.4.0/docs/Data-Primitive-ByteArray.html#v:writeByteArray https://hackage.haskell.org/package/primitive-0.7.4.0/docs/D... I like Haskell because it lets me write clean interfaces at a high level but fall back to byte-level stuff when needed.
• snovv_crash 4y ago
  It isn't just log(n), it's also L1 vs L3 access times and an extra level of pointer chasing.
  • savingsPossible 4y ago
    Just to confirm, you are talking about L1 and L3 caches, right?
    • snovv_crash 4y ago
      Yes, and the specific advantages of using contiguous in-memory representations for data which is accessed sequentially.