An approach for cheap small tables of int values

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

An approach for cheap small tables of int values

Dibyendu Majumdar
One of the problems I have thought about for a while is how to
implement multi-dimensional array indexing efficiently. I have been
playing with Torch recently where I noticed that Lua tables are often
used as small sets of integer values representing tensor dimensions
etc.

I think it may be possible to have an optimized special case of small
table as follows:

If the table contains 1,2 or 3 int values, pack these into the TValue
itself - without any heap allocation. Then it will be quite cheap to
create these small table objects.

Of course this is just an initial thought and there are undoubtedly
implementation issues I have not foreseen.

Regards
Dibyendu

Reply | Threaded
Open this post in threaded view
|

Re: An approach for cheap small tables of int values

Daurnimator
On 11 March 2018 at 12:07, Dibyendu Majumdar <[hidden email]> wrote:

> One of the problems I have thought about for a while is how to
> implement multi-dimensional array indexing efficiently. I have been
> playing with Torch recently where I noticed that Lua tables are often
> used as small sets of integer values representing tensor dimensions
> etc.
>
> I think it may be possible to have an optimized special case of small
> table as follows:
>
> If the table contains 1,2 or 3 int values, pack these into the TValue
> itself - without any heap allocation. Then it will be quite cheap to
> create these small table objects.
>
> Of course this is just an initial thought and there are undoubtedly
> implementation issues I have not foreseen.
>
> Regards
> Dibyendu

A TValue is only 4+8=12 bytes (though require 16 byte alignment).
How do you propose to fit 1,2 or 3 int values in there? You can barely
fit one 64bit integer.

Reply | Threaded
Open this post in threaded view
|

Re: An approach for cheap small tables of int values

Dibyendu Majumdar
On 11 March 2018 at 01:51, Daurnimator <[hidden email]> wrote:

> On 11 March 2018 at 12:07, Dibyendu Majumdar <[hidden email]> wrote:
>> One of the problems I have thought about for a while is how to
>> implement multi-dimensional array indexing efficiently. I have been
>> playing with Torch recently where I noticed that Lua tables are often
>> used as small sets of integer values representing tensor dimensions
>> etc.
>>
>> I think it may be possible to have an optimized special case of small
>> table as follows:
>>
>> If the table contains 1,2 or 3 int values, pack these into the TValue
>> itself - without any heap allocation. Then it will be quite cheap to
>> create these small table objects.
>>
>> Of course this is just an initial thought and there are undoubtedly
>> implementation issues I have not foreseen.
>>
>
> A TValue is only 4+8=12 bytes (though require 16 byte alignment).
> How do you propose to fit 1,2 or 3 int values in there? You can barely
> fit one 64bit integer.
>

It is a trade-off between slight CPU overhead versus the overhead of
heap allocation. Most of the time the int values are small enough to
fit into 32 bits - so the code can simply check the if the values are
small (bit masking?) and then fit up to 3 values into the TValue
structure which is 16 bytes. This check will cost some CPU cycles ....
but still worth it probably given that the alternative of heap
allocation is hugely expensive.