153
What are some cool and obscure data structure you know of? (programming.dev)
submitted 9 months ago by to c/programming@programming.dev
56 comments fedilink hide all child comments
you are viewing a single comment's thread
view the rest of the comments
[–] 5 points 9 months ago (5 children)

Interesting idea, but your trick is never really going to help (you can store up to 255 bytes instead of 254). Also always using 256 bytes for every string seems wasteful.

I think LLVM's small string optimisation is always going to be a better option: https://joellaity.com/2020/01/31/string.html

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 5 child comments
    •
  • [–] 6 points 9 months ago (4 children)

    22 characters is significantly less useful than 255 characters. I use this for resource name keys, asset file paths, and a few other scenarios. The max size is configurable, so I know that nothing I am going to store is ever going to require heap allocations (really bad to be doing every frame in a game engine).

    I developed this specifically after benchmarking a simpler version and noticed a significant amount of time being spent in strlen(), and it had real benefits in my case.
    Admittedly just storing a struct with a static buffer and separate size would have worked pretty much the same and eliminated the 255 char limitation, but it was fun to build.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 4 child comments
    •
  • [–] 1 point 9 months ago (3 children)

    22 characters is significantly less useful than 255 characters.

    You can still use more than 22 characters; it just switches to the heap.

    nothing I am going to store is ever going to require heap allocations

    I would put good money that using 256 bytes everywhere is going to be slower overall than just using the heap when you need more than 22 characters. 22 is quite a lot, especially for keys. ThisReallyLongKey is still only 17.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 3 child comments
    •
  • [–] 1 point 9 months ago (2 children)

    I don't use 256 bytes everywhere. I use a mix of 64, 128, and 256 byte strings depending on the specific use case.
    In a hot path, having the data inline is much more important than saving a few hundred bytes. Cache efficiency plus eliminating heap allocations has huge performance benefits in a game engine that's running frames as fast as possible.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] 1 point 9 months ago (1 child)

    having the data inline

    It's not as simple as that, depending on the architecture. Typically they would fetch 64-byte cache lines so your 128 bytes aren't going to be magically more cached than 128 bytes on the heap.

    Avoiding allocations may help but also maybe not. This is definitely in "I don't believe it until I see benchmarks" realm. I would be really really surprised if the allocation cost was remotely bad enough to justify the "sorry your file is too long" errors.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 1 child comment
    •