Re: TaggedArrays (Proposal)

[Charles Oliver Nutter]

On Sat, Jul 7, 2012 at 1:45 PM, Rémi Forax  wrote:
> Exception are not expensive if you throw them and just catch them (and
> don't use them) in the same inlining horizon,
> so you can use them to implement non Java control flow without thinking
> too much.

Important to note here that if they don't inline, you get considerably
slower exception logic, so it's crucial that the exception throw and
catch inline together. This is hard to guarantee on current VMs...and
in fact this may be the most difficult aspect of writing low-level
systems for the JVM right now (like language implementations): you
can't make any guarantees.

- Charlie
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

Hi Dain

I use exceptions to handle non local returns in ST which are not 
exceptional ( happen alot).
I did a quick look at the timing and the throw/catch was not slow.

I believe John Rose has a blog entry on it

mark



From:   Dain Sundstrom 
To: Da Vinci Machine Project 
Date:   07/07/2012 10:10 AM
Subject:Re: TaggedArrays (Proposal)
Sent by:mlvm-dev-boun...@openjdk.java.net



On Jul 7, 2012, at 1:56 AM, Rémi Forax wrote:

> You have also to figure out how to get two return values from a method 
call,
> but exceptions are your best friend here.

Can you give an example of what you mean here?  Also, from all the 
presentations I've seen on the JVM, exceptions are very expensive to throw 
and catch, so I would expect this to be way slower then say returning the 
multiple values using a generated results class.

-dain
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

Thanks Rémi,  good example

is big compared to the code of the generated assembler so the JIT may 
decide to not inline something

I assume that changing the maxInline will fix this if its an issue

You have also to figure out how to get two return values from a method 
call,
but exceptions are your best friend here.

I already do this for other ST patterns so no problem.

thanks
mark___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Dain Sundstrom]

Wow.  That dramatically changes my mental model of exceptions in the JVM.  This 
is going to dramatically simplify some of my code.

thanks

-dain

On Jul 7, 2012, at 11:48 AM, Vitaly Davidovich wrote:

> Here's a blog post from John Rose explaining that exception throwing compiles 
> to a goto in cases like this: 
> https://blogs.oracle.com/jrose/entry/longjumps_considered_inexpensive
> 
> Sent from my phone
> 
> On Jul 7, 2012 2:43 PM, "Rémi Forax"  wrote:
> On 07/07/2012 07:02 PM, Dain Sundstrom wrote:
> > On Jul 7, 2012, at 1:56 AM, Rémi Forax wrote:
> >
> >> You have also to figure out how to get two return values from a method 
> >> call,
> >> but exceptions are your best friend here.
> > Can you give an example of what you mean here?  Also, from all the 
> > presentations I've seen on the JVM, exceptions are very expensive to throw 
> > and catch, so I would expect this to be way slower then say returning the 
> > multiple values using a generated results class.
> 
> Exception are not expensive if you throw them and just catch them (and
> don't use them) in the same inlining horizon,
> so you can use them to implement non Java control flow without thinking
> too much.
> 
> Anyway, the idea here is to use exception as an exceptional mechanism by
> example when
> something that should be an int is not. In that case, throwing an
> exception is not a big deal
> because the VM will have to deopt which usual have a bigger impact on
> the run time.
> 
> >
> > -dain
> 
> Rémi
> 
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Vitaly Davidovich]

Here's a blog post from John Rose explaining that exception throwing
compiles to a goto in cases like this:
https://blogs.oracle.com/jrose/entry/longjumps_considered_inexpensive

Sent from my phone
On Jul 7, 2012 2:43 PM, "Rémi Forax"  wrote:

> On 07/07/2012 07:02 PM, Dain Sundstrom wrote:
> > On Jul 7, 2012, at 1:56 AM, Rémi Forax wrote:
> >
> >> You have also to figure out how to get two return values from a method
> call,
> >> but exceptions are your best friend here.
> > Can you give an example of what you mean here?  Also, from all the
> presentations I've seen on the JVM, exceptions are very expensive to throw
> and catch, so I would expect this to be way slower then say returning the
> multiple values using a generated results class.
>
> Exception are not expensive if you throw them and just catch them (and
> don't use them) in the same inlining horizon,
> so you can use them to implement non Java control flow without thinking
> too much.
>
> Anyway, the idea here is to use exception as an exceptional mechanism by
> example when
> something that should be an int is not. In that case, throwing an
> exception is not a big deal
> because the VM will have to deopt which usual have a bigger impact on
> the run time.
>
> >
> > -dain
>
> Rémi
>
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/07/2012 07:02 PM, Dain Sundstrom wrote:
> On Jul 7, 2012, at 1:56 AM, Rémi Forax wrote:
>
>> You have also to figure out how to get two return values from a method call,
>> but exceptions are your best friend here.
> Can you give an example of what you mean here?  Also, from all the 
> presentations I've seen on the JVM, exceptions are very expensive to throw 
> and catch, so I would expect this to be way slower then say returning the 
> multiple values using a generated results class.

Exception are not expensive if you throw them and just catch them (and 
don't use them) in the same inlining horizon,
so you can use them to implement non Java control flow without thinking 
too much.

Anyway, the idea here is to use exception as an exceptional mechanism by 
example when
something that should be an int is not. In that case, throwing an 
exception is not a big deal
because the VM will have to deopt which usual have a bigger impact on 
the run time.

>
> -dain

Rémi

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Dain Sundstrom]

On Jul 7, 2012, at 1:56 AM, Rémi Forax wrote:

> You have also to figure out how to get two return values from a method call,
> but exceptions are your best friend here.

Can you give an example of what you mean here?  Also, from all the 
presentations I've seen on the JVM, exceptions are very expensive to throw and 
catch, so I would expect this to be way slower then say returning the multiple 
values using a generated results class.

-dain
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/07/2012 04:54 AM, Mark Roos wrote:
> Hi Rémi,  you mention
> And now the trick, there is a nice way (several in fact) to explain to
> the JIT
> that even if the bytecode contains tests, if the variable contains
> effectively an int,
> it's a good idea to remove them.
>
> Ok,  in Smalltalk there are some methods which are usually integer ops
> so its easy to determine vars that are likely integer.  I have slots in
> the stack reserved for just this idea.
>
> So if I have a pair of slots A and B where A would be the integer from 
> and B the reference.
> Would I test B to be null and if so do an integer op on A?

yes, that the basic idea.

>
> So plese point me at the bytecode tricks that make the test go away.

It's not a bytecode trick, it's a JIT trick.
The VM profiles jump instruction like 'if' to know which branch is 
taken, and
doesn't generate code but a deoptimization code if a branch is never taken.
So the generator of a backend will generate a code like this for a + 1:

   int r1 = ...
   Object o1 = ...
   if (o1 == null) {
  r2 = r1 + 1
  o2 = null
   } else {
  r2 = 0
  o2 = invokedynamic + o1, 1
   }

   if (o2 == null) {  // next instruction
   ...
   } else { ...
   ...

and because o1 is never null, the JIT will generate

jne a_deoptimization_code
inc r2

also because the JIT propagates null value aggressively, the jump can 
also disappear because
there is perhaps already another check before, by example, the check o2 
== null will
be removed here.

So the idea is to consider that if a variable can store an int, you 
should use two variables in the bytecode,
so result of an operation will be spilled into two variables instead of 
using the stack.
I call this idea, split-path and this is really effective, the main 
drawback is that the generated bytecode size
is big compared to the code of the generated assembler so the JIT may 
decide to not inline something
that it should.

You have also to figure out how to get two return values from a method call,
but exceptions are your best friend here.

>
> regards
> mark

rgds,
Rémi

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

Hi Rémi,  you mention
And now the trick, there is a nice way (several in fact) to explain to 
the JIT
that even if the bytecode contains tests, if the variable contains 
effectively an int,
it's a good idea to remove them.

Ok,  in Smalltalk there are some methods which are usually integer ops
so its easy to determine vars that are likely integer.  I have slots in 
the stack reserved for just this idea.

So if I have a pair of slots A and B where A would be the integer from and 
B the reference.
Would I test B to be null and if so do an integer op on A?

So plese point me at the bytecode tricks that make the test go away.

regards
mark

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/06/2012 08:48 PM, Mark Roos wrote:
> From Rémi on static analysis for loops
>
> Not having such kind of analysis is almost a crime.
>
> For a language like Smalltalk I was thinking that having such an analysis
> would be the work of the gods.
>
> With user overridable methods, reflection and run time code creation I 
> have only found a few
> places where I could do such an static analysis.  And those are fragile.
>
> So do you have a good paper that would apply?  I have looked at many 
> from the 80s/90s and
> have yet to find a general approach for a Smalltalk style language.
>
> I am thinking of adding a mutable flag to integers so I can share a 
> body but 'lazy' freeze to
> a real integer but it seems like I'll be adding lots of checks just to 
> fix what could be a small problem
> over an entire application.

yes, i don't think it's a good idea too because it's too late,
you want to avoid boxing not try to share boxes.

>
> I also have a thought to allocate a few primitive slots in each stack 
> frame to pass real primitives
> but again I have to test everywhere for which slot is valid.

First the idea is to use an analysis but not to answer to the question, 
"is this variable is an integer or not"
but to answer to the question "is this variable may be an integer or not".
Once the analysis done, you know how many supplementary slots you need.
And now the trick, there is a nice way (several in fact) to explain to 
the JIT
that even if the bytecode contains tests, if the variable contains 
effectively an int,
it's a good idea to remove them.

>
> The best thought may be to add patterns to the language to avoid the 
> use of visible integers
> as indexes  ( e.g. instead of '1 to:3 do:[aBlock over a collection]' 
> do 'aCollection from:1 to:3 do:[ aBlock on each indexed item]')
> Now I can do the static analysis.  As they say 'If it hurts don't do it'

> regards
> mark

cheers,
Rémi

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

>From Rémi on static analysis for loops

Not having such kind of analysis is almost a crime.

For a language like Smalltalk I was thinking that having such an analysis
would be the work of the gods.

With user overridable methods, reflection and run time code creation I 
have only found a few
places where I could do such an static analysis.  And those are fragile. 

So do you have a good paper that would apply?  I have looked at many from 
the 80s/90s and
have yet to find a general approach for a Smalltalk style language.

I am thinking of adding a mutable flag to integers so I can share a body 
but 'lazy' freeze to
a real integer but it seems like I'll be adding lots of checks just to fix 
what could be a small problem
over an entire application.

I also have a thought to allocate a few primitive slots in each stack 
frame to pass real primitives 
but again I have to test everywhere for which slot is valid.

The best thought may be to add patterns to the language to avoid the use 
of visible integers
as indexes  ( e.g. instead of '1 to:3 do:[aBlock over a collection]' do 
'aCollection from:1 to:3 do:[ aBlock on each indexed item]')
Now I can do the static analysis.  As they say 'If it hurts don't do it'

regards
mark___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

I see, it looks like you are using them to hold instance vars of objects. 
I was looking for
large arrays/collections.

I have looked at this before in our app but the number of integers used 
like this did not seem to
warrant much concern ( Double Vectors and byte[] are the dominant memory 
users).

thanks
mark



From:   Jim Laskey 
To: Da Vinci Machine Project 
Date:   07/05/2012 01:51 PM
Subject:Re: TaggedArrays (Proposal)
Sent by:mlvm-dev-boun...@openjdk.java.net



Fairly common patterns like

var p =  {
  fontsize: 15,
  lineheight: 22,
  color: 0x000,
  fontfamily: "Georgia, FreeSerif, Times, serif"
};

p.color = "white";

We need flexible slots without allocating 2x memory.

For "for like" constructs we typically use static analysis to reduce to 
integer.  With TaggedArray slots for frames we could use integer 
dynamically.

Cheers,

-- Jim






On 2012-07-05, at 5:26 PM, Mark Roos wrote:

Hi Ji! m 

I was wondering if you could post the use case that led you develop the 
TaggedArray? 
I looked over our Smalltalk app and I could not see an obvious pattern 
where mixing 
primitives and references in a collection is common. 

On a similar note I was curious how you are avoiding the integer 
allocation when using 
a 'for' like pattern to index over an array. That is a real performance 
hit for me so I 
am looking for a good solution 

thanks 
mark___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Jim Laskey]

On 2012-07-05, at 9:26 PM, Rémi Forax wrote:

> On 07/05/2012 10:42 PM, Jim Laskey wrote:
>> Fairly common patterns like
>> 
>> var p =  {
>>  fontsize: 15,
>>  lineheight: 22,
>>  color: 0x000,
>>  fontfamily: "Georgia, FreeSerif, Times, serif"
>> };
>> 
>> p.color = "white";
>> 
>> We need flexible slots without allocating 2x memory.
>> 
>> For "for like" constructs we typically use static analysis to reduce 
>> to integer.
> 
> Not having such kind of analysis is almost a crime.
> 
> Jim, do you have a paper explaining the static analysis you use,
> I have some trouble to keep mine linear.
> 

Marcus Lagergren will be doing a talk at JavaOne on type specific optimizations 
that we use.

>> With TaggedArray slots for frames we could use integer dynamically.
> 
> yes, but performance will be awful (ok, better than using boxing but 2x 
> or 3x slower
> than C or Java) if you don't have any kind of type propagation.

We're seeing 2x using C2, but the benefit is that if you have to roll over into 
another type (ex. box) you can use the same slot.

One subtlety I should point out, the plan is to have the copy method optimized 
to inline small copies, so that constant length copies of 1-4 (or so) will be 
native memory to memory moves.  This means you can move values, 
object/frame/stack to object/frame/stack without any type checking (1-1 with 
C/Java.)

> 
>> 
>> Cheers,
>> 
>> -- Jim
> 
> cheers,
> Rémi
> 
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/05/2012 10:42 PM, Jim Laskey wrote:
> Fairly common patterns like
>
> var p =  {
>   fontsize: 15,
>   lineheight: 22,
>   color: 0x000,
>   fontfamily: "Georgia, FreeSerif, Times, serif"
> };
>
> p.color = "white";
>
> We need flexible slots without allocating 2x memory.
>
> For "for like" constructs we typically use static analysis to reduce 
> to integer.

Not having such kind of analysis is almost a crime.

Jim, do you have a paper explaining the static analysis you use,
I have some trouble to keep mine linear.

> With TaggedArray slots for frames we could use integer dynamically.

yes, but performance will be awful (ok, better than using boxing but 2x 
or 3x slower
than C or Java) if you don't have any kind of type propagation.

>
> Cheers,
>
> -- Jim

cheers,
Rémi

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Jim Laskey]

