Re: An approach for cheap small tables of int values

[Dibyendu Majumdar <mobile@...>]

On 11 March 2018 at 01:51, Daurnimator <quae@daurnimator.com> wrote:
> On 11 March 2018 at 12:07, Dibyendu Majumdar <mobile@majumdar.org.uk> 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.