6 ms·

This could be different in game dev, but in the last years of writing rust (outside of learning the language) I very rarely need to index any collection. There

This could be different in game dev, but in the last years of writing rust (outside of learning the language) I very rarely need to index any collection. There is a very certain way rust is supposed to be used, which is a negative on it's own, but it will lead to a fulfilling and productive programming experience. (My opinion) If you need to regularly index something, then you're using the language wrong.

ChadNauseam 1y ago
This is getting downvoted but it's kind of true. Indexing collections all the time usually means you're not using iterators enough. (Although iterators become very annoying for fallible code that you want to return a Result, so sometimes it's cleaner not to use them.) However this problem does still come up in iterator contexts. For example Iterator::take takes a usize.
- kevincox 1y ago
  While you maybe "shouldn't" be indexing collections often (which I also don't agree with, there is a reason that we have more collections then linked lists, lookup is important) even just getting the size of a collection which is often very related to business logic can be quite annoying.
  - AndrewDucker 1y ago
    For data that needs to be looked up mostly I want a hashtable. Not always, but mostly. It's rare that I want to look up something but its position in a list.
- bunderbunder 1y ago
  An iterator works if you're sequentially visiting every item in the collection, in the order they're stored. It's terrible if you need random access, though. Concrete example: pulling a single item out of a zip file, which supports random access, is O(1). Pulling a single item out of a *.tar.gz file, which can only be accessed by iterating it, is O(N).
  - cantrecallmypwd 1y ago
    History lesson for the cheap seats in the back: Compressed tars are terrible for random access because the compression occurs after the concatenation and so knows nothing about inner file metadata, but it's good for streaming and backups. Uncompressed tars are much better for random access. (Tar was a used as a backup mechanism to tape (tape archive).) Zips are terrible for streaming because their metadata is stored at the end, but are better for 1-pass creation and on-disk random access. (Remember that zip files and programs were created in an era of multiple floppy disk-based backups.) When fast tar enumeration is desired, at the cost of compatibility and compression potential, it might be worth compressing files and then taring them when and if zipping alone isn't achieving enough compression and/or decompression performance. FUSE compressed tar mounting gets to be really expensive with terabyte archives.
    - fc417fc802 1y ago
      > compressing files and then taring them Just use squashfs if that is the functionality that you need.
      - cantrecallmypwd 1y ago
        That works too if it's available.
  - int_19h 1y ago
    In C++, random access iterators are a thing. Indeed, raw pointers satisfy the requirements of a random access iterator concept. Is that not the case in Rust?
bunderbunder 1y ago
I'm no game dev but I have had friends who do it professionally. Long story short, yes, it's very different in game dev. It's very common to pre-allocate space for all your working data as large statically sized arrays because dynamic allocation is bad for performance. Oftentimes the data gets organized in parallel arrays (https://en.wikipedia.org/wiki/Parallel_array https://en.wikipedia.org/wiki/Parallel_array) instead of in collections of structs. This can save a lot of memory (because the data gets packed more densely) be more cache-friendly, and makes it much easier to make efficient use of SIMD instructions. This is also fairly common in scientific computing (which is more my wheelhouse), and for the same reason: it's good for performance.
- Pet_Ant 1y ago
  > Oftentimes the data gets organized in parallel arrays (https://en.wikipedia.org/wiki/Parallel_array https://en.wikipedia.org/wiki/Parallel_array) instead of in collections of structs. This can save a lot of memory (because the data gets packed more densely) be more cache-friendly, and makes it much easier to make efficient use of SIMD instructions. That seems like something that could very easily be turned into a compiler optimisation and enabled with something like an annotation. Would have some issue when calling across library boundaries ( a lot like the handling of gradual types), but within the codebase that'd be easy.
  - bunderbunder 1y ago
    Meh. I've tried "SIMD magic wand" tools before, and found them to be verschlimmbessern. At least on the scientific computing side of things, having the way the code says the data is organized match the way the data is actually organized ends up being a lot easier in the long run than organizing it in a way that gives frontend developers warm fuzzies and then doing constant mental gymnastics to keep track of what the program is actually doing under the hood. I think it's probably like sock knitting. People who do a lot of sock knitting tend to use double-pointed needles. They take some getting used to and look intimidating, though. So people who are just learning to knit socks tend to jump through all sorts of hoops and use clever tricks to allow them to continue using the same kind of knitting needles they're already used to. From there it can go two ways: either they get frustrated, decide sock knitting is not for them, and go back to knitting other things; or they get frustrated, decide magic loop is not for them, and learn how to use double-pointed needles.
nonameiguess 1y ago
I'm not a game dev, but what's a straightforward way of adjusting some channel of a pixel at coordinate X,Y without indexing the underlying raster array? Iterators are fine when you want to perform some operation on every item in a collection but that is far from the only thing you ever might want to do with a collection.
- deleted 1y ago
  [deleted]
- maccard 1y ago
  Game dev here. If you’re concerned about performance the only answer to this is a pixel shader, as anything else involves either cpu based rendering or a texture copy back and forth.
  - fc417fc802 1y ago
    A compute shader could update some subset of pixels in a texture. It's on the programmer to prevent race conditions though. However that would again involve explicit indexing. In general I think GP is correct. There is some subset of problems that absolutely requires indexing to express efficiently.
    - spookie 1y ago
      You can manipulate texture coordinate derivatives in order to just sample a subset of the whole texture on a pixel shader and only shade those pixels (basically the same as mipmapping, but you can have the "window" wherever you want really). This is something you can't do on a compute shader, given you don't have access to the built-in derivative methods (building your own won't be cheaper either). Still, if you want those changes to persist, a compute shader would be the way to go. You _can_ do it using a pixel shader but it really is less clean and more hacky.
      - fc417fc802 1y ago
        That is true. Hadn't occurred to me because I'd had in mind pixel sorting stuff I did in the past where the fetches and stores aren't contiguous. Interestingly enough the derivative functions are available to compute shaders as of SM 6.6. [0] Oddly SPIR-V only makes the associated opcodes [1] available to the fragment execution model for some reason. I'm not sure how something like DXVK handles that. I'm not clear if the associated DXIL or SPIR-V opcodes are actually implemented in hardware. I couldn't immediately find anything relevant in the particular ISA I checked and I'm nowhere near motivated enough to go digging through the Mesa source code to see how the magic happens. Relevant because since you mentioned it I'm curious how much of a perf hit rolling your own is. [0] https://microsoft.github.io/DirectX-Specs/d3d/HLSL_SM_6_6_Derivatives.html https://microsoft.github.io/DirectX-Specs/d3d/HLSL_SM_6_6_De... [1] https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.html#OpDPdx https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.htm...
at_compile_time 1y ago
On the contrary, I find indices to be the most natural way to represent anything that resembles a graph in Rust. They allow you to sidestep the usual issues that arise with ownership and borrowing, particularly with mutability, by handing ownership to the collection and using indices to allow nodes to refer to one another. It's delightfully simple compared to the mess of Arc and RefCell that tends to result when one tries to apply patterns from languages that leave "shared XOR mutable" as the programmer's responsibility. That's not to say that Vec and usize are appropriate for the task, but Rust's type system can be used to do a lot better.

ChadNauseam 1y ago

This is getting downvoted but it's kind of true. Indexing collections all the time usually means you're not using iterators enough. (Although iterators become very annoying for fallible code that you want to return a Result, so sometimes it's cleaner not to use them.) However this problem does still come up in iterator contexts. For example Iterator::take takes a usize.

kevincox 1y ago
While you maybe "shouldn't" be indexing collections often (which I also don't agree with, there is a reason that we have more collections then linked lists, lookup is important) even just getting the size of a collection which is often very related to business logic can be quite annoying.
- AndrewDucker 1y ago
  For data that needs to be looked up mostly I want a hashtable. Not always, but mostly. It's rare that I want to look up something but its position in a list.
bunderbunder 1y ago
An iterator works if you're sequentially visiting every item in the collection, in the order they're stored. It's terrible if you need random access, though. Concrete example: pulling a single item out of a zip file, which supports random access, is O(1). Pulling a single item out of a *.tar.gz file, which can only be accessed by iterating it, is O(N).
- cantrecallmypwd 1y ago
  History lesson for the cheap seats in the back: Compressed tars are terrible for random access because the compression occurs after the concatenation and so knows nothing about inner file metadata, but it's good for streaming and backups. Uncompressed tars are much better for random access. (Tar was a used as a backup mechanism to tape (tape archive).) Zips are terrible for streaming because their metadata is stored at the end, but are better for 1-pass creation and on-disk random access. (Remember that zip files and programs were created in an era of multiple floppy disk-based backups.) When fast tar enumeration is desired, at the cost of compatibility and compression potential, it might be worth compressing files and then taring them when and if zipping alone isn't achieving enough compression and/or decompression performance. FUSE compressed tar mounting gets to be really expensive with terabyte archives.
  - fc417fc802 1y ago
    > compressing files and then taring them Just use squashfs if that is the functionality that you need.
    - cantrecallmypwd 1y ago
      That works too if it's available.
- int_19h 1y ago
  In C++, random access iterators are a thing. Indeed, raw pointers satisfy the requirements of a random access iterator concept. Is that not the case in Rust?

bunderbunder 1y ago

I'm no game dev but I have had friends who do it professionally. Long story short, yes, it's very different in game dev. It's very common to pre-allocate space for all your working data as large statically sized arrays because dynamic allocation is bad for performance. Oftentimes the data gets organized in parallel arrays (https://en.wikipedia.org/wiki/Parallel_array https://en.wikipedia.org/wiki/Parallel_array) instead of in collections of structs. This can save a lot of memory (because the data gets packed more densely) be more cache-friendly, and makes it much easier to make efficient use of SIMD instructions. This is also fairly common in scientific computing (which is more my wheelhouse), and for the same reason: it's good for performance.

Pet_Ant 1y ago
> Oftentimes the data gets organized in parallel arrays (https://en.wikipedia.org/wiki/Parallel_array https://en.wikipedia.org/wiki/Parallel_array) instead of in collections of structs. This can save a lot of memory (because the data gets packed more densely) be more cache-friendly, and makes it much easier to make efficient use of SIMD instructions. That seems like something that could very easily be turned into a compiler optimisation and enabled with something like an annotation. Would have some issue when calling across library boundaries ( a lot like the handling of gradual types), but within the codebase that'd be easy.
- bunderbunder 1y ago
  Meh. I've tried "SIMD magic wand" tools before, and found them to be verschlimmbessern. At least on the scientific computing side of things, having the way the code says the data is organized match the way the data is actually organized ends up being a lot easier in the long run than organizing it in a way that gives frontend developers warm fuzzies and then doing constant mental gymnastics to keep track of what the program is actually doing under the hood. I think it's probably like sock knitting. People who do a lot of sock knitting tend to use double-pointed needles. They take some getting used to and look intimidating, though. So people who are just learning to knit socks tend to jump through all sorts of hoops and use clever tricks to allow them to continue using the same kind of knitting needles they're already used to. From there it can go two ways: either they get frustrated, decide sock knitting is not for them, and go back to knitting other things; or they get frustrated, decide magic loop is not for them, and learn how to use double-pointed needles.

nonameiguess 1y ago

I'm not a game dev, but what's a straightforward way of adjusting some channel of a pixel at coordinate X,Y without indexing the underlying raster array? Iterators are fine when you want to perform some operation on every item in a collection but that is far from the only thing you ever might want to do with a collection.

deleted 1y ago
[deleted]
maccard 1y ago
Game dev here. If you’re concerned about performance the only answer to this is a pixel shader, as anything else involves either cpu based rendering or a texture copy back and forth.
- fc417fc802 1y ago
  A compute shader could update some subset of pixels in a texture. It's on the programmer to prevent race conditions though. However that would again involve explicit indexing. In general I think GP is correct. There is some subset of problems that absolutely requires indexing to express efficiently.
  - spookie 1y ago
    You can manipulate texture coordinate derivatives in order to just sample a subset of the whole texture on a pixel shader and only shade those pixels (basically the same as mipmapping, but you can have the "window" wherever you want really). This is something you can't do on a compute shader, given you don't have access to the built-in derivative methods (building your own won't be cheaper either). Still, if you want those changes to persist, a compute shader would be the way to go. You _can_ do it using a pixel shader but it really is less clean and more hacky.
    - fc417fc802 1y ago
      That is true. Hadn't occurred to me because I'd had in mind pixel sorting stuff I did in the past where the fetches and stores aren't contiguous. Interestingly enough the derivative functions are available to compute shaders as of SM 6.6. [0] Oddly SPIR-V only makes the associated opcodes [1] available to the fragment execution model for some reason. I'm not sure how something like DXVK handles that. I'm not clear if the associated DXIL or SPIR-V opcodes are actually implemented in hardware. I couldn't immediately find anything relevant in the particular ISA I checked and I'm nowhere near motivated enough to go digging through the Mesa source code to see how the magic happens. Relevant because since you mentioned it I'm curious how much of a perf hit rolling your own is. [0] https://microsoft.github.io/DirectX-Specs/d3d/HLSL_SM_6_6_Derivatives.html https://microsoft.github.io/DirectX-Specs/d3d/HLSL_SM_6_6_De... [1] https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.html#OpDPdx https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.htm...

at_compile_time 1y ago

On the contrary, I find indices to be the most natural way to represent anything that resembles a graph in Rust. They allow you to sidestep the usual issues that arise with ownership and borrowing, particularly with mutability, by handing ownership to the collection and using indices to allow nodes to refer to one another. It's delightfully simple compared to the mess of Arc and RefCell that tends to result when one tries to apply patterns from languages that leave "shared XOR mutable" as the programmer's responsibility. That's not to say that Vec and usize are appropriate for the task, but Rust's type system can be used to do a lot better.