Fairly common patterns like

var p =  {
  fontsize: 15,
  lineheight: 22,
  color: 0x000,
  fontfamily: "Georgia, FreeSerif, Times, serif"
};

p.color = "white";

We need flexible slots without allocating 2x memory.

For "for like" constructs we typically use static analysis to reduce to 
integer.  With TaggedArray slots for frames we could use integer dynamically.

Cheers,

-- Jim






On 2012-07-05, at 5:26 PM, Mark Roos wrote:

> Hi Jim 
> 
> I was wondering if you could post the use case that led you develop the 
> TaggedArray? 
> I looked over our Smalltalk app and I could not see an obvious pattern where 
> mixing 
> primitives and references in a collection is common. 
> 
> On a similar note I was curious how you are avoiding the integer allocation 
> when using 
> a 'for' like pattern to index over an array. That is a real performance hit 
> for me so I 
> am looking for a good solution 
> 
> thanks 
> mark___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

Hi Jim

I was wondering if you could post the use case that led you develop the 
TaggedArray?
I looked over our Smalltalk app and I could not see an obvious pattern 
where mixing
primitives and references in a collection is common.

On a similar note I was curious how you are avoiding the integer 
allocation when using
a 'for' like pattern to index over an array. That is a real performance 
hit for me so I
am looking for a good solution

thanks
mark___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Jim Laskey]

Note: The POC was implemented in JNI. 

Sent from my iPhone 4

On 2012-07-04, at 6:12 AM, Jim Laskey  wrote:

> I think we can handle that. Give us a few to get at least one of the native 
> versions working (C2/server - intel)
> 
> Sent from my iPhone 4
> 
> On 2012-07-04, at 6:03 AM, Rémi Forax  wrote:
> 
>> On 07/04/2012 03:18 AM, Jim Laskey wrote:
>>> Actually it's built on a modified 7. Getting it into a 7 release is a 
>>> community issue. I think tagged values comes under JSR-292, so some of 
>>> the process is covered. Not sure what the other steps involve. And of 
>>> course the API/implementation needs to be picked on a bit too.
>>> 
>>> Sent from my iPhone 4
>> 
>> Jim, is there a way to getting it as a patch in the mlvm workspace,
>> so we can test a little bit the API/implementation.
>> 
>> Rémi
>> 
>>> 
>>> On 2012-07-03, at 10:01 PM, Mark Roos >> > wrote:
>>> 
 Hi Jim,  You made a comment:
 
 implementation for platforms not supporting TaggedArrays (and JDK 1.7)
 
 Are you saying that a native version fo jdk1.7 is not possible,  or 
 just that you have not got around to it?
 
 regards
 mark
 
 ___
 mlvm-dev mailing list
 mlvm-dev@openjdk.java.net 
 http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>>> 
>>> 
>>> ___
>>> mlvm-dev mailing list
>>> mlvm-dev@openjdk.java.net
>>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>> 
>> 
>> ___
>> mlvm-dev mailing list
>> mlvm-dev@openjdk.java.net
>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Jim Laskey]

I think we can handle that. Give us a few to get at least one of the native 
versions working (C2/server - intel)

Sent from my iPhone 4

On 2012-07-04, at 6:03 AM, Rémi Forax  wrote:

