You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@parquet.apache.org by bl...@apache.org on 2016/04/21 05:47:55 UTC
parquet-mr git commit: PARQUET-585: Slowly ramp up sizes of int[]s in
IntList to keep sizes small when data sets are small
Repository: parquet-mr
Updated Branches:
refs/heads/master 6b24a1d1b -> 36ce032b6
PARQUET-585: Slowly ramp up sizes of int[]s in IntList to keep sizes small when data sets are small
One of the follow up items from PR - https://github.com/apache/parquet-mr/pull/339 was to slowly ramp up the size of the int[] created in IntList to ensure we don't allocate 64K arrays right off the bat. This PR updates the code to start with a 4K array then keeps doubling till 64K (and stays at 64K after that).
Author: Piyush Narang <pn...@twitter.com>
Closes #341 from piyushnarang/master and squashes the following commits:
0bc6b84 [Piyush Narang] Fix review comments - add spaces, check slab size, fix slab init
d1b4df1 [Piyush Narang] Make IntListTest values relative to constants in IntList
9617015 [Piyush Narang] Update IntList slab creation to keep bumping up size gradually
ebf1c58 [Piyush Narang] Merge branch 'master' of https://github.com/apache/parquet-mr
3ecc577 [Piyush Narang] Remove redundant IntList ctor
f7dfd5f [Piyush Narang] Switch int[] initialization in IntList to be lazy
Project: http://git-wip-us.apache.org/repos/asf/parquet-mr/repo
Commit: http://git-wip-us.apache.org/repos/asf/parquet-mr/commit/36ce032b
Tree: http://git-wip-us.apache.org/repos/asf/parquet-mr/tree/36ce032b
Diff: http://git-wip-us.apache.org/repos/asf/parquet-mr/diff/36ce032b
Branch: refs/heads/master
Commit: 36ce032b612fc0a1156d28bca7327e06337c8815
Parents: 6b24a1d
Author: Piyush Narang <pn...@twitter.com>
Authored: Wed Apr 20 20:47:49 2016 -0700
Committer: Ryan Blue <bl...@apache.org>
Committed: Wed Apr 20 20:47:49 2016 -0700
----------------------------------------------------------------------
.../column/values/dictionary/IntList.java | 64 ++++++++++++---
.../column/values/dictionary/IntListTest.java | 84 ++++++++++++++++++++
2 files changed, 136 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/parquet-mr/blob/36ce032b/parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java
----------------------------------------------------------------------
diff --git a/parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java b/parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java
index 8e6228a..dca1470 100644
--- a/parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java
+++ b/parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java
@@ -31,7 +31,20 @@ import java.util.List;
*/
public class IntList {
- private static final int SLAB_SIZE = 64 * 1024;
+ static final int MAX_SLAB_SIZE = 64 * 1024;
+ static final int INITIAL_SLAB_SIZE = 4 * 1024;
+
+ // Double slab size till we reach the max slab size. At that point we just add slabs of size
+ // MAX_SLAB_SIZE. This ensures we don't allocate very large slabs from the start if we don't have
+ // too much data.
+ private int currentSlabSize = INITIAL_SLAB_SIZE;
+
+ /**
+ * Visible for testing to verify the current slab size
+ */
+ int getCurrentSlabSize() {
+ return currentSlabSize;
+ }
/**
* to iterate on the content of the list
@@ -43,14 +56,17 @@ public class IntList {
public static class IntIterator {
private final int[][] slabs;
- private int current;
private final int count;
+ private int current;
+ private int currentRow;
+ private int currentCol;
+
/**
* slabs will be iterated in order up to the provided count
* as the last slab may not be full
* @param slabs contain the ints
- * @param count total count of ints
+ * @param count count of ints
*/
public IntIterator(int[][] slabs, int count) {
this.slabs = slabs;
@@ -68,11 +84,19 @@ public class IntList {
* @return the next int
*/
public int next() {
- final int result = slabs[current / SLAB_SIZE][current % SLAB_SIZE];
- ++ current;
+ final int result = slabs[currentRow][currentCol];
+ incrementPosition();
return result;
}
+ private void incrementPosition() {
+ current++;
+ currentCol++;
+ if (currentCol >= slabs[currentRow].length) {
+ currentCol = 0;
+ currentRow++;
+ }
+ }
}
private List<int[]> slabs = new ArrayList<int[]>();
@@ -82,20 +106,31 @@ public class IntList {
private int[] currentSlab;
private int currentSlabPos;
- private void initSlab() {
- currentSlab = new int[SLAB_SIZE];
+ private void allocateSlab() {
+ currentSlab = new int[currentSlabSize];
currentSlabPos = 0;
}
+ // Double slab size up to the MAX_SLAB_SIZE limit
+ private void updateCurrentSlabSize() {
+ if (currentSlabSize < MAX_SLAB_SIZE) {
+ currentSlabSize *= 2;
+ if (currentSlabSize > MAX_SLAB_SIZE) {
+ currentSlabSize = MAX_SLAB_SIZE;
+ }
+ }
+ }
+
/**
* @param i value to append to the end of the list
*/
public void add(int i) {
if (currentSlab == null) {
- initSlab();
+ allocateSlab();
} else if (currentSlabPos == currentSlab.length) {
slabs.add(currentSlab);
- initSlab();
+ updateCurrentSlabSize();
+ allocateSlab();
}
currentSlab[currentSlabPos] = i;
@@ -108,19 +143,24 @@ public class IntList {
*/
public IntIterator iterator() {
if (currentSlab == null) {
- initSlab();
+ allocateSlab();
}
int[][] itSlabs = slabs.toArray(new int[slabs.size() + 1][]);
itSlabs[slabs.size()] = currentSlab;
- return new IntIterator(itSlabs, SLAB_SIZE * slabs.size() + currentSlabPos);
+ return new IntIterator(itSlabs, size());
}
/**
* @return the current size of the list
*/
public int size() {
- return SLAB_SIZE * slabs.size() + currentSlabPos;
+ int size = currentSlabPos;
+ for (int [] slab : slabs) {
+ size += slab.length;
+ }
+
+ return size;
}
}
http://git-wip-us.apache.org/repos/asf/parquet-mr/blob/36ce032b/parquet-column/src/test/java/org/apache/parquet/column/values/dictionary/IntListTest.java
----------------------------------------------------------------------
diff --git a/parquet-column/src/test/java/org/apache/parquet/column/values/dictionary/IntListTest.java b/parquet-column/src/test/java/org/apache/parquet/column/values/dictionary/IntListTest.java
new file mode 100644
index 0000000..e6df4db
--- /dev/null
+++ b/parquet-column/src/test/java/org/apache/parquet/column/values/dictionary/IntListTest.java
@@ -0,0 +1,84 @@
+/*
+ * 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.parquet.column.values.dictionary;
+
+import org.junit.Test;
+
+import junit.framework.Assert;
+
+public class IntListTest {
+
+ /**
+ * Test IntList of fairly small size (< INITIAL_SLAB_SIZE), this tests a single slab being created
+ */
+ @Test
+ public void testSmallList() {
+ int testSize = IntList.INITIAL_SLAB_SIZE - 100;
+ doTestIntList(testSize, IntList.INITIAL_SLAB_SIZE);
+ }
+
+ /**
+ * Test IntList > INITIAL_SLAB_SIZE so that we have multiple slabs being created
+ */
+ @Test
+ public void testListGreaterThanInitialSlabSize() {
+ int testSize = IntList.INITIAL_SLAB_SIZE + 100;
+ doTestIntList(testSize, IntList.INITIAL_SLAB_SIZE * 2);
+ }
+
+ /**
+ * Test IntList of a fairly large size (> MAX_SLAB_SIZE) so that we have multiple slabs
+ * created of varying sizes
+ */
+ @Test
+ public void testListGreaterThanMaxSlabSize() {
+ int testSize = IntList.MAX_SLAB_SIZE * 4 + 100;
+ doTestIntList(testSize, IntList.MAX_SLAB_SIZE);
+ }
+
+ private void doTestIntList(int testSize, int expectedSlabSize) {
+ IntList testList = new IntList();
+ populateList(testList, testSize);
+
+ verifyIteratorResults(testSize, testList);
+
+ // confirm the size of the current slab
+ Assert.assertEquals(expectedSlabSize, testList.getCurrentSlabSize());
+ }
+
+ private void populateList(IntList testList, int size) {
+ for(int i = 0; i < size; i++) {
+ testList.add(i);
+ }
+ }
+
+ private void verifyIteratorResults(int testSize, IntList testList) {
+ IntList.IntIterator iterator = testList.iterator();
+ int expected = 0;
+
+ while (iterator.hasNext()) {
+ int val = iterator.next();
+ Assert.assertEquals(expected, val);
+ expected++;
+ }
+
+ // ensure we have the correct final value of expected
+ Assert.assertEquals(testSize, expected);
+ }
+}