Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Why "lock" functionality is introduced for all the objects?

Reply
Thread Tools

Why "lock" functionality is introduced for all the objects?

 
 
Tom Anderson
Guest
Posts: n/a
 
      07-01-2011
On Thu, 30 Jun 2011, KitKat wrote:

> On 30/06/2011 6:04 PM, Tom Anderson wrote:
>> What happened then was that a very clever chap called David Bacon, who
>> worked for IBM, invented a thing called a thin lock:
>>
>> http://www.research.ibm.com/people/d...ml#Bacon98Thin
>>
>> Which was subsequently improved by another clever chap called Tamiya
>> Onodera into a thing called a tasuki lock, which you don't hear so much
>> about.

>
> Are you sure that last one was a "chap"? "Tamiya" sounds rather feminine to
> me.


Perhaps - and a quick google reveals that it is a girl's name in Hebrew.
However, in Japanese, i believe it's a family name, and that Tamiya
Onodera is Dr Tamiya's name written in the normal Japanese order, putting
his family name first. Although i could be wrong.

>> The details are described quite clearly in the papers, but the upshot
>> is that an object is created with neither a lock nor a slot for a lock
>> pointer (and so only a two-word header), and the lock is allocated only
>> when needed, and then wired in. Some fancy footwork means that the
>> object doesn't need to grow a pointer when this happens; the header
>> remains two words, at the expense of some slight awkwardness elsewhere.

>
> Such as?


The object's identity hash is shuffled between the object and its lock
according to whether it has an expanded lock or not.

> I can think of only one possibility that could be even close to
> efficient: maintain an IdentityHashMap<Object,Lock> somewhere under the
> hood.


That might be memory-efficient, but it would not be at all time-efficient,
as it would require a map lookup to lock an object. Resizing the hash
would be an interesting exercise, too. Actually, i think early JVMs (1.1
era, IIRC, perhaps even 1.0) used something a bit like this; they didn't
use the identity hash, but back then the garbage collector was non-moving,
so they could use addresses as keys, and there was a global lock table
somewhere. I don't know how it handled resizing. Badly, i expect.

tom

--
The fundamental cause of trouble in the world today is that the stupid
are cocksure while the intelligent are full of doubt. -- Bertrand Russell
 
Reply With Quote
 
 
 
 
KitKat
Guest
Posts: n/a
 
      07-01-2011
On 01/07/2011 4:40 PM, Tom Anderson wrote:
> On Thu, 30 Jun 2011, KitKat wrote:
>
>> Are you sure that last one was a "chap"? "Tamiya" sounds rather
>> feminine to me.

>
> Perhaps - and a quick google reveals that it is a girl's name in Hebrew.
> However, in Japanese, i believe it's a family name, and that Tamiya
> Onodera is Dr Tamiya's name written in the normal Japanese order,
> putting his family name first. Although i could be wrong.


???

Regardless of which, "Onodera" also sounds feminine.

> The object's identity hash is shuffled between the object and its lock
> according to whether it has an expanded lock or not.


That would work, if that's what the second word in the object header
normally is. Assuming it's the heap address at time of creation, and
objects are aligned on word boundaries, the two least order bits of the
identity hash are going to be zero, so you can use those bits for
something else and mask them off to get the hash.

On the other hand, that suggests a way to make object headers of only
*one* word.

Consider: how likely are we to have four billion vtables in a running
32-bit JVM? Let alone Long.MAX_VALUE - Long.MIN_VALUE + 1 in a 64-bit one?

Reserve a low chunk of the address space (and call it part of permgen?)
for vtables and your vtable pointers get quite short. The vtable pointer
plus a few bits of the object's initial address would still make a
pretty decent identity hash for collections with heterogeneous keys;
homogeneous keys, in my experience, are usually value objects with
overridden hashCode such as Strings and you can make the
initial-address-bits (and the thin lock bit) the low order bits. Shift
right one bit to lose the lock bit and have the hash; shift right n bits
for some fairly small n to get the vtable pointer. Vtable lookup is a
tiny bit slower due to a test of the lock bit plus one added shift
instruction on each lookup, but the critical performance points tend to
get JITted into direct calls or branch-predictable is-it-a-Foo?
jump-or-normal-vtable-lookup choices. And the vast majority of
production Java code is I/O bound anyway.

