[Vm-dev] Spur Object 64 bit format

[Igor Stasenko]

On 12 November 2013 19:23, Eliot Miranda <eliot.miranda at gmail.com> wrote:

>
> Hi Igor,
>
>
> On Tue, Nov 12, 2013 at 3:37 AM, Igor Stasenko <siguctua at gmail.com> wrote:
>
>>
>> And let me remind you what i proposed back then:
>>
>> :)
>> ===========
>> About immediates zoo.
>>
>> Keep in mind, that the more immediates we have, the more complex
>> implementation
>> tends to be.
>>
>> I would just keep 2 data types:
>>  - integers
>>  - floats
>>
>> and third, special 'arbitrary' immediate , which seen by VM as a 60-bit
>> value.
>> The interpretation of this value depends on lookup in range-table,
>> where developer specifying the correspondence between the value
>> interval and class:
>> [min .. max] -> class
>>
>
> for this idea to go anywhere you'd have to show at least the pseudo-code
> for the inline cache test in machine code methods.  These schemes seem
> great in theory but in practice end up with a long, complex and slow
> fetchClassOf: and/or inline cache test.  To remind you, you have to compete
> with the following in Spur Cog:
>
> Limm:
> andl $0x1, %eax
> j Lcmp
>  Lentry:
> movl %edx, %eax
> andl $0x3, %eax
>  jnz Limm
> movl 0(%edx), %eax
> andl $0x3fffff, %eax
>  Lcmp:
>

It is extra comparison for immediate case:

cmp eax, LowRange
jl miss
cmp eax, HighRange
jg miss

so, if value between low & high range, it is already known what class it is
otherwise
you got cache miss.

And this scheme works even better if you pick highest bit for tagging, like
that you can get rid of testing tag bit completely:
andl $0x1, %eax
j Lcmp
and start straight from comparing with high and low values.
That of course, if we can use highest bit for tagging.

The class lookup then will be binary search in table of ranges, which is
O(log n).



>
> This occurs at the start of every method.  Its efficiency and size is
> really important for performance and compactness of machine code.  I'm
> really not trying to be negative; it is simply a fact of life with a
> Smalltalk JIT.
>
> intervals, of course, cannot overlap.
>> Determining a class of such immediate might be slower - O(log2(n)) at
>> best (where n is size of range table), but from other side,
>> how many different kinds of immediates you can fit into 60-bit value?
>> Right, it is 2^60. Much more than proposed 8 isn't? :)
>>
>> And this extra cost can be mitigated completely by inline cache.
>> - in case of regular reference, you must fetch the object's class and
>> then compare it with one, stored in cache.
>> - in case of immediate reference, you compare immediate value with min
>> and max stored in cache fields.
>> And if value is in range, you got a cache hit, and free to proceed.
>> So, its just 1 extra comparison comparing to 'classic' inline cache.
>>
>> And, after thinking how inline cache is organized, now you can scratch
>> the first my paragraph related to  immediates!
>> We really don't need to discriminate between small integers/floats/rest!!
>> They could also be nothing more than just one of a range(s) defined in
>> our zoo of 'special' immediates!
>>
>> So, at the end we will have just two kinds of references:
>>  - zero bit == 0 -- an object pointer
>>  - zero bit == 1 -- an immediate
>>
>> Voila!.
>>
>> We can have real zoo of immediates, and simple implementation to support
>> them.
>> And not saying that range-table is provided by language-side, so we're
>> free to rearrange them at any moment.
>>
>> And of course, it doesn't means that VM could not reserve some of the
>> ranges for own 'contracted'
>> immediates, like Characters, and even class reference for example.
>> Think about it :)
>>
>>
>>
>> On 12 November 2013 11:56, Henrik Johansen <henrik.s.johansen at veloxit.no>wrote:
>>
>>>
>>>
>>> On 12 Nov 2013, at 11:55 , Henrik Johansen <henrik.s.johansen at veloxit.no>
>>> wrote:
>>>
>>> nterest ~= time and: [skills]
>>>
>>>
>>> OT: I swear, missing parenthesis will be the death of me!
>>>
>>>
>>
>>
>> --
>> Best regards,
>> Igor Stasenko.
>>
>>
>
>
> --
> best,
> Eliot
>
>


-- 
Best regards,
Igor Stasenko.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20131114/e08bbad3/attachment.htm