I frequently having a hard time deciding which transpose to use when there are multiple consumers that each want a different shape

Sounds like a database

Yeah it gave me this hunch too.

I could imagine a language /framework where we declare the schema of data, indexes on this schema, and either let a query planner optimise data access or explicitly specify which index to use

You've described SQL :)

Sure at a conceptual level all stored data, even transitory, is a database, but I don't think that's a helpful analysis here, for a start current databases are far too limited.

A database implies a separate runtime system to manage data, whereas this is data storage within a program, part of 'data-structures and algorithms'.

Sure, but you're describing a fully functional database integrated with a fully functional programming language.

Just because you're describing a possibly novel integration of those two systems doesn't mean it's not valuable to consider the prior art for both constituent pieces.

The Jai programming language has some support for that.

OpenMP is doing something like that

Legion is also doing something like that: https://legion.stanford.edu/

Halide is pretty specialized and only somewhat related to this, but I really like the concept: https://halide-lang.org/

A tldr is: define your logical algorithm and its implementation separately, so you can freely tweak the implementation to optimize it without risking correctness.

I’m working on a masters thesis doing essentially this, for the problem of prefetching. There are a lot of existing papers demonstrating techniques for smarter prefetching for non- sequential data structures like trees and graphs. That can be done with some success purely at the hardware level, but having language- level semantic information helps a lot for dealing with complex data structures. What I’m working on is a cache controller modification to allow the running program or OS to tell the cache controller how best to prefetch specific pieces of data.

"having language- level semantic information helps a lot for dealing with complex data structures."

Yes that's what I'm thinking - much of the current stuff seems to be trying to guess what the code is doing from a low level (eg branch prediction) whereas the language itself could tell.

I'm pretty sure I've read a PhD thesis that implements exactly that - e.g. the program can load a program into the prefetcher

Sounds like a nightmare post-spectre.

Definitely possible, it’s a fairly active area. There are a few very similar techniques I’ve seen covered, but I think the details of my/our approach are still unique enough to merit publishing (for now), if I can get reasonable performance results.

And yes, loading semi-arbitrary code into a prefetcher is quite scary. It was the first question I had about this project. I think that maybe picking and choosing one of a multitude of prefetching "recipes" which are trusted would be more plausible as en eventual viable strategy. Like, the compiler inserts some instructions after allocating the nodes of a DAG that says "hey prefetcher, this is a DAG, please choose the graph prefetching algo with x/y/z parameters."

I've previously written about the idea of serialised access patterns. If we could somehow represent all the patterns of the data we're accessing, we could optimise layout.

See SHAPES[1] for a method of selecting data layout without sacrificing the abstraction programmers are typically used to having in OOP.

The idea is that a "layout" is decoupled from the object that stores the data. Layouts are attached to a memory pool which is used to allocate objects. The same object representation can have its data laid out in multiple ways depending on which pool allocates it.

[1]https://www.doc.ic.ac.uk/%7Escd/ShapesOnwards.pdf

> an array of structures, the compiler/language should be able to turn that into a structure of arrays

class Point:

    i: int

    def get_x():

        return x_array[i]

# shift every point

x_array += 1