[fpc-devel] TAVLTree(avl_tree.pp) thread safety, fcl-xml(DOM) is also concerned.

Sergei Gorelkin sergei_gorelkin at mail.ru
Wed Aug 6 21:37:55 CEST 2008

Mattias Gaertner wrote:
> On Wed, 6 Aug 2008 19:41:27 +0100
> "Inoussa OUEDRAOGO" <inoussa12 at gmail.com> wrote:
>> Hi,
>> TAVLTree in avl_tree.pp is not thread safe due to the node
>> allocation and de-allocation done through the global
>> declared "NodeMemManager" variable. TAVLTreeNodeMemManager
>> implementation is cleary not thread safe, which btw IMHO
>> is a good thing ( for performance reason).
>> Proposition :
>> (a) TAVLTree should allow, at construct time, to
>>     specify a Node memory manager which will be kept and used.
>>     If not specified the global one will be used.
>> (b) "NodeMemManager" should be declared as "ThreadVar".
>> This changes does not break the API while making the
>> implementation thread safe.
>> By the way note that the XML DOM's implementation
>> ( TDOMNode_WithChildren ) uses TAVLTree, so every code that uses the
>> fcl-xml package mainly the DOM unit, is not thread safe. If this
>> proposition is accepted it will be nice to have it introduced in the
>> soon to be release fpc 2.2.2, in the case that is still possible,
>> mainly for server programming.
>> Attached is a patch that demonstrate the above proposition.
> Providing a local node mem manager does not repair xml dom.
> Maybe move NodeMemManager to the interface, so that a user can replace
> it with a threadsafe one?
Since this topic is touched, I would like to vote for removing avl_tree 
dependency from the DOM altogether. The reason is that the avl tree of 
child nodes is useless for any real-world XML data because it does not 
handle duplicate names. The tree is useful only for the one particular 
case of XML configs where each node name is unique. OTOH, it causes 
considerable performance penalties (each insert results in two searches, 
  first one for checking the existence, second one for insert itself; 
each search is a number of calls to Node.GetNodeName, which, in case of 
Windows, is a Widestring copy, etc.)
Therefore I'd suggest to remove the avltree from DOM. In order to keep 
configs at the reasonable speed, it is possible to implement indexing 
within TXMLConfig class itself, preferably hashmap-based. Alternatively, 
it is possible to use Registry-like access (OpenKey/CloseKey methods) 
that I had already implemented in newer xmlconf.pp unit. The advantage 
is that the searches are done starting from the 'opened key', not from 
the root, so linear search isn't too slow.


More information about the fpc-devel mailing list