| /* |
| * Copyright (C) 2011 The Guava Authors |
| * |
| * 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 com.google.common.collect; |
| |
| import static com.google.common.base.Preconditions.checkArgument; |
| import static com.google.common.collect.CollectPreconditions.checkNonnegative; |
| |
| import com.google.caliper.BeforeExperiment; |
| import com.google.caliper.Benchmark; |
| import com.google.caliper.Param; |
| import com.google.common.annotations.VisibleForTesting; |
| import com.google.common.primitives.Ints; |
| import com.google.common.util.concurrent.ThreadFactoryBuilder; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Random; |
| import java.util.Set; |
| import java.util.concurrent.Callable; |
| import java.util.concurrent.ConcurrentHashMap; |
| import java.util.concurrent.ConcurrentMap; |
| import java.util.concurrent.ExecutionException; |
| import java.util.concurrent.ExecutorService; |
| import java.util.concurrent.Executors; |
| import java.util.concurrent.Future; |
| import org.checkerframework.checker.nullness.qual.Nullable; |
| |
| /** |
| * Benchmarks for {@link ConcurrentHashMultiset}. |
| * |
| * @author mike nonemacher |
| */ |
| public class ConcurrentHashMultisetBenchmark { |
| @Param({"1", "2", "4", "8"}) |
| int threads; |
| |
| @Param({"3", "30", "300"}) |
| int size; |
| |
| @Param MultisetSupplier implSupplier; |
| |
| private Multiset<Integer> multiset; |
| private ImmutableList<Integer> keys; |
| private ExecutorService threadPool; |
| |
| @BeforeExperiment |
| void setUp() throws Exception { |
| multiset = implSupplier.get(); |
| ImmutableList.Builder<Integer> builder = ImmutableList.builder(); |
| for (int i = 0; i < size; i++) { |
| builder.add(i); |
| } |
| keys = builder.build(); |
| threadPool = |
| Executors.newFixedThreadPool(threads, new ThreadFactoryBuilder().setDaemon(true).build()); |
| } |
| |
| @Benchmark |
| long add(final int reps) throws ExecutionException, InterruptedException { |
| return doMultithreadedLoop( |
| new Callable<Long>() { |
| @Override |
| public Long call() { |
| return runAddSingleThread(reps); |
| } |
| }); |
| } |
| |
| @Benchmark |
| long addRemove(final int reps) throws ExecutionException, InterruptedException { |
| return doMultithreadedLoop( |
| new Callable<Long>() { |
| @Override |
| public Long call() { |
| return runAddRemoveSingleThread(reps); |
| } |
| }); |
| } |
| |
| private long doMultithreadedLoop(Callable<Long> task) |
| throws InterruptedException, ExecutionException { |
| |
| List<Future<Long>> futures = Lists.newArrayListWithCapacity(threads); |
| for (int i = 0; i < threads; i++) { |
| futures.add(threadPool.submit(task)); |
| } |
| long total = 0; |
| for (Future<Long> future : futures) { |
| total += future.get(); |
| } |
| return total; |
| } |
| |
| private long runAddSingleThread(int reps) { |
| Random random = new Random(); |
| int nKeys = keys.size(); |
| long blah = 0; |
| for (int i = 0; i < reps; i++) { |
| Integer key = keys.get(random.nextInt(nKeys)); |
| int delta = random.nextInt(5); |
| blah += delta; |
| multiset.add(key, delta); |
| } |
| return blah; |
| } |
| |
| private long runAddRemoveSingleThread(int reps) { |
| Random random = new Random(); |
| int nKeys = keys.size(); |
| long blah = 0; |
| for (int i = 0; i < reps; i++) { |
| Integer key = keys.get(random.nextInt(nKeys)); |
| // This range is [-5, 4] - slight negative bias so we often hit zero, which brings the |
| // auto-removal of zeroes into play. |
| int delta = random.nextInt(10) - 5; |
| blah += delta; |
| if (delta >= 0) { |
| multiset.add(key, delta); |
| } else { |
| multiset.remove(key, -delta); |
| } |
| } |
| return blah; |
| } |
| |
| private enum MultisetSupplier { |
| CONCURRENT_HASH_MULTISET() { |
| @Override |
| Multiset<Integer> get() { |
| return ConcurrentHashMultiset.create(); |
| } |
| }, |
| BOXED_ATOMIC_REPLACE() { |
| @Override |
| Multiset<Integer> get() { |
| return OldConcurrentHashMultiset.create(); |
| } |
| }, |
| SYNCHRONIZED_MULTISET() { |
| @Override |
| Multiset<Integer> get() { |
| return Synchronized.multiset(HashMultiset.<Integer>create(), null); |
| } |
| }, |
| ; |
| |
| abstract Multiset<Integer> get(); |
| } |
| |
| /** |
| * Duplication of the old version of ConcurrentHashMultiset (with some unused stuff removed, like |
| * serialization code) which used a map with boxed integers for the values. |
| */ |
| private static final class OldConcurrentHashMultiset<E> extends AbstractMultiset<E> { |
| /** The number of occurrences of each element. */ |
| private final transient ConcurrentMap<E, Integer> countMap; |
| |
| /** |
| * Creates a new, empty {@code OldConcurrentHashMultiset} using the default initial capacity, |
| * load factor, and concurrency settings. |
| */ |
| public static <E> OldConcurrentHashMultiset<E> create() { |
| return new OldConcurrentHashMultiset<E>(new ConcurrentHashMap<E, Integer>()); |
| } |
| |
| @VisibleForTesting |
| OldConcurrentHashMultiset(ConcurrentMap<E, Integer> countMap) { |
| checkArgument(countMap.isEmpty()); |
| this.countMap = countMap; |
| } |
| |
| // Query Operations |
| |
| /** |
| * Returns the number of occurrences of {@code element} in this multiset. |
| * |
| * @param element the element to look for |
| * @return the nonnegative number of occurrences of the element |
| */ |
| @Override |
| public int count(@Nullable Object element) { |
| try { |
| return unbox(countMap.get(element)); |
| } catch (NullPointerException | ClassCastException e) { |
| return 0; |
| } |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * <p>If the data in the multiset is modified by any other threads during this method, it is |
| * undefined which (if any) of these modifications will be reflected in the result. |
| */ |
| @Override |
| public int size() { |
| long sum = 0L; |
| for (Integer value : countMap.values()) { |
| sum += value; |
| } |
| return Ints.saturatedCast(sum); |
| } |
| |
| /* |
| * Note: the superclass toArray() methods assume that size() gives a correct |
| * answer, which ours does not. |
| */ |
| |
| @Override |
| public Object[] toArray() { |
| return snapshot().toArray(); |
| } |
| |
| @Override |
| public <T> T[] toArray(T[] array) { |
| return snapshot().toArray(array); |
| } |
| |
| /* |
| * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but |
| * either of these would recurse back to us again! |
| */ |
| private List<E> snapshot() { |
| List<E> list = Lists.newArrayListWithExpectedSize(size()); |
| for (Multiset.Entry<E> entry : entrySet()) { |
| E element = entry.getElement(); |
| for (int i = entry.getCount(); i > 0; i--) { |
| list.add(element); |
| } |
| } |
| return list; |
| } |
| |
| // Modification Operations |
| |
| /** |
| * Adds a number of occurrences of the specified element to this multiset. |
| * |
| * @param element the element to add |
| * @param occurrences the number of occurrences to add |
| * @return the previous count of the element before the operation; possibly zero |
| * @throws IllegalArgumentException if {@code occurrences} is negative, or if the resulting |
| * amount would exceed {@link Integer#MAX_VALUE} |
| */ |
| @Override |
| public int add(E element, int occurrences) { |
| if (occurrences == 0) { |
| return count(element); |
| } |
| checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences); |
| |
| while (true) { |
| int current = count(element); |
| if (current == 0) { |
| if (countMap.putIfAbsent(element, occurrences) == null) { |
| return 0; |
| } |
| } else { |
| checkArgument( |
| occurrences <= Integer.MAX_VALUE - current, |
| "Overflow adding %s occurrences to a count of %s", |
| occurrences, |
| current); |
| int next = current + occurrences; |
| if (countMap.replace(element, current, next)) { |
| return current; |
| } |
| } |
| // If we're still here, there was a race, so just try again. |
| } |
| } |
| |
| /** |
| * Removes a number of occurrences of the specified element from this multiset. If the multiset |
| * contains fewer than this number of occurrences to begin with, all occurrences will be |
| * removed. |
| * |
| * @param element the element whose occurrences should be removed |
| * @param occurrences the number of occurrences of the element to remove |
| * @return the count of the element before the operation; possibly zero |
| * @throws IllegalArgumentException if {@code occurrences} is negative |
| */ |
| @Override |
| public int remove(@Nullable Object element, int occurrences) { |
| if (occurrences == 0) { |
| return count(element); |
| } |
| checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences); |
| |
| while (true) { |
| int current = count(element); |
| if (current == 0) { |
| return 0; |
| } |
| if (occurrences >= current) { |
| if (countMap.remove(element, current)) { |
| return current; |
| } |
| } else { |
| // We know it's an "E" because it already exists in the map. |
| @SuppressWarnings("unchecked") |
| E casted = (E) element; |
| |
| if (countMap.replace(casted, current, current - occurrences)) { |
| return current; |
| } |
| } |
| // If we're still here, there was a race, so just try again. |
| } |
| } |
| |
| /** |
| * Removes <b>all</b> occurrences of the specified element from this multiset. This method |
| * complements {@link Multiset#remove(Object)}, which removes only one occurrence at a time. |
| * |
| * @param element the element whose occurrences should all be removed |
| * @return the number of occurrences successfully removed, possibly zero |
| */ |
| private int removeAllOccurrences(@Nullable Object element) { |
| try { |
| return unbox(countMap.remove(element)); |
| } catch (NullPointerException | ClassCastException e) { |
| return 0; |
| } |
| } |
| |
| /** |
| * Removes exactly the specified number of occurrences of {@code element}, or makes no change if |
| * this is not possible. |
| * |
| * <p>This method, in contrast to {@link #remove(Object, int)}, has no effect when the element |
| * count is smaller than {@code occurrences}. |
| * |
| * @param element the element to remove |
| * @param occurrences the number of occurrences of {@code element} to remove |
| * @return {@code true} if the removal was possible (including if {@code occurrences} is zero) |
| */ |
| public boolean removeExactly(@Nullable Object element, int occurrences) { |
| if (occurrences == 0) { |
| return true; |
| } |
| checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences); |
| |
| while (true) { |
| int current = count(element); |
| if (occurrences > current) { |
| return false; |
| } |
| if (occurrences == current) { |
| if (countMap.remove(element, occurrences)) { |
| return true; |
| } |
| } else { |
| @SuppressWarnings("unchecked") // it's in the map, must be an "E" |
| E casted = (E) element; |
| if (countMap.replace(casted, current, current - occurrences)) { |
| return true; |
| } |
| } |
| // If we're still here, there was a race, so just try again. |
| } |
| } |
| |
| /** |
| * Adds or removes occurrences of {@code element} such that the {@link #count} of the element |
| * becomes {@code count}. |
| * |
| * @return the count of {@code element} in the multiset before this call |
| * @throws IllegalArgumentException if {@code count} is negative |
| */ |
| @Override |
| public int setCount(E element, int count) { |
| checkNonnegative(count, "count"); |
| return (count == 0) ? removeAllOccurrences(element) : unbox(countMap.put(element, count)); |
| } |
| |
| /** |
| * Sets the number of occurrences of {@code element} to {@code newCount}, but only if the count |
| * is currently {@code oldCount}. If {@code element} does not appear in the multiset exactly |
| * {@code oldCount} times, no changes will be made. |
| * |
| * @return {@code true} if the change was successful. This usually indicates that the multiset |
| * has been modified, but not always: in the case that {@code oldCount == newCount}, the |
| * method will return {@code true} if the condition was met. |
| * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is negative |
| */ |
| @Override |
| public boolean setCount(E element, int oldCount, int newCount) { |
| checkNonnegative(oldCount, "oldCount"); |
| checkNonnegative(newCount, "newCount"); |
| if (newCount == 0) { |
| if (oldCount == 0) { |
| // No change to make, but must return true if the element is not present |
| return !countMap.containsKey(element); |
| } else { |
| return countMap.remove(element, oldCount); |
| } |
| } |
| if (oldCount == 0) { |
| return countMap.putIfAbsent(element, newCount) == null; |
| } |
| return countMap.replace(element, oldCount, newCount); |
| } |
| |
| // Views |
| |
| @Override |
| Set<E> createElementSet() { |
| final Set<E> delegate = countMap.keySet(); |
| return new ForwardingSet<E>() { |
| @Override |
| protected Set<E> delegate() { |
| return delegate; |
| } |
| |
| @Override |
| public boolean remove(Object object) { |
| try { |
| return delegate.remove(object); |
| } catch (NullPointerException | ClassCastException e) { |
| return false; |
| } |
| } |
| }; |
| } |
| |
| @Override |
| Iterator<E> elementIterator() { |
| throw new AssertionError("should never be called"); |
| } |
| |
| private transient EntrySet entrySet; |
| |
| @Override |
| public Set<Multiset.Entry<E>> entrySet() { |
| EntrySet result = entrySet; |
| if (result == null) { |
| entrySet = result = new EntrySet(); |
| } |
| return result; |
| } |
| |
| @Override |
| int distinctElements() { |
| return countMap.size(); |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return countMap.isEmpty(); |
| } |
| |
| @Override |
| Iterator<Entry<E>> entryIterator() { |
| final Iterator<Map.Entry<E, Integer>> backingIterator = countMap.entrySet().iterator(); |
| return new Iterator<Entry<E>>() { |
| @Override |
| public boolean hasNext() { |
| return backingIterator.hasNext(); |
| } |
| |
| @Override |
| public Multiset.Entry<E> next() { |
| Map.Entry<E, Integer> backingEntry = backingIterator.next(); |
| return Multisets.immutableEntry(backingEntry.getKey(), backingEntry.getValue()); |
| } |
| |
| @Override |
| public void remove() { |
| backingIterator.remove(); |
| } |
| }; |
| } |
| |
| @Override |
| public Iterator<E> iterator() { |
| return Multisets.iteratorImpl(this); |
| } |
| |
| @Override |
| public void clear() { |
| countMap.clear(); |
| } |
| |
| private class EntrySet extends AbstractMultiset<E>.EntrySet { |
| @Override |
| Multiset<E> multiset() { |
| return OldConcurrentHashMultiset.this; |
| } |
| |
| /* |
| * Note: the superclass toArray() methods assume that size() gives a correct |
| * answer, which ours does not. |
| */ |
| |
| @Override |
| public Object[] toArray() { |
| return snapshot().toArray(); |
| } |
| |
| @Override |
| public <T> T[] toArray(T[] array) { |
| return snapshot().toArray(array); |
| } |
| |
| private List<Multiset.Entry<E>> snapshot() { |
| List<Multiset.Entry<E>> list = Lists.newArrayListWithExpectedSize(size()); |
| // not Iterables.addAll(list, this), because that'll forward back here |
| Iterators.addAll(list, iterator()); |
| return list; |
| } |
| |
| @Override |
| public boolean remove(Object object) { |
| if (object instanceof Multiset.Entry) { |
| Multiset.Entry<?> entry = (Multiset.Entry<?>) object; |
| Object element = entry.getElement(); |
| int entryCount = entry.getCount(); |
| return countMap.remove(element, entryCount); |
| } |
| return false; |
| } |
| |
| /** The hash code is the same as countMap's, though the objects aren't equal. */ |
| @Override |
| public int hashCode() { |
| return countMap.hashCode(); |
| } |
| } |
| |
| /** We use a special form of unboxing that treats null as zero. */ |
| private static int unbox(@Nullable Integer i) { |
| return (i == null) ? 0 : i; |
| } |
| } |
| } |