Home » forums » LtU Forum

Automatic data structure / layout selection?

I'm looking for any research on compilers which automatically select different data layouts or structures in order to improve efficiency. For example, changing an array of structures to a structure of arrays to make it easier to use vector operations. However I don't just mean selecting one data layout and using it throughout the program but converting between different layouts at appropriate points such as a sequence which could be implemented as a linked list or an array depending on which operations were being performed on it. I also wonder if something like this could be integrated with a copying garbage collector.

By George Morrison at 2009-03-23 17:56 | LtU Forum | previous forum topic | next forum topic | other blogs | 3885 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Two jump to mind:

Two jump to mind: "Chameleon: Adaptive Selection of Collections" (PLDI 2009) and Merlin (couldn't find the reference). Look at those and work backwards.

For various reasons, I wouldn't expect to find much. I suspect this is wonderfully low-hanging fruit (esp. when you go to handling parallel programs -- general tuning, handling false sharing, lock precision, etc.).

By lmeyerov at Mon, 2009-03-23 18:10 | login or register to post comments

I can't find out much about

I can't find out much about the Chameleon paper probably because PLDI09 hasn't happened yet and couldn't find any relevant project called Merlin.

I did however find a few possibly relevant papers:
Macroscopic Data Structure Analysis and Optimization
On automatic data structure selection and code generation for sparse computations
Nonlinear array layouts for hierarchical memory systems

By George Morrison at Sat, 2009-03-28 16:05 | login or register to post comments