Well, except when the object needs a fat lock. Then the whole word
becomes a pointer to a structure that points to the vtable and contains
the lock and identity hash. Now vtable lookup has an added indirection.
But the bottleneck with such objects will usually be contention for the
lock itself, not CPU cycles.

> That might be memory-efficient, but it would not be at all
> time-efficient, as it would require a map lookup to lock an object.


Map lookups are O(1) and a low level implementation in C built into the
JVM would boil down to masking and shifting the hash and then a pointer
addition and dereference, only needed when you wanted to lock or unlock
an object -- and again, the time spent on this will be dwarfed by the
time spent in contention for the lock anyway, fairly often. Branch
prediction and pipelining might help in the case of high-CPU areas that
lock an object with low contention, in that some of the work might
proceed in parallel with lock acquisition in the absence of contention
(though, only as far as work that can be done in cache or registers,
since the lock must be held prior to any memory reads or writes in the
guarded object, and on initial acquisition failure that work may have to
be repeated later on acquisitoon).
 
Reply With Quote
 
 
 
 
Joshua Maurice
Guest
Posts: n/a
 
      07-02-2011
On Jun 28, 10:12*pm,
supercalifragilisticexpialadiamaticonormalizeringe limatisticantations
<supercalifragilisticexpialadiamaticonormalizering elimatisticantati...@averylongandannoyingdomainnam e.com>
wrote:
> On 28/06/2011 4:43 PM, BGB wrote:
>
> > yeah...

>
> > they made every object lockable but not every object cloneable, where
> > one would think cloning would be generally a higher priority.

>
> If they'd been smarter about managing mutability to begin with (e.g.
> fields immutable by default, objects normally immutable) cloning would
> not be a priority at all.
>
> Sure, the boxed primitives and Strings are immutable, and that's about
> it. We've got mutable stuff out the wazoo, most of which probably
> shouldn't be -- java.util.Date, anyone? Not to mention java.awt.Point
> and friends. All those conundrums about whether Square should be a
> subclass of Rectangle, or Circle of Ellipse, go away if they aren't
> mutable. Then they clearly are subclasses. Mutable collections and
> arrays also make type reasoning more complicated and don't allow casting
> a List<Sub> to a List<Super> as then you might add a non-Sub Super to
> the list. If the list wasn't mutable there'd be no problem casting a
> List<Sub> to a List<Super>.
>
> I could go on...but I won't.


If you want a functional language, go use a functional language and
stop complaining that Java is not a functional language.
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      07-02-2011
On 6/28/2011 10:12 PM,
supercalifragilisticexpialadiamaticonormalizeringe limatisticantations wrote:
> If the list wasn't mutable there'd be no problem casting a
> List<Sub> to a List<Super>.


And then I'd complain because my program would be spending more time
copying the values between immutable queues than actually doing work. As
long as the language has the potential for mutable collections (which
most people want for performance reasons), you have the potential for
generics casting issues.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
supercalifragilisticexpialadiamaticonormalizeringelimatisticantations
Guest
Posts: n/a
 
      07-02-2011
On 01/07/2011 9:28 PM, Joshua Maurice wrote:
> On Jun 28, 10:12 pm,
> supercalifragilisticexpialadiamaticonormalizeringe limatisticantations
> <supercalifragilisticexpialadiamaticonormalizering elimatisticantati...@averylongandannoyingdomainnam e.com>
>> Sure, the boxed primitives and Strings are immutable, and that's about
>> it. We've got mutable stuff out the wazoo, most of which probably
>> shouldn't be -- java.util.Date, anyone? Not to mention java.awt.Point
>> and friends.

>
> If you want a functional language, go use a functional language and
> stop complaining that Java is not a functional language.


Contrary to popular belief, immutability is not solely useful in a
functional language. In fact, OO languages benefit greatly if their
"value types" (things you're likely to want to use as hash keys and to
generally represent state) are immutable.
 
Reply With Quote
 
supercalifragilisticexpialadiamaticonormalizeringelimatisticantations
Guest
Posts: n/a
 
      07-02-2011
On 01/07/2011 10:05 PM, Joshua Cranmer wrote:
> On 6/28/2011 10:12 PM,
> supercalifragilisticexpialadiamaticonormalizeringe limatisticantations
> wrote:
>> If the list wasn't mutable there'd be no problem casting a
>> List<Sub> to a List<Super>.

