Data structure placement

Compilers have optimised instruction placement and register use. We don’t need to put further effort into optimising instruction selection. We now need to chase the remaining 90% of performance by optimising data structures. I propose data structure optimising machines. They should be aware of cache lines and VM paging.

A data structure optimiser would place data to optimise cache line usage. It analyses and rewrites code to make use of caches. For example:

for item in game_entities:
  x_vector = math.sin(item.angle)
  y_vector = math.cos(item.angle)
  item["x"] -= x_vector * item.speed
  item["y"] -= y_vector * item.speed

In this code, we require item.angle and item. speed. So we can store the game data like so:

game_entities = [
{"angle": 30 / Math.PI * 180, "speed": 1, "x": 100, "y": 100},
{"angle": 160 / Math.PI * 180, "speed": 1, "x": 50, "y": 50}

We want game_entities.angle, game_entities.x, game_entities.y, game_entities.speed to all be nearby one another so they are loaded together by the cache lines.

I want to be able to write the above code, even if the data layout is somewhat different. The compiler should make the conversions necessary to access all the data. For example, if we were running mass calculations across game entities, we might produce this layout:

xes = [100, 50]
yes = [100, 50]
speeds = [1, 1]
angles = [30, 160]
number_of_entities = 2
for item in range(0, number_of_entities):
  x = xes[item]
  y = yes[item]
  speed = speeds[item]
  angle = angles[item]
  xes[item] -= Math.sin(angle) * speed
  yes[item] -= Math.cos(angle) * speed

It’s almost like an automatic switchover to column based variables rather than row based variables. A bit like how we have column orientated databases and row based databases.

Leave a Reply

Your email address will not be published. Required fields are marked *