On 12 Nov 2013, at 11:55 , Henrik Johansen henrik.s.johansen@veloxit.no wrote:

nterest ~= time and: [skills]

OT: I swear, missing parenthesis will be the death of me!

I'm not sure I totally understand the post of Igor, since I was in the process of responding to Eliot, I need more time :)

Concerning single precision Float, they all can be represented losslessly in such immediate double (but Nan and Inf), so it might be better to let the VM as simple as possible like strongly suggested by Igor, and let experiments occur at image side.

Of course, I'm pretty convinced that Character MUST be in the immediate zoo, it's an obvious optimization given that so many algorithms suffers from human interaction and must deal with text at one moment or another :)

2013/11/12 Igor Stasenko siguctua@gmail.com

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

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@veloxit.nowrote:

...

On 12 Nov 2013, at 11:55 , Henrik Johansen henrik.s.johansen@veloxit.no wrote:

nterest ~= time and: [skills]

OT: I swear, missing parenthesis will be the death of me!

-- Best regards, Igor Stasenko.

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

Hi Igor,

On Tue, Nov 12, 2013 at 3:37 AM, Igor Stasenko siguctua@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@veloxit.nowrote:

...

On 12 Nov 2013, at 11:55 , Henrik Johansen henrik.s.johansen@veloxit.no wrote:

nterest ~= time and: [skills]

OT: I swear, missing parenthesis will be the death of me!

-- Best regards, Igor Stasenko.

-- best, Eliot

On 14 November 2013 17:44, Eliot Miranda eliot.miranda@gmail.com wrote:

On Thu, Nov 14, 2013 at 3:43 AM, Igor Stasenko siguctua@gmail.com wrote:

...

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

...

Hi Igor,

On Tue, Nov 12, 2013 at 3:37 AM, Igor Stasenko siguctua@gmail.comwrote:

...

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

I don't understand. Does that mean there are two cache entries, one for HighRange one for LowRange? Spell it out please. Give the pseudo-code. Right now it is too vague for me to see how it is supposed to work.

Two entries where? If i understand, in COG you using generated code for inline cache, by jumping onto PIC entry for checking if it hits or misses. So, you just generate different code for immediate case(s), to check that receiver oop value is tagged and within certain range (cache hit) , or not (cache miss).

A pseudo-code for bit-pattern matching is this:

"presuming least significant bit is tag" (oop bitAnd: 2r101) == 2r101 ifTrue: [ hit ] ifFalse: [ miss ]

And code for range matching is this:

"presuming least significant bit is tag" (oop odd and: [ oop between: lowValue and: highValue]) ifTrue: [ hit ] ifFalse: [ miss ]

"or presuming most significant bit is tag" (oop between: lowValue and: highValue) ifTrue: [ hit ] ifFalse: [ 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).

So the inline cache becomes a range of entries? That will cause a significant code bloat.

i'm not sure i understood, what that extra inline cache you talking about? presuming that each PIC is generated code, you just generate different code for entry which specialized to detect that given oop is of certain immediate class.

But if its not, then yes, you need to hold these two values somewhere to be able to compare them with input oop. But even in that case, i fail to see how single extra comparison could cause so much bloat.

And it always good to compare, how much bloat will cause bit pattern matching code.

What is clearly beneficial for immediate ranges that you can redefine them at any moment by introducing new kinds of immediates , without need to even touch VM: language can easily control that. And the potential number of immediate classes is much bigger , if you encode them in ranges, because:

2^31 (smallint) + 2^32 (short float) + 2^24 (character unicode) = 6459228160

which leaves us:

2^63 - 6459228160 = 9223372030395547648 space for other kinds of immediates, which we can introduce later !!without!! need to ever bother VM again.

On 15 November 2013 18:26, Eliot Miranda eliot.miranda@gmail.com wrote:

Hi Igor,

On Fri, Nov 15, 2013 at 5:04 AM, Igor Stasenko siguctua@gmail.com wrote:

...

On 14 November 2013 17:44, Eliot Miranda eliot.miranda@gmail.com wrote:

...

On Thu, Nov 14, 2013 at 3:43 AM, Igor Stasenko siguctua@gmail.comwrote:

...