> On 07/04/2012 03:18 AM, Jim Laskey wrote:
>> Actually it's built on a modified 7. Getting it into a 7 release is a 
>> community issue. I think tagged values comes under JSR-292, so some of 
>> the process is covered. Not sure what the other steps involve. And of 
>> course the API/implementation needs to be picked on a bit too.
>> 
>> Sent from my iPhone 4
> 
> Jim, is there a way to getting it as a patch in the mlvm workspace,
> so we can test a little bit the API/implementation.
> 
> Rémi
> 
>> 
>> On 2012-07-03, at 10:01 PM, Mark Roos > > wrote:
>> 
>>> Hi Jim,  You made a comment:
>>> 
>>> implementation for platforms not supporting TaggedArrays (and JDK 1.7)
>>> 
>>> Are you saying that a native version fo jdk1.7 is not possible,  or 
>>> just that you have not got around to it?
>>> 
>>> regards
>>> mark
>>> 
>>> ___
>>> mlvm-dev mailing list
>>> mlvm-dev@openjdk.java.net 
>>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>> 
>> 
>> ___
>> mlvm-dev mailing list
>> mlvm-dev@openjdk.java.net
>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
> 
> 
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/04/2012 03:18 AM, Jim Laskey wrote:
> Actually it's built on a modified 7. Getting it into a 7 release is a 
> community issue. I think tagged values comes under JSR-292, so some of 
> the process is covered. Not sure what the other steps involve. And of 
> course the API/implementation needs to be picked on a bit too.
>
> Sent from my iPhone 4

Jim, is there a way to getting it as a patch in the mlvm workspace,
so we can test a little bit the API/implementation.

Rémi

>
> On 2012-07-03, at 10:01 PM, Mark Roos  > wrote:
>
>> Hi Jim,  You made a comment:
>>
>> implementation for platforms not supporting TaggedArrays (and JDK 1.7)
>>
>> Are you saying that a native version fo jdk1.7 is not possible,  or 
>> just that you have not got around to it?
>>
>> regards
>> mark
>>
>> ___
>> mlvm-dev mailing list
>> mlvm-dev@openjdk.java.net 
>> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>
>
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev


___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Jim Laskey]

Actually it's built on a modified 7. Getting it into a 7 release is a community 
issue. I think tagged values comes under JSR-292, so some of the process is 
covered. Not sure what the other steps involve. And of course the 
API/implementation needs to be picked on a bit too. 

Sent from my iPhone 4

On 2012-07-03, at 10:01 PM, Mark Roos  wrote:

> Hi Jim,  You made a comment: 
> 
> implementation for platforms not supporting TaggedArrays (and JDK 
> 1.7) 
> 
> Are you saying that a native version fo jdk1.7 is not possible,  or just that 
> you have not got around to it? 
> 
> regards 
> mark 
> 
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

Hi Jim,  You made a comment:

implementation for platforms not supporting TaggedArrays (and JDK 
1.7)

Are you saying that a native version fo jdk1.7 is not possible,  or just 
that you have not got around to it?

regards
mark

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Thomas Wuerthinger]

Jim,

can you also make the native part (in particular the JNI implementation) 
available? We'd like to experiment with it in the context of the GraalVM 
repository.


Thx, thomas


On 02.07.2012 15:05, Jim Laskey wrote:
During a week in the rarefied air of Stockholm back in May, a 
sleepless night got me thinking.  The day after that, the thinking 
became a reality.  I've been sitting on the code since, not sure what 
to do next.  So..., why not start the month leading up to the JVMLS 
with a discussion about dynamic values.


Every jLanguage developer knows that primitive boxing is the enemy. 
 Even more so for untyped languages.  We need a way to interleave 
primitive types with references.


Tagged values (value types) for dynamic languages have been approached 
from a dozen different angles over the history of Java.  However, no 
one seems to be satisfied with any of the proposals so far.  Either 
the implementation is too limiting for the language developer or too 
complex to implement.


Most recently, John (Rose) proposed hiding value tagging in the JVM 
via the Integer/Long/Float/Double.valueof methods.  I saw a few issues 
with this proposal.  First, the implementation works differently on 32 
bit and 64 bit platforms (only half a solution on each).  Secondly, 
control of the tag bits is hidden such that it doesn't give a language 
implementor any leeway on bit usage.  Finally, it will take a long 
time for it to get introduced into the JVM.  The implementation is 
complex, scattered all over the VM and will lead to a significant 
multiplier for testing coverage.


It occurred to me on that sleepless Monday night, that the solution 
for most dynamic languages could be so much simpler.  First, we have 
to look at what it is we really need.  Ultimately it's about boxing. 
 We want to avoid allocating memory whenever we need to store a 
primitive value in an object.  Concerning ourselves with passing 
around tagged values in registers and storing in stack frames is all 
red herring.  All that is needed is a mechanism for storing tagged 
values (or compressed values) in a no-type slot of a generic object. 
 Thinking about it in these terms isolates all issues to a single 
array-like class, and thus simplifies implementation and simplifies 
testing.  Instances of this class can be used as objects, as stack 
frames and even full stacks.  A good percentage of a dynamic language 
needs are covered.


So, Rickard Bäckman (also of Oracle) and I defined an API and 
implemented (in HotSpot) an interface called TaggedArray. 
 Conceptional, TaggedArray is a fixed array of no-type slots (64-bit), 
where each slot can contain either a reference or a tagged long value 
(least significant bit set.)  Internally, TaggedArray class's doOop 
method knows that it should skip any 64-bit value with the least 
significant bit set.  How the language developer uses the other 63 
bits is up to them.  References are just addresses.  On 32 bit 
machines, the address (or packed address) is stored in the high 
32-bits (user has no access)  So there is no interference with the tag 
bit.


We supply four implementations of the API.  1) is a naive two parallel 
arrays (one Object[], one long[]) implementation for platforms not 
supporting TaggedArrays (and JDK 1.7), 2) an optimized version of 1) 
 that allocates each array on demand, 3) a JNI implementation 
(minimally needed for the interpreter) that uses the native 
implementation and 4) the native implementation that is recognized by 
both the C1/C2 compilers (effort only partially completed.)  In 
general, the implementation choice is transparent to the user (optimal 
choice.)


I've enclosed a JavaDoc and the roughed out source.  For discussion. 
 Fire away.


Cheers,

-- Jim








___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev


___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Krystal Mok]

@Howard

Your suggestion could pretty much work if the underlying VM is using a
conservative collector, where it'd actually include a set of filters to
check if a value is a (or "looks like a") real reference.

There are also a couple of runtimes that implements exact GC by tagging
values, but most JVMs that I know of doesn't work that way. They'd expect
all reference type fields to contain valid references.

- Kris

On Tue, Jul 3, 2012 at 1:46 PM, Howard Lovatt wrote:

