Return-Path: X-Original-To: apmail-cassandra-commits-archive@www.apache.org Delivered-To: apmail-cassandra-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 4665B17F79 for ; Wed, 4 Mar 2015 05:02:31 +0000 (UTC) Received: (qmail 89097 invoked by uid 500); 4 Mar 2015 05:02:31 -0000 Delivered-To: apmail-cassandra-commits-archive@cassandra.apache.org Received: (qmail 89055 invoked by uid 500); 4 Mar 2015 05:02:31 -0000 Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@cassandra.apache.org Delivered-To: mailing list commits@cassandra.apache.org Received: (qmail 89044 invoked by uid 99); 4 Mar 2015 05:02:31 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 04 Mar 2015 05:02:31 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id CB52DE07F3; Wed, 4 Mar 2015 05:02:30 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: aleksey@apache.org To: commits@cassandra.apache.org Message-Id: <2a6656a8cef543768f49a425e011f974@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: cassandra git commit: Make EstimatedHistogram#percentile() use ceil instead of floor Date: Wed, 4 Mar 2015 05:02:30 +0000 (UTC) Repository: cassandra Updated Branches: refs/heads/cassandra-2.1 0127b6963 -> d4e37869b Make EstimatedHistogram#percentile() use ceil instead of floor patch by Carl Yeksigian; reviewed by Chris Lohfink for CASSANDRA-8883 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/d4e37869 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/d4e37869 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/d4e37869 Branch: refs/heads/cassandra-2.1 Commit: d4e37869b1465b231ada7554fb7a6d5ccf43f493 Parents: 0127b69 Author: Carl Yeksigian Authored: Tue Mar 3 13:54:51 2015 -0500 Committer: Aleksey Yeschenko Committed: Tue Mar 3 21:01:14 2015 -0800 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../cassandra/utils/EstimatedHistogram.java | 2 +- .../cassandra/utils/EstimatedHistogramTest.java | 52 ++++++++++++++++---- 3 files changed, 44 insertions(+), 11 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/d4e37869/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 7ce6200..748acf8 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 2.1.4 + * Make EstimatedHistogram#percentile() use ceil instead of floor (CASSANDRA-8883) * Fix top partitions reporting wrong cardinality (CASSANDRA-8834) * Fix rare NPE in KeyCacheSerializer (CASSANDRA-8067) * Pick sstables for validation as late as possible inc repairs (CASSANDRA-8366) http://git-wip-us.apache.org/repos/asf/cassandra/blob/d4e37869/src/java/org/apache/cassandra/utils/EstimatedHistogram.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/EstimatedHistogram.java b/src/java/org/apache/cassandra/utils/EstimatedHistogram.java index 196a3b9..a5c51c8 100644 --- a/src/java/org/apache/cassandra/utils/EstimatedHistogram.java +++ b/src/java/org/apache/cassandra/utils/EstimatedHistogram.java @@ -178,7 +178,7 @@ public class EstimatedHistogram if (buckets.get(lastBucket) > 0) throw new IllegalStateException("Unable to compute when histogram overflowed"); - long pcount = (long) Math.floor(count() * percentile); + long pcount = (long) Math.ceil(count() * percentile); if (pcount == 0) return 0; http://git-wip-us.apache.org/repos/asf/cassandra/blob/d4e37869/test/unit/org/apache/cassandra/utils/EstimatedHistogramTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/utils/EstimatedHistogramTest.java b/test/unit/org/apache/cassandra/utils/EstimatedHistogramTest.java index bbfd1c7..eebaa25 100644 --- a/test/unit/org/apache/cassandra/utils/EstimatedHistogramTest.java +++ b/test/unit/org/apache/cassandra/utils/EstimatedHistogramTest.java @@ -75,17 +75,49 @@ public class EstimatedHistogramTest @Test public void testPercentile() { - EstimatedHistogram histogram = new EstimatedHistogram(); - // percentile of empty histogram is 0 - assertEquals(0, histogram.percentile(0.99)); + { + EstimatedHistogram histogram = new EstimatedHistogram(); + // percentile of empty histogram is 0 + assertEquals(0, histogram.percentile(0.99)); - histogram.add(1); - // percentile of histogram with just one value will return 0 except 100th - assertEquals(0, histogram.percentile(0.99)); - assertEquals(1, histogram.percentile(1.00)); + histogram.add(1); + // percentile of a histogram with one element should be that element + assertEquals(1, histogram.percentile(0.99)); + + histogram.add(10); + assertEquals(10, histogram.percentile(0.99)); + } + + { + EstimatedHistogram histogram = new EstimatedHistogram(); + + histogram.add(1); + histogram.add(2); + histogram.add(3); + histogram.add(4); + histogram.add(5); + + assertEquals(0, histogram.percentile(0.00)); + assertEquals(3, histogram.percentile(0.50)); + assertEquals(3, histogram.percentile(0.60)); + assertEquals(5, histogram.percentile(1.00)); + } + + { + EstimatedHistogram histogram = new EstimatedHistogram(); + + for (int i = 11; i <= 20; i++) + histogram.add(i); - histogram.add(10); - assertEquals(1, histogram.percentile(0.99)); - assertEquals(10, histogram.percentile(1.00)); + // Right now the histogram looks like: + // 10 12 14 17 20 + // 0 2 2 3 3 + // %: 0 20 40 70 100 + assertEquals(12, histogram.percentile(0.01)); + assertEquals(14, histogram.percentile(0.30)); + assertEquals(17, histogram.percentile(0.50)); + assertEquals(17, histogram.percentile(0.60)); + assertEquals(20, histogram.percentile(0.80)); + } } }