Dears, I had a question regarding to RtlLookupElementGenericTableFullAvl .
From MSDN, there is a word for this function :
“If a matching element is found, RtlLookupElementGenericTableFullAvl rebalances the generic table’s AVL tree.”
My question is, is it necessary to rebalances the AVL tree after Lookup? Because this characteristic will make it impossible to use ERESOURCE to synchronizing the RTL_AVL_TABLE table, result in performance issue.
Does anybody know is this a MSDN documentation issue? Or RtlLookupElementGenericTableFullAvl have a reason that must perform rebalances after lookup ?
Thnaks in advance.
xxxxx@trend.com.tw wrote:
Dears, I had a question regarding to RtlLookupElementGenericTableFullAvl .
From MSDN, there is a word for this function :
“If a matching element is found, RtlLookupElementGenericTableFullAvl rebalances the generic table’s AVL tree.”
My question is, is it necessary to rebalances the AVL tree after Lookup? Because this characteristic will make it impossible to use ERESOURCE to synchronizing the RTL_AVL_TABLE table, result in performance issue.
Does anybody know is this a MSDN documentation issue? Or RtlLookupElementGenericTableFullAvl have a reason that must perform rebalances after lookup ?
That is the ‘beauty’ of an AVL tree, it re-balances after a successful
lookup to ensure that the most commonly accessed nodes are close to the
root. Therefore they will take less time to locate the next time around.
You can still use an ERESOURCE but it must be taken exclusively due to
this characteristic. As well, you can use a fast mutex for the locking,
assuming you are running at <= APC level.
Pete
–
Kernel Drivers
Windows File System and Device Driver Consulting
www.KernelDrivers.com
866.263.9295
Thank you, Pete.
Do you know is it possible to do both shared and exclusive access on Rtl…GeneralTable APIs ?
Because serializing access to splay/AVL tree structure can have major performance implications.That is what I am worry about.
Per my understanding,
An AVL tree rebalances only on additions and deletions.
Splay tree rebalances on lookups.
I rechecked on wikipedia, my understanding seems to be correct.
http://en.wikipedia.org/wiki/AVL_tree#Lookup
So I went and looked at the documentation of RtlLookupElementGenericTableFullAvl.
The documentation says that this API is used for AVL trees and not splay trees.
However, the documentations says further that:
“If a matching element is found, RtlLookupElementGenericTableFullAvl rebalances the generic table’s AVL tree.”
So: Is Microsoft’s implementation a variation of the traditional AVL tree? Or is there a documentation bug here?
(I would assume it’s a documentation bug.)
xxxxx@trend.com.tw wrote:
Thank you, Pete.
Do you know is it possible to do both shared and exclusive access on Rtl…GeneralTable APIs ?
Because serializing access to splay/AVL tree structure can have major performance implications.That is what I am worry about.
From what I have experienced with these APIs is that the lookup
routines all perform a rebalance in order to optimize the lookup of the
most recently accessed elements. Thus you need to exclusively protect
the tree when performing the lookup.
Because of this as well as my stubbornness, I implemented my own btree
routines. They are trivial to implement and you have control over what
is happening.
Pete
–
Kernel Drivers
Windows File System and Device Driver Consulting
www.KernelDrivers.com
866.263.9295
On 12/16/2009 8:56 AM, Peter Scott wrote:
xxxxx@trend.com.tw wrote:
> Thank you, Pete.
> Do you know is it possible to do both shared and exclusive access on
> Rtl…GeneralTable APIs ?
> Because serializing access to splay/AVL tree structure can have major
> performance implications.That is what I am worry about.
From what I have experienced with these APIs is that the lookup
routines all perform a rebalance in order to optimize the lookup of the
most recently accessed elements. Thus you need to exclusively protect
the tree when performing the lookup.
Because of this as well as my stubbornness, I implemented my own btree
routines. They are trivial to implement and you have control over what
is happening.
Pete
The AVL tree package does not rebalance the tree on lookup. It only
does so on insert and delete (I just verified with a look at the code).
It is not necessary to have exclusive access to an AVL tree when
looking up, only when inserting and deleting. Shared access suffices on
lookup.
The MSDN documentation is wrong, and I have contacted the doc writer to
fix it.
–
Christian [MSFT]
This posting is provided “AS IS” with no warranties, and confers no rights.
The issue is that the AVL version does not rebalance, but the Splay
version DOES rebalance (since that’s the point of splay trees.)
So you should be careful to pick the version that yields the behavior
that you are seeking. To be honest, I’m not sure when the AVL trees
were added - it looks like it might have been for XP, perhaps Windows
2000. I know that I stopped using the generic table package pre-Windows
2000 because of the exclusive locking requirements. Of course, these
days we try to use lock free dynamic hash packages anyway as much as
possible, since eliminating locks and most waits (you only need to wait
when resizing the hash table) yields better performance.
Fixing the documentation will be good, since it will then at least
encourage people to use the AVL tree package.
Tony
OSR
>that you are seeking. To be honest, I’m not sure when the AVL trees
were added - it looks like it might have been for XP
XP.
–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com
I have a wee problem related to RtlLookupElementGenericTableFullAvl.
The export is missing from NTDLL.DLL on XP SP3. It is present in NTOSKRNL.EXE and exported.
I call this routine from user-mode code, and on other OS’s it’s fully exported and works fine.
I cannot use RtlLookupElementGenericTableAvl as I need the values of the other parameters to the “full” version.
I’ve thought of a few NASTY hacks to try to get around this.
-
RtlLookupElementGenericTableAvl calls RtlLookupElementGenericTableFullAvl and discards the parameters I need on the stack. They will likely be there on the stack upon return to my routine, and I could access them with some assembler code (since this is xp, I can assume x86).
-
Hard code the address (validate the “correct bytes” are present at the address expected). I could grab the address from the call instruction embedded in the non-Full version.
Surely there has to be a better solution than these?
I would use stl maps in user land!
I think they use Red Black balanced BST’s.