Data loading Hash Map

Question

I'm trying to improve my code's performance, and I've found an area where the execution time is being significantly increased. I've had a look through the code but I can't see how I can improve it.

AddData gets called over 200,000 times.

public void AddData(String label, int fromid, int toid, double distance, boolean oneway, int speedlimit) 
    {     
        currentRoad = new Edge(label, fromid, toid, distance, speedlimit, oneway);

        tempVertex = allVertices.GetValue(fromid);
        tempVertex.addEdge(currentRoad);         
        allEdges.AddItem(currentRoad);  
        if (!oneway)
        {
            currentRoad = new Edge(label, toid, fromid, distance, speedlimit, oneway);
            tempVertex = allVertices.GetValue(toid);
            tempVertex.addEdge(currentRoad);
        }         
    }

The method within the AddData function that takes a large proportion of the time is allEdges.AddItem().

allEdges is a Hash Map containing vectors of Edges. (Edges is a class).

Here is my implementation of the Hash Map AddItem function:

public void AddItem(Edge value)
  {
       if ((noofitems/data.length) > 0.7)
       {
           long time = System.nanoTime();
           EdgeHashPair[] newMap = new EdgeHashPair[data.length * multiplier];  
           multiplier = 8;
            for (EdgeHashPair oldMap1 : data) 
            {
                if (oldMap1 != null) 
                {
                    int index = HashFunction(oldMap1.data.GetItem(0).label);
                    int increment = 1;
                    index = index % newMap.length;
                    boolean inserted = false;
                    while (!inserted) 
                    {
                        if (newMap[index] == null) 
                        {
                            newMap[index] = oldMap1;
                            inserted = true;
                        } 
                        else                        
                        {                            
                            index = index + (increment<<1);
                            index = index % newMap.length;
                        }
                    }      
                }
            }
           data = newMap; 
           System.out.println("Hash map resizing took: " + ((System.nanoTime() - time)/1000000) + "ms");
       }


        int index=HashFunction(value.label);
        index = index % data.length;        
        int increment = 1;
        boolean inserted = false;
        while (!inserted)
        {                  
            if (data[index] == null)
            {
                data[index] = new EdgeHashPair();
                data[index].addItem(value);
                noofitems++;
                inserted = true;
            }
            else
            {
                if (data[index].data.GetItem(0).label.compareTo(value.label) == 0)
                {
                    data[index].addItem(value);
                    inserted = true;
                    noitems++;
                }
                else
                {
                    index = index + (increment<<1);
                    index = index % data.length;
                }
            }           
        }   
  }

Hash function:

      private int HashFunction(String key)
      {
        // Task 1 code: Hash the key and return a long value
        int code = 29;     
        for (int i=0; i < key.length(); i++) 
        {
            code = code*53+(key.charAt(i));
        }    
        return (code < 0 ? -code : code);
  }

From timings I've done, the loading of data currently takes around 50% of my execution time (around 1000ms), which I feel is extremely high and would love to be able to reduce this.

Edit: The program is a navigation application, it stores edges and vertices and then calculates many routes.

To make life easier for reviewers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. See also this meta question — Simon Forsberg♦, Apr 28 at 9:46
Right, we have no idea what it does, and especially, I can't see why java.util.HashMap shouldn't be used. — maaartinus, Apr 28 at 15:42

Pimgd · Answer 1 · 2015-04-28 11:59:01Z

Let's talk about this bit of code.

    int index=HashFunction(value.label);
    index = index % data.length;        
    int increment = 1;
    boolean inserted = false;
    while (!inserted)
    {                  
        if (data[index] == null)
        {
            data[index] = new EdgeHashPair();
            data[index].addItem(value);
            noofitems++;
            inserted = true;
        }
        else
        {
            if (data[index].data.GetItem(0).label.compareTo(value.label) == 0)
            {
                data[index].addItem(value);
                inserted = true;
                noitems++;
            }
            else
            {
                index = index + (increment<<1);
                index = index % data.length;
            }
        }           
    }

