headers
Guy Katz | 1 Jun 2004 13:48

need to use collection.sort w. CopyOnWriteArrayList but cant.....

hi;
i am using CopyOnWriteArrayList.
i need ot add sort capability and tried doing it through the
Collections.sort but this fails cause the sort method eventually calls the
set method on the list iterator and this is not supported in the
CopyOnWriteArrayList.
do i have alternatives? i want to keep using the CopyOnWriteArrayList - it
fits my needs (multi thread env, small ammout of modifications a lot of
reads using the list iterator).
thanks in advance.

the exception:
java.lang.UnsupportedOperationException
	at
EDU.oswego.cs.dl.util.concurrent.CopyOnWriteArrayList$COWIterator.set(Unknow
n Source)
	at java.util.Collections.sort(Collections.java:117)
	at components.Test.doit(Test.java:38)

____________________
Guy Katz
Allot Communications
gkatz <at> allot.com
tel: +972 9 7619288
fax: +972 9 7443626
Permalink | Reply | 11 comments |
headers
Doug Lea | 1 Jun 2004 13:42
Favicon

Re: need to use collection.sort w. CopyOnWriteArrayList but cant.....


> i need ot add sort capability and tried doing it through the
> Collections.sort but this fails cause the sort method eventually calls the
> set method on the list iterator and this is not supported in the
> CopyOnWriteArrayList.
> do i have alternatives?

You could use something like (omitting any generic types you might be
using here):

  Object[] array = list.toArray();
  Arrays.sort(array);
  list.clear();
  list.addAll(Arrays.asList(array));

This is not too fast, but at least makes only two full copies
per sort rather than a copy per element change.

-Doug
Permalink | Reply | 10 comments |
headers
Doug Lea | 1 Jun 2004 14:01
Favicon

Re: concurrency-oriented languages on the JVM


> 
> Erlang
> http://www.erlang.org/
> 
> Mozart/Oz
> http://www.mozart-oz.org/
> ...
> haven't been ported to the JVM.  I've heard that
> this is because gaps in the JVM instruction set
> would make such ports dozens of times slower than
> their current native incarnations.
> 
> So, my questions are:
> 1) Is this true with pre 1.5 JVMs?

I don't know. I was hoping someone who knows something about implementing
Erlang or Mozart would answer, but apparently not.

> 2) Does JSR-166 change this?

We would be surprised if there is any kind of
synchronization/threading support that people cannot build efficiently
from what's in JSR166. The only mismatch I know of offhand is that
Erlang uses a process-centric (no shared memory) rather than
thread-centric approach.  Very fine-grained implementations of
Isolates (JSR121) might be nicer for this but don't exist yet.  So
this would need to be enforced by compilers and runtime classes but I
wouldn't think it would add much if any overhead.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Osvaldo Pinali Doederlein | 1 Jun 2004 19:48
Picon

Re: need to use collection.sort w. CopyOnWriteArrayList but cant.....

Doug Lea wrote:
>>i need ot add sort capability and tried doing it through the
>>Collections.sort but this fails cause the sort method eventually calls the
>>set method on the list iterator and this is not supported in the
>>CopyOnWriteArrayList.
>>do i have alternatives?
> 
> You could use something like (omitting any generic types you might be
> using here):
> 
>   Object[] array = list.toArray();
>   Arrays.sort(array);
>   list.clear();
>   list.addAll(Arrays.asList(array));
> 
> This is not too fast, but at least makes only two full copies
> per sort rather than a copy per element change.

I suppose we could have methods like sort() added to the List interface.
This would allow CopyOnWriteArrayList to override the method so this
workaround could be implemented transparently to the user, and also
more efficiently (using less reallocations/copies).  I never understood
why the Collections framework choose this anti-OO design of having most
algorithms as statics of utility classes like Arrays and Collections.
It makes sense only for the methods that operate on primitive types,
e.g. sort(int[]).  Add interfaces like Sortable() { void sort(); } just
in case some non-List collection can sort, and so on.  This suggestion
is too late for Tiger --trivial implementations are possible, but ideal
implementations of some methods, which could be optimized with direct
access to the collections' private members, may need more work and QA.
(Continue reading)

