Mike Duigou | 3 Jan 21:16 2011
Picon

Re: Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]


On Dec 24 2010, at 17:32 , Ulf Zibis wrote:

> Trying to correct white space ...
> 
> Am 23.12.2010 23:59, schrieb Paul Benedict:
>> Ulf, a previous email by Remi said only to invoke size() if the collection is a Set.
> Thanks I missed that.
> My guess was, that size() should be always faster than instantiating an iterator for the final for-loop,
and then seeing, that there is no element.

An earlier webrev had an isEmpty() check in the "c1 is a Set" half of the branch. This optimization would pay
off in some cases but cost a small amount in others. Since I don't have any strong sense of whether including
it would be of actual benefit or harm I opted to take it out in later revisions.

Mike

Mike Duigou | 3 Jan 23:15 2011
Picon

Re: Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]


On Dec 23 2010, at 13:24 , Ulf Zibis wrote:

> Am 23.12.2010 20:46, schrieb Mike Duigou:
>> I have updated the webrev with the javadoc changes (identical to below) and Ulf's suggested code changes:
>> 
>> http://cr.openjdk.java.net/~mduigou/6728865.3/webrev/
> 
> Thanks, I could convince you mostly.
> But, IMO, the inner comments are too expatiated ("less than O(N/2)" is used 3 times).

I've tried to favour clarity and simplicity of language over brevity for comments and mostly intended the
comments for casual readers trying to understanding the operation of the method rather than future
maintainers. This applies to the source code as well-- I've somewhat ignored "Optimizations" which make
the source code smaller but no faster in execution. 

> Aren't the explanation comments from my last example clear enough and more fluently readable?
> You use "ceiling(n/2)". Didn't you mean "ceiling O(N/2)" for consistence?

The example refers to the total number of actual comparisons not it's O complexity so "ceiling(N/2)" is correct.

> "//than mere Collection's,iterate on c2."
> 2 spaces are missing
> 

One space added.

> "// One (or both) collections is/are empty. Nothing will match."
> Shorter:
> "// At least one collection is empty. Nothing will match."
(Continue reading)

Ulf Zibis | 4 Jan 02:02 2011
Picon
Picon

Re: Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]

Am 03.01.2011 21:16, schrieb Mike Duigou:
> On Dec 24 2010, at 17:32 , Ulf Zibis wrote:
>
>> Am 23.12.2010 23:59, schrieb Paul Benedict:
>>> Ulf, a previous email by Remi said only to invoke size() if the collection is a Set.
>> Thanks I missed that.
>> My guess was, that size() should be always faster than instantiating an iterator for the final for-loop,
and then seeing, that there is no element.
> An earlier webrev had an isEmpty() check in the "c1 is a Set" half of the branch. This optimization would pay
off in some cases but cost a small amount in others. Since I don't have any strong sense of whether including
it would be of actual benefit or harm I opted to take it out in later revisions.
>
For the same reason you could set the empty-check at 1st place. This would result in the most simple 
(and fast) code (see my before post).
- in all implementations, I have seen, "isEmpty()" is equivalent to "size() == 0"
- "cost a small amount in others" applies rarely; the only implementation, I have seen, where 
"Set.size() can be expensive", is ConcurrentSkipListSet (are there others?).
- swapping c1 , c2 only happens in the very rare applying cases.

Anyway, isn't size() anyhow cheaper than superfluously looping contains() ? E.g. Given Set c1 with 
100 elements and Set c2 with 0 elements. Then we iterate and compare over 100 elements needlessly.

-Ulf

Ulf Zibis | 4 Jan 02:02 2011
Picon
Picon

Re: Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]

Am 03.01.2011 23:15, schrieb Mike Duigou:
> I've tried to favour clarity and simplicity of language over brevity for comments and mostly intended the
comments for casual readers trying to understanding the operation of the method rather than future maintainers.
OK, we are different. For me, redundancy usually reduces clarity. I would need more time to read and 
understand the comments, especially as a non-english native.