>
> And then I'd complain because my program would be spending more time
> copying the values between immutable queues than actually doing work. As
> long as the language has the potential for mutable collections (which
> most people want for performance reasons), you have the potential for
> generics casting issues.


Lists are, in my experience, typically constructed, then consumed; only
infrequently is a mutable one maintained with recurring episodes of
reading and writing over time. The common case could have been optimized
with better support than the various Collections.unmodifiableFoo()
methods provide. For example, if you could tag a list as not modifiable
the compiler can both disallow writing through it and allow casting from
UnmodifiableList<Sub> to UnmodifiableList<Super>. We kinda have that now
in that we can cast List<Sub> to List<? extends Super> and then the
compiler will indeed not let us add to it, but <? extends Super> is both
awkward and not equal to Super. A lot of methods might be written to
demand a List<Super> even if they won't modify the list, and will thus
work with a List<? extends Super>. More generally it complicates
generics. The fact of the matter is that <? extends X> is like of like
"unmodifiable, and also <X>", at least for collections; a more clear way
of (separately) expressing "unmodifiable" would have been nice.

So, basically, what I'm saying is that we should have had some notion of
constness in Java.
 
Reply With Quote
 
BGB
Guest
Posts: n/a
 
      07-04-2011
On 7/1/2011 7:05 PM, Joshua Cranmer wrote:
> On 6/28/2011 10:12 PM,
> supercalifragilisticexpialadiamaticonormalizeringe limatisticantations
> wrote:
>> If the list wasn't mutable there'd be no problem casting a
>> List<Sub> to a List<Super>.

>
> And then I'd complain because my program would be spending more time
> copying the values between immutable queues than actually doing work. As
> long as the language has the potential for mutable collections (which
> most people want for performance reasons), you have the potential for
> generics casting issues.
>


well, and probably putting more pressure on the garbage collector.

a great downside of using an FP-like style with a GC and a language/VM
that generally lacks the concept of user-defined value-types is that it
increases the amount of garbage produced (thus increasing the number of
GC cycles).

a language with 'struct' need not have this issue, as then they can use
it for implementing such value types.