> @Kris, I was assuming that the tag would be sufficient for the JVM since
> 'real' references would be aligned and hence naturally not tagged. But I
> don't know enough about the JVM and hence you could well be correct. --
> Howard.
>
>
> On 3 July 2012 15:40, Krystal Mok  wrote:
>
>> On Tue, Jul 3, 2012 at 1:28 PM, Howard Lovatt wrote:
>>
>>> I like the idea and something along these lines would be a great
>>> addition to the standard library, which I will come back to as a PS.
>>>
>>> In com.sun.misc.Unsafe there are already getLong(Object, int) and
>>> setLong(Object, int, long) methods and the same for Object. No doubt if we
>>> used getLong and setLong as they stand they would fail due to type checking
>>> if used to access references to Objects in an Object[]. However if similar
>>> methods were added that circumvented the type checking,
>>> getLongOrReference(Object, int) and setLongOrReference(Object, int, long),
>>> then you could write:
>>>
>>> private Object[] vsAndRs;
>>>
>>> ...
>>>
>>> @Override public long getValue(final int index) {
>>> checkIndex(pos);
>>> final long value = Unsafe.getLongOrReference(vsAndRs, index);
>>> if ( (value & TaggedArrays.TAG) != 0 ) {
>>> return value;
>>> }
>>> throw new TaggedArrayException("value at index =" + index + " is not
>>> tagged");
>>> }
>>>
>>> @Override public Object getReference(final int index) {
>>> if ( isReference(index) ) {
>>> return vsAndRs[index];
>>> }
>>> throw new TaggedArrayException("reference at index =" + index +" is
>>> tagged");
>>> }
>>>
>>> ..
>>>
>>> Which would save half the space and still be understandable Java (i.e.
>>> not a collection of native calls).
>>>
>>> It's not just about type checking at Java level, but also something deep
>> within the VM: the need to distinguish between a plain value and a
>> reference (pointer), which is fundamental to a exact/accurate garbage
>> collector.
>> Jim's idea includes modifying the doOop() function in the VM, which is
>> exactly where HotSpot handles reference fields within an object.
>>
>> If you put random values into a place where HotSpot (or other JVM impls
>> using exact GC) think it's a reference, then something bad may happen later
>> (e.g. during GC), that the VM think it had found a corrupted reference.
>>
>> - Kris
>>
>>
>>> Great work,
>>>
>>>  -- Howard.
>>>
>>> PS A few random thoughts for the interface, assuming that something like
>>> this makes it into the JDK then the following additions might be nice:
>>>
>>> 1. Fills that accept a lambda that receives the index as its argument
>>> (filling function as opposed to filling constant).
>>> 2. A second interface and second factory that define tagged arrays for
>>> long and double in addition to Objects, like the example code given.
>>> 3. TaggedArray32, primarily for phones etc., with the extended
>>> interface, point 2 above, for TaggedArray32 accepting Objects, ints, and
>>> floats. On a 64 bit system TaggedArray32 would be the same as TaggedArray,
>>> but for 32 bit systems it would save space.
>>>
>>>
>>> On 2 July 2012 23:05, Jim Laskey  wrote:
>>>
 During a week in the rarefied air of Stockholm back in May, a sleepless
 night got me thinking.  The day after that, the thinking became a reality.
  I've been sitting on the code since, not sure what to do next.  So..., why
 not start the month leading up to the JVMLS with a discussion about dynamic
 values.

 Every jLanguage developer knows that primitive boxing is the enemy.
  Even more so for untyped languages.  We need a way to interleave primitive
 types with references.

 Tagged values (value types) for dynamic languages have been approached
 from a dozen different angles over the history of Java.  However, no one
 seems to be satisfied with any of the proposals so far.  Either the
 implementation is too limiting for the language developer or too complex to
 implement.

 Most recently, John (Rose) proposed hiding value tagging in the JVM via
 the Integer/Long/Float/Double.valueof methods.  I saw a few issues with
 this proposal.  First, the implementation works differently on 32 bit and
 64 bit platforms (only half a solution on each).  Secondly, control of the
 tag bits is hidden such that it doesn't give a language implementor any
 leeway on bit usage.  Finally, it will take a long time for it to get
 introduced into the JVM.  The implementation is complex,

Re: TaggedArrays (Proposal)

[Howard Lovatt]

@Kris, I was assuming that the tag would be sufficient for the JVM since
'real' references would be aligned and hence naturally not tagged. But I
don't know enough about the JVM and hence you could well be correct. --
Howard.

On 3 July 2012 15:40, Krystal Mok  wrote:

> On Tue, Jul 3, 2012 at 1:28 PM, Howard Lovatt wrote:
>
>> I like the idea and something along these lines would be a great addition
>> to the standard library, which I will come back to as a PS.
>>
>> In com.sun.misc.Unsafe there are already getLong(Object, int) and
>> setLong(Object, int, long) methods and the same for Object. No doubt if we
>> used getLong and setLong as they stand they would fail due to type checking
>> if used to access references to Objects in an Object[]. However if similar
>> methods were added that circumvented the type checking,
>> getLongOrReference(Object, int) and setLongOrReference(Object, int, long),
>> then you could write:
>>
>> private Object[] vsAndRs;
>>
>> ...
>>
>> @Override public long getValue(final int index) {
>> checkIndex(pos);
>> final long value = Unsafe.getLongOrReference(vsAndRs, index);
>> if ( (value & TaggedArrays.TAG) != 0 ) {
>> return value;
>> }
>> throw new TaggedArrayException("value at index =" + index + " is not
>> tagged");
>> }
>>
>> @Override public Object getReference(final int index) {
>> if ( isReference(index) ) {
>> return vsAndRs[index];
>> }
>> throw new TaggedArrayException("reference at index =" + index +" is
>> tagged");
>> }
>>
>> ..
>>
>> Which would save half the space and still be understandable Java (i.e.
>> not a collection of native calls).
>>
>> It's not just about type checking at Java level, but also something deep
> within the VM: the need to distinguish between a plain value and a
> reference (pointer), which is fundamental to a exact/accurate garbage
> collector.
> Jim's idea includes modifying the doOop() function in the VM, which is
> exactly where HotSpot handles reference fields within an object.
>
> If you put random values into a place where HotSpot (or other JVM impls
> using exact GC) think it's a reference, then something bad may happen later
> (e.g. during GC), that the VM think it had found a corrupted reference.
>
> - Kris
>
>
>> Great work,
>>
>>  -- Howard.
>>
>> PS A few random thoughts for the interface, assuming that something like
>> this makes it into the JDK then the following additions might be nice:
>>
>> 1. Fills that accept a lambda that receives the index as its argument
>> (filling function as opposed to filling constant).
>> 2. A second interface and second factory that define tagged arrays for
>> long and double in addition to Objects, like the example code given.
>> 3. TaggedArray32, primarily for phones etc., with the extended interface,
>> point 2 above, for TaggedArray32 accepting Objects, ints, and floats. On a
>> 64 bit system TaggedArray32 would be the same as TaggedArray, but for 32
>> bit systems it would save space.
>>
>>
>> On 2 July 2012 23:05, Jim Laskey  wrote:
>>
>>> During a week in the rarefied air of Stockholm back in May, a sleepless
>>> night got me thinking.  The day after that, the thinking became a reality.
>>>  I've been sitting on the code since, not sure what to do next.  So..., why
>>> not start the month leading up to the JVMLS with a discussion about dynamic
>>> values.
>>>
>>> Every jLanguage developer knows that primitive boxing is the enemy.
>>>  Even more so for untyped languages.  We need a way to interleave primitive
>>> types with references.
>>>
>>> Tagged values (value types) for dynamic languages have been approached
>>> from a dozen different angles over the history of Java.  However, no one
>>> seems to be satisfied with any of the proposals so far.  Either the
>>> implementation is too limiting for the language developer or too complex to
>>> implement.
>>>
>>> Most recently, John (Rose) proposed hiding value tagging in the JVM via
>>> the Integer/Long/Float/Double.valueof methods.  I saw a few issues with
>>> this proposal.  First, the implementation works differently on 32 bit and
>>> 64 bit platforms (only half a solution on each).  Secondly, control of the
>>> tag bits is hidden such that it doesn't give a language implementor any
>>> leeway on bit usage.  Finally, it will take a long time for it to get
>>> introduced into the JVM.  The implementation is complex, scattered all over
>>> the VM and will lead to a significant multiplier for testing coverage.
>>>
>>> It occurred to me on that sleepless Monday night, that the solution for
>>> most dynamic languages could be so much simpler.  First, we have to look at
>>> what it is we really need.  Ultimately it's about boxing.  We want to avoid
>>> allocating memory whenever we need to store a primitive value in an object.
>>>  Concerning ourselves with passing around tagged values in registers and
>>> storing in stack frames is all red herring.  All that is needed is a
>>> mechanism for st

Re: TaggedArrays (Proposal)

[Krystal Mok]

On Tue, Jul 3, 2012 at 1:28 PM, Howard Lovatt wrote:

> I like the idea and something along these lines would be a great addition
> to the standard library, which I will come back to as a PS.
>
> In com.sun.misc.Unsafe there are already getLong(Object, int) and
> setLong(Object, int, long) methods and the same for Object. No doubt if we
> used getLong and setLong as they stand they would fail due to type checking
> if used to access references to Objects in an Object[]. However if similar
> methods were added that circumvented the type checking,
> getLongOrReference(Object, int) and setLongOrReference(Object, int, long),
> then you could write:
>
> private Object[] vsAndRs;
>
> ...
>
> @Override public long getValue(final int index) {
> checkIndex(pos);
> final long value = Unsafe.getLongOrReference(vsAndRs, index);
> if ( (value & TaggedArrays.TAG) != 0 ) {
> return value;
> }
> throw new TaggedArrayException("value at index =" + index + " is not
> tagged");
> }
>
> @Override public Object getReference(final int index) {
> if ( isReference(index) ) {
> return vsAndRs[index];
> }
> throw new TaggedArrayException("reference at index =" + index +" is
> tagged");
> }
>
> ..
>
> Which would save half the space and still be understandable Java (i.e. not
> a collection of native calls).
>
> It's not just about type checking at Java level, but also something deep
within the VM: the need to distinguish between a plain value and a
reference (pointer), which is fundamental to a exact/accurate garbage
collector.
Jim's idea includes modifying the doOop() function in the VM, which is
exactly where HotSpot handles reference fields within an object.

If you put random values into a place where HotSpot (or other JVM impls
using exact GC) think it's a reference, then something bad may happen later
(e.g. during GC), that the VM think it had found a corrupted reference.

- Kris


> Great work,
>
>  -- Howard.
>
> PS A few random thoughts for the interface, assuming that something like
> this makes it into the JDK then the following additions might be nice:
>
> 1. Fills that accept a lambda that receives the index as its argument
> (filling function as opposed to filling constant).
> 2. A second interface and second factory that define tagged arrays for
> long and double in addition to Objects, like the example code given.
> 3. TaggedArray32, primarily for phones etc., with the extended interface,
> point 2 above, for TaggedArray32 accepting Objects, ints, and floats. On a
> 64 bit system TaggedArray32 would be the same as TaggedArray, but for 32
> bit systems it would save space.
>
>
> On 2 July 2012 23:05, Jim Laskey  wrote:
>
>> During a week in the rarefied air of Stockholm back in May, a sleepless
>> night got me thinking.  The day after that, the thinking became a reality.
>>  I've been sitting on the code since, not sure what to do next.  So..., why
>> not start the month leading up to the JVMLS with a discussion about dynamic
>> values.
>>
>> Every jLanguage developer knows that primitive boxing is the enemy.  Even
>> more so for untyped languages.  We need a way to interleave primitive types
>> with references.
>>
>> Tagged values (value types) for dynamic languages have been approached
>> from a dozen different angles over the history of Java.  However, no one
>> seems to be satisfied with any of the proposals so far.  Either the
>> implementation is too limiting for the language developer or too complex to
>> implement.
>>
>> Most recently, John (Rose) proposed hiding value tagging in the JVM via
>> the Integer/Long/Float/Double.valueof methods.  I saw a few issues with
>> this proposal.  First, the implementation works differently on 32 bit and
>> 64 bit platforms (only half a solution on each).  Secondly, control of the
>> tag bits is hidden such that it doesn't give a language implementor any
>> leeway on bit usage.  Finally, it will take a long time for it to get
>> introduced into the JVM.  The implementation is complex, scattered all over
>> the VM and will lead to a significant multiplier for testing coverage.
>>
>> It occurred to me on that sleepless Monday night, that the solution for
>> most dynamic languages could be so much simpler.  First, we have to look at
>> what it is we really need.  Ultimately it's about boxing.  We want to avoid
>> allocating memory whenever we need to store a primitive value in an object.
>>  Concerning ourselves with passing around tagged values in registers and
>> storing in stack frames is all red herring.  All that is needed is a
>> mechanism for storing tagged values (or compressed values) in a no-type
>> slot of a generic object.  Thinking about it in these terms isolates all
>> issues to a single array-like class, and thus simplifies implementation and
>> simplifies testing.  Instances of this class can be used as objects, as
>> stack frames and even full stacks.  A good percentage of a dynamic language
>> needs are covered

Re: TaggedArrays (Proposal)

[Howard Lovatt]

I like the idea and something along these lines would be a great addition
to the standard library, which I will come back to as a PS.

In com.sun.misc.Unsafe there are already getLong(Object, int) and
setLong(Object, int, long) methods and the same for Object. No doubt if we
used getLong and setLong as they stand they would fail due to type checking
if used to access references to Objects in an Object[]. However if similar
methods were added that circumvented the type checking,
getLongOrReference(Object, int) and setLongOrReference(Object, int, long),
then you could write:

private Object[] vsAndRs;

...

@Override public long getValue(final int index) {
checkIndex(pos);
final long value = Unsafe.getLongOrReference(vsAndRs, index);
if ( (value & TaggedArrays.TAG) != 0 ) {
return value;
}
throw new TaggedArrayException("value at index =" + index + " is not
tagged");
}

@Override public Object getReference(final int index) {
if ( isReference(index) ) {
return vsAndRs[index];
}
throw new TaggedArrayException("reference at index =" + index +" is
tagged");
}

..

Which would save half the space and still be understandable Java (i.e. not
a collection of native calls).

Great work,

 -- Howard.

PS A few random thoughts for the interface, assuming that something like
this makes it into the JDK then the following additions might be nice:

1. Fills that accept a lambda that receives the index as its argument
(filling function as opposed to filling constant).
2. A second interface and second factory that define tagged arrays for long
and double in addition to Objects, like the example code given.
3. TaggedArray32, primarily for phones etc., with the extended interface,
point 2 above, for TaggedArray32 accepting Objects, ints, and floats. On a
64 bit system TaggedArray32 would be the same as TaggedArray, but for 32
bit systems it would save space.


On 2 July 2012 23:05, Jim Laskey  wrote:

> During a week in the rarefied air of Stockholm back in May, a sleepless
> night got me thinking.  The day after that, the thinking became a reality.
>  I've been sitting on the code since, not sure what to do next.  So..., why
> not start the month leading up to the JVMLS with a discussion about dynamic
> values.
>
> Every jLanguage developer knows that primitive boxing is the enemy.  Even
> more so for untyped languages.  We need a way to interleave primitive types
> with references.
>
> Tagged values (value types) for dynamic languages have been approached
> from a dozen different angles over the history of Java.  However, no one
> seems to be satisfied with any of the proposals so far.  Either the
> implementation is too limiting for the language developer or too complex to
> implement.
>
> Most recently, John (Rose) proposed hiding value tagging in the JVM via
> the Integer/Long/Float/Double.valueof methods.  I saw a few issues with
> this proposal.  First, the implementation works differently on 32 bit and
> 64 bit platforms (only half a solution on each).  Secondly, control of the
> tag bits is hidden such that it doesn't give a language implementor any
> leeway on bit usage.  Finally, it will take a long time for it to get
> introduced into the JVM.  The implementation is complex, scattered all over
> the VM and will lead to a significant multiplier for testing coverage.
>
> It occurred to me on that sleepless Monday night, that the solution for
> most dynamic languages could be so much simpler.  First, we have to look at
> what it is we really need.  Ultimately it's about boxing.  We want to avoid
> allocating memory whenever we need to store a primitive value in an object.
>  Concerning ourselves with passing around tagged values in registers and
> storing in stack frames is all red herring.  All that is needed is a
> mechanism for storing tagged values (or compressed values) in a no-type
> slot of a generic object.  Thinking about it in these terms isolates all
> issues to a single array-like class, and thus simplifies implementation and
> simplifies testing.  Instances of this class can be used as objects, as
> stack frames and even full stacks.  A good percentage of a dynamic language
> needs are covered.
>
> So, Rickard Bäckman (also of Oracle) and I defined an API and implemented
> (in HotSpot) an interface called TaggedArray.  Conceptional, TaggedArray is
> a fixed array of no-type slots (64-bit), where each slot can contain either
> a reference or a tagged long value (least significant bit set.)
>  Internally, TaggedArray class's doOop method knows that it should skip
> any 64-bit value with the least significant bit set.  How the language
> developer uses the other 63 bits is up to them.  References are just
> addresses.  On 32 bit machines, the address (or packed address) is stored
> in the high 32-bits (user has no access)  So there is no interference with
> the tag bit.
>
> We supply four implementations of the API.  1) is a naive two parallel
> arrays (one Obje

Re: TaggedArrays (Proposal)

[Charles Oliver Nutter]

A couple quick thoughts from my end.

JRuby does maintain a couple parallel stacks for "out of band" data
that crosses method activations, and I have explored using a large
array as well for closure scopes.

Currently, JRuby has a set of different-sized heap scopes for up to 4
local variables and then things failover into an array version. My
experiment was to allocate one large array ahead of time and make all
scopes be a single one that has an offset, size, and array reference.
It would eliminate the cost of allocating scopes with N fields for N
variables or allocating a scope plus an array.

In practice, it did help allocation a bit, but since I still had to
wrap the array in a structure to track the offsets it was a marginal
improvement at best.

At this point I'm still hoping for escape analysis to save me from too
much allocation of boxed numerics (hard) boxed argument lists (easy,
since they're usually inlinable), and closure scopes (impossible until
JVMs can inline through a closure-receiving method to the closure
itself).

- Charlie

On Mon, Jul 2, 2012 at 6:14 PM, Mark Roos  wrote:
> Hi Jim,  some free from thinking.
>
> My implementation does not have a parallel stack so I am using the java
> stack frame to hold
> temps and pass arguments.   Even so I can see how I would use a TaggedArray.
>  Instead of
> using jvm var slots I would have one slot with a Tagged Array in it to hold
> my method temps.
> When invoking a callsite I would create a TaggedArray to hold the arguments
> and pass that
> to the invoke.  I could cache the frames (assuming a cheap way to null the
> contents of a
> TaggedArray) to reduce object creation.
>
> So the question is then how to handle the callsite code selection.  The
> first GWT would
> have to test if the object is a reference or a tag and route.  Seems like it
> would work.
>
> So other than extra overhead of using the arrays instead of the native stack
> it will
> probably work for me.
>
> I'll have to think some more
>
> regards
> mark
>
>
> ___
> mlvm-dev mailing list
> mlvm-dev@openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Mark Roos]

Hi Jim,  some free from thinking.

My implementation does not have a parallel stack so I am using the java 
stack frame to hold
temps and pass arguments.   Even so I can see how I would use a 
TaggedArray.  Instead of
using jvm var slots I would have one slot with a Tagged Array in it to 
hold my method temps.
When invoking a callsite I would create a TaggedArray to hold the 
arguments and pass that
to the invoke.  I could cache the frames (assuming a cheap way to null the 
contents of a
TaggedArray) to reduce object creation.

So the question is then how to handle the callsite code selection.  The 
first GWT would
have to test if the object is a reference or a tag and route.  Seems like 
it would work.

So other than extra overhead of using the arrays instead of the native 
stack it will
probably work for me.

I'll have to think some more

regards
mark

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Jim Laskey]

Mark,

I'll walk into the trap of offering a solution.  While I'm not familiar with 
your implementation of SmallTalk, the array example might work like this 
(generic/loose java)

// language stack
public static TaggedArray stack = TaggedArrays.allocate(1024*1024);
public static int TOS = -1;

// value conversions
long toValue(int i) { return ((long)i << TaggedArrays.SHIFT) | 
TaggedArrays.TAG; }
int toInt(long v) { return (int)(v >> TaggedArrays.SHIFT) ; }

// stack manipulation
void pushObject(Object o) { stack.setReference(++TOS, o); }
void pushInt(int i) { stack.setValue(++TOS, toValue(i)); }
Object popObject() { stack.getReference(TOS--); }
int popInt() { toInt(stack.getValue(TOS--)); }



// push array on stack
pushObject(new byte[1]);
// push index on stack
pushInt(10);

// get the array element, leaving the result on the stack
invoke("getArray"); 

// work with the result
int b = popInt(); 


The code for getArray might be something like (loose error handling)

int i;
Object a;

try {
i = popInt();
} catch (TaggedArrayException | IndexOutOfBoundsException ex) {
// handle the fact it wasn't a value or underflow
}

try {
a = popObject();
} catch (TaggedArrayException | IndexOutOfBoundsException ex) {
// handle the fact it wasn't an object or underflow
}

...

if (a instanceof byte[]) {
// get the byte array element
long b = ((byte[])a)[i];
// push result on the stack
pushInt(b);
} else ...


Not the best of examples, but
- there are no boxed values involved here
- the JVM compiler would convert setValue/setReference/getValue/getReference to 
simple memory access, so will perform well
- the net result is very simple native code without a lot of runtime handling
- note: you can choose to encrypt "values" suitable for your language needs 

I'll see if we can set up a TaggedArray breakout session at the summit and run 
thru other possibilities.

Cheers,

-- Jim





On 2012-07-02, at 2:23 PM, Mark Roos wrote:

> From Jim 
> 
> It occurred to me on that sleepless Monday night, that the solution for most 
> dynamic languages could be so much simpler.  First, we have to look at what 
> it is we really need.  Ultimately it's about boxing.  We want to avoid 
> allocating memory whenever we need to store a primitive value in an object.  
> Concerning ourselves with passing around tagged values in registers and 
> storing in stack frames is all red herring.  All that is needed is a 
> mechanism for storing tagged values (or compressed values) in a no-type slot 
> of a generic object.  Thinking about it in these terms isolates all issues to 
> a single array-like class, and thus simplifies implementation and simplifies 
> testing.  Instances of this class can be used as objects, as stack frames and 
> even full stacks.  A good percentage of a dynamic language needs are covered. 
> 
> Just having spent the last year implementing Smalltalk on the JVM the issue 
> of boxing ( particularly for integers ) is of interest for me.  While I agree 
> with 
> your statement that allocating memory is the big issue,  I don't really 
> understand your comment about 'when we store a primitive'.  My most visible 
> issue 
> is in a 'for loop' like construct where I generate an index and use it to 
> access a byte array.  In this case I need to create both the index and the 
> byte accessed. 
> For instance scanning a million byte array requires that I create a million 
> indexes and then another million ( assuming no cache ) one for each byte 
> accessed.   
> These are all then discarded.  Its not clear to me how your proposal would 
> help here. 
> 
> As I have thought about the boxing issue ( the Smalltalk I am using as a 
> reference has tagged integers ) I keep thinking that any jvm solution is 
> probably   
> going to have some 'java' or other target driven characteristics that make it 
> hard to use.  In my case I have a java class that all of my objects are 
> instances of. 
> If there were a 'tagged' object type then it would have to be able to 
> substitute as one of my instances,  hold or reference the same information 
> (like method lookups, class, shape etc ), exist on the stack or in a temp,  
> be testable in a GWT  
> 
> Here I agree with you that making this work in the JVM is probably too 
> difficult. 
> 
> So my thoughts are back to how to have a boxed primitive with no allocation 
> overhead unless it is saved or accessed outside of a thread, in other words 
> how to reuse the box.  I can do this for some situations where I can prove 
> the scope but I have yet to figure out a general solutio

Re: TaggedArrays (Proposal)

[Mark Roos]

>From Jim

It occurred to me on that sleepless Monday night, that the solution for 
most dynamic languages could be so much simpler.  First, we have to look 
at what it is we really need.  Ultimately it's about boxing.  We want to 
avoid allocating memory whenever we need to store a primitive value in an 
object.  Concerning ourselves with passing around tagged values in 
registers and storing in stack frames is all red herring.  All that is 
needed is a mechanism for storing tagged values (or compressed values) in 
a no-type slot of a generic object.  Thinking about it in these terms 
isolates all issues to a single array-like class, and thus simplifies 
implementation and simplifies testing.  Instances of this class can be 
used as objects, as stack frames and even full stacks.  A good percentage 
of a dynamic language needs are covered.

Just having spent the last year implementing Smalltalk on the JVM the 
issue of boxing ( particularly for integers ) is of interest for me. While 
I agree with
your statement that allocating memory is the big issue,  I don't really 
understand your comment about 'when we store a primitive'.  My most 
visible issue
is in a 'for loop' like construct where I generate an index and use it to 
access a byte array.  In this case I need to create both the index and the 
byte accessed.
For instance scanning a million byte array requires that I create a 
million indexes and then another million ( assuming no cache ) one for 
each byte accessed. 
These are all then discarded.  Its not clear to me how your proposal would 
help here.

As I have thought about the boxing issue ( the Smalltalk I am using as a 
reference has tagged integers ) I keep thinking that any jvm solution is 
probably 
going to have some 'java' or other target driven characteristics that make 
it hard to use.  In my case I have a java class that all of my objects are 
instances of. 
If there were a 'tagged' object type then it would have to be able to 
substitute as one of my instances,  hold or reference the same information 

(like method lookups, class, shape etc ), exist on the stack or in a temp, 
 be testable in a GWT  

Here I agree with you that making this work in the JVM is probably too 
difficult.

So my thoughts are back to how to have a boxed primitive with no 
allocation overhead unless it is saved or accessed outside of a thread, in 
other words 
how to reuse the box.  I can do this for some situations where I can prove 
the scope but I have yet to figure out a general solution.

So while I can see a use for mixing references and primitives in an array 
it has not shown up in my work as amajor issue.  Perhaps this is due to my 
not 
keeping parallel stacks?

In any case hope to hear more on this at the summit

regards
mark









___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/02/2012 04:11 PM, ravenex wrote:
> Very cool stuff, Jim and Rickard!
> I guess people are going to start missing NaN encoded tagged 
> value/pointers now that there's something real to play with ;-)
>
> @Remi The subclass suggestion sounds a lot like Maxine's Hybrid 
> objects, where named fields and an untyped array is bundled into a 
> single object. Which pretty much emulates what people like to do in 
> C/C++, something nice to have.
>
> > I think that getValue()/setValue() should return the long with the 
> bit set because
> > If i want to execute x + 1, I can convert it to x + 2 at compile 
> time thus avoid the shifts at runtime.
>
> Even without changing the API, this kind of transformation could 
> easily be intrinsified in the JITs, not a big worry. Cheers, Raven 

Yes, it's the Maxine hybrid object and also comes from the fact that 
most of the runtime have a common super type,
like RubyObject in JRuby, GroovyObject in Groovy etc. which is used to 
provide a base class for some
specialized runtime classes.

Rémi

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev

Re: TaggedArrays (Proposal)

[ravenex]

So 32-bit is a pain-point for NaN encoding. I was only playing on x64 and 
didn't notice that. Thanks for the info!
  
 (Sorry for the messed formatting in the previous mail)
   
 - Raven

 

 -- Original --
  From:  "Jim Laskey";
 Date:  Mon, Jul 2, 2012 10:21 PM
 To:  "Da Vinci Machine Project"; 
 
 Subject:  Re: TaggedArrays (Proposal)

 

We had been using NaN encodings in Nashorn but moving away from it because of 
32-bit FP emulation issues.  If you use a sNaN, 32-bit FP emulation converts 
sNaN to qNaN on load and creates a mess of things.



On 2012-07-02, at 11:11 AM, ravenex wrote:

> Very cool stuff, Jim and Rickard! I guess people are going to start missing 
> NaN encoded tagged value/pointers now that there's something real to play 
> with ;-) @Remi The subclass suggestion sounds a lot like Maxine's Hybrid 
> objects, where named fields and an untyped array is bundled into a single 
> object. Which pretty much emulates what people like to do in C/C++, something 
> nice to have. > I think that getValue()/setValue() should return the long 
> with the bit set because > If i want to execute x + 1, I can convert it to x 
> + 2 at compile time thus avoid the shifts at runtime. Even without changing 
> the API, this kind of transformation could easily be intrinsified in the 
> JITs, not a big worry. Cheers, Raven -- Original 
> -- From: "Rémi Fora"; Date: Mon, Jul 2, 2012 09:57 PM To: 
> "mlvm-dev";  Subject: Re: TaggedArrays (Proposal) On 07/02/2012 03:05 PM, Jim 
> Laskey wrote: > During a week in the rarefied air of Stockholm back in May, a 
> > sleepless night got me thinking. The day after that, the thinking > became 
> a reality. I've been sitting on the code since, not sure what > to do next. 
> So..., why not start the month leading up to the JVMLS > with a discussion 
> about dynamic values. > > Every jLanguage developer knows that primitive 
> boxing is the enemy. > Even more so for untyped languages. We need a way to 
> interleave > primitive types with references. > > Tagged values (value types) 
> for dynamic languages have been approached > from a dozen different angles 
> over the history of Java. However, no > one seems to be satisfied with any of 
> the proposals so far. Either > the implementation is too limiting for the 
> language developer or too > complex to implement. > > Most recently, John 
> (Rose) proposed hiding value tagging in the JVM > via the 
> Integer/Long/Float/Double.valueof methods. I saw a few issues > with this 
> proposal. First, the implementation works differently on 32 > bit and 64 bit 
> platforms (only half a solution on each). Secondly, > control of the tag bits 
> is hidden such that it doesn't give a language > implementor any leeway on 
> bit usage. Finally, it will take a long > time for it to get introduced into 
> the JVM. The implementation is > complex, scattered all over the VM and will 
> lead to a significant > multiplier for testing coverage. but it will also 
> help Java perf. > > It occurred to me on that sleepless Monday night, that 
> the solution > for most dynamic languages could be so much simpler. First, we 
> have > to look at what it is we really need. Ultimately it's about boxing. > 
> We want to avoid allocating memory whenever we need to store a > primitive 
> value in an object. Concerning ourselves with passing > around tagged values 
> in registers and storing in stack frames is all > red herring. All that is 
> needed is a mechanism for storing tagged > values (or compressed values) in a 
> no-type slot of a generic object. > Thinking about it in these terms isolates 
> all issues to a single > array-like class, and thus simplifies implementation 
> and simplifies > testing. Instances of this class can be used as objects, as 
> stack > frames and even full stacks. A good percentage of a dynamic language 
> > needs are covered. using it as a stack frames will require a pretty good 
> escape analysis if you want same perf as the native stack or is there a trick 
> somewhere ? But given that there is a trick to avoid boxing for local 
> variables (see my talk at next JVM Summit), having an array like this just 
> for storing fields is enough to pull its weight. > > So, Rickard Bäckman 
> (also of Oracle) and I defined an API and > implemented (in HotSpot) an 
> interface called TaggedArray.  > Conceptional, TaggedArray is a fixed array 
> of no-type slots (64-bit), > where each slot can contain either a reference 
> or a tagged long value > (least significant bit set.) Internally, TaggedArray 
> class

Re: TaggedArrays (Proposal)

[Jim Laskey]

We had been using NaN encodings in Nashorn but moving away from it because of 
32-bit FP emulation issues.  If you use a sNaN, 32-bit FP emulation converts 
sNaN to qNaN on load and creates a mess of things.



On 2012-07-02, at 11:11 AM, ravenex wrote:

> Very cool stuff, Jim and Rickard! I guess people are going to start missing 
> NaN encoded tagged value/pointers now that there's something real to play 
> with ;-) @Remi The subclass suggestion sounds a lot like Maxine's Hybrid 
> objects, where named fields and an untyped array is bundled into a single 
> object. Which pretty much emulates what people like to do in C/C++, something 
> nice to have. > I think that getValue()/setValue() should return the long 
> with the bit set because > If i want to execute x + 1, I can convert it to x 
> + 2 at compile time thus avoid the shifts at runtime. Even without changing 
> the API, this kind of transformation could easily be intrinsified in the 
> JITs, not a big worry. Cheers, Raven -- Original 
> -- From: "Rémi Fora"; Date: Mon, Jul 2, 2012 09:57 PM To: 
> "mlvm-dev";  Subject: Re: TaggedArrays (Proposal) On 07/02/2012 03:05 PM, Jim 
> Laskey wrote: > During a week in the rarefied air of Stockholm back in May, a 
> > sleepless night got me thinking. The day after that, the thinking > became 
> a reality. I've been sitting on the code since, not sure what > to do next. 
> So..., why not start the month leading up to the JVMLS > with a discussion 
> about dynamic values. > > Every jLanguage developer knows that primitive 
> boxing is the enemy. > Even more so for untyped languages. We need a way to 
> interleave > primitive types with references. > > Tagged values (value types) 
> for dynamic languages have been approached > from a dozen different angles 
> over the history of Java. However, no > one seems to be satisfied with any of 
> the proposals so far. Either > the implementation is too limiting for the 
> language developer or too > complex to implement. > > Most recently, John 
> (Rose) proposed hiding value tagging in the JVM > via the 
> Integer/Long/Float/Double.valueof methods. I saw a few issues > with this 
> proposal. First, the implementation works differently on 32 > bit and 64 bit 
> platforms (only half a solution on each). Secondly, > control of the tag bits 
> is hidden such that it doesn't give a language > implementor any leeway on 
> bit usage. Finally, it will take a long > time for it to get introduced into 
> the JVM. The implementation is > complex, scattered all over the VM and will 
> lead to a significant > multiplier for testing coverage. but it will also 
> help Java perf. > > It occurred to me on that sleepless Monday night, that 
> the solution > for most dynamic languages could be so much simpler. First, we 
> have > to look at what it is we really need. Ultimately it's about boxing. > 
> We want to avoid allocating memory whenever we need to store a > primitive 
> value in an object. Concerning ourselves with passing > around tagged values 
> in registers and storing in stack frames is all > red herring. All that is 
> needed is a mechanism for storing tagged > values (or compressed values) in a 
> no-type slot of a generic object. > Thinking about it in these terms isolates 
> all issues to a single > array-like class, and thus simplifies implementation 
> and simplifies > testing. Instances of this class can be used as objects, as 
> stack > frames and even full stacks. A good percentage of a dynamic language 
> > needs are covered. using it as a stack frames will require a pretty good 
> escape analysis if you want same perf as the native stack or is there a trick 
> somewhere ? But given that there is a trick to avoid boxing for local 
> variables (see my talk at next JVM Summit), having an array like this just 
> for storing fields is enough to pull its weight. > > So, Rickard Bäckman 
> (also of Oracle) and I defined an API and > implemented (in HotSpot) an 
> interface called TaggedArray.  > Conceptional, TaggedArray is a fixed array 
> of no-type slots (64-bit), > where each slot can contain either a reference 
> or a tagged long value > (least significant bit set.) Internally, TaggedArray 
> class's doOop > method knows that it should skip any 64-bit value with the 
> least > significant bit set. How the language developer uses the other 63 > 
> bits is up to them. References are just addresses. On 32 bit  > machines, the 
> address (or packed address) is stored in the high > 32-bits (user has no 
> access) So there is no interference with the tag > bit. >

Re: TaggedArrays (Proposal)

[ravenex]

Very cool stuff, Jim and Rickard! I guess people are going to start missing NaN 
encoded tagged value/pointers now that there's something real to play with ;-) 
@Remi The subclass suggestion sounds a lot like Maxine's Hybrid objects, where 
named fields and an untyped array is bundled into a single object. Which pretty 
much emulates what people like to do in C/C++, something nice to have. > I 
think that getValue()/setValue() should return the long with the bit set 
because > If i want to execute x + 1, I can convert it to x + 2 at compile time 
thus avoid the shifts at runtime. Even without changing the API, this kind of 
transformation could easily be intrinsified in the JITs, not a big worry. 
Cheers, Raven -- Original -- From:  "Rémi 
Fora"; Date:  Mon, Jul 2, 2012 09:57 PM To:  "mlvm-dev";  Subject:  Re: 
TaggedArrays (Proposal) On 07/02/2012 03:05 PM, Jim Laskey wrote: > During a 
week in the rarefied air of Stockholm back in May, a  > sleepless night got me 
thinking.  The day after that, the thinking  > became a reality.  I've been 
sitting on the code since, not sure what  > to do next.  So..., why not start 
the month leading up to the JVMLS  > with a discussion about dynamic values. > 
> Every jLanguage developer knows that primitive boxing is the enemy.  >  Even 
more so for untyped languages.  We need a way to interleave  > primitive types 
with references. > > Tagged values (value types) for dynamic languages have 
been approached  > from a dozen different angles over the history of Java.  
However, no  > one seems to be satisfied with any of the proposals so far.  
Either  > the implementation is too limiting for the language developer or too  
> complex to implement. > > Most recently, John (Rose) proposed hiding value 
tagging in the JVM  > via the Integer/Long/Float/Double.valueof methods.  I saw 
a few issues  > with this proposal.  First, the implementation works 
differently on 32  > bit and 64 bit platforms (only half a solution on each).  
Secondly,  > control of the tag bits is hidden such that it doesn't give a 
language  > implementor any leeway on bit usage.  Finally, it will take a long  
> time for it to get introduced into the JVM.  The implementation is  > 
complex, scattered all over the VM and will lead to a significant  > multiplier 
for testing coverage. but it will also help Java perf. > > It occurred to me on 
that sleepless Monday night, that the solution  > for most dynamic languages 
could be so much simpler.  First, we have  > to look at what it is we really 
need.  Ultimately it's about boxing.  >  We want to avoid allocating memory 
whenever we need to store a  > primitive value in an object.  Concerning 
ourselves with passing  > around tagged values in registers and storing in 
stack frames is all  > red herring.  All that is needed is a mechanism for 
storing tagged  > values (or compressed values) in a no-type slot of a generic 
object.  >  Thinking about it in these terms isolates all issues to a single  > 
array-like class, and thus simplifies implementation and simplifies  > testing. 
 Instances of this class can be used as objects, as stack  > frames and even 
full stacks.  A good percentage of a dynamic language  > needs are covered. 
using it as a stack frames will require a pretty good escape analysis if  you 
want same perf as the native stack or is there a trick somewhere ? But given 
that there is a trick to avoid boxing for local variables (see  my talk at next 
JVM Summit), having an array like this just for storing fields is enough to 
pull its  weight. > > So, Rickard Bäckman (also of Oracle) and I defined an API 
and  > implemented (in HotSpot) an interface called TaggedArray.  >  
Conceptional, TaggedArray is a fixed array of no-type slots (64-bit),  > where 
each slot can contain either a reference or a tagged long value  > (least 
significant bit set.)  Internally, TaggedArray class's doOop  > method knows 
that it should skip any 64-bit value with the least  > significant bit set.  
How the language developer uses the other 63  > bits is up to them.  References 
are just addresses.  On 32 bit  > machines, the address (or packed address) is 
stored in the high  > 32-bits (user has no access)  So there is no interference 
with the tag  > bit. > > We supply four implementations of the API.  1) is a 
naive two parallel  > arrays (one Object[], one long[]) implementation for 
platforms not  > supporting TaggedArrays (and JDK 1.7), 2) an optimized version 
of 1)  >  that allocates each array on demand, 3) a JNI implementation  > 
(minimally needed for the interpreter) that uses the native  > implementation 
and 4) the native implementation that is recognized by  > both the C1/C2 
co