>   This applies to the source code as well-- I've somewhat ignored "Optimizations" which make the source
code smaller but no faster in execution.
Well, I think a single swap (single CPU instruction) is little faster, than copying to local 
variables, and in Hotspot optimization case reduces register pressure. Anyway, your code reorders 
the arguments in more cases than necessary.
That's why I have constructed the decision maps to clearly see the common paths.

>
> The example refers to the total number of actual comparisons not it's O complexity so "ceiling(N/2)" is correct.
I was in error, as I finally noted (overseen ?).
But I still think, (N+1)/2 is more correct than ceiling(N/2).
N=2: match can be in 1st or 2nd position, so 1.5 comparisions in avarage!
N=3: match can be in 1st, 2nd or 3rd position, so 2 comparisions in avarage!
N=4: match can be in 1st to 4th position, so 2.5 comparisions in avarage!

>> "//than mere Collection's,iterate on c2."
>> 2 spaces are missing
> One space added.
The 2nd one is after the comma. ;-)

>
>> Javadoc:
>> - the term ' <at> throws NullPointerException' is duplicated, don't know if that would work ?
> This is intentionally copying the style of Collection methods where two separate  <at> throws
(Continue reading)

Mohan Radhakrishnan | 5 Jan 14:52 2011
Picon

Data structure concurrency question

Hi,

     Ascii representation of UML multiplicity :

 

Logger Name 1---------* Logger 1----------1 Levels

 

 

I have a requirement to associate one logger name with multiple Loggers each of which is in turn associated with a single level. What is a concurrent data structure recommendation for this ?

 

      It is basically a map of maps. The accesses are not going to be highly concurrent but the log messages should not be interleaved.

 

 

Thanks,

Mohan

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Mohan Radhakrishnan | 6 Jan 08:25 2011
Picon

Re: Race condition on singleton

Hi,
     What about this ? Is this a similar singleton ? Since the map is static we haven't anticipated any problem.

Should the method be synchronized ? There could be a problem with a partially created object ? Logically
even if threads get interleaved the map will anyway have the right object.

We run this code with about 10-15 threads with no problem.

	private static Test test = null;

	private static Hashtable<String, Test> logMap = new Hashtable<String, Test >();

	public static Test getInstance( String logName ) {

		if (null == logMap.get(logName)) {

			test = new Test (logName);

			logMap.put(logName, test);

		} else {

			test = logMap.get(logName);

		}

		return test;

	 }

Thanks,
Mohan
-----Original Message-----
From: concurrency-interest-bounces <at> cs.oswego.edu
[mailto:concurrency-interest-bounces <at> cs.oswego.edu] On Behalf Of Marco Villalobos
Sent: Monday, December 13, 2010 10:58 AM
To: concurrency-interest
Subject: Re: [concurrency-interest] Race condition on singleton

By simply reading his code, which I assume is an abridged version of
the original, I didn't notice anything that would cause an NPE.

However, if his original code uses static variables, then order of
those declarations will matter.

For example:

public class WillNPE {

    private final static WillNPE instance = new WillNPE();
    private final static Set<Integer> set = new HashSet<Integer>();

    public static WillNPE getInstance() {
        return instance;
    }

    public WillNPE() {
        set.add(1);
    }

    public static void main(String args[]) {
        WillNPE local = WillNPE.getInstance();
    }
}

On Sun, Dec 12, 2010 at 9:10 PM, Justin T. Sampson <justin <at> krasama.com> wrote:
> I'm surprised with all the replies that no one commented on the lack of
> synchronization on accessing the contents of the map. That can easily cause
> NPEs from within map.put(k, v), or almost any other arbitrary behavior for
> that matter.
> Cheers,
> Justin
>
> On Thu, Dec 9, 2010 at 4:44 AM, Guy Korland <gkorland <at> gmail.com> wrote:
>>
>> Hi,
>> We found a very strange pattern that seems like contradicting the Java
>> Memory Model.
>> It seems like a class that is maintained as singleton doesn't have its
>> constructor fully initialized!
>> See the code example bellow.
>> public class MyClass{
>>   private static final MyClass = new MyClass();
>>
>>   private final HashMap map;
>>   private MyClass(){
>>       map = new HashMap();
>>   }
>>   public void put(Object k, Object v){
>>      map.put(k,v);
>>   }
>>   static public getMyClass(){
>>     return myClass;
>>   }
>> }
>>
>> And when we invoke the following:
>> MyClass.getMyClass().put("a","b");
>> We get a NullPointerException on the "map.put(k,v);", meaning the
>> map==null !?!?
>> Any ideas?
>> Thanks,
>> Guy Korland
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest <at> cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Mark Thornton | 6 Jan 09:26 2011
Picon

