On Fri, May 20, 2022 at 5:04 PM Elijah Stone <elro...@elronnd.net> wrote: > Was that from intel?
I guess (after reading below) that that depends on what you mean by "from". > My impression--pieced together piecemeal from various sources--is that > 'structure of arrays' was a design pattern and meme that arose in the late 90s > to early 2000s in the world of game development, and which was itself > ultimately a derivative of the earlier columnar stores--from at least the 70s, > if not earlier--which were common in finance for representing time-series tick > data, often in APL! Indeed. > This pattern of columnar storage can better be seen as a special case of > _transposition_ of multidimensional data--that is dyadic |:--rearranging axes > such that common access patterns exhibit greater spatial locality wrt ravel > order (which is how arrays are generally represented in memory). Yes, though there's other issues having to do with the sizes and interpretations (and/or types) of the items. > And this is why the view of one particular axis ordering which places short > axes at the end as an 'inefficient abstraction' is really naive. Locality is > an important aspect of optimisation, but locality is a property of accesses, > not of data structures, and in some cases what you call 'array of structures' > really is more efficient. This does lead into algorithmic dependencies. And, also, it leads into expected workloads. > But really, the issue of transposition and columnarity is a bit of a giveaway: > these are all patterns that apply to _tabular_ data. Whereas the > distinguishing feature of 'objects'--_particularly_ in languages like j, which > are prototype-based--is their _heterogeneity_. They are good at modeling > nonuniform data in a way which may be harder with arrays. (I still don't know > a more space-efficient representation for graphs than an adjacency matrix.) There's a degree of truth to that. That said, a space efficient representation of a relatively sparse directed graph would be a two column matrix, with one column representing connections and the other column representing node ids. For the less commonly treated densely connected directed graph, you could replace the column representing connections with a column representing the absence of a connection. > I prefer, then, to think of 'array spaces'. Any portion of an array space may > be realised at any given time by a named array; by a cell of an array; by an > intermediate array; by a function; by a cache; etc. A locale/object is a > flexible mechanism that is commonly used to hold some realisations of some > portions of some array spaces (among other things). That is a point of > flexibility and modularity, not performance! Certainly. But for highly optimized micro-modules you want a compiler which automatically detects and removes as many unnecessary mechanisms as possible from the implementation. And, for us to have that in J, we would probably want a J compiler for some constrained subset of the language, and a systematic and well documented way of calling between J and these compiled artifacts (along with callbacks for compiled adverbs and conjunctions). > And I will note that I would be somewhat surprised were any foundational > tenets of j's design were founded in performance. I expect it was just a > happy accident (or, perhaps, something a bit deeper than that, but not by > much) that arrays turned out to be fast. The original design of APL (and inherited by J) was rooted in specification of machine architecture. So it shouldn't be too surprising that there's a good match between machine operations and language primitives. > And, again, it is surely a mistake to think that arrays will always be faster > than pointer-chasing. It is contextual. (I will avow that an array-oriented > language will _encourage_ array-oriented approaches, which may be faster than > the alternative where both are feasible.) To give one relevant, recent > example, I gave up on trying to represent bounding volume hierarchies in a way > consumable by I. (though some improvements to I.'s implementation are in the > pipeline, as a result of that, so it was not a complete waste). I would be > genuinely curious to know if somebody is able to come up with a good > array-oriented BVH construction. Pointer chasing maps onto arrays as indexing. That said, I haven't spent much time thinking about bounded volume hierarchies. Thanks, -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