Re: TaggedArrays (Proposal)

[Jim Laskey]

On 2012-07-02, at 10:57 AM, Rémi Forax wrote:

> On 07/02/2012 03:05 PM, Jim Laskey wrote:
>> During a week in the rarefied air of Stockholm back in May, a 
>> sleepless night got me thinking.  The day after that, the thinking 
>> became a reality.  I've been sitting on the code since, not sure what 
>> to do next.  So..., why not start the month leading up to the JVMLS 
>> with a discussion about dynamic values.
>> 
>> Every jLanguage developer knows that primitive boxing is the enemy. 
>> Even more so for untyped languages.  We need a way to interleave 
>> primitive types with references.
>> 
>> Tagged values (value types) for dynamic languages have been approached 
>> from a dozen different angles over the history of Java.  However, no 
>> one seems to be satisfied with any of the proposals so far.  Either 
>> the implementation is too limiting for the language developer or too 
>> complex to implement.
>> 
>> Most recently, John (Rose) proposed hiding value tagging in the JVM 
>> via the Integer/Long/Float/Double.valueof methods.  I saw a few issues 
>> with this proposal.  First, the implementation works differently on 32 
>> bit and 64 bit platforms (only half a solution on each).  Secondly, 
>> control of the tag bits is hidden such that it doesn't give a language 
>> implementor any leeway on bit usage.  Finally, it will take a long 
>> time for it to get introduced into the JVM.  The implementation is 
>> complex, scattered all over the VM and will lead to a significant 
>> multiplier for testing coverage.
> 
> but it will also help Java perf.