Re: Race condition on singleton

On 06/01/2011 07:25, Mohan Radhakrishnan wrote:
> Hi,
>       What about this ? Is this a similar singleton ? Since the map is static we haven't anticipated any problem.
>
> Should the method be synchronized ? There could be a problem with a partially created object ? Logically
even if threads get interleaved the map will anyway have the right object.
>
> We run this code with about 10-15 threads with no problem.

You got lucky, that code is badly broken. The simplest fix would be to 
synchronize the getInstance method.

Mark Thornton

>
> 	private static Test test = null;
>
> 	private static Hashtable<String, Test>  logMap = new Hashtable<String, Test>();
>
> 	public static Test getInstance( String logName ) {
>
> 		if (null == logMap.get(logName)) {
>
> 			test = new Test (logName);
>
> 			logMap.put(logName, test);
>
>
> 		} else {
>
> 			test = logMap.get(logName);
>
> 		}
>
> 		return test;
>
> 	 }
>
> Thanks,
> Mohan
> -----Original Message-----
> From: concurrency-interest-bounces <at> cs.oswego.edu
[mailto:concurrency-interest-bounces <at> cs.oswego.edu] On Behalf Of Marco Villalobos
> Sent: Monday, December 13, 2010 10:58 AM
> To: concurrency-interest
> Subject: Re: [concurrency-interest] Race condition on singleton
>
> By simply reading his code, which I assume is an abridged version of
> the original, I didn't notice anything that would cause an NPE.
>
> However, if his original code uses static variables, then order of
> those declarations will matter.
>
> For example:
>
> public class WillNPE {
>
>      private final static WillNPE instance = new WillNPE();
>      private final static Set<Integer>  set = new HashSet<Integer>();
>
>      public static WillNPE getInstance() {
>          return instance;
>      }
>
>      public WillNPE() {
>          set.add(1);
>      }
>
>      public static void main(String args[]) {
>          WillNPE local = WillNPE.getInstance();
>      }
> }
>
>
> On Sun, Dec 12, 2010 at 9:10 PM, Justin T. Sampson<justin <at> krasama.com>  wrote:
>> I'm surprised with all the replies that no one commented on the lack of
>> synchronization on accessing the contents of the map. That can easily cause
>> NPEs from within map.put(k, v), or almost any other arbitrary behavior for
>> that matter.
>> Cheers,
>> Justin
>>
>> On Thu, Dec 9, 2010 at 4:44 AM, Guy Korland<gkorland <at> gmail.com>  wrote:
>>> Hi,
>>> We found a very strange pattern that seems like contradicting the Java
>>> Memory Model.
>>> It seems like a class that is maintained as singleton doesn't have its
>>> constructor fully initialized!
>>> See the code example bellow.
>>> public class MyClass{
>>>    private static final MyClass = new MyClass();
>>>
>>>    private final HashMap map;
>>>    private MyClass(){
>>>        map = new HashMap();
>>>    }
>>>    public void put(Object k, Object v){
>>>       map.put(k,v);
>>>    }
>>>    static public getMyClass(){
>>>      return myClass;
>>>    }
>>> }
>>>
>>> And when we invoke the following:
>>> MyClass.getMyClass().put("a","b");
>>> We get a NullPointerException on the "map.put(k,v);", meaning the
>>> map==null !?!?
>>> Any ideas?
>>> Thanks,
>>> Guy Korland
>>>
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> Concurrency-interest <at> cs.oswego.edu
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest <at> cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Sébastien Bocq | 7 Jan 16:01 2011
Picon

