5 ms·

> C code uses a lot of linked lists because linked lists are easy. Strong disagree. I don't see any reason why a competent programmer would hand-code a linked

> C code uses a lot of linked lists because linked lists are easy. Strong disagree. I don't see any reason why a competent programmer would hand-code a linked list, which is more of a hassle to make than a simple array (e.g. using buffer pointer + capacity and/or length field), unless the linked list makes actual sense for performance.

mhh__ 5y ago
I'm not saying you're duty bound to do it but rather giving an example of something which in my experience is encouraged by C since it's the path of least friction. Try writing a type that can automatically switch layout from AOS to SOA in C, you just can't do it.
- uluyol 5y ago
  Out of curiosity, what are some languages that can automatically switch layout between struct-of-arrays and array-of-structs?
  - mhh__ 5y ago
    The only language I know for sure to do it for you (as in you don't have to write the type) was Jai a while back (I'm told Blow removed that feature). The only language I've actually done it in, is D. It's probably doable in many other nu-C languages these days, but D at very least can make it basically seamless as long as you do some try-and-break-shit testing to make sure nothing is relying on saving pointers when they shouldn't. This obviously constrains the definition of automatic ;) I don't have my implementation to hand because it grew out of patch that failed due to aforementioned pointer-saving in code that I'm not paid enough to refactor (), but here's one someone else made https://github.com/nordlow/phobos-next/blob/master/src/nxt/soa_petar_kirov.d https://github.com/nordlow/phobos-next/blob/master/src/nxt/s... there's another one in that repository too. I've never used those particular implementations but they're both by people I know so hopefully they're not too bad. A more subtle thing, which I haven't used in anger, but would like to try at some point is to use programmer annotations (probably in the form of user defined attributes) to try and group things so things are stored such that temporal locality <=> spacial locality, but I've never bothered to actually do it. There are some arrays of structs in an old bit of the D compiler that are roughly the size of a cacheline, and aren't accessed particularly uniformly. I profiled this and found that something like 75% of all LLC misses (hitting DRAM) were due to 2 particularly miserable lines... inside an O(n^2) algorithm.
  - wahern 5y ago
    ISPC has some support for this using the "soa<>" qualifier. For example, struct Point { float x, y, z; }; soa<8> Point pts[...]; for (int i = 0; i < 8; ++i) { pts[i].x + pts[i].y } behaves as if originally written like struct Point { float x[8], y[8], z[8]; }; Point pts; for (int i = 0; i < 8; ++i) { pts.x[i] + pts.y[i]; } See https://ispc.github.io/ispc.html#structure-of-array-types https://ispc.github.io/ispc.html#structure-of-array-types I've not yet had an excuse to use ISPC myself, unfortunately :(
  - dangets 5y ago
    Zig has a compile time annotation that can do it. https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0 https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-i...
  - tjalfi 5y ago
    Jovial 73 has the PAR qualifier which converts an AoS to a SoA.
- jstimpfle 5y ago
  You can't hide AOS vs SOA in C and in most other languages, but that has nothing to do at all with linked lists. (you could use a macro to encapsulate the layout though, or in C++ could code a function that returns a reference) In what situations are linked lists the path of least friction??
  - mhh__ 5y ago
    I picked linked lists as a real example of something I've seen people do. It doesn't really make any difference my point. C is a bad programming language in 2022
    - jstimpfle 5y ago
      Well picking an invalid example (C encourages the use of linked lists in situations where they aren't a good idea) and a very questionable example (automatic conversions between different SAO/AOS representations are not mostly at an experimental stage but are an important feature for performance programming in 2022) is not a good way to support a claim that isn't empirically evident.
      - mhh__ 5y ago
        It's empirically evident in that no-one is picking C for new projects anymore. Anything fast is in C++ or C++ like languages.

mhh__ 5y ago

I'm not saying you're duty bound to do it but rather giving an example of something which in my experience is encouraged by C since it's the path of least friction. Try writing a type that can automatically switch layout from AOS to SOA in C, you just can't do it.

uluyol 5y ago
Out of curiosity, what are some languages that can automatically switch layout between struct-of-arrays and array-of-structs?
- mhh__ 5y ago
  The only language I know for sure to do it for you (as in you don't have to write the type) was Jai a while back (I'm told Blow removed that feature). The only language I've actually done it in, is D. It's probably doable in many other nu-C languages these days, but D at very least can make it basically seamless as long as you do some try-and-break-shit testing to make sure nothing is relying on saving pointers when they shouldn't. This obviously constrains the definition of automatic ;) I don't have my implementation to hand because it grew out of patch that failed due to aforementioned pointer-saving in code that I'm not paid enough to refactor (), but here's one someone else made https://github.com/nordlow/phobos-next/blob/master/src/nxt/soa_petar_kirov.d https://github.com/nordlow/phobos-next/blob/master/src/nxt/s... there's another one in that repository too. I've never used those particular implementations but they're both by people I know so hopefully they're not too bad. A more subtle thing, which I haven't used in anger, but would like to try at some point is to use programmer annotations (probably in the form of user defined attributes) to try and group things so things are stored such that temporal locality <=> spacial locality, but I've never bothered to actually do it. There are some arrays of structs in an old bit of the D compiler that are roughly the size of a cacheline, and aren't accessed particularly uniformly. I profiled this and found that something like 75% of all LLC misses (hitting DRAM) were due to 2 particularly miserable lines... inside an O(n^2) algorithm.
- wahern 5y ago
  ISPC has some support for this using the "soa<>" qualifier. For example, struct Point { float x, y, z; }; soa<8> Point pts[...]; for (int i = 0; i < 8; ++i) { pts[i].x + pts[i].y } behaves as if originally written like struct Point { float x[8], y[8], z[8]; }; Point pts; for (int i = 0; i < 8; ++i) { pts.x[i] + pts.y[i]; } See https://ispc.github.io/ispc.html#structure-of-array-types https://ispc.github.io/ispc.html#structure-of-array-types I've not yet had an excuse to use ISPC myself, unfortunately :(
- dangets 5y ago
  Zig has a compile time annotation that can do it. https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0 https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-i...
- tjalfi 5y ago
  Jovial 73 has the PAR qualifier which converts an AoS to a SoA.
jstimpfle 5y ago
You can't hide AOS vs SOA in C and in most other languages, but that has nothing to do at all with linked lists. (you could use a macro to encapsulate the layout though, or in C++ could code a function that returns a reference) In what situations are linked lists the path of least friction??
- mhh__ 5y ago
  I picked linked lists as a real example of something I've seen people do. It doesn't really make any difference my point. C is a bad programming language in 2022
  - jstimpfle 5y ago
    Well picking an invalid example (C encourages the use of linked lists in situations where they aren't a good idea) and a very questionable example (automatic conversions between different SAO/AOS representations are not mostly at an experimental stage but are an important feature for performance programming in 2022) is not a good way to support a claim that isn't empirically evident.
    - mhh__ 5y ago
      It's empirically evident in that no-one is picking C for new projects anymore. Anything fast is in C++ or C++ like languages.