Use SyncLock or Monitor on a binary tree

[Ken]

I have a binary tree in VB NET and insertions seem to be slow.



The program receives data from one source and inserts it into the tree.



The program receives data from another source and looks the data up in the
tree.



When inserting data into the tree, access seems to be denied the other
thread while the insert(s) are taking place. (250 - 3000 records to insert
at time)



I currently have no synchronization in place.



Should I use "SyncLock" or "Monitor" to control the access of each of the
threads?



I have not had this problem with VB6 or VC++6. I thought VB NET would at
least be an improvement over VB6, but that does not seem to be true in this
case - unless, of course, I do require some synchronization method to
achieve the same throughput.



Any ideas or thoughts would be welcome.

 

[Cor Ligthert [MVP]]

Ken,

As long as there is in one thread only written while that data is not to be
used in the other thread, than there has nothign to be synchronized. However
as soon as that data had indexes or whatever than it has.

Be aware that if it does not crash, than that is probably not the problem.

A multithreading program will need forever more processing time. Only if
there are parallel processes can the total throughput time be increased by
multithreading.

I hope this gives a simple idea, you given information is in my opinion to
less to give us more idea's

I hope that it helps anyway.

Cor

 

[Brian Gideon]

Ken,

Adding synchronization to an already slow operation is just going to
make it slower. Though, if your data structure really does need to be
accessed by more than one thread then you have no choice. You must use
SyncLock, Monitor, or other synchronization techniques.

How do you know that access is being denied to the data structure from
thread A when thread B is writing? If you're not using any
synchronization then neither thread A or B will block. How do you know
that multiple threads are even involved?

What kind of binary tree are you using?

Brian

 

[Ken]

Brian, thanks for the interest.

"How do you know that access is being denied to the data structure from
thread A when thread B is writing?'

If I perform lookups while no data is being loaded into the tree, then the
response time is acceptable. However, if data is being loaded into the tree
while I am attempting lookups, the response time can (doesn't always) span
long periods of time (7 seconds - 1 minute).

"If you're not using any synchronization then neither thread A or B will
block. How do you know
that multiple threads are even involved?"

I am assuming that multiple threads are involved because of the noticeable
problem I stated above.
If I am only performing the lookup, then the response is good.
If I am only loading data, then the response is good.


"What kind of binary tree are you using?"

A hashed index of 1000 binary trees. Not balanced.

If we used a Social Security number to insert into the tree. (<-- Not what I
am using, just call it an ID - all numbers)

Dim SSN as String
SSN = "123-45-6789"
HashTree(789).Insert(SSN)

In the tree, I look at the root node. If it is empty, this SSN would go
there. If not empty, check to see if SSN is Less or Greater than Root. Less
goes left, greater goes right.

You can see how this could become more like a linked list. I'm sure portions
of it do resemble a linked list.

I don't think that is the problem. I can put 100,000 items in a collection,
array, or linked list and access the last element much faster than 7 or 8
seconds.

One last thing: Data is received and loaded via TCPIP. Data is retrieved via
serial communications.

*******
The processor spikes as the data is being loaded into the tree from the
sockets. This is when the most notable delays in the serial communications
occur.

Are the serial ports being denied access while the large amount of data is
being loaded, or is the processor too busy to entertain any more requests
until the load finishes?
*******

VS2005, I understand, is supposed to have serial and socket support. I have
VS .Net 2003.

 

[Brian Gideon]

Ken,

I don't think I can explain the performance issue without seeing some
code or having more information. But, based on what you've said about
sockets and serial communication I'm more comfortable with your
assertion that more than one thread is involved. If that's the case
then you will need to synchronization access to the data structure.

Have you tried profiling the application to see what's taking so long
reading the data structure?

Brian