4 ms·

I haven’t heard much about JAI for a few years, is this idea catching on? I don’t know why not both, is it maybe because one of the two layouts will almost alw

by dahart 4y ago

I haven’t heard much about JAI for a few years, is this idea catching on? I don’t know why not both, is it maybe because one of the two layouts will almost always have worse performance for any given access pattern? I can see uses for having both for the non-critical-path parts, though maybe once you’re indexing it in the awkward but perf-friendly way, you’ve already done the hard work and there’s little point to proving the other style of indexing? (Isn’t the best perf always found using whatever layout & indexing is the most difficult… there must be some eponymous law for this, right?) I guess it is possible to have multiple critical paths each favoring a different layout. Not sure how often I’ve ever seen that in practice, I would guess it’s probably rather rare.

hinkley 4y ago
The most obvious one to me is what if you change your mind? What if 90% of these objects should be compactly slab allocated, but you also run small, very disjointed numbers of them through an editor or an undo list or whatever and so they need to live separate from this array? I don't know what the answer is, but I feel like a few good candidates will come out of the conversations started by Rust. You can't replace an object with a new object while it's globally readable. But if you own the parent object, you can rewrite it however you want, or whichever ways are compatible with the other invariants you want for the system, like max time per frame or response time.
- moonchild 4y ago
  > You can't replace an object with a new object while it's globally readable Sure you can. This is the whole point of smalltalk become: and common lisp CHANGE-CLASS.
  - hinkley 4y ago
    Those change the type annotations for a memory location. Also if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying. We are talking about retaining the type and swapping the pointers from an independent object to a set of offsets into a struct of arrays.
    - moonchild 4y ago
      > if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying You are making a big assumption. Neither common lisp nor smalltalk specify the semantics of concurrent programs, but it is certainly possible to implement such a feature without, as you say, concurrency gotchas. Perhaps a better example is concurrently compacting gcs for java.
moonchild 4y ago
As far as I can tell, the 'structure of arrays' design pattern appeared in the game development world some time around 1998-2005. Columnar layouts have been known for upwards of 50 years now, as has the general notion that the way you lay out and represent your data matters and can be adjusted at will for your use cases. Many different layouts and optimisation structures are known and have been used, esp. in databases.
- hinkley 4y ago
  Blow isn’t inventing structs of arrays. It’s as you say a common gaming idiom and one he’s used before. What he was doing is trying to make it a first class citizen. Very few languages do anything for these. None of the language I use have iterator that work for this. You have to write your own bookkeeping logic every time.
marcinjachymiak 4y ago
The memory layout can be better this way depending on how the fields of a strict are laid out. It also gives the data better locality. Let's say you're iterating over position coordinates of some set of objects in a game. With an array-of-structs you can lose ou on cache locality if unrelated fields are nearby. If you use a struct-of-arrays you get cache locality advantages anytime you do something like "iterate over this 1 field for each object" The latter approach is called data oriented programming btw, and seems to have been around for a while. Andrew Kelley gave a good talk about it recently while using Zig: https://media.handmade-seattle.com/practical-data-oriented-design/ https://media.handmade-seattle.com/practical-data-oriented-d...

by dahart 4y ago

hinkley 4y ago

The most obvious one to me is what if you change your mind? What if 90% of these objects should be compactly slab allocated, but you also run small, very disjointed numbers of them through an editor or an undo list or whatever and so they need to live separate from this array? I don't know what the answer is, but I feel like a few good candidates will come out of the conversations started by Rust. You can't replace an object with a new object while it's globally readable. But if you own the parent object, you can rewrite it however you want, or whichever ways are compatible with the other invariants you want for the system, like max time per frame or response time.

moonchild 4y ago
> You can't replace an object with a new object while it's globally readable Sure you can. This is the whole point of smalltalk become: and common lisp CHANGE-CLASS.
- hinkley 4y ago
  Those change the type annotations for a memory location. Also if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying. We are talking about retaining the type and swapping the pointers from an independent object to a set of offsets into a struct of arrays.
  - moonchild 4y ago
    > if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying You are making a big assumption. Neither common lisp nor smalltalk specify the semantics of concurrent programs, but it is certainly possible to implement such a feature without, as you say, concurrency gotchas. Perhaps a better example is concurrently compacting gcs for java.

moonchild 4y ago

As far as I can tell, the 'structure of arrays' design pattern appeared in the game development world some time around 1998-2005. Columnar layouts have been known for upwards of 50 years now, as has the general notion that the way you lay out and represent your data matters and can be adjusted at will for your use cases. Many different layouts and optimisation structures are known and have been used, esp. in databases.

hinkley 4y ago
Blow isn’t inventing structs of arrays. It’s as you say a common gaming idiom and one he’s used before. What he was doing is trying to make it a first class citizen. Very few languages do anything for these. None of the language I use have iterator that work for this. You have to write your own bookkeeping logic every time.

marcinjachymiak 4y ago

The memory layout can be better this way depending on how the fields of a strict are laid out. It also gives the data better locality. Let's say you're iterating over position coordinates of some set of objects in a game. With an array-of-structs you can lose ou on cache locality if unrelated fields are nearby. If you use a struct-of-arrays you get cache locality advantages anytime you do something like "iterate over this 1 field for each object" The latter approach is called data oriented programming btw, and seems to have been around for a while. Andrew Kelley gave a good talk about it recently while using Zig: https://media.handmade-seattle.com/practical-data-oriented-design/ https://media.handmade-seattle.com/practical-data-oriented-d...