What Impact Do Static HashTables and Classes have on the CPU?

[Mark S.]

Hello,

I've written a high performance web app with C# and it completely relies on
static hash tables (using sync) and classes. Under real world stress this
app is handling 5 get requests per CPU per second.

I've gone from a single-core/single-proc, to a dual-core/single-proc to a
dual-core/dual-proc and as I suspected the number of requests per second per
CPU does not increase it remains at 5 per CPU.

My reading of IIS threading suggests that 10-12 per requests per second can
be expected from a non-static class based app. If this assumption is
correct, do you have any suggestions on how I might be able to increase the
number of requests per second?

TIA

 

[Ignacio Machin \( .NET/ C# MVP \)]

Hi,

I think that your problem may be that you need to sync the access to the
static elements, in this escenario only one thread can access a given
resource. of course this is a BIG constrains. Adding more processors solve
nothing and may even make the things worse as more thread can be potentally
be waiting for the resource.

why you need to use static resourcers?

 

[Alberto Poblacion]

I've written a high performance web app with C# and it completely relies
on static hash tables (using sync) [...] any suggestions on how I might be
able to increase the number of requests per second?

If you are using System.Collections.Hashtable objects and mostly reading
them, you can make use of the characteristic of the Hashtable of being
thread-safe for multiple readers or only one writer. Instead of using sync,
use a ReaderWrtiterLock, which will give you better concurrency.

 

[Christof Nordiek]

Hi Mark,

since you are tolking about static hashtables, I suppose you are using
shared data that is shared by all requests.
Surely, you have to synchronize the access to this data, but you should try
to minimize the time, during wich each request is locked. All codeparts wich
are locked against the same lock-object will be executed, as if they were on
one thread. So fore this part of your code the dual-core/dual-proc will have
absolutly no advantage.

HTH
Christof

 

[Mark S.]

Allow me to clarification my numbers just a bit.

Using the performance monitor:
(Number of get request per second to asp.net app 2.0) / (CPU %) = N request
per second per 1% CPU.

Single single-core: 8 per
Single dual-core: 6 per
Dual dual-core: 5 per

Alberto,

If you are using System.Collections.Hashtable objects and mostly
reading them, you can make use of the characteristic of the Hashtable of
being thread-safe for multiple readers or only one writer. Instead of
using sync, use a ReaderWrtiterLock, which will give you better
concurrency.

Unfortunately each request writes.

Ignacio,

why you need to use static resourcers?

Every request makes decisions based on what the other request had written to
the static hashTable and then writes what it decided to do back. This
sequential decision makes is required by the code's business logic. If you
or anyone else has a better way to achieve this logic, I'm open to
suggestions.

THX

 

[Willy Denoyette [MVP]]

Hello,

I've written a high performance web app with C# and it completely relies on static hash
tables (using sync) and classes. Under real world stress this app is handling 5 get
requests per CPU per second.

I've gone from a single-core/single-proc, to a dual-core/single-proc to a
dual-core/dual-proc and as I suspected the number of requests per second per CPU does not
increase it remains at 5 per CPU.

My reading of IIS threading suggests that 10-12 per requests per second can be expected
from a non-static class based app. If this assumption is correct, do you have any
suggestions on how I might be able to increase the number of requests per second?

TIA

Just curious how you are stress testing this.
What's the OS the server (IIS) runs on?
What kind (OS and application) and how many clients (PC's) do you have to access the server?
What's the round-trip time for a single get request?

Willy.

 

[Mark S.]

Just curious how you are stress testing this.

In the beginning I used Web Application Stress Tool but to be honest I don't
remember the exact numbers, but it was in the ballpark.
http://www.microsoft.com/downloads/...5A-062A-439E-A67D-75A89AA36495&displaylang=en

The application is live, so the numbers I mentioned previously are real
world numbers.

What's the OS the server (IIS) runs on?

Windows 2003 SP 2 IIS 6.0 ASP.NET 2.0

What kind (OS and application) and how many clients (PC's) do you have to
access the server?

Dedicated web servers running nothing else. Application servers only aspx
pages which returns HTML and Javascript, no images are being served. All
data is stored in varioius flavors of hashTables. A timer process collects
the data and sends it to the database, the incoming requests never read or
write to the db directly. This is makes all the difference.

1.4 million unique visitors a day. 4.5 million get requests an hour during
business hours.

What's the round-trip time for a single get request?

As you know being a web app the time will depend on the network, but to give
you a baseline, removing the most the network latency. Here's how long it
takes from the dev server to the live web farm:

6K file gziped (iis) to 2.3K: 0.041 seconds (half the time there's 0.100
second additional delay)
7byte file: 0.009 seconds
3K file gziped (iis) to 1.3K: 0.028 seconds (half the time there's 0.100
second additional delay)

HTH

 

[Jon Skeet [C# MVP]]

I've written a high performance web app with C# and it completely relies
on static hash tables (using sync) [...] any suggestions on how I might be
able to increase the number of requests per second?

If you are using System.Collections.Hashtable objects and mostly reading
them, you can make use of the characteristic of the Hashtable of being
thread-safe for multiple readers or only one writer. Instead of using sync,
use a ReaderWrtiterLock, which will give you better concurrency.

ReaderWriterLocks have fairly hefty overheads - unless the work you do
within the lock is significant, the overhead could well be more than
the gain due to more concurrency.

 

[Bruce Wood]

Every request makes decisions based on what the other request had written to
the static hashTable and then writes what it decided to do back. This
sequential decision makes is required by the code's business logic. If you
or anyone else has a better way to achieve this logic, I'm open to
suggestions.

OK... I'll take a crack at it.

First, though:

1. What are the keys in the hash table? What do they represent?
2. How many keys can there be?
3. How are they structured?
4. How (and when) can new keys be created?

Once I know the answers to these questions, perhaps I can suggest a
better structure.

A preview... what I'm thinking now.

The problem with a hashtable is that the correspondence between a key
and the corresponding hash bucket and its chain of keys is arbitrary.
This means that two threads writing to the same hashtable practically
have to lock the whole structure and therefore run serially.

If, however, you could create a different structure that understands
the structure of your keys, you might be able to selectively lock only
parts of the structure. Viz: one thread writing to the structure under
key A might be able to run in parallel with another thread writing
under key B if the two keys have nothing in common within the data
structure. If you were, for example, to roll your own hash table, you
could attach a different lock object to each hash bucket, and lock the
buckets individually rather than taking out a lock on the entire
table.

Of course, whether this gives you improvements in concurrency entirely
depends upon the nature of your problem. If it is highly likely that
all threads will be working on the same key at the same time then it
doesn't buy you much. If, on the other hand, multiple threads are
likely working on different keys at the same time, and the keys can be
structured so that they are unlikely to land in the same part of the
collection structure, then it's highly likely that threads will run
without any locking contention whatsoever.

As usual, the answer is, "It depends." It depends upon the answers to
those questions, above.

 

[Willy Denoyette [MVP]]

In the beginning I used Web Application Stress Tool but to be honest I don't remember the
exact numbers, but it was in the ballpark.

I see, that means that (IMO) the shared hashtable lockings aren't the real bottleneck, isn't
it?, if they were, you would have topped at approx. the same figures you are seeing now.
I would suggest you to profile your application on a staging server, in order to pin-point
the bottleneck. Another option is to take regular snap-shot dumps of the running application
using adplus.vbs and investigate the dump off-line using Windbg.exe and sos.dll.

Willy.

 

[Chris Mullins [MVP]]

I've written a high performance web app with C# and it completely relies
on static hash tables (using sync) and classes. Under real world stress
this app is handling 5 get requests per CPU per second.

If you're only getting 5 requests per second, then I suspect you're doing
alot more than reading & writing values to a hashtable.

If that is in fact all you're doing, and you're only getting 5 requests per
second, you need to re-evaluate your algorithm from the ground up, as you
should be getting a number that requires scientific notation to properly
describe.

 

[Mark S.]

Chris,

You're right, but failed to accurately describe my numbers, below I've
reposted the carination. It clarification runs really fast 400 get requests
a second takes 35% CPU.

Allow me to clarification my numbers just a bit.

Using the performance monitor:
(Number of get request per second to asp.net app 2.0) / (CPU %) = N request
per second per 1% CPU.

Single single-core: 8 per
Single dual-core: 6 per
Dual dual-core: 5 per

 

[Mark S.]

Bruce,

I think you're on to something good here. Let's see what we can come up
with.

1. What are the keys in the hash table? What do they represent?
3. How are they structured?

The keys are GUID and they represent a collection data. A background process
grabs xml from the database and massages it into a struct of arrays.

So the keys are GUID and the values are a struct.

public static Hashtable myHash = Hashtable.Synchronized(new Hashtable());

public struct myStruct
{
public string html;
}

public static String myLogic(String targetID) {
if (myHash.Contains(targetID))
{
lock (myHash.SyncRoot)
{
struct myStruct = (struct)myHash[targetID];
// read data, make decisions based on data, update struct with
results
// struct of arrays greatly simplifed for sake of this
conversation
return myStruct.html;
}
}
}

2. How many keys can there be?

Currently 208, but that will grow to 500 in a couple months and in six
months up to 1000.

4. How (and when) can new keys be created?

Whenever data entry admins change data in the database the hashTable is
updated. This happens a couple hundred times a day. A background process
reads the live hash table, corrilates it's data with the incoming data,
contructs a new seperate hashTable, and once complete, locks the live
hashTable and does a quick swap.

 

[Christof Nordiek]

Hi Mark,

would it be a problem, if between the reads and the writes of one request
there are writes of other request?
If so, you should not lock on the Hashtable, while processing the data, but
only the writes and the reads.
Otherwise, you should try to limit the data locked, f.e. only lock the key
while processing. Not easy to do, if the key is of a value type. So, an
alternative would be, to use a class as data and lock on that instance.

If serializing only the reading and writing of the data gives you this
problem, then I suppose, you have to redesign your datastructure.

Christof

 

[Bruce Wood]

Hi Mark,

would it be a problem, if between the reads and the writes of one request
there are writes of other request?
If so, you should not lock on the Hashtable, while processing the data, but
only the writes and the reads.
Otherwise, you should try to limit the data locked, f.e. only lock the key
while processing. Not easy to do, if the key is of a value type. So, an
alternative would be, to use a class as data and lock on that instance.

OK... that beats my idea hands down.

Christof is right: you have two locking scenarios here:

1. Adding a new key to the hash table: need to lock the whole table.

2. Manipulating the data structure that is under one key: make it a
class and lock the instance in the hash table.

The very fact that you want to manipulate the data that's already in
the hash table, rather than just writing it once and possibly deleting
it later, says that you want these to be classes, not structs. Plus,
by making them classes, you get the added benefit that you can lock on
them.

So now you can have one thread updating one instance and another
thread updating another instance and they won't collide.

The only time you need to lock the whole thing is when you add a new
key and when you're fetching instances to update. If even this
contention is too much for you, then you can move to the solution I
proposed: roll your own hash table structure, and allow for locking on
individual hash buckets. If you do this, then the pseudo-code would
be: calculate hash value for GUID, calculate bucket index from hash
value, lock bucket, fetch data instance, lock data instance, unlock
bucket, update data instance, unlock data instance. This improves
concurrency because a thread that is manipulating / searching the hash
chain at bucket #15 isn't in contention for a lock with another thread
that is manipulating / searching the hash chain at bucket #3, and even
if threads are updating class instances in the same chain, they need
to lock the bucket only long enough to find the item they want to
update.

If you allow for deletions from the hash table, then the thread doing
the deletion has to lock both the table (or the bucket) _and_ the item
to be deleted, to ensure that nobody else is updating the item while
it's being deleted.