but, I have seen cases where people have abused struct (mostly in C#),
generally using references-to-struct for things which would probably
have been better done with a heap-allocated class instance.


in my own personal language, it may be possible to create structs using
a constructor and using 'final' on fields to create an immutable struct.


or such...
 
Reply With Quote
 
supercalifragilisticexpialadiamaticonormalizeringelimatisticantations
Guest
Posts: n/a
 
      07-05-2011
On 04/07/2011 12:39 PM, BGB wrote:
> On 7/1/2011 7:05 PM, Joshua Cranmer wrote:
>> On 6/28/2011 10:12 PM,
>> supercalifragilisticexpialadiamaticonormalizeringe limatisticantations
>> wrote:
>>> If the list wasn't mutable there'd be no problem casting a
>>> List<Sub> to a List<Super>.

>>
>> And then I'd complain because my program would be spending more time
>> copying the values between immutable queues than actually doing work. As
>> long as the language has the potential for mutable collections (which
>> most people want for performance reasons), you have the potential for
>> generics casting issues.

>
> well, and probably putting more pressure on the garbage collector.


Typical immutable usage-patterns create more pressure in one single
predominant way: by producing more very-short-lived temporaries holding
intermediate values. Assuming the JIT doesn't optimize those out of the
heap altogether, they will die in edenspace which generally makes them
extremely cheap (as the gc cost to clean up edenspace is proportional
only to the number of survivors, not the number of dead objects). Where
they can be a bit less cheap is that heap space requirements to avoid
more major collections may be higher.

> a great downside of using an FP-like style with a GC and a language/VM
> that generally lacks the concept of user-defined value-types is that it
> increases the amount of garbage produced (thus increasing the number of
> GC cycles).


Don't forget that the JIT can optimize local temporary objects that
escape analysis shows never leave the method scope (or have their
identity hash code needed) into being defacto "value type" objects
instead of heap objects.

 
Reply With Quote
 
BGB
Guest
Posts: n/a
 
      07-05-2011
On 7/1/2011 3:08 PM, KitKat wrote:
> On 01/07/2011 4:40 PM, Tom Anderson wrote:
>> On Thu, 30 Jun 2011, KitKat wrote:
>>
>>> Are you sure that last one was a "chap"? "Tamiya" sounds rather
>>> feminine to me.

>>
>> Perhaps - and a quick google reveals that it is a girl's name in Hebrew.
>> However, in Japanese, i believe it's a family name, and that Tamiya
>> Onodera is Dr Tamiya's name written in the normal Japanese order,
>> putting his family name first. Although i could be wrong.

>
> ???
>
> Regardless of which, "Onodera" also sounds feminine.
>


grr... the name is not latin-based, not everything that ends in 'a' is
female.

not like it is some guy with a name like "Chibichibi Hitomi" or
something, which would be a bit suspect.


"anata wa des-ka?"
"chibi-chibi hitomi wa deeesuuu!" (meanwhile doing an imbalanced stance).

as other people look with a solidly "WTF?" expression upon hearing this.

another person stands up, puts his hands to his face, and a background
voice exclaims "shaaku!" (IOW: "shock!").


>> The object's identity hash is shuffled between the object and its lock
>> according to whether it has an expanded lock or not.

>
> That would work, if that's what the second word in the object header
> normally is. Assuming it's the heap address at time of creation, and
> objects are aligned on word boundaries, the two least order bits of the
> identity hash are going to be zero, so you can use those bits for
> something else and mask them off to get the hash.
>
> On the other hand, that suggests a way to make object headers of only
> *one* word.
>
> Consider: how likely are we to have four billion vtables in a running
> 32-bit JVM? Let alone Long.MAX_VALUE - Long.MIN_VALUE + 1 in a 64-bit one?
>


well, that is the cost of full pointers probably.
everything is addressable.

storing type-IDs as an id-number can also work, then one fetches the
vtable/... via an array index. a downside though is that this would have
a potential performance impact, as additional operations are now needed
to access the vtable.


or, one can reserve a chunk of memory (wherever it is) and subtract out
the address. then one can re-add the relative address to the base address.

say, a 64-bit base address known to the VM, and only a 32-bit relative
address is stored in the object (possibly shifted right 3 bits with the
top-3 used for the lock).

in x86-64, this can be done mostly with a single instruction, say:
lea rcx, [rbx+rax*8]

or, say, one calls a method (rdx=object, rbx=magic base pointer):
mov eax, [rdx] ;fetch vtable word from object
mov ecx, [rbx+rax*8+72] ;access vtable entry at offset 72
lea r8, [rbx+rcx] ;add method address to base
call r8 ;call method


> Reserve a low chunk of the address space (and call it part of permgen?)
> for vtables and your vtable pointers get quite short. The vtable pointer
> plus a few bits of the object's initial address would still make a
> pretty decent identity hash for collections with heterogeneous keys;
> homogeneous keys, in my experience, are usually value objects with
> overridden hashCode such as Strings and you can make the
> initial-address-bits (and the thin lock bit) the low order bits. Shift
> right one bit to lose the lock bit and have the hash; shift right n bits
> for some fairly small n to get the vtable pointer. Vtable lookup is a
> tiny bit slower due to a test of the lock bit plus one added shift
> instruction on each lookup, but the critical performance points tend to
> get JITted into direct calls or branch-predictable is-it-a-Foo?
> jump-or-normal-vtable-lookup choices. And the vast majority of
> production Java code is I/O bound anyway.
>
> Well, except when the object needs a fat lock. Then the whole word
> becomes a pointer to a structure that points to the vtable and contains
> the lock and identity hash. Now vtable lookup has an added indirection.
> But the bottleneck with such objects will usually be contention for the
> lock itself, not CPU cycles.
>



>> That might be memory-efficient, but it would not be at all
>> time-efficient, as it would require a map lookup to lock an object.

>
> Map lookups are O(1) and a low level implementation in C built into the
> JVM would boil down to masking and shifting the hash and then a pointer
> addition and dereference, only needed when you wanted to lock or unlock
> an object -- and again, the time spent on this will be dwarfed by the
> time spent in contention for the lock anyway, fairly often. Branch
> prediction and pipelining might help in the case of high-CPU areas that
> lock an object with low contention, in that some of the work might
> proceed in parallel with lock acquisition in the absence of contention
> (though, only as far as work that can be done in cache or registers,
> since the lock must be held prior to any memory reads or writes in the
> guarded object, and on initial acquisition failure that work may have to
> be repeated later on acquisitoon).


yep.

a table need not be all that expensive.

in my VM at least, interface method dispatch is itself done via the use
of a hash table (as well as using a table for any object locking).


actually, a variant of the relative-address scheme is used as well on
x86-64, but in this case more due to the x86-64 ISA generally using
32-bit offsets for everything (calls/jumps/... are limited to 32-bits
unless one wants to use GPRs to hold the temporary addresses, meaning it
is much more efficient to try to have most of ones' JITted code/data be
within a +-2GB window).

in this case, calls outside of this window are generally handled via
trampolines within the window.

in effect, this window forms an "executable heap". granted, currently
the whole region is read/write/execute, where I guess on some systems
SELinux may make a problem for this, but I have yet to address this
(seems to work fine on my systems... mostly tested with Fedora x86-64).

(note: I also target Win64 and Win32 as well, with Win64 being done in
roughly the same way, and all this being N/A to Win32).

sadly, the region currently uses manual-MM. the GC can scan the region
for references, but code/data/bss sections are not automatically
reclaimed, as I found out after initial implementation that this would
create serious implementation problems, and so instead opted with using
different executable memory for GCed code, as well as it having to
follow special rules, ...


current setup:
4GB RWX (combined code/data/bss, allocation starts from the middle and
follows an even/odd "spiral" pattern).

theoretically, one would have to double-map the code-heap in this case, say:
2GB RX (code/rodata), 2GB RW (data/bss), 2GB RW (alias for code-heap)
or:
2GB RX (code/rodata), 2GB RW (data/bss, alias to first region)


presumably, the standard JVM does something similar internally?...


in the hypothetical object situation, this region would also be used for
object vtables/... as well (but, as given before, would additionally
require a region-base pointer, that or use relative addresses, which
have their own complexities, and require "movsx rax, dword [...]"
instructions).


or such...
 
Reply With Quote
 
KitKat
Guest
Posts: n/a
 
      07-05-2011
On 05/07/2011 3:15 PM, BGB wrote:
> On 7/1/2011 3:08 PM, KitKat wrote:
>> Regardless of which, "Onodera" also sounds feminine.

>
> grr... the name is not latin-based,


What does Latin have to do with Java, BGB?

> not everything that ends in 'a' is female.


No, just the names that do.

> not like it is some guy with a name like "Chibichibi Hitomi" or
> something, which would be a bit suspect.


Yes, "i" instead of "y" endings are also usually feminine.

> "anata wa des-ka?"
> "chibi-chibi hitomi wa deeesuuu!" (meanwhile doing an imbalanced stance).


What does your public drunkenness have to do with Java, BGB?

> as other people look with a solidly "WTF?" expression upon hearing this.
>
> another person stands up, puts his hands to his face, and a background
> voice exclaims "shaaku!" (IOW: "shock!").


What does your hallucination have to do with Java, BGB?

> storing type-IDs as an id-number can also work, then one fetches the
> vtable/... via an array index. a downside though is that this would have
> a potential performance impact, as additional operations are now needed
> to access the vtable.


Even the other suggestion involved a shift and mask, as well as a prior
bit-test and branch in case of a thick lock in which event the vtable
was one more indirection away, though branch prediction would take care
of the latter handily for every method invocation not called inside of a
critical section.

> or, one can reserve a chunk of memory (wherever it is) and subtract out
> the address. then one can re-add the relative address to the base address.


Doubles heap size, if you're suggesting what it sounds like you're
suggesting.

> say, a 64-bit base address known to the VM, and only a 32-bit relative
> address is stored in the object (possibly shifted right 3 bits with the
> top-3 used for the lock).


Limits the heap to what the limit would be in a 32-bit VM.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
findcontrol("PlaceHolderPrice") why why why why why why why why why why why Mr. SweatyFinger ASP .Net 2 12-02-2006 03:46 PM
Server 2003 SP1 introduced "enableBestFitResponseEncoding" setting =?Utf-8?B?VG9yc3RlbiBTdHVybQ==?= ASP .Net 0 08-31-2005 12:57 PM
Change in config on 1700 when firewall is introduced - HELP! Kapamarou Cisco 0 12-29-2003 05:40 PM
weird white space being introduced into <td> neverstill ASP .Net 1 12-05-2003 06:12 PM
New Exam Question Types and Testlet Exam Format to Be Introduced Petter BÝrkeeiet MCSE 1 09-18-2003 02:02 PM



Advertisments