On 12 November 2013 19:23, Eliot Miranda eliot.miranda@gmail.comwrote:

...

Hi Igor,

On Tue, Nov 12, 2013 at 3:37 AM, Igor Stasenko siguctua@gmail.comwrote:

...

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

I don't understand. Does that mean there are two cache entries, one for HighRange one for LowRange? Spell it out please. Give the pseudo-code. Right now it is too vague for me to see how it is supposed to work.

Two entries where? If i understand, in COG you using generated code for inline cache, by jumping onto PIC entry for checking if it hits or misses. So, you just generate different code for immediate case(s), to check that receiver oop value is tagged and within certain range (cache hit) , or not (cache miss).

That's not right. PICs are only used at send sites that prove to be polymorphic, i.e. become PICs after a send failure. At first they are simply monomorphic inline caches with a single entry. Only 9% of active send sites fail to be rebound to PICs.

oh right , i was speaking about monomorphic cache. yeah.. we discussed this with Clement today.. and while it is good to have virtually unlimited number of immediate classes.. in reality we can barely find 10 cases which worth turning into immediate objects. Maybe one day i will try to run the experiment with it.. but for Spur, i think it not worth to do. I remember why i offered this model is because i feel a bit of a loss, when people were discussing how much bits to reserve for immediates tag (3 or 4) and then how much immediate types you got, and then its like a lottery to pick a lucky ones which will become immediate ones (while unlucky poor ones will be left behind ;)

...

A pseudo-code for bit-pattern matching is this:

"presuming least significant bit is tag" (oop bitAnd: 2r101) == 2r101 ifTrue: [ hit ] ifFalse: [ miss ]

And code for range matching is this:

"presuming least significant bit is tag" (oop odd and: [ oop between: lowValue and: highValue]) ifTrue: [ hit ] ifFalse: [ miss ]

"or presuming most significant bit is tag" (oop between: lowValue and: highValue) ifTrue: [ hit ] ifFalse: [ miss ]

and how are these two pieces of code related?

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).

So the inline cache becomes a range of entries? That will cause a significant code bloat.

i'm not sure i understood, what that extra inline cache you talking about? presuming that each PIC is generated code, you just generate different code for entry which specialized to detect that given oop is of certain immediate class.

But if its not, then yes, you need to hold these two values somewhere to be able to compare them with input oop. But even in that case, i fail to see how single extra comparison could cause so much bloat.

And it always good to compare, how much bloat will cause bit pattern matching code.

What is clearly beneficial for immediate ranges that you can redefine them at any moment by introducing new kinds of immediates , without need to even touch VM: language can easily control that. And the potential number of immediate classes is much bigger , if you encode them in ranges, because:

2^31 (smallint) + 2^32 (short float) + 2^24 (character unicode) = 6459228160

which leaves us:

2^63 - 6459228160 = 9223372030395547648 space for other kinds of immediates, which we can introduce later !!without!! need to ever bother VM again.

-- Best regards, Igor Stasenko.

-- best, Eliot

On Tue, Nov 12, 2013 at 3:56 AM, Clément Bera bera.clement@gmail.comwrote:

Hey,

By the way as you are talking about Immediate objects tags and Spur's object representation, I read on other VMs reports that it is faster in overall performance to have pointers tagged with the xxx1 and SmallIntegers tagged with xxx0, because SmallIntegers arithmetics is then much faster. Is it possible to modify that easily in Cog to try ? Do you have to edit only a few methods such as #longAt:, #integerValueOf: and SmallInteger primitives ?

Another thing, I read in a java VM report that only 1% of objects needs a hash (other objects hash are unused), so their hash implementation took only 2 bits in the header, being: 01 -> no hash 10 -> hash is the object's address 11 -> hash is in a header extension Therefore, on first access to the hash, hash bits switches from 01 to 10, and the GC on objects with 10 switches the hash bits from 10 to 11 and add a header extension with the old address of the object. But I know I'm not teaching you anything there. What I would like to know is why did you choose in Spur to have a 22bits hash in the header over this implementation, and will the hash in Spur be calculated at each instantiation or lazily ?

Thanks for any answers,

Regards, Clement

2013/11/12 Henrik Johansen henrik.s.johansen@veloxit.no

...