But of course. :-)


> 
>> 
>> It occurred to me on that sleepless Monday night, that the solution 
>> for most dynamic languages could be so much simpler.  First, we have 
>> to look at what it is we really need.  Ultimately it's about boxing. 
>> We want to avoid allocating memory whenever we need to store a 
>> primitive value in an object.  Concerning ourselves with passing 
>> around tagged values in registers and storing in stack frames is all 
>> red herring.  All that is needed is a mechanism for storing tagged 
>> values (or compressed values) in a no-type slot of a generic object. 
>> Thinking about it in these terms isolates all issues to a single 
>> array-like class, and thus simplifies implementation and simplifies 
>> testing.  Instances of this class can be used as objects, as stack 
>> frames and even full stacks.  A good percentage of a dynamic language 
>> needs are covered.
> 
> using it as a stack frames will require a pretty good escape analysis if 
> you want same perf as the native stack
> or is there a trick somewhere ?
> But given that there is a trick to avoid boxing for local variables (see 
> my talk at next JVM Summit),
> having an array like this just for storing fields is enough to pull its 
> weight.

I was thinking in terms of languages that use a side stack in conjunction with 
the system stack.

> 
> 
>> 
>> So, Rickard Bäckman (also of Oracle) and I defined an API and 
>> implemented (in HotSpot) an interface called TaggedArray. 
>> Conceptional, TaggedArray is a fixed array of no-type slots (64-bit), 
>> where each slot can contain either a reference or a tagged long value 
>> (least significant bit set.)  Internally, TaggedArray class's doOop 
>> method knows that it should skip any 64-bit value with the least 
>> significant bit set.  How the language developer uses the other 63 
>> bits is up to them.  References are just addresses.  On 32 bit 
>> machines, the address (or packed address) is stored in the high 
>> 32-bits (user has no access)  So there is no interference with the tag 
>> bit.
>> 
>> We supply four implementations of the API.  1) is a naive two parallel 
>> arrays (one Object[], one long[]) implementation for platforms not 
>> supporting TaggedArrays (and JDK 1.7), 2) an optimized version of 1) 
>> that allocates each array on demand, 3) a JNI implementation 
>> (minimally needed for the interpreter) that uses the native 
>> implementation and 4) the native implementation that is recognized by 
>> both the C1/C2 compilers (effort only partially completed.)  In 
>> general, the implementation choice is transparent to the user (optimal 
>> choice.)
> 
> Being able to subclass it in order to add fixed field like a metaclass 
> field, i.e a field that
> is always a reference, would be cool too.

