[concurrency-interest] Scalable object cache

Peter Firmstone peter.firmstone at zeus.net.au
Wed Feb 29 16:24:21 EST 2012


On Thu, 2012-03-01 at 00:39, ?iktor ?lang wrote:
> Sooo, you're saying that toString, hashCode and equals will only ever
> be called by the Thread that calls get()?

No, these methods could be called by any thread.  It could be used as a
key in a hash map, or in a tree map, if using a Comparator.  The
Comparator implementation tries to avoid calling get on TimedReferrer
unless it has a positive match.  This allows unmatching TimedReferrers
to be removed from a map or set, if they are not being matched.

It's up to the implementor of the referent to make their hashCode(),
equals() and Comparator nonblocking / scalable if they want.  I'm just
trying to allow that to be possible.

All this is invisible to client developers the public API is very small,
but well documented.

Cheers,

Peter.

/* Copyright (c) 2010-2012 Zeus Project Services Pty Ltd.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package au.net.zeus.collection;

import java.util.Comparator;

/**
 * Implements equals and hashCode, subclass ReferenceComparator
implements 
 * Serializable and contains serial data.
 * 
 * @author Peter Firmstone.
 */
abstract class AbstractReferenceComparator<T> implements
Comparator<Referrer<T>> {

    AbstractReferenceComparator() {
    }

    /**
     * This is implemented such that if either Referrer contains a null
     * referent, the comparison is only made using Referrer's, this may
     * have a different natural order, than the comparator provided,
however
     * equals will always return 0, this is important to correctly
remove
     * a Referrer once its referent has been collected.
     * 
     * The following tests give this a good workout:
     * 
     * com/sun/jini/test/impl/joinmanager/ZRegisterStorm.td
     * com/sun/jini/test/spec/renewalmanager/EventTest.td
     * 
     * @param o1
     * @param o2
     * @return 
     */
    public int compare(Referrer<T> o1, Referrer<T> o2) {
        if (o1 == o2) return 0;
        T t1 = null;
        if (o1 instanceof UntouchableReferrer){
            t1 = ((UntouchableReferrer<T>)o1).lookDontTouch();
        } else {
            t1 = o1.get();
        }
        T t2 = null;
        if (o2 instanceof UntouchableReferrer){
            t2 = ((UntouchableReferrer<T>)o2).lookDontTouch();
        } else {
            t2 = o2.get();
        }
        if ( t1 != null && t2 != null){
            int c = get().compare(t1, t2);
            if ( c == 0 ){// If untouchable this is a hit.
                o1.get();
                o2.get();
            }
            return c;
        }
        int hash1 = o1.hashCode();
        int hash2 = o2.hashCode();
        if (hash1 < hash2) return -1;
        if (hash1 > hash2) return 1;
        if (o1.equals(o2)) return 0;
        return -1;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (o instanceof AbstractReferenceComparator) {
            return get().equals(((AbstractReferenceComparator)
o).get());
        }
        return false;
    }

    abstract Comparator<? super T> get();

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 61 * hash + (this.get() != null ? this.get().hashCode() :
0);
        return hash;
    }
    
}


> 
> On Wed, Feb 29, 2012 at 2:37 PM, Peter Firmstone
> <peter.firmstone at zeus.net.au> wrote:
>         I don't have the hardware to test this so I'm hoping someone
>         on the list
>         will know.
>         
>         In the class below, the get() method returns the referent,
>         provided it
>         hasn't been enqueued.
>         
>         Both read and clock are volatile, clock is written to, once
>         every 10
>         seconds (or an interval the developer sets) by a single
>         thread.
>         
>         if (read < clock) read = clock; //Avoid unnecessary volatile
>         write.
>         
>         If many threads are retrieving the referent, the volatile read
>         variable
>         is written at least once in between clock updates, but any
>         further
>         retrievals will only be reads.
>         
>         So in this case the volatile long values are multi read, with
>         occasional
>         writes, does get() look scalable to you?
>         
>         Regards,
>         
>         Peter.
>         
>         /*
>          * Copyright 2012 Zeus Project Services Pty Ltd.
>          *
>          * Licensed under the Apache License, Version 2.0 (the
>         "License");
>          * you may not use this file except in compliance with the
>         License.
>          * You may obtain a copy of the License at
>          *
>          *      http://www.apache.org/licenses/LICENSE-2.0
>          *
>          * Unless required by applicable law or agreed to in writing,
>         software
>          * distributed under the License is distributed on an "AS IS"
>         BASIS,
>          * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
>         express or
>         implied.
>          * See the License for the specific language governing
>         permissions and
>          * limitations under the License.
>          */
>         package au.net.zeus.collection;
>         
>         /**
>          *
>          * @author Peter Firmstone.
>          */
>         class TimedReferrer<T> implements Referrer<T>, TimeBomb {
>         
>            private volatile long clock;
>            private volatile long read;
>            private final TimedRefQueue queue;
>            private volatile T referent;
>            private volatile boolean enqued;
>            private final Object lock;
>            private final int hash;
>         
>            TimedReferrer(T k, TimedRefQueue q){
>                long time = System.nanoTime();
>                clock = time;
>                read = time;
>                referent = k;
>                queue = q;
>                enqued = false;
>                lock = new Object();
>                int hash = 7;
>                hash = 29 * hash + k.hashCode();
>                hash = 29 * hash + k.getClass().hashCode();
>                this.hash = hash;
>            }
>         
>            public T get() {
>                // Doesn't need to be atomic.
>                if (read < clock) read = clock; //Avoid unnecessary
>         volatile
>         write.
>                return referent;
>            }
>         
>            public void clear() {
>                referent = null;
>            }
>         
>            public boolean isEnqueued() {
>                return enqued;
>            }
>         
>            public boolean enqueue() {
>                if (enqued) return false;
>                if (referent == null) return false;
>                if (queue == null) return false;
>                synchronized (lock){ // Sync for atomic write of
>         enqued.
>                    if (enqued) return false;
>                    enqued = queue.offer(this);
>                }
>                return enqued;
>            }
>         
>            @Override
>            public void updateClock(long time){
>                if (read < clock) { // only write volatile if
>         necessary.
>                    enqueue();
>                    clear();
>                } else {
>                    clock = time;
>                }
>            }
>         
>            @Override
>            public boolean equals(Object o) {
>                if (this == o)  return true; // Same reference.
>                if (!(o instanceof Referrer))  return false;
>                Object k1 = get();
>                Object k2 = ((Referrer) o).get();
>                if ( k1 != null && k1.equals(k2)) return true;
>                return ( k1 == null && k2 == null && hashCode() ==
>         o.hashCode()); // Both objects were collected.
>            }
>         
>            @Override
>            public int hashCode() {
>                Object k = get();
>                int hash = 7;
>                if (k != null) {
>                    hash = 29 * hash + k.hashCode();
>                    hash = 29 * hash + k.getClass().hashCode();
>                } else {
>                    hash = this.hash;
>                }
>                return hash;
>            }
>         
>            @Override
>            public String toString(){
>                Object s = get();
>                if (s != null) return s.toString();
>                return super.toString();
>            }
>         
>         }
>         
>         _______________________________________________
>         Concurrency-interest mailing list
>         Concurrency-interest at cs.oswego.edu
>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> 
> 
> 
> 
> -- 
> Viktor Klang
> 
> Akka Tech Lead
> Typesafe - The software stack for applications that scale
> 
> Twitter: @viktorklang



More information about the Concurrency-interest mailing list