On 12 Nov 2013, at 11:55 , Henrik Johansen henrik.s.johansen@veloxit.no wrote:

nterest ~= time and: [skills]

OT: I swear, missing parenthesis will be the death of me!

Thanks for the answer.

Clement I love your questions :) Stef

On Nov 12, 2013, at 7:33 PM, Eliot Miranda eliot.miranda@gmail.com wrote:

Hi Clément,

On Tue, Nov 12, 2013 at 3:56 AM, Clément Bera bera.clement@gmail.com wrote:

Hey,

By the way as you are talking about Immediate objects tags and Spur's object representation, I read on other VMs reports that it is faster in overall performance to have pointers tagged with the xxx1 and SmallIntegers tagged with xxx0, because SmallIntegers arithmetics is then much faster.

I'm sure that was true 20 years ago when register operations were about the same speed as memory operations. But now that memory operations are at least an order of magnitude slower I suspect that adjusting the tags (all register operations) are in the noise. But I agree it *would* be interesting to measure.

Is it possible to modify that easily in Cog to try ? Do you have to edit only a few methods such as #longAt:, #integerValueOf: and SmallInteger primitives ?

You'd have to modify the isImmediate:/isNonImmediate:, isIntegerObject:, isNonIntegerObject:, and storePointer:ofObject:withValue:/fetchPointer:ofObject: methods, and then the code generated by the CogObjectRepresentation subclass, and modify the bootstrap to produce an image with the new tagging. The VM is factored so that this isn't horribly difficult. But it's work. Perhaps it would be a good student project?

Another thing, I read in a java VM report that only 1% of objects needs a hash (other objects hash are unused), so their hash implementation took only 2 bits in the header, being: 01 -> no hash 10 -> hash is the object's address 11 -> hash is in a header extension Therefore, on first access to the hash, hash bits switches from 01 to 10, and the GC on objects with 10 switches the hash bits from 10 to 11 and add a header extension with the old address of the object. But I know I'm not teaching you anything there.

That's clever. Yes you are :-). Thanks.

What I would like to know is why did you choose in Spur to have a 22bits hash in the header over this implementation, and will the hash in Spur be calculated at each instantiation or lazily ?

I chose the 22 bit hash scheme because it is part of the idea of having class indices. Notice that an object's class index is 22 bits also. The point here is that a class's hash is its class index. So to instantiate a class one copies the class's hash into the instance's class index, avoiding searching the class table to find the class's index. Perhaps this isn't the most optimal approach but it is coherent, and worked well for 64-bit VisualWorks.

The hash calculation is lazy. The hash field is 0 when instantiated. Hence

Behavior>>identityHash "Answer a SmallInteger whose value is related to the receiver's identity. This method must not be overridden. Primitive. Fails if the receiver is not a Behavior. Essential. See Object documentation whatIsAPrimitive.

Do not override."

<primitive: 175> self primitiveFailed

InterpreterPrimitives>>primitiveBehaviorHash | hashOrError | self assert: ((objectMemory isNonImmediate: self stackTop) and: [self addressCouldBeClassObj: self stackTop]). hashOrError := objectMemory ensureBehaviorHash: self stackTop. hashOrError >= 0 ifTrue: [self pop: argumentCount + 1 thenPushInteger: hashOrError] ifFalse: [self primitiveFailFor: hashOrError negated]

SpurMemoryManager>>ensureBehaviorHash: aBehavior | newHash err | <inline: true> self assert: (coInterpreter addressCouldBeClassObj: aBehavior). (newHash := self rawHashBitsOf: aBehavior) = 0 ifTrue: [(err := self enterIntoClassTable: aBehavior) ~= 0 ifTrue: [^err negated]. newHash := self rawHashBitsOf: aBehavior. self assert: (self classAtIndex: newHash) = aBehavior]. ^newHash

Thanks for any answers,

Regards, Clement

cheers!

2013/11/12 Henrik Johansen henrik.s.johansen@veloxit.no

On 12 Nov 2013, at 11:55 , Henrik Johansen henrik.s.johansen@veloxit.no wrote:

...

nterest ~= time and: [skills]

OT: I swear, missing parenthesis will be the death of me!

-- best, Eliot

Sadly, interest ~= time and: [skills] :/

so true for me too.

Stef