There isn’t enough data to say anything real about his problem, but there’=
s several
things that may be going wrong, besides the obvious spinlock implementatio=
n issue.
He seems to be searching for a node value inside a critical section, that’=
s not a
good idea. Now, there’s several things that might be causing the slowdown,=
here’s
some things to try.
A hash table may help if collision chains are kept short enough, but that =
may be
only part of the issue. I would for example do a test run forcing retrieva=
l to always
access the first key, to see if performance is being lost because of synch=
ronization
or because of the search. If I implemented the hash table, I would do a fe=
w test runs
on sample data to make sure my collision chains are short enough.
Note that it’s a sledgehammer approach to just acquire a spinlock every ti=
me one
reads or writes to the queue. If he can have multiple readers concurrent o=
n the
queue, but only one writer, he can try this:
Reader( )
{
acquire(rSpin);
nreaders++;
if (nreaders=3D=3D1) acquire(wSpin);
release (rSpin);
dequeue( );
acquire(rSpin);
nreaders–;
if (nreaders=3D=3D0) release(wSpin);
release(rSpin);
}
Writer( )
{
acquire(wSpin);
enqueue( );
release(wSpin);
}
The way it works is, once the first reader grabs the wSpin lock, subsequen=
t readers
don’t need to spin waiting. Remember, only writes must be synchronized ! T=
his
however gives priority to the readers, use with care. And of course, if he=
needs to
update the queue at every read, that’s a different question. A variation o=
f this
technique is the following course-grained solution,
Reader( )
{
acquire(rSpin);
while (nWriters>0);
nReaders++;
release(rSpin);
dequeue( );
lock{nReaders–};
}
Writer( )
{
acquire(rSpin);
while (nReaders>0 || nWriters>0);
nWriters++;
release(rSpin);
enqueue( );
lock{nWriters–};
This is a bit lighter on the writers. As I originally said in my other pos=
t, Readers and
Writers is a well studied problem. I recommend going into a good textbook,=
there’s
plenty of suggestions on how to make it run better.
Another point is, if he’s looking up the list, using a linked list may be =
a bad idea for a
number of reasons, if nothing else because pointer chasing is slow and tax=
es the
cache. One way to do it is to structure the queue as an array of pointers,=
this will
help keeping cache locality and it might even allow one to use a rep scas =
to search
for that value.
The problem with an AVL tree in this context is that removals require writ=
ing to the
data structure, which would negate most of the benefits of the Reader/Writ=
er
synchronization logic. But, in that direction, I would prefer to structure=
the data as a
priority queue using his search argument as priority, that will guarantee =
log time
access and no need to implement AVL rotations which may be tough to debug.=
A
priority queue can be simply implemented as an array, because the children=
of
element queue[p] are to be found at queue[2*p] and queue[2*p+1]. This may =
avoid
searching, which is particularly advisable if done inside a spinlock !
Last but not least, he should make sure he’s not allocating memory inside =
a critical
section.
Alberto.
On 25 Dec 2003 at 22:03, Jake Oshins wrote:
I second Don’s suggestion. As I said before, your biggest problem is
that you need better data-management algorithms. An AVL tree might be
simpler than the hash table and it might solve your performance
problems.
–
Jake Oshins
Windows Base Kernel Team
This posting is provided “AS IS” with no warranties, and confers no
rights.
“Don Burn” wrote in message news:xxxxx@ntdev…
>
> Synchornizing Access to a Linked List: complete pictureConsider using
> a hash function based on the first field you mention to split the list
> into multiple lists each with an associated spin lock. This should
> improve performance in both the single processor case where the list
> is long and the multiprocessor case by reducing lock contention.
>
> Don Burn (MVP, Windows DDK)
> Windows 2k/XP/2k3 Filesystem and Driver Consulting
>
> ----- Original Message -----
> From: I=F1aki Castillo
> To: Windows System Software Devs Interest List
> Sent: Wednesday, December 24, 2003 7:12 AM
> Subject: [ntdev] Synchornizing Access to a Linked List: complete
> picture
>
>
> Thanks for your answers. Here is the whole picture.
> The linked list I am using stores data in non paged pool space.
> The writer runs always at PASSIVE level. It allocates new nodes if
> necessary and fills up the fields on each node. Writing and allocating
> new nodes is rare. At most, it may happen 10 times per minute on an
> average loaded machine. Reading is another story. Readers are
> arbitrary threads that run at APC or DPC levels. They never run at
> PASSIVE level. The actual IRQL depends on the point from which my code
> is called. I assume DPC level all the time. Reading may be performed a
> lot of times, in the order of hundred of times per second. The reader
> perfoms each read in two steps: first it looks for the right node,
> and, if it exists on the list, it reads all the fields in the node.
> Both, writing and reading are synchronized using an ordinary (no
> Stack) Spinlock. While reading, the following tasks are performed:
> 1-Acquire Spinlock 2-Check the first field on each node, to look for a
> certain value 3-If found the right value, read the others fields of
> that node on local variables . 4-Release Spinlock There may be many
> nodes but I have checked that performance problem occurs even with
> only a couple of nodes in the list. I have checked also that node
> checking is performed correctly. There are no calls to other functions
> from within the spinlock and the data is located always in non paged
> pool. Removing synchronization completely (just for testing) improves
> speed about 30% when code is runing on multi processor machines. Of
> course this is not a solution but it means that synchronization is
> taking too much time. I know there are others ways to synchronize but
> I need one available at DPC. I have not tried the new version of
> queued SpinLocks. Thanks for your comments. Inaki.
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=3D256
>
> You are currently subscribed to ntdev as: xxxxx@acm.org
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=3D256
>
> You are currently subscribed to ntdev as: xxxxx@ieee.org
> To unsubscribe send a blank email to xxxxx@lists.osr.com