Not so easy - the end of the tagged array object is the array area.  Adding 
fields before that area in subclasses complicates determining the base of the 
array.  This would also affect performance (fixed vs variable.)  Reserving a 
slot and doing a getReference(i) on that slot would only cost you the bit test.

> 
> About the API, the two method set should be setValue()/setReference().

Sure.

> I think that getValue()/setValue() should return the long with the bit 
> set because
> If i want to execute x + 1, I can convert it to x + 2 at compile time 
> thus avoid the shifts at runtime.

It does return the bit.

Re: TaggedArrays (Proposal)

[Rémi Forax]

On 07/02/2012 03:05 PM, Jim Laskey wrote:
> During a week in the rarefied air of Stockholm back in May, a 
> sleepless night got me thinking.  The day after that, the thinking 
> became a reality.  I've been sitting on the code since, not sure what 
> to do next.  So..., why not start the month leading up to the JVMLS 
> with a discussion about dynamic values.
>
> Every jLanguage developer knows that primitive boxing is the enemy. 
>  Even more so for untyped languages.  We need a way to interleave 
> primitive types with references.
>
> Tagged values (value types) for dynamic languages have been approached 
> from a dozen different angles over the history of Java.  However, no 
> one seems to be satisfied with any of the proposals so far.  Either 
> the implementation is too limiting for the language developer or too 
> complex to implement.
>
> Most recently, John (Rose) proposed hiding value tagging in the JVM 
> via the Integer/Long/Float/Double.valueof methods.  I saw a few issues 
> with this proposal.  First, the implementation works differently on 32 
> bit and 64 bit platforms (only half a solution on each).  Secondly, 
> control of the tag bits is hidden such that it doesn't give a language 
> implementor any leeway on bit usage.  Finally, it will take a long 
> time for it to get introduced into the JVM.  The implementation is 
> complex, scattered all over the VM and will lead to a significant 
> multiplier for testing coverage.

