6 ms·

It seems to me there is scope for a language feature of 'managed memory' where you declare the data you need and how it is to be accessed (or access can be dete

It seems to me there is scope for a language feature of 'managed memory' where you declare the data you need and how it is to be accessed (or access can be determined from the program), and let the language/compiler figure out how to organize it for safety and performance. For example if you declare an array of structures, the compiler/language should be able to turn that into a structure of arrays under the hood if that is the way the data is accessed. Not sure how that could work in practice, I guess you'd start with hints, but it seems like something to research. Indeed I'm sure there's already some research in this area.

klysm 3y ago
I frequently having a hard time deciding which transpose to use when there are multiple consumers that each want a different shape
ttymck 3y ago
Sounds like a database
- williamdclt 3y ago
  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
  - ttymck 3y ago
    You've described SQL :)
- jacknews 3y ago
  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'.
  - ttymck 3y ago
    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.
jzwinck 3y ago
The Jai programming language has some support for that.
mati365 3y ago
OpenMP is doing something like that
01100011 3y ago
Legion is also doing something like that: https://legion.stanford.edu/ https://legion.stanford.edu/
Groxx 3y ago
Halide is pretty specialized and only somewhat related to this, but I really like the concept: https://halide-lang.org/ 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.
jakeinspace 3y ago
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.
- jacknews 3y ago
  "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.
- mhh__ 3y ago
  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.
  - jakeinspace 3y ago
    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."
samsquire 3y ago
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.
sparkie 3y ago
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 https://www.doc.ic.ac.uk/%7Escd/ShapesOnwards.pdf
jamann 3y ago
> 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

klysm 3y ago

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

ttymck 3y ago

Sounds like a database

williamdclt 3y ago
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
- ttymck 3y ago
  You've described SQL :)
jacknews 3y ago
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'.
- ttymck 3y ago
  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.

jzwinck 3y ago

The Jai programming language has some support for that.

mati365 3y ago

OpenMP is doing something like that

01100011 3y ago

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

Groxx 3y ago

Halide is pretty specialized and only somewhat related to this, but I really like the concept: https://halide-lang.org/ 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.

jakeinspace 3y ago

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.

jacknews 3y ago
"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.
mhh__ 3y ago
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.
- jakeinspace 3y ago
  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."

samsquire 3y ago

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.

sparkie 3y ago

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 https://www.doc.ic.ac.uk/%7Escd/ShapesOnwards.pdf

jamann 3y ago

> 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