Permalink | Reply | 9 comments |
headers
Joshua Bloch | 1 Jun 2004 21:25
Picon

Re: need to use collection.sort w. CopyOnWriteArrayList but cant.....

Osvaldo,

>
> I suppose we could have methods like sort() added to the List interface.

It violates compatibility to add a method to a widely implemented 
interface such as List, so this is not a possiblity.

>  I never understood
> why the Collections framework choose this anti-OO design of having most
> algorithms as statics of utility classes like Arrays and Collections.

To keep the core interfaces small, general, and learnable.  For the most 
part, we are very happy with the design. 

       Regards,

       Josh
Permalink | Reply | 8 comments |
headers
Osvaldo Pinali Doederlein | 2 Jun 2004 19:25
Picon

Re: need to use collection.sort w. CopyOnWriteArrayList but cant.....

Hi Joshua,

Joshua Bloch wrote:
> Osvaldo,
>> I suppose we could have methods like sort() added to the List interface.
> It violates compatibility to add a method to a widely implemented 
> interface such as List, so this is not a possiblity.

Yes, at this time this would be a major problem(*).  I was thinking in
new interfaces, like Sortable, that could be implemented by concrete
classes like ArrayList but not extended by the interfaces. This would
avoid (most) compatibility issues, even though not a perfect design
either; people would need casts like ((Sortable)myList).sort() to not
hardwire code to the concrete classes...

(*) Except that, if everybody who implements (say) List do it indirectly
by subclassing an abstract class, like AbstractList, that takes care of
all generic methods (sort() would certainly fit here), then there's no
problem even in modifying the interface.  But I realize that Java's
concern for backwards compatibility doesn't allow statements like
"properly written code won't have problems" in critical cases like this.

>>  I never understood
>> why the Collections framework choose this anti-OO design of having most
>> algorithms as statics of utility classes like Arrays and Collections.
> To keep the core interfaces small, general, and learnable.  For the most 
> part, we are very happy with the design.

I see (oops!).  I think I'm more biased by the design of Smalltalk --
collections packed with utility methods -- but of course, in ST, adding
(Continue reading)

Permalink | Reply | 7 comments |
headers
Gregg G. Wonderly | 3 Jun 2004 05:20

Re: [ Osvaldo Pinali Doederlein ] need to use collection.sort w. CopyOnWriteArrayList but cant.....


