parquet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From b...@apache.org
Subject [06/50] [abbrv] parquet-mr git commit: PARQUET-585: Slowly ramp up sizes of int[]s in IntList to keep sizes small when data sets are small
Date Thu, 19 Jan 2017 01:27:17 GMT
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 <pnarang@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/7885f9fb
Tree: http://git-wip-us.apache.org/repos/asf/parquet-mr/tree/7885f9fb
Diff: http://git-wip-us.apache.org/repos/asf/parquet-mr/diff/7885f9fb

Branch: refs/heads/parquet-1.8.x
Commit: 7885f9fb9b51633b3b9a161cc88ed8b7a3cca79d
Parents: aa249a5
Author: Piyush Narang <pnarang@twitter.com>
Authored: Wed Apr 20 20:47:49 2016 -0700
Committer: Ryan Blue <blue@apache.org>
Committed: Mon Jan 9 16:54:53 2017 -0800

----------------------------------------------------------------------
 .../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/7885f9fb/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/7885f9fb/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);
+  }
+}


Mime
View raw message