Concurrent sequential access to a mutable field without the volatile modifier

Hello,

I made a simple test (see below) to verify my assumption that a variable mutated sequentially by multiple threads must be marked as volatile to have mutations visible across these threads. How comes my test succeeds even though I omitted the volatile keyword?

Thanks,
Sébastien

import java.util.concurrent.*;

public class VolatileTest {

    static class CountTask implements Runnable {
        public int count = 0;             // volatile omitted
        public void run() { count++; }
        <at> Override
        public String toString() {return String.valueOf(count);}
    };

    static class SimpleExecutor implements Runnable {

       LinkedBlockingQueue<Runnable> queue = new LinkedBlockingQueue<Runnable>();
      
       public void submit(Runnable runnable) { queue.offer(runnable); }

       volatile Thread thread = null;

       public void run() {

          thread = Thread.currentThread();
         
          while (thread != null) {

            try {
                Runnable task = queue.take();
                task.run();
            } catch (InterruptedException e) {}
          }
       }
   
       public void shutdown() {
         Thread t = thread;
         thread = null;
         t.interrupt();
       }
      
       public SimpleExecutor() {
           new Thread(this).start();
       }
    }
   
    static class LoopTask implements Runnable {
        CountDownLatch latch;
        int count;
        Runnable task;
        SimpleExecutor[] executors;

        /** Repeat a task sequentially using different executors
         *
         * <at> param executors the executors
         * <at> param count     the number of iterations
         * <at> param latch     latch decremented after the last iteration
         * <at> param task      the task invoked repeatedly
         */
        public LoopTask(SimpleExecutor[] executors, int count, CountDownLatch latch, Runnable task) {
            this.executors = executors;
            this.latch = latch;
            this.count = count;
            this.task  = task;
        }

        public void run() {
            if (count == 0)
                latch.countDown();
            else {
                task.run();
                executors[count % executors.length].submit(new LoopTask(executors, count - 1, latch, task));
            }
        }
    }

     public static void main(String[] args) throws Exception {
       int loops = 1000000;
       int nbExecs = 10;
      
       CountDownLatch latch = new CountDownLatch(1);
       SimpleExecutor[] executors = new SimpleExecutor[nbExecs];
      
       for (int i = 0; i < executors.length; i++)
         executors[i] = new SimpleExecutor();
      
       CountTask task = new CountTask();
      
       try {
           new LoopTask(executors, loops, latch, task).run();

           latch.await();

           System.out.println(task);
           assert(task.count == loops); 
       } finally {
           for (int i = 0; i < executors.length; i++)
               executors[i].shutdown();
       }
     }
}

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Mark Thornton | 7 Jan 16:17 2011
Picon

Re: Concurrent sequential access to a mutable field without the volatile modifier

On 07/01/2011 15:01, Sébastien Bocq wrote:
> Hello,
>
> I made a simple test (see below) to verify my assumption that a 
> variable mutated sequentially by multiple threads must be marked as 
> volatile to have mutations visible across these threads. How comes my 
> test succeeds even though I omitted the volatile keyword?

The absence of volatile merely means the mutations may not be visible, 
it doesn't guarantee that they won't be visible. So in some 
implementations your mutations may be visible while in others they may 
not. Adding volatile gives you a guarantee of visibility.

Mark
Sébastien Bocq | 7 Jan 16:32 2011
Picon

Re: Concurrent sequential access to a mutable field without the volatile modifier

2011/1/7 Mark Thornton <mthornton <at> optrak.co.uk>

On 07/01/2011 15:01, Sébastien Bocq wrote:
Hello,

I made a simple test (see below) to verify my assumption that a variable mutated sequentially by multiple threads must be marked as volatile to have mutations visible across these threads. How comes my test succeeds even though I omitted the volatile keyword?

The absence of volatile merely means the mutations may not be visible, it doesn't guarantee that they won't be visible. So in some implementations your mutations may be visible while in others they may not. Adding volatile gives you a guarantee of visibility.


Ok, I needed to be sure.

Thanks for the swift answer,
Sébastien
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Gmane