Skip to content

Instantly share code, notes, and snippets.

@burmanm

burmanm/BSTBench.java

Last active July 5, 2018 20:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save burmanm/7fb14589d5c0d11ae79c018bd7849653 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save burmanm/7fb14589d5c0d11ae79c018bd7849653 to your computer and use it in GitHub Desktop.
Download ZIP
Bench for CASSANDRA-7282
Raw
BSTBench.java
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you 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 org.apache.cassandra.test.microbench;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import com.google.common.annotations.VisibleForTesting;
import org.apache.cassandra.dht.Murmur3Partitioner;
import org.apache.cassandra.dht.Range;
import org.apache.cassandra.dht.Token;
import org.apache.cassandra.utils.HashComparable;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Threads;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.infra.Blackhole;
/**
* @author michael
*/
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 4, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 8, time = 2, timeUnit = TimeUnit.SECONDS)
@Fork(value = 2)
@Threads(4)
@State(Scope.Benchmark)
public class BSTBench
{
@Param({"4", "16", "64", "256", "512"})
int vnodes;
private ImmutableRangeTree searchTree;
private long[] searchpath;
private long[] mins;
private long[] maxs;
@Setup(Level.Trial)
public void setup() {
searchTree = new ImmutableRangeTree<>(createLimitedRanges(vnodes));
mins = new long[vnodes];
maxs = new long[vnodes];
ArrayList<Long> indexSearch = new ArrayList<>(vnodes);
for(int i = 0; i < vnodes; i++) {
mins[i] = searchTree.nodes[i].min;
maxs[i] = searchTree.nodes[i].max;
indexSearch.add(ThreadLocalRandom.current().nextLong(searchTree.nodes[i].min, searchTree.nodes[i].max));
}
Collections.shuffle(indexSearch);
searchpath = new long[vnodes];
for(int i = 0; i < vnodes; i++)
{
searchpath[i] = indexSearch.get(i);
}
}
@Benchmark
public void treeSeek(Blackhole bh) {
for(int i = 0; i < searchpath.length; i++) {
bh.consume(searchTree.search(searchpath[i]));
}
}
@Benchmark
public void binarySeek(Blackhole bh) {
for(int i = 0; i < searchpath.length; i++) {
bh.consume(ImmutableRangeTree.binarySearch(searchTree.nodes, searchpath[i]));
}
}
@Benchmark
public void linearSearch(Blackhole bh) {
for(int i = 0; i < searchpath.length; i++) {
for(int j = 0; j < searchTree.nodes.length; j++) {
/*
// This is slower in this microbenchmark than the option below (as we don't need these directives and branches)
if(searchTree.nodes[j].compareTo(searchpath[i]) == 0) {
bh.consume(searchTree.nodes[j]);
break;
}
*/
if(searchTree.nodes[j].min >= searchpath[i] && searchTree.nodes[j].max <= searchpath[i]) {
bh.consume(searchTree.nodes[j]);
break;
}
}
}
}
@Benchmark
public void multiArrayLinearSearch(Blackhole bh) {
for(int i = 0; i < searchpath.length; i++) {
for(int j = 0; j < mins.length; j++) {
if(mins[j] >= searchpath[i] && maxs[j] <= searchpath[i]) {
bh.consume(searchTree.nodes[j]);
break;
}
}
}
}
@Benchmark
public void multiArrayBinarySeek(Blackhole bh) {
for(int i = 0; i < searchpath.length; i++)
{
bh.consume(binarySearch0(searchpath[i]));
}
}
RangeIndexNode binarySearch0(long hash)
{
int left = 0;
int right = mins.length - 1;
RangeIndexNode node = null;
while(left <= right) {
int mid = left + right >>> 1;
long min = mins[mid];
if (min < hash) {
left = mid + 1;
} else {
if (min <= hash) {
node = searchTree.nodes[mid];
break;
}
right = mid - 1;
}
}
if(node == null) {
node = searchTree.nodes[left - 1];
}
if (node.min <= hash && node.max >= hash)
{
return node;
}
return null;
// Using Arrays.binarySearch is even slower (due to the added calculation)
/*
int i = Arrays.binarySearch(mins, hash);
if (i < 0) // In case the match wasn't exact
i = -(i + 1) - 1;
RangeIndexNode node = searchTree.nodes[i];
if (node.min <= hash && node.max >= hash)
{
return node;
}
return null;
*/
}
public Collection<Range<Token>> createLimitedRanges(int numberOfRanges)
{
int subPartSize = numberOfRanges * 64;
Collection<Range<Token>> ranges = new ArrayList<>(numberOfRanges);
// Pick 4 ranges out of 16 possible ranges
long partRange = BigInteger.valueOf(Murmur3Partitioner.MAXIMUM)
.subtract(BigInteger.valueOf(Murmur3Partitioner.MINIMUM.comparableHashCode()))
.divide(BigInteger.valueOf(subPartSize)).longValue();
int[] parts = ThreadLocalRandom.current().ints(0, subPartSize - 1).distinct().limit(numberOfRanges).sorted().toArray();
for (int part : parts)
{
long min = Murmur3Partitioner.MINIMUM.comparableHashCode() + part * partRange;
long max = min + partRange;
ranges.add(new Range<>(new Murmur3Partitioner.LongToken(min), new Murmur3Partitioner.LongToken(max)));
}
return ranges;
}
/**
* Small immutable balanced search tree for token range searches.
*/
private static class ImmutableRangeTree<K extends HashComparable<? super K>, V>
{
private RangeIndexNode parent;
private RangeIndexNode[] nodes;
/**
* Create ImmutableRangeTree from a given Collection of tokens. Token ranges which wrap are unwrapped and
* new nodes are created for each sub range.
*
* @param tokens A sorted collection of ranges
* @return Balanced ImmutableTree
*/
public ImmutableRangeTree(Collection<Range<Token>> tokens)
{
ArrayList<Range<Token>> ranges = new ArrayList<>(tokens.size());
for (Range<Token> tokenRange : tokens)
{
if (tokenRange.isWrapAround())
{
ranges.addAll(tokenRange.unwrap());
}
else
{
ranges.add(tokenRange);
}
}
nodes = new RangeIndexNode[ranges.size()];
for (int i = 0; i < ranges.size(); i++)
{
Range<Token> r = ranges.get(i);
nodes[i] = new RangeIndexNode(r.left.comparableHashCode(), r.right.comparableHashCode());
}
buildFromSortedArray(0, nodes.length - 1);
}
/**
* Builds balanced tree from a sorted array by linking existing RangeIndexNodes
*/
private RangeIndexNode<K, V> buildFromSortedArray(int start, int end)
{
if (start > end)
return null;
int middle = (start + end) / 2;
if (parent == null)
parent = nodes[middle];
nodes[middle].left = buildFromSortedArray(start, middle - 1);
nodes[middle].right = buildFromSortedArray(middle + 1, end);
return nodes[middle];
}
public RangeIndexNode<K, V> search(long hash)
{
RangeIndexNode node = parent;
while (node != null)
{
switch (node.compareTo(hash))
{
case -1:
node = node.left;
break;
case 1:
node = node.right;
break;
case 0:
return node;
}
}
// The token range is unknown to us, return null and handle this in the findIndex(hash) method
return null;
}
static RangeIndexNode binarySearch(RangeIndexNode[] nodes, long hash) {
int left = 0;
int right = nodes.length - 1;
while(left <= right) {
int mid = left + right >>> 1;
RangeIndexNode node = nodes[mid];
switch(node.compareTo(hash))
{
case 1:
left = mid + 1;
break;
case 0:
return node;
case -1:
right = mid - 1;
break;
}
}
return null;
}
}
/**
* A slice of hash table index, covering only a single token range.
*/
@VisibleForTesting
static class RangeIndexNode<K extends HashComparable<? super K>, V>
{
private long min;
private long max;
RangeIndexNode<K, V> right;
RangeIndexNode<K, V> left;
public RangeIndexNode(long min, long max)
{
this.min = min;
this.max = max;
}
// Intentionally not implementing Comparable
int compareTo(long hash)
{
if (hash < min)
{
// Left
return -1;
}
else if (hash > max)
{
// Right
return 1;
}
else
{
// In the range
return 0;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment