Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 293
  • Last Modified:

Hashtable performance 1500 hits per second

Hashtable gets hit 1500 times per second.

Each hit consists of a loop requiring adding/removing entries based upon a numbered index.

Hashtable must be synclocked since multiple threads will be hitting it simaltaneously.

How will the hashtable hold up if speed is of the most importance?

0
Hepen
Asked:
Hepen
  • 6
  • 5
  • 4
2 Solutions
 
anyoneisCommented:
Just a few ideas - no facts... How many entries? Part of the efficiency of a HashTable depends on the hash function - is the value you are going to be using for a key "well-hashable" (I'm sure there is a real word for that... :-)

What do you mean by "based on a numbered index." If that is really how you want to access it what you really want is an ArrayList? Or better yet, the List generic class.

David
0
 
HepenAuthor Commented:
400000 entries.

The keys will be like:
2
3
4
5
6
7
19
20
21
22
23
28
29
402
403
404
405

I need to use the fastest object. I think it is a hashtable I could be wrong.  I need a "key" that is important.
0
 
anyoneisCommented:
An integer hash should be pretty efficient. You ar etreating it like a sparse array. Sounds workable to me.
0
Configuration Guide and Best Practices

Read the guide to learn how to orchestrate Data ONTAP, create application-consistent backups and enable fast recovery from NetApp storage snapshots. Version 9.5 also contains performance and scalability enhancements to meet the needs of the largest enterprise environments.

 
HepenAuthor Commented:
sparse array? .. hmmm do u suggest something better and more efficient?

Key & Object  

0
 
fffej78Commented:
So if you know exactly how many entries there are and the keys are known, why aren't you just declaring two arrays of the maximum size and implementing the map interface on top of that?

    class MyMap : IDictionary<int,Object>
    {
        private int[] keys = new int[400000];
        private Object[] values = new Object[400000];

        public void Add(int key, object value)
        {
            keys[key] = key;
            values[key] = value;
        }

       // And so on...
     }

In fact why do you have integer keys?  If you have that why don't you put things in an array?

public class NotReallyAMAp
{
  Object[] object = new Object[ 400000 ];

  Object get( int key )
  {
     return object[ key ];
     //or if you really start from the number 2
     // return object[ key - 2 ];
  }
}

"Hashtable must be synclocked since multiple threads will be hitting it simaltaneously"

Are you sure?  For example, if two threads are competing to remove simulataneously then that doesn't matter (whatever happens one will succeed, the other will do nothing because there is nothing to remove).  If two threads are competing to add the same object, then that doesn't matter either (one will add it, one will then overwrite with the same value).

Of course, if you have the situation where multiple threads may be writing and reading the same key at the same time, then of course you do need synchronisation!
0
 
HepenAuthor Commented:
400,000 at most.

This entire implementation is so I can keep things around 400,000 instead of 64,000,000 preset in an array.  I can save a lot of memory and use it for other things.

This information however is very helpful.. the following..............................

"Hashtable must be synclocked since multiple threads will be hitting it simaltaneously"

Are you sure?  For example, if two threads are competing to remove simulataneously then that doesn't matter (whatever happens one will succeed, the other will do nothing because there is nothing to remove).  If two threads are competing to add the same object, then that doesn't matter either (one will add it, one will then overwrite with the same value).

Of course, if you have the situation where multiple threads may be writing and reading the same key at the same time, then of course you do need synchronisation!

0
 
fffej78Commented:
To me it seems like a map / hashtable is the wrong structure.  If you have something indexed by integers, then an array is a good structure to use, especially if the size is fixed.  I'd go for the array approach unless there is a really important reason not too.  You can always implement the Map interface on top of a single array if you must have a map for interaction with something else.
0
 
HepenAuthor Commented:
so you are recommending a single array instead of a hashtable?

Array or arraylist?
0
 
fffej78Commented:
Yeah, an array of fixed size instead of a hashtable if:

* You have a fixed size number of elements
* You index via an integer and nothing else

I'd just go for a plain old array.  You have no need for any of the ArrayList extra bits and pieces (unless there is anything else you want from the structure that you haven't specified in the question).

Object[] myObjects = new Object[ 400000 ];

And access it via

Object get( int index )
{
  return myObjects[ index ];
}

Object set( int index, Object value )
{
  assert index>=0 && index<=myObjects.length; //not sure on exact syntax here this is a Java assertion :)
  myObjects[ index ] = value; // remember you have to make sure index is from 0 to 400000
}
0
 
anyoneisCommented:
fffej78's wrote:
>>Yeah, an array of fixed size instead of a hashtable if:
>>* You have a fixed size number of elements
>>* You index via an integer and nothing else

I think fffej78 is right on.

Hepen wrote:

>>Of course, if you have the situation where multiple threads may be writing and reading
>>the same key at the same time, then of course you do need synchronisation!

This is not quite correct! From online help:

"A Hashtable can support one writer and multiple readers concurrently. To support multiple writers, all operations must be done through this [Synchronized] wrapper only."

Enumeration is another issue:

"Enumerating through a collection is intrinsically not a thread-safe procedure. Even when a collection is synchronized, other threads could still modify the collection, which causes the enumerator to throw an exception. To guarantee thread safety during enumeration, you can either lock the collection [(using SyncRoot)] during the entire enumeration or catch the exceptions resulting from changes made by other threads."

Presumably, in a multiple writer situation not involving enumeration, you could use synclock, but you will get better concurrency using the Synchronized wrapper.

David




0
 
fffej78Commented:
Good point David, my mistake!

I think the point is right though, think through your specific concurrency needs before deciding that something must be sync-locked.  Don't just make assumptions just because you are using multiple threads.
0
 
HepenAuthor Commented:
so for reading i don't have to synclock.

But for writing I do?
0
 
fffej78Commented:
Is it just static data?  What are you overwriting?  What do "multiple threads hitting it simultaneously" mean?  I think you need to clarify the problem with respect to what's actually in this huge array :)
0
 
HepenAuthor Commented:
multiple threads will be reading & writing to the hashtable and there will be plenty of times where they may hit the hashtable at the same time.

From that description above it looks like a hashtable can be read without synclocking it and without having to worry about thread problems.

But for writing I have to use the syncroot. Is that correct?

The data isn't static its dynamic.  entries will be added & removed .. The size can fluxuate from 1 to 10 to 100 to 4000 to 8231 all the way to 400000 or even 500000 but it will stay between that range somewhat.
0
 
anyoneisCommented:
(Speaking of multiple threads...)

 On the HashTable approach, I was totally wrong about the Synchronized wrapper:
"Synchronized supports multiple writing threads, provided that no threads are reading the Hashtable. The synchronized wrapper does not provide thread-safe access in the case of one or more readers and one or more writers."

So, it appears to me that SyncRoot locking is required in any mixed reader/writer situation.

>> The size can fluxuate from 1 to 10 to 100 to 4000 to 8231 all the way to 400000 or even 500000 but it will stay between that range somewhat.

What is the range of the indices? The range of the count of entries is pretty large...
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

  • 6
  • 5
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now