LEB128 tests and performance measurements.
Change-Id: I1850a2ff9225cfab8f896619c212b1b55f03ae94
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index b07753c..bed48ba 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -22,6 +22,7 @@
compiler/elf_writer_test.cc \
compiler/image_test.cc \
compiler/jni/jni_compiler_test.cc \
+ compiler/leb128_encoder_test.cc \
compiler/oat_test.cc \
compiler/output_stream_test.cc \
compiler/utils/dedupe_set_test.cc \
diff --git a/compiler/leb128_encoder_test.cc b/compiler/leb128_encoder_test.cc
new file mode 100644
index 0000000..4fa8075
--- /dev/null
+++ b/compiler/leb128_encoder_test.cc
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#include "base/histogram-inl.h"
+#include "common_test.h"
+#include "leb128.h"
+#include "leb128_encoder.h"
+
+namespace art {
+
+class Leb128Test : public CommonTest {};
+
+struct DecodeUnsignedLeb128TestCase {
+ uint32_t decoded;
+ uint8_t leb128_data[5];
+};
+
+static DecodeUnsignedLeb128TestCase uleb128_tests[] = {
+ {0, {0, 0, 0, 0, 0}},
+ {1, {1, 0, 0, 0, 0}},
+ {0x7F, {0x7F, 0, 0, 0, 0}},
+ {0x80, {0x80, 1, 0, 0, 0}},
+ {0x81, {0x81, 1, 0, 0, 0}},
+ {0xFF, {0xFF, 1, 0, 0, 0}},
+ {0x4000, {0x80, 0x80, 1, 0, 0}},
+ {0x4001, {0x81, 0x80, 1, 0, 0}},
+ {0x4081, {0x81, 0x81, 1, 0, 0}},
+ {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0x7F, 0}},
+ {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}},
+};
+
+TEST_F(Leb128Test, Singles) {
+ // Test individual encodings.
+ for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
+ UnsignedLeb128EncodingVector builder;
+ builder.PushBack(uleb128_tests[i].decoded);
+ const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
+ const uint8_t* encoded_data_ptr = &builder.GetData()[0];
+ for (size_t j = 0; j < 5; ++j) {
+ if (j < builder.GetData().size()) {
+ EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
+ } else {
+ EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
+ }
+ }
+ EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
+ }
+}
+
+TEST_F(Leb128Test, Stream) {
+ // Encode a number of entries.
+ UnsignedLeb128EncodingVector builder;
+ for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
+ builder.PushBack(uleb128_tests[i].decoded);
+ }
+ const uint8_t* encoded_data_ptr = &builder.GetData()[0];
+ for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
+ const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
+ for (size_t j = 0; j < 5; ++j) {
+ if (data_ptr[j] != 0) {
+ EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
+ }
+ }
+ EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
+ }
+}
+
+TEST_F(Leb128Test, Speed) {
+ UniquePtr<Histogram<uint64_t> > enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5));
+ UniquePtr<Histogram<uint64_t> > dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5));
+ UnsignedLeb128EncodingVector builder;
+ // Push back 1024 chunks of 1024 values measuring encoding speed.
+ uint64_t last_time = NanoTime();
+ for (size_t i = 0; i < 1024; i++) {
+ for (size_t j = 0; j < 1024; j++) {
+ builder.PushBack((i * 1024) + j);
+ }
+ uint64_t cur_time = NanoTime();
+ enc_hist->AddValue(cur_time - last_time);
+ last_time = cur_time;
+ }
+ // Verify encoding and measure decode speed.
+ const uint8_t* encoded_data_ptr = &builder.GetData()[0];
+ last_time = NanoTime();
+ for (size_t i = 0; i < 1024; i++) {
+ for (size_t j = 0; j < 1024; j++) {
+ EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), (i * 1024) + j);
+ }
+ uint64_t cur_time = NanoTime();
+ dec_hist->AddValue(cur_time - last_time);
+ last_time = cur_time;
+ }
+
+ Histogram<uint64_t>::CumulativeData enc_data;
+ enc_hist->CreateHistogram(&enc_data);
+ enc_hist->PrintConfidenceIntervals(std::cout, 0.99, enc_data);
+
+ Histogram<uint64_t>::CumulativeData dec_data;
+ dec_hist->CreateHistogram(&dec_data);
+ dec_hist->PrintConfidenceIntervals(std::cout, 0.99, dec_data);
+}
+
+} // namespace art
diff --git a/runtime/base/histogram-inl.h b/runtime/base/histogram-inl.h
index 0345266..9e08ae6 100644
--- a/runtime/base/histogram-inl.h
+++ b/runtime/base/histogram-inl.h
@@ -170,20 +170,20 @@
os << FormatDuration(Max() * kAdjust, unit) << "\n";
}
-template <class Value> inline void Histogram<Value>::CreateHistogram(CumulativeData& out_data) {
+template <class Value> inline void Histogram<Value>::CreateHistogram(CumulativeData* out_data) {
DCHECK_GT(sample_size_, 0ull);
- out_data.freq_.clear();
- out_data.perc_.clear();
+ out_data->freq_.clear();
+ out_data->perc_.clear();
uint64_t accumulated = 0;
- out_data.freq_.push_back(accumulated);
- out_data.perc_.push_back(0.0);
+ out_data->freq_.push_back(accumulated);
+ out_data->perc_.push_back(0.0);
for (size_t idx = 0; idx < frequency_.size(); idx++) {
accumulated += frequency_[idx];
- out_data.freq_.push_back(accumulated);
- out_data.perc_.push_back(static_cast<double>(accumulated) / static_cast<double>(sample_size_));
+ out_data->freq_.push_back(accumulated);
+ out_data->perc_.push_back(static_cast<double>(accumulated) / static_cast<double>(sample_size_));
}
- DCHECK_EQ(out_data.freq_.back(), sample_size_);
- DCHECK_LE(std::abs(out_data.perc_.back() - 1.0), 0.001);
+ DCHECK_EQ(out_data->freq_.back(), sample_size_);
+ DCHECK_LE(std::abs(out_data->perc_.back() - 1.0), 0.001);
}
template <class Value>
diff --git a/runtime/base/histogram.h b/runtime/base/histogram.h
index 2a02cf4..e22b6e1 100644
--- a/runtime/base/histogram.h
+++ b/runtime/base/histogram.h
@@ -47,7 +47,7 @@
// cumulative_freq[i] = sum(frequency[j] : 0 < j < i )
// Accumulative summation of percentiles; which is the frequency / SampleSize
// cumulative_perc[i] = sum(frequency[j] / SampleSize : 0 < j < i )
- void CreateHistogram(CumulativeData& data);
+ void CreateHistogram(CumulativeData* data);
// Reset the cumulative values, next time CreateHistogram is called it will recreate the cache.
void Reset();
double Mean() const;
diff --git a/runtime/base/histogram_test.cc b/runtime/base/histogram_test.cc
index 534440c..9d371f5 100644
--- a/runtime/base/histogram_test.cc
+++ b/runtime/base/histogram_test.cc
@@ -85,7 +85,7 @@
hist->AddValue(145);
hist->AddValue(155);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
PerValue = hist->Percentile(0.50, data);
EXPECT_EQ(875, static_cast<int>(PerValue * 10));
}
@@ -117,7 +117,7 @@
hist->AddValue(200);
hist->AddValue(205);
hist->AddValue(212);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
PerValue = hist->Percentile(0.50, data);
std::string text;
@@ -132,7 +132,6 @@
TEST(Histtest, Reset) {
UniquePtr<Histogram<uint64_t> > hist(new Histogram<uint64_t>("Reset", 5));
- Histogram<uint64_t>::CumulativeData data;
double PerValue;
hist->AddValue(0);
@@ -160,7 +159,8 @@
hist->AddValue(200);
hist->AddValue(205);
hist->AddValue(212);
- hist->CreateHistogram(data);
+ Histogram<uint64_t>::CumulativeData data;
+ hist->CreateHistogram(&data);
PerValue = hist->Percentile(0.50, data);
std::string text;
@@ -185,7 +185,7 @@
hist->AddValue(68);
hist->AddValue(75);
hist->AddValue(93);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
hist->AddValue(110);
hist->AddValue(121);
hist->AddValue(132);
@@ -194,14 +194,14 @@
hist->AddValue(155);
hist->AddValue(163);
hist->AddValue(168);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
hist->AddValue(175);
hist->AddValue(182);
hist->AddValue(193);
hist->AddValue(200);
hist->AddValue(205);
hist->AddValue(212);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
PerValue = hist->Percentile(0.50, data);
std::stringstream stream;
std::string expected("MultipleCreateHist:\t99% C.I. 15us-212us Avg: 126.380us Max: 212us\n");
@@ -217,7 +217,7 @@
Histogram<uint64_t>::CumulativeData data;
hist->AddValue(1);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
std::stringstream stream;
std::string expected = "SingleValue:\t99% C.I. 1us-1us Avg: 1us Max: 1us\n";
hist->PrintConfidenceIntervals(stream, 0.99, data);
@@ -234,7 +234,7 @@
for (uint64_t idx = 0ull; idx < 150ull; idx++) {
hist->AddValue(0);
}
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
per_995 = hist->Percentile(0.995, data);
EXPECT_EQ(per_995, 0);
hist->Reset();
@@ -243,7 +243,7 @@
hist->AddValue(val);
}
}
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
per_005 = hist->Percentile(0.005, data);
per_995 = hist->Percentile(0.995, data);
EXPECT_EQ(1, per_005);
@@ -260,7 +260,7 @@
}
}
hist->AddValue(10000);
- hist->CreateHistogram(data);
+ hist->CreateHistogram(&data);
std::stringstream stream;
std::string expected = "SpikyValues:\t99% C.I. 0.089us-2541.825us Avg: 95.033us Max: 10000us\n";
hist->PrintConfidenceIntervals(stream, 0.99, data);
diff --git a/runtime/base/timing_logger.cc b/runtime/base/timing_logger.cc
index dae8201..bebbd70 100644
--- a/runtime/base/timing_logger.cc
+++ b/runtime/base/timing_logger.cc
@@ -115,7 +115,7 @@
for (CumulativeLogger::HistogramsIterator it = histograms_.begin(), end = histograms_.end();
it != end; ++it) {
Histogram<uint64_t>::CumulativeData cumulative_data;
- it->second->CreateHistogram(cumulative_data);
+ it->second->CreateHistogram(&cumulative_data);
it->second->PrintConfidenceIntervals(os, 0.99, cumulative_data);
// Reset cumulative values to save memory. We don't expect DumpHistogram to be called often, so
// it is not performance critical.
