Re: Vector (was Re: Change character in string)
On Sat, 14 Mar 2009, Andreas Leitgeb wrote:
Lew <noone@lewscanon.com> wrote:
Andreas Leitgeb wrote:
Current score:
minus 100 points against Vector.
I lost.
Here is the source of the underlying 'SynchronizedList' nested class's
'equals()' method:
public boolean equals(Object o) {
synchronized(mutex) {return list.equals(o);}
}
Now I have quite the mental exercise ahead of me to figure out why
'Vector#equals()' deadlocks and 'SynchronizedList#equals()' doesn't.
In the task of comparing two synchronized Lists there is a
"meta"-critical path: that, where the own lock and a foreign lock
may(*) be aquired (i.e. the infamous dining philosophers problem).
If for any pairs of locks (namely each List's one) there is a master
lock, which must be aquired first, then the problem is avoided.
For the philosophers that would mean, that before even taking their
first fork, they'd first have to grab the one napkin in the center of
the table (ugh :-)
Actually, there's another way: if there's a total order on the forks, then
the philosophers just have to agree to always pick them up in that order.
Let's say they're numbered, with fork 1 being the highest priority,
followed by 2, etc. If you've got fork m, you can only ever be waiting for
fork n, where n > m; whoever holds fork n can only ever be waiting for
fork p, where p > n, and since that means p > m, they can't be waiting for
the fork you're holding, and so there's no possibility of deadlocking with
them. You can extend that analysis to show that you also can't make
deadlocks with larger numbers of people.
In the philosophers' case, there's an even simpler solution that doesn't
involve a total order: you colour the forks red or black, and lay them
around the table in alternating colours (and if there are an odd number of
diners, you set an extra place, or give one of them chopsticks). You then
instruct the philosophers to pick up their black fork first, then their
red fork. You can only ever be waiting for a red fork, while holding a
black fork, so you know that nobody who holds the fork you're after can
ever be waiting for a fork you're holding. Deadlock cannot ensue.
The former case is applicable to the list equals problem, although the
latter is not. The solution looks like:
// assume non-identity, non-nullity and listness are known by this point
public boolean equals(List<?> that) {
List<?> first;
List<?> second;
if (order(this, that)) {
first = this;
second = that;
}
else {
first = that;
second = this;
}
synchronized (first) {
synchronized (second) {
return list.equals(that);
}
}
}
static boolean order(List<?> a, List<?> b) {
// this is the only tricky bit
// but as long as it's consistent, it doesn't matter how you do it
}
To implement order, i'd just compare the identity hashes:
static boolean order(List<?> a, List<?> b) {
if (a == b) throw new IllegalArgumentException();
int ida = System.identityHashCode(a);
int idb = System.identityHashCode(b);
if (ida == idb) throw new RuntimeException("whoops");
return ida > idb;
}
The one weakness there is that it fails for different objects which have
the same identity hash. You could mitigate this by adding some
tie-breaking rules (eg go on the lexicographical order of their class
names), but there's no easy way to guarantee an answer.
You could break ties arbitrarily, and then record the decision in a global
map, so that if you saw the same pair again, you could give a consistent
decision. That's pretty evil, though.
tom
--
Everyone in the world is doing something without me.