This discussion is archived
1 Reply Latest reply: Apr 29, 2009 9:23 AM by 843829 RSS

Help me please, How can I inline the function?

843829 Newbie
Currently Being Moderated
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 Newbie
    Currently Being Moderated
    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