Implement inline caching for tables (optimization) #2

New Issue

2017-06-06T13:25:36Z

ghost commented

2017-06-06 13:25:36 +00:00

(Migrated from github.com)

Like https://github.com/v8/v8/wiki/Design%20Elements#fast-property-access explains, LuaJ could optimize field accesses by implement a trick called "inline caching". I think this optimization is done for prototype-based things, but maybe in Lua we can base in metatable's __index.

ghost commented

2017-06-06 13:41:38 +00:00

(Migrated from github.com)

How would it work? Suppose we've an empty table t. This table is currently based in an hidden class, call it,C0, which tells it the offset of which each field will be stored in memory. Each time it defines a new field, it does transition from CA to CB hidden class, in this way class CB tells how the fields that were in the previous CA class are stored and how the new field is stored (all the previous fields can be in the same offset of course). When there's no CB class, then a new CB class must be created, structuring it the same way as described before. And so on.

When a field is suddenly deleted (with nil, -nan or __mode), then there're two things to do: 1. Create a new hidden class, which tells the table to store its fields in hash mode. 2. Fill the deleted field offset with the nil value.

In this optimization it'd be much performant for a code to add fields in the same sequence, because otherwise then other hidden classes will be created for that sequence. Of course everyone will add fields sequentially in the same order as tables of the same type.

In order to avoid accumulating hidden classes for the table type, this optimization must only happen with metatable __index based tables, a.k.a. instances.

How would it work? Suppose we've an empty table `t`. This table is currently based in an hidden class, call it,`C0`, which tells it the offset of which each field will be stored in memory. Each time it defines a new field, it does transition from `CA` to `CB` hidden class, in this way class `CB` tells how the fields that were in the previous `CA` class are stored and how the new field is stored (all the previous fields can be in the same offset of course). When there's no `CB` class, then a new `CB` class must be created, structuring it the same way as described before. And so on. When a field is suddenly deleted (with `nil`, `-nan` or __mode), then there're two things to do: 1. Create a new hidden class, which tells the table to store its fields in hash mode. 2. Fill the deleted field offset with the `nil` value. In this optimization it'd be much performant for a code to add fields in the same sequence, because otherwise then other hidden classes will be created for that sequence. Of course everyone will add fields sequentially in the same order as tables of the same type. In order to avoid accumulating hidden classes for the table type, this optimization must only happen with metatable __index based tables, a.k.a. instances.

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: open-autonomous-connection/luaj#2