First, you have an else block in here...

        else
        {
            if (data[index].data.GetItem(0).label.compareTo(value.label) == 0)
            {
                data[index].addItem(value);
                inserted = true;
                noitems++;
            }
            else
            {
                index = index + (increment<<1);
                index = index % data.length;
            }
        }

... containing only an if-elseif chain. Merge these as such:

        else if (data[index].data.GetItem(0).label.compareTo(value.label) == 0)
        {
            data[index].addItem(value);
            inserted = true;
            noitems++;
        }
        else
        {
            index = index + (increment<<1);
            index = index % data.length;
        }

Second, you only use increment in a constant expression (increment<<1). Consider replacing this with the raw constant instead.

Third, you always loop at least once. So replace your while loop with a do-while loop.

Now for some design issues that could lead to reduced performance...

                int index = HashFunction(oldMap1.data.GetItem(0).label);

    int index=HashFunction(value.label);

When you resize the map, you rehash all the entries, even although their values didn't change. Store the calculated hash in the item.

    for (int i=0; i < key.length(); i++) 
    {
        code = code*53+(key.charAt(i));
    }

When you hash the key, you do so via for-loop over String.length() and String.charAt. These are two function calls, and String.charAt continuously checks the length. Consider declaring a char array of length key.length(), then setting it with String.getChars. I'm assuming you have keys of a decent length here, and not very short. Do several performance tests for this, at different times and with different sets of data.

Performance-tuning your code is likely to be hard without semantics surrounding your code and timing information. See if there's ways to profile which functions take longest... on a more granular level than just this function.

Thank you for taking the time to look over the code and suggest things :) I've already changed my while loops to do-while! Regarding the length of the strings, I'll attempt this first and see what the performance is like! For your last suggestion about collecting all the data first into an array, do you mean creating a large array of Edges, storing all the data in there and then iterating over the array and putting them into the Hash map/Vertices from there? — Craig, Apr 28 at 10:16
@Craig something like that. Also, depending on how much data you have, you might have memory-page issues as well, and it could be worth it to sort hashes into buckets first so that you can insert items into the hashmap one memory page at a time (and thereby avoiding page swaps). — Pimgd, Apr 28 at 10:22
As I'm reading in the data from a file, and calling AddData over 200,000 times, how would I store that data in an array without creating Edge objects? When I create an Edge array, it's null - or am I missing something? — Craig, Apr 28 at 11:16
@Craig ... I had lunch. I made a mistake, I was thinking about C structs which is just allocating a large block of memory and then writing to it. — Pimgd, Apr 28 at 12:00
Ah okay no worries :) I've changed my code to fit the suggestions you said, and have decreased the time by around 100-150 ms! — Craig, Apr 28 at 12:05

maaartinus · Answer 2 · 2015-04-28 15:41:00Z

You wrote an own hashing

   private int HashFunction(String key)
      {
        // Task 1 code: Hash the key and return a long value
        int code = 29;     
        for (int i=0; i < key.length(); i++) 
        {
            code = code*53+(key.charAt(i));
        }    
        return (code < 0 ? -code : code);
  }

but...

There's already String.hashCode.
The original uses a very tiny multiplier (31) leading to hash conflicts even for ASCII strings of length 2 and so does yours. But this rarely matters.
The original can be sped up by a factor of nearly four, but you don't use the trick.
The original gets cached in a private field String.hash, but your can not do it.
You're trying to make the hashCode positive, but you fail for Integer.MIN_VALUE.
And there's no reason for this, except when you use modulo-addressing instead of binary masking.
But it's hardly ever a good idea to use use modulo-addressing since % is many ten times slower than &.

asked	4 months ago
viewed	64 times
active	4 months ago

current community

your communities

more stack exchange communities

Data loading Hash Map

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged java performance graph hash-table or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Data loading Hash Map

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java performance graph hash-table or ask your own question.

Related

Hot Network Questions