but it will also help Java perf.

>
> It occurred to me on that sleepless Monday night, that the solution 
> for most dynamic languages could be so much simpler.  First, we have 
> to look at what it is we really need.  Ultimately it's about boxing. 
>  We want to avoid allocating memory whenever we need to store a 
> primitive value in an object.  Concerning ourselves with passing 
> around tagged values in registers and storing in stack frames is all 
> red herring.  All that is needed is a mechanism for storing tagged 
> values (or compressed values) in a no-type slot of a generic object. 
>  Thinking about it in these terms isolates all issues to a single 
> array-like class, and thus simplifies implementation and simplifies 
> testing.  Instances of this class can be used as objects, as stack 
> frames and even full stacks.  A good percentage of a dynamic language 
> needs are covered.

using it as a stack frames will require a pretty good escape analysis if 
you want same perf as the native stack
or is there a trick somewhere ?
But given that there is a trick to avoid boxing for local variables (see 
my talk at next JVM Summit),
having an array like this just for storing fields is enough to pull its 
weight.

>
> So, Rickard Bäckman (also of Oracle) and I defined an API and 
> implemented (in HotSpot) an interface called TaggedArray. 
>  Conceptional, TaggedArray is a fixed array of no-type slots (64-bit), 
> where each slot can contain either a reference or a tagged long value 
> (least significant bit set.)  Internally, TaggedArray class's doOop 
> method knows that it should skip any 64-bit value with the least 
> significant bit set.  How the language developer uses the other 63 
> bits is up to them.  References are just addresses.  On 32 bit 
> machines, the address (or packed address) is stored in the high 
> 32-bits (user has no access)  So there is no interference with the tag 
> bit.
>
> We supply four implementations of the API.  1) is a naive two parallel 
> arrays (one Object[], one long[]) implementation for platforms not 
> supporting TaggedArrays (and JDK 1.7), 2) an optimized version of 1) 
>  that allocates each array on demand, 3) a JNI implementation 
> (minimally needed for the interpreter) that uses the native 
> implementation and 4) the native implementation that is recognized by 
> both the C1/C2 compilers (effort only partially completed.)  In 
> general, the implementation choice is transparent to the user (optimal 
> choice.)

Being able to subclass it in order to add fixed field like a metaclass 
field, i.e a field that
is always a reference, would be cool too.

About the API, the two method set should be setValue()/setReference().
I think that getValue()/setValue() should return the long with the bit 
set because
If i want to execute x + 1, I can convert it to x + 2 at compile time 
thus avoid the shifts at runtime.

>
> I've enclosed a JavaDoc and the roughed out source.  For discussion. 
>  Fire away.
>
> Cheers,
>
> -- Jim

cheers,
Rémi

___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev