Change character in string

[Lew]

Oh really?  (Or are you just splitting hairs now, about eclipse -
not Vector - being the one writing/throwing/issuing warnings?)

Really! They only claimed that your expression that lacked a type
argument would issue that warning, not that it was a difference
between 'ArrayList' and 'Vector' /per se/. You generalized from a
specific comment, then attributed the generalization to RGB instead of
yourself.

My original two contestants *both* had that omission. (I just checked
back.) And in that case, eclipse really should have warned about both.

Well, of course. But the point wasn't about 'ArrayList' vs. 'Vector',
it was about inclusion or omission of the type argument.

PS: Is RGB plural?

Well, of course not. "They/their/them" has been used as a gender-
neutral singular pronoun in English since before Shakespeare's time.
Get with the program.

 

[Andreas Leitgeb]

I think Sun missed a trick here: they could have made the post-generics
declaration of Vector look like:
public class Vector implements List<Object>

If they had done that, they'd have made an indirect but clear obsoletion
statement against Vector, that I wouldn't have disputed then.
Yet, they didn't.

That would ease the pain of legacy code which uses raw Vectors, as it
would need the addition of lots of type bindings to compile without
warnings,

In the second line of this paragraph, didn't you mean "wouldn't need" ?

If talk was about pure legacy code, then -source 1.4 should get rid of all
those unchecked-warnings, and such code also doesn't contain variables with
types like List<Foo>. But even if *such* code is compiled with -source
1.5 and spews out gobs of [unchecked] warnings, it's still no way less safe
as the same code was back when compiled with a 1.4 javac.

If, however, you're talking about new sources having to use Vector for
old interfaces, then not changing Vector at all would surely have been
the easiest signal by Sun to declare it unmisunderstandably as obsolete.
Yet, they didn't.

 

[Andreas Leitgeb]

Please go back the thread and read that original post by RGB.

Well, of course. But the point wasn't about 'ArrayList' vs. 'Vector',
it was about inclusion or omission of the type argument.

Where did you gather that from?
Will it boil down to Shakespeare again?

PS: Is RGB plural?

[explanation of plural pronouns used for gender-neutral singular]

Thanks. In my roughly 25 years of learning english and about 15 years
of actively reading/posting to newsgroups and other places in the net
I haven't yet come across this. I'll probably stick with "his/her"
and "he/she", myself, but next time I read it from you, I'll now know
what you mean. PS: Next time you may address me as "thou".

 

[Lew]

Please go back the thread and read that original post by RGB.


Where did you gather that from?
Will it boil down to Shakespeare again?

Please, you go back [to] the thread and read that original post by
RGB.

Here is the exact quote from RGB, without any re-arrangement of
attributions other than removal of a quote of something I wrote that
didn't figure in:

Andreas Leitgeb wrote: ....

One thing you can do with the former but not the latter is compile
without warnings. The latter gives me this warning in Eclipse:
"Type safety: The expression of type Vector needs unchecked conversion
to conform to List<Foo>"

The statement that RGB made is exactly true for the exact, specific
example that you posted. There is absolutely nothing in RGB's post
that states that this is generally true for all uses of 'ArrayList'
vs. 'Vector', only for the specific example that you posted. In that
example, one 'new' expression lacked a type parameter.

 

[Lew]

PS: Is RGB plural?

[explanation of plural pronouns used for gender-neutral singular]

Thanks. In my roughly 25 years of learning english and about 15 years
of actively reading/posting to newsgroups and other places in the net
I haven't yet come across this.  I'll probably stick with "his/her"
and "he/she", myself, but next time I read it from you, I'll now know
what you mean. PS: Next time you may address me as "thou".

Take note of
<http://en.wikipedia.org/wiki/Singular_they>

You may note the citations including from Shakespeare's /Romeo and
Juliet/ and earlier.

 

[Lew]

I completely withdraw what I said.

I was wrong.

 

[Andreas Leitgeb]

I was wrong.

Based on how long it took you to spot it, it's quite likely that
RGB fell for the same misread, when he/she tried it in eclipse.
This case closed. (unless RGB speaks up, that is)

The contest is still open, with (now corrected):
  List<Foo> lf= Collections.synchronizedList(new ArrayList<Foo>());
  List<Foo> lf= new Vector<Foo>();
Scores so far:
half a point to the former for being in line with other
Collection implementations' synchronized wrappings.
quarter of a point to the latter for being shorter to write.
half a point to the latter for being "slightly faster" according to Sun.

I.e.: No strong points on either side.

What's the point of this?
My goal is to convince you to not take every mention of Vector as a
trigger to post how the hell bad it is. It isn't always. It's that
only if context is clearly free of synchronisation requirements, or
some poster also uses Vector for variable or (even worse) parameter
types.

Fair?

 

[Lew]

The contest is still open, with (now corrected):
   List<Foo> lf= Collections.synchronizedList(new ArrayList<Foo>());
   List<Foo> lf= new Vector<Foo>();
Scores so far:
  half a point to the former for being in line with other
      Collection implementations' synchronized wrappings.

Being consistent with collections is worth at least a full point.

  quarter of a point to the latter for being shorter to write.

No points for being shorter to write. That's just laziness and not
useful.

  half a point to the latter for being "slightly faster" according to Sun.

I don't believe it, and even if true I wouldn't give that more than a
hundredth of a point. Where is this documented, and under what
conditions were the speed tests made?

I.e.: No strong points on either side.

One point to 'synchronizedList()' for being able to wrap
implementations other than 'ArrayList'. That way if one needs to
refactor there's less engineering effort to it.

One point to 'synchronizedList()' for not pulling in 'Enumaration',
about which even Sun says:

NOTE: The functionality of this interface is duplicated by the Iterator interface.
In addition, Iterator adds an optional remove operation, and has shorter method
names. New implementations should consider using Iterator in preference to
Enumeration.

What's the point of this?
My goal is to convince you to not take every mention of Vector as a
trigger to post how the hell bad it is. It isn't always. It's that
only if context is clearly free of synchronisation requirements, or
some poster also uses Vector for variable or (even worse) parameter
types.

Fair?

The real problem is that people usually use 'Vector' where
synchronization is not needed, i.e., in lieu of an unsynchronized
'ArrayList'. Getting in the habit of never using 'Vector' prevents
that, a whole other point in favor of eschewing 'Vector'.

I think the burden is on 'Vector' to justify itself, and that it
should not be used any more. Even were it a raw tie, which I don't
believe it is, then 'ArrayList' should win absent a clear, strong
advantage to 'Vector'.

However, I see at least a four-point advantage to using a non-Vector
'List', so I'm going to continue to advocate for that.

Given that 'ArrayList' is a leaner, more compliant implementation of
'List' than is 'Vector', that it has the flexibility of being
unsynchronized or synchronized, that it can easily be replaced by
other 'List' implementations in either scenario, and that 'Vector'
offers no advantages over other 'List' implementations, and that using
'Vector' is socially equivalent to using 'thou' in modern American
Standard English and is just as archaic and strange, I say eschew
Vector where legacy code doesn't require it.

 

[Bent C Dalager]

Based on how long it took you to spot it, it's quite likely that
RGB fell for the same misread, when he/she tried it in eclipse.
This case closed. (unless RGB speaks up, that is)

The contest is still open, with (now corrected):
  List<Foo> lf= Collections.synchronizedList(new ArrayList<Foo>());
  List<Foo> lf= new Vector<Foo>();
Scores so far:
half a point to the former for being in line with other
Collection implementations' synchronized wrappings.
quarter of a point to the latter for being shorter to write.
half a point to the latter for being "slightly faster" according to Sun.

I am going to take this as an invitation to vent my pet peeve with
Vector again (even if I don't really understand what the contest is
all about). My apologies if it has been mentioned before in this
thread - I'm something of a latecomer to the discussion.

In the context of the above quoted text, the following program works
fine with a synchronized ArrayList but deadlocks with Vector. This has
been the case forever and I just checked it now with JDK6_12 on
Ubuntu: still a deadlock.

Switch the comment around in createList() to deadlock or not deadlock.

As far as I can recall, the difference between the two is that Vector
synchronizes equals() while the synchronizedList() wrapper
doesn't. It's been a while though so don't take that as gospel.

Cheers,
Bent D


import java.util.*;

public class Test
{
public static void main(String args[])
{
List<Integer> a = createList();
List<Integer> b = createList();
populate(a);
populate(b);
Thread t1 = new Thread(new MyRunnable(a, b)); // spot the difference
Thread t2 = new Thread(new MyRunnable(b, a)); // spot the difference
t1.start();
t2.start();
}

private static List<Integer> createList()
{
//return Collections.synchronizedList(new ArrayList<Integer>());
return new Vector<Integer>();
}

private static void populate(List<Integer> l)
{
for (int ii = 0; ii < 1000; ++ii) l.add(ii);
}

static class MyRunnable implements Runnable
{
List<Integer> list1, list2;
public MyRunnable(List<Integer> l1, List<Integer> l2)
{
list1 = l1;
list2 = l2;
}
public void run()
{
for (int ii = 0; ii < 1000; ++ii) list1.equals(list2);
}
}
}

 

[Andreas Leitgeb]

I am going to take this as an invitation to vent my pet peeve with
Vector again (even if I don't really understand what the contest is
all about). My apologies if it has been mentioned before in this
thread - I'm something of a latecomer to the discussion.
[demonstration of deadlock-weakness of Vector w.r.t. .equals()]

No, it hasn't and I'm very grateful to this contribution.

Current score:
minus 100 points against Vector.

I lost.

 

[Andreas Leitgeb]

Bent convinced me. I surrender.

 

[Andreas Leitgeb]

Actually, it was you who rearranged his post.

Sorry, something must have eaten away the "his/".
Perhaps the idog ... :-}

 

[Lew]

I am going to take this as an invitation to vent my pet peeve with
Vector again (even if I don't really understand what the contest is
all about). My apologies if it has been mentioned before in this
thread - I'm something of a latecomer to the discussion.
[demonstration of deadlock-weakness of Vector w.r.t. .equals()]

No, it hasn't and I'm very grateful to this contribution.

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);}
}

That's good, because if 'equals()' weren't synchronized it would be broken.

I am grateful to Bent also, because I never knew about this flaw with
'Vector'. It is good to have more than just an aesthetic argument for my choice.

Now I have quite the mental exercise ahead of me to figure out why
'Vector#equals()' deadlocks and 'SynchronizedList#equals()' doesn't.

Here's the source from 'Vector':

public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
public synchronized boolean equals(Object o) {
return super.equals(o);
}
...
}

How interesting that Sun, who usually espouses
"opening-brace-on-the-same-line", gives it a separate line at the class level
here.

 

[Bent C Dalager]

Now I have quite the mental exercise ahead of me to figure out why
'Vector#equals()' deadlocks and 'SynchronizedList#equals()' doesn't.

The listIterator that ArrayList uses to access the other lists's
objects isn't synchronized. It is provided by the backing list and
doesn't get wrapped by SynchronizedList.

Vector's calls to retrieve the elements from the other Vector are
synchronized since it calls Vector.get() to do so, via a ListIterator.

Therefore, when a has been locked by one thread and it is trying to
access b's elements but b has been locked by the other thread, there
is a deadlock for Vector but not for a SynchronizedList.

Incidentally, the following code shows that you can't really rely upon
synchronizing the data structures. The code will cause concurrent
modification exceptions for Vector and SynchronizedList. Well, and
plain ArrayList.

What we need is strict two-phase locking. Or something else that
actually works.

Cheers,
Bent D


import java.util.*;

public class Test
{
public static void main(String args[])
{
List<Integer> a = createList();
List<Integer> b = createList();
populate(a);
populate(b);
Thread t1 = new Thread(new Equalizer(a, b));
// call new Mutator(a) instead and it should work
Thread t2 = new Thread(new Mutater(b));
t1.start();
t2.start();
}

private static List<Integer> createList()
{
//
//return Collections.synchronizedList(new ArrayList<Integer>());
//return new ArrayList<Integer>();
return new Vector<Integer>();
}

private static void populate(List<Integer> l)
{
for (int ii = 0; ii < 1000; ++ii) l.add(ii);
}

static class Equalizer implements Runnable
{
List<Integer> list1, list2;
public Equalizer(List<Integer> l1, List<Integer> l2)
{
list1 = l1;
list2 = l2;
}
public void run()
{
for (int ii = 0; ii < 1000; ++ii) list1.equals(list2);
}
}

static class Mutater implements Runnable
{
List<Integer> list;
public Mutater(List<Integer> l)
{
list = l;
}
public void run()
{
for (int ii = 0; ii < 1000; ++ii)
{
list.clear();
populate(list);
}
}
}
}

 

[Lew]

The listIterator that ArrayList uses to access the other lists's
objects isn't synchronized. It is provided by the backing list and
doesn't get wrapped by SynchronizedList.

OK, but neither is the 'Vector#listIterator()' method, which is inherited from
'AbstractList' and therefore not synchronized.

The 'synchronizedList()' wrapped version of the 'ArrayList' goes through

synchronized(mutex) {return list.equals(o);}

so, although the iterator itself isn't synchronized, it is called from a
synchronized code block, as is 'Vector''s.

I'm still not spotting the difference, exactly.

 

[Lew]

The get() is synchronized.

But when I look at the source for 'Vector' I don't see 'get()' invoked in the
'equals()' implementation:

public synchronized boolean equals(Object o) {
return super.equals(o);
}

which calls:

public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;

ListIterator<E> e1 = listIterator();
ListIterator e2 = ((List) o).listIterator();
while(e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}

If I understand Bent's comments correctly:

Vector: for any given instance, the equals() method itself is
synchronized, and the getter to retrieve each element of the _other_

What getter? This is what I'm missing.

list being compared to is synchronized. There are two Vector
instances. Calling equals() on each, one thread per, locks both. This
lock won't be released until the equals() method has completed. The
equals() method won't complete until it has successfully retrieved each
element from the _other_ list. But it can't, because the other list got
locked when the other thread called equals().

I thought of that, but I didn't see how that differed from two synchronized
lists calling 'equals()', one in each thread. I don't see any use of a getter.

 

[Andreas Leitgeb]

I assume you've confirmed it actually deadlocks as he says, so obviously
each thread is trying to take two different locks _somewhere_.

I did, and it did.

 

[Andreas Leitgeb]

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

Vector otoh, already has it's first fork when .equals() is invoked
on it, so it's too late for grabbing the napkin now. To repair
Vector, it would have to be made unsynchronized itself, and then
each method would have to aquire Collections.synchronizedCollection's
mutex object, and sync on that, first. Maybe that's the reason, why
Sun say that Vector is slightly faster: because it doesn't use the
central lock - and that has a hidden price tag that may really hurt.

*: Most likely it *is* obtained somewhere. But till someone digs it
up I just say "may".

 

[Andreas Leitgeb]

This "mutex" is a *non*-static field, so something was wrong
with my previous speculations. No central napkin on the table.

But then, why does it work?

 

[Bent C Dalager]

But when I look at the source for 'Vector' I don't see 'get()' invoked in the
'equals()' implementation:

public synchronized boolean equals(Object o) {
return super.equals(o);
}

which calls:

public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;

ListIterator<E> e1 = listIterator();
ListIterator e2 = ((List) o).listIterator();
while(e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();

The listIterator is AbstractList$Itr which has this next():

public E next() {
checkForComodification();
try {
E next = get(cursor); // HERE
lastRet = cursor++;
return next;
} catch(IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}

The get() being called at HERE is that of Vector (it's abstract in
AbstracList), which is synchronized.

The same listIterator is used by SynchronizedArrayList but the get()
/it/ calls is that of the base unscynchronized ArrayList.

Either way of doing it is wrong: in one case you end up deadlocking
and in the other you're not synchronizing on all the data that you
need. And neither of these flaws is obvious to the user, or even
documented in any way that I know of.

I have always found this rather serious because, of all the methods
you can call on a List you'd expect equals() to be among the safer
ones. All sorts of algorithms rely on being able to use it all the
time - but perhaps that's my GUI bias shining through.

Cheers,
Bent D