1 Reply Latest reply: Apr 29, 2009 11:23 AM by 843829 RSS

    Help me please, How can I inline the function?

    843829
      Dear all
      Because jdk HashMap use Object type for the key and value, so I write a Hashtable for <int, int>, but the put and get speed to slow.
      In the test code, one million put and get need 235ms and 150ms.(Use nanotime). But when I write the code with C, it less then 1ms. So I know
      the problem is inline, the function call use so many time then running logic code. But how can I inline the function?

      Code here:

      import java.awt.event.ActionEvent;
      import java.awt.event.ActionListener;
      import java.util.HashMap;
      import java.util.Random;

      import javax.swing.JButton;
      import javax.swing.JFrame;

      /**
      * Int&#30340;&#21704;&#24076;&#34920;
      * @author xjf
      *
      */
      public class IntHashMap {

      /**
      * use Min_Value figure Empty_Key, mean No keyset in the map;
      */
      public static final int EMPTY_KEY = Integer.MIN_VALUE;
      private static final int EMPTY = -2;
      private static final int NO_NEXT = -1;

      private int N = 512;
      private int[] map;
      private int[] empty;//from capacity
      private int capacity;
      private int emptyCount;

      int getCount;

      public IntHashMap(int capacity)
      {
      map = new int[(capacity + capacity)*3]; //three int, key, value, nextIndex
      for (int i = 0; i< capacity; i++)
      {
      map[i*3+2] = EMPTY;
      }
      this.capacity = capacity;
      empty = new int[capacity];
      for (int i = 0; i< capacity; i++)
      {
      empty[i] = i;
      }
      emptyCount = capacity;
      }

      public final void put(int key, int value)
      {
      int index = (key%capacity)*3;
      if (map[index + 2] == EMPTY)
      {
      map[index] = key;
      map[index+1] = value;
      map[index+2] = NO_NEXT;
      }
      else
      {
      if (map[index] == key)
      {
      map[index+1] = value; //same key, reset value
      return;
      }
      if (emptyCount == 0) //full
      {
      expand();
      }
      while(map[index+2] != NO_NEXT)
      {
      if (map[index+2] < 0)
      {
      System.out.println("Error");
      }
      index = map[index+2];
      if (index < 0)
      {
      System.out.println("Error");
      }
      if (map[index] == key)
      {
      map[index+1] = value; //same key,reset value
      return;
      }
      }
      emptyCount--;
      int nextIndex = (capacity+empty[emptyCount])*3;
      map[index+2] = nextIndex;
      map[nextIndex] = key;
      map[nextIndex+1] = value;
      map[nextIndex+2] = NO_NEXT;
      }
      }

      private final int get(int key)
      {
      getCount++;
      int index = (key%capacity)*3;
      if (map[index+2] == EMPTY)
      {
      return EMPTY_KEY;
      }
      if (map[index] == key)
      {
      return map[index+1];
      }
      while(map[index] != key && map[index+2] != NO_NEXT)
      {
      getCount++;
      index = map[index+2];
      if (map[index] == key)
      {
      return map[index+1];
      }
      }
      return EMPTY_KEY;
      }

      private void expand()
      {
      int N = capacity/8;
      int[] table = new int[map.length+N*3];
      System.arraycopy(map, 0, table, 0, map.length);
      map = table;

      table = new int[empty.length + N];
      System.arraycopy(empty, 0, table, 0, emptyCount);
      for (int i = 0,j=emptyCount; i< N; i++,j++)
      {
      table[j] = empty.length + i;
      }
      empty = table;
      emptyCount += N;
      }

      private void test2()
      {
      int N = 1000000;
      int[] v = new int[N];
      Random r = new Random(0xFFFF);
      for (int i = 0; i< N; i++)
      {
      v[i] = r.nextInt(0x7FFFFFFF);
      }
      IntHashMap map = new IntHashMap((int)(N*3/Math.PI));
      long t0 = System.nanoTime();
      int end = N-1;
      int dupPut = 0;
      for (int i = 0; i< end; i++)
      {
      map.put(v, v[i+1]);
      }

      long t1 = System.nanoTime();
      map.getCount = 0;
      int dup = 0;
      for (int i =0,j=1; i< end; i++,j++)
      {
      map.get(v[i]);
      }
      long t2 = System.nanoTime();
      System.out.println("put time=" + (t1-t0)*1.0/1000000 + ", dup =" + dupPut);
      System.out.println("capacity=" + map.capacity + ", real len=" + map.map.length + ", empty=" + map.emptyCount);
      System.out.println("get time=" + (t2 - t1)*1.0/1000000 + ", getCount=" + map.getCount + ", dup=" + dup);
      }

      /**
      * @param args
      */
      public static void main(String[] args) {
      JFrame f = new JFrame();
      f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      f.setSize(640, 480);
      JButton btn = new JButton("Start");
      btn.addActionListener(new ActionListener()
      {
      public void actionPerformed(ActionEvent e)
      {
      test2();
      }
      }
      );
      f.getContentPane().add(btn, "North");
      f.setVisible(true);
      }

      }

      xjf
      2008-1-6
        • 1. Re: Help me please, How can I inline the function?
          843829
          The java runtime does inlining automatic by gathering profiling information during runtime, so no manual inlinig is needed.
          I suspect something else stange is going on here ...

          My profiler says that almost all time is spent inside the get method, so probably something is going wrong there?

          - Clemens

          Edited by: linuxhippy on Apr 29, 2009 9:19 AM