>If you replicate the sort method as a static of the
>concrete class, and the programmer static-imports these too, and their
>more specific signature guarantees precedence, then "sort(myList)" would
>invoke CopyOnWriteArrayList.sort(CopyOnWriteArrayList).  But it's a huge
>hack, horrible design, and abuse of static imports :-(

I would suggest that perhaps the easist thing for people who need the 
inheritance hierachy, or some other class relationship is to create wrapper 
classes that make the language of programming fit the discriptive language of 
the problem domain.  Then, you can change what you call, or work out different 
details for your special case, and everyone can benefit from having a simpliar 
base API that doesn't try to support a particular problem domain to the 
exclusion of others.

-----
gregg <at> cytetech.com  (Cyte Technologies Inc)
Permalink | Reply | 6 comments |
headers
Osvaldo Pinali Doederlein | 3 Jun 2004 18:15
Picon

Re: [ Osvaldo Pinali Doederlein ] need to use collection.sort w. CopyOnWriteArrayList but cant.....

Gregg G. Wonderly wrote:
>>If you replicate the sort method as a static of the
>>concrete class, and the programmer static-imports these too, and their
>>more specific signature guarantees precedence, then "sort(myList)" would
>>invoke CopyOnWriteArrayList.sort(CopyOnWriteArrayList).  But it's a huge
>>hack, horrible design, and abuse of static imports :-(
> 
> I would suggest that perhaps the easist thing for people who need the 
> inheritance hierachy, or some other class relationship is to create wrapper 
> classes that make the language of programming fit the discriptive language of 
> the problem domain.  Then, you can change what you call, or work out different 
> details for your special case, and everyone can benefit from having a simpliar 
> base API that doesn't try to support a particular problem domain to the 
> exclusion of others.

Unfortunately this won't work, and even if it did, it's a workaround
for a bug.  The current implementation of Collections.sort() breaks
the semantics of the collections API: sort(List) should work with any
implementation of List (I'm not requiring a performant behavior, only
correct behavior). The problem is that the contracts involved in this
problem are multiple and have subtle dependencies:

* List must provide a ListIterator; that's OK.
* ListIterator is free to implement set() or not; that's OK too.
* Collections.sort(List) promises to sort any List, with the single
   (and obvious) condition that "specified list must be modifiable".
   But that's not specific enough, it doesn't state "modifiable through
   iterators", and such constraint wouldn't make any sense.

The conclusion is that Collections.sort() is broken, and nobody should
(Continue reading)

Permalink | Reply | 5 comments |
headers
Joseph Bowbeer | 3 Jun 2004 19:21

Re: [ Osvaldo Pinali Doederlein ] need to use collection.sort w. CopyOnWriteArrayList but cant.....

Osvaldo,

Wouldn't your suggested fix, to use List indexing instead of List iteration,
hurt performance when List is a LinkedList or one of its kin?

----- Original Message ----- 
From: "Osvaldo Pinali Doederlein" <osvaldo <at> visionnaire.com.br>
To: <gregg.wonderly <at> pobox.com>
Cc: "Joshua Bloch" <joshua.bloch <at> sun.com>; "Guy Katz" <gkatz <at> allot.com>;
<concurrency-interest <at> altair.cs.oswego.edu>
Sent: Thursday, June 03, 2004 9:15 AM
Subject: Re: [ Osvaldo Pinali Doederlein ] [concurrency-interest] need to
use collection.sort w. CopyOnWriteArrayList but cant.....

Gregg G. Wonderly wrote:
>>If you replicate the sort method as a static of the
>>concrete class, and the programmer static-imports these too, and their
>>more specific signature guarantees precedence, then "sort(myList)" would
>>invoke CopyOnWriteArrayList.sort(CopyOnWriteArrayList).  But it's a huge
>>hack, horrible design, and abuse of static imports :-(
>
> I would suggest that perhaps the easist thing for people who need the
> inheritance hierachy, or some other class relationship is to create
wrapper
> classes that make the language of programming fit the discriptive language
of
> the problem domain.  Then, you can change what you call, or work out
different
> details for your special case, and everyone can benefit from having a
simpliar
(Continue reading)

Permalink | Reply | 1 comment |
headers
Osvaldo Pinali Doederlein | 3 Jun 2004 21:33
Picon

Re: [ Osvaldo Pinali Doederlein ] need to use collection.sort w. CopyOnWriteArrayList but cant.....

Joseph Bowbeer wrote:
> Osvaldo,
> Wouldn't your suggested fix, to use List indexing instead of List iteration,
> hurt performance when List is a LinkedList or one of its kin?

You are correct -- I forgot this additional reason to use ListIterator!
Then, the correct fix is only more complex, e.g., have special cases to
put sorted elements back in the list.  The best solution I can think is
something like this:

if (list instanceof RandomAccess) {
   // Must work, even though RandomAccess doesn't guarantee that
   // the list is modifiable, because sort() requires this
   loop to put elements with set();
} else try {
   loop to put elements with ListIterator;
}
catch (UnsupportedOperationException) {
   loop to put elements with clear() & add()
}

This provides maximum performance for the concrete classes that have
efficient set(index,element), those marked by RandomAccess (includes
CopyOnWriteArrayList).  Unfortunately there isn't a similar marker or
specification requiring modifiable iterators, so we must rely on an
exception for other cases.  Attempt first the current method with
iterators; this will work, but just in case it fails, try once again
with clear()/add().  The last method is not fail-safe either because
sort() doesn't require that the list supports these also-optional
operations, but I guess we won't find many lists that are mutable,
(Continue reading)

Permalink | Reply | 0 comments |

Gmane