1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.lang3; 18 19 import java.util.BitSet; 20 import java.util.HashSet; 21 import java.util.concurrent.TimeUnit; 22 23 import org.openjdk.jmh.annotations.Benchmark; 24 import org.openjdk.jmh.annotations.BenchmarkMode; 25 import org.openjdk.jmh.annotations.Mode; 26 import org.openjdk.jmh.annotations.OutputTimeUnit; 27 import org.openjdk.jmh.annotations.Scope; 28 import org.openjdk.jmh.annotations.State; 29 30 /** 31 * Test to show whether using BitSet for removeAll() methods is faster than using HashSet. 32 */ 33 @BenchmarkMode(Mode.AverageTime) 34 @OutputTimeUnit(TimeUnit.NANOSECONDS) 35 @State(Scope.Thread) 36 public class HashSetvBitSetTest extends AbstractLangTest { 37 38 private static final int numberOfElementsToCompute = 10; 39 40 @Benchmark testHashSet()41 public int[] testHashSet() { 42 final HashSet<Integer> toRemove = new HashSet<>(); 43 int found = 0; 44 for (int i = 0; i < numberOfElementsToCompute; i++) { 45 toRemove.add(found++); 46 } 47 return extractIndices(toRemove); 48 } 49 50 @Benchmark testBitSet()51 public int[] testBitSet() { 52 final BitSet toRemove = new BitSet(); 53 int found = 0; 54 for (int i = 0; i < numberOfElementsToCompute; i++) { 55 toRemove.set(found++); 56 } 57 return extractIndices(toRemove); 58 } 59 60 @Benchmark timeBitSetRemoveAll()61 public int[] timeBitSetRemoveAll() { 62 final BitSet toRemove = new BitSet(); 63 final int[] array = new int[100]; 64 toRemove.set(10, 20); 65 return (int[]) ArrayUtils.removeAll(array, toRemove); 66 } 67 68 @Benchmark timeExtractRemoveAll()69 public int[] timeExtractRemoveAll() { 70 final BitSet toRemove = new BitSet(); 71 final int[] array = new int[100]; 72 toRemove.set(10, 20); 73 final int[] extractIndices = extractIndices(toRemove); 74 return (int[]) ArrayUtils.removeAll((Object) array, extractIndices); 75 } 76 77 // --- utility methods extractIndices(final HashSet<Integer> coll)78 private static int[] extractIndices(final HashSet<Integer> coll) { 79 final int[] result = new int[coll.size()]; 80 int i = 0; 81 for (final Integer index : coll) { 82 result[i++] = index.intValue(); 83 } 84 return result; 85 } 86 extractIndices(final BitSet coll)87 private static int[] extractIndices(final BitSet coll) { 88 final int[] result = new int[coll.cardinality()]; 89 int i = 0; 90 int j=0; 91 while ((j=coll.nextSetBit(j)) != -1) { 92 result[i++] = j++; 93 } 94 return result; 95 } 96 } 97