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.

Best regards.

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?

Mattias

Huh? What's the point of having a global (read: constant) default declared as threadvar? So, (b) is unnecessary (at least in your patch).

Another solution would be to declare it as ThreadVar and overwriting it upon construction.

But wait... this makes me think if we can't do it automatically: If we have a new thread, we need a new instance in most cases anyway (except when there's actually only one thread handling XML-data, which I consider rather unlikely).

This changes does not break the API while making the implementation thread safe.

Depending solely on the discipline of the caller. And consider the XML-case, it wouldn't even be possible without changing this API, too. And most likely a lot of other APIs on the way to tackle it down.

As I just pointed out, it wouldn't make handling XML data threadsafe. There's no way to specify upon creation of the TXMLDocument that this will be used in another thread, needing a new NodeManager instance.

Vinzent.

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.

Regards,
Sergei

2008/8/6 Mattias Gaertner :

A "threadvar" declared variable is local to the calling thread. But if object is modified in more than one thread, indeed there are still some problems ( for objects using the default manager ) : Thread A create a node n1 and the node is released in ThreadB .

Maybe move NodeMemManager to the interface, so that a user can replace it with a threadsafe one?

Good solution, but : if ThreadA create an avl object that is _exclusively_ used in ThreadA, why should ThreadA wait in a multithreaded node mem manager? That is when comes the constructor that takes a node mem manager. That way, ThreadA could provide a local node mem manager that is not multithreaded and thus not paying penalty of multithreaded node mem manager.

2008/8/6 Vinzent Höfler :

Indeed.

The variable is currently initialized via the initialization section. A ThreadA creating a TXMLConfig, which creates a tree will have no mem manager.

Yes, threadvar is a good idea. But still a thread needs to initialize it.

But a structure with less mem might be even better for dom xml as already mentioned by Sergei.

Mattias

Mattias

2008/8/6 Mattias Gaertner :

You are absolutely rigth.

But a structure with less mem might be even better for dom xml as already mentioned by Sergei.

Indeed. But the avl implementation provided can be used without xml. So my second proposition :

Another proposition is to introduce a base avl class say TBaseAVLTree that defines two abstract virtual methods "NewNode()" and "FreeNode()" and then define :
- TAVLTree : that _do not_ use a node mem manager
- TAVLMangedTree that uses a node mem manager provided in the constructor

TBaseAVLTree = class
...
protected
  function NewNode() : TAVLTreeNode;virtual;abstract;
  procedure FreeNode(ANode : TAVLTree);virtual;abstract;
...
end;
TAVLTree = class(TBaseAVLTree)
protected
  function NewNode() : TAVLTreeNode;override;
  { implemented as
    begin
      Result:=TAVLTreeNode.Create();
    end;}
  procedure FreeNode(ANode : TAVLTree);override;
  { implemented as
    begin
      if ( ANode  nil ) then
        ANode.Free();
    end;}
end;
TAVLMangedTree = class(TBaseAVLTree)
private
  FNodeMemManager : TAVLTreeNodeMemManager;
protected
  // these implementations use FNodeMemManager
  function NewNode() : TAVLTreeNode;override;
  procedure FreeNode(ANode : TAVLTree);override;
public
  constructor Create(OnCompareMethod: TListSortCompare;
ANodeMemManager : TAVLTreeNodeMemManager);
end;

Yes. But the reference this threadvar is pointing to is _not_.

ThreadVar don't help here unless you provide them with a different node manager reference in each thread which is kind of senselessly redundant considering that your patch already can provide a local reference for each instance created.

And even so, the XML code does not call this new API unless changed, so your patch actually changes nothing in regard to the XML data.

It only works in cases where I directly instantiate an AVLTree. Or, how else is me - the programmer - supposed to know if a class uses an AVLTree or not? And even if I knew that (by digging through the whole source), I couldn't do anything about it, because the classes don't provide that interface to me. IOW: I don't have control over it.

[moving NodeManager to interface]

Good solution, but : if ThreadA create an avl object that is _exclusively_ used in ThreadA, why should ThreadA wait in a multithreaded node mem manager?

That's where a ThreadVar becomes useful: Each thread could install its personal instance of the (unsafe) NodeMemManager via this "global" (yet thread-local) reference. No further changes to the code needed, but the programmer must be aware of this problem each time he creates a thread using any instance of the AVLTree directly or indirectly.

That's surely not a nice solution, but something you can at least work with. Although it still smells rotten to me.

That is when comes the constructor that takes a node mem manager. That way, ThreadA could provide a local node mem manager that is not multithreaded and thus not paying penalty of multithreaded node mem manager.

That's theoretically possible (but then again, this is perfectly solvable without ThreadVars), but this change in the API must then be followed up to *any* class that /might/ use an AVLTree instance to be any effective. I'd say: No way to do that, especially not in the timeframe you propose. And then you may consider the required changes to all the existing code, to make that actually thread-safe...

IMO, the least intrusive change would be to define the NodeManager as ThreadVar and let it "somehow" determine if it's running in a new thread and then overwrite the thread local variable with a new instance. It would leave all existing interfaces untouched and even would make already existing code automatically thread-safe in that regard.

Of course, removing the usage of the AVLTree altogether would achieve about the same, but would be a slightly more intrusive change.

Vinzent.

2008/8/6 Vinzent Höfler :

Even this schema is not thread safe : ThreadA create a avl and populate it. ThreadB
delete some nodes of that avl. The deleted nodes have been created using ThreadA's
node mem manager while collected by ThreadB's node mem manager.

Of course, removing the usage of the AVLTree altogether would achieve about the same, but would be a slightly more intrusive change.

Introducing a AVLTree implementation that skip alltogether the node mem manager ( see my second proposition about TBaseAVLTree, TAVLTree and TAVLManagedTree) seems like a non breaking change still being thread safe and providing a way to use
a node mem manager whenever needed.

Perhaps another option is to remove the NodeMemManager altogether and simply use GetMem/FreeMem (or New/Dispose)?

Micha

2008/8/6 Micha Nelissen :

The second proposition contains a default TAVLTree that remove the node mem manager and TAVLManagedTree that has a node mem manager for people who do need it that way.

Was that (a) or (b)? I didn't see this?

Micha

This would be great to have in 2.2.2.

In order to keep configs at the reasonable speed, it is possible to implement indexing within TXMLConfig class itself, preferably hashmap-based.

This would be a performance tweak which (from my POV) does not need to be in 2.2.2, although it would be nice.

If I understand correctly, this would change the usage of xmlconfig which would require changes to any existing code using it? If so, it's probably not an option for 2.2.2, maybe even not for 2.2.4 ..

regards
Burkhard

Zitat von Burkhard Carstens :

The widestrings version is slow under linux too. Last time I tested (a few months ago) it was about 2 to 10 times slower than the ansistring version. Mainly because of the parser.

The performance penalty without the trees can be quite big for things like txmlconfig. For example for lazarus project files it can be a hundred times slower without the trees.
Note: lazarus itself uses its own ansistring version of xml parser, so this not a direct problem for lazarus.

I second that. The main advantage of TXMLConfig is it's easy usage. I guess you can gain some speed by implementing some kind of caching for paths. Maybe I will do that for the lazarus ansistring version. But IMO this is too risky for fpc 2.2.2 which is released soon.

About avl tree:
For thread safety I guess the best thing is to not use the node mem manager.

Mattias

What about this:
* let TAVLTree access the node manager using a local reference (TAVLTree.FNodeMemManager)
* in TAVLTree.create:

  if IsMultiThread then
    FNodeMemManager:=TAVLTreeNodeMemManager.create
  else
    FNodeMemManager:=NodeMemManager;

* in TAVLTree.destroy:

  if IsMultiThread then
    FNodeMemManager.free;

This way, nothing would change for single threaded apps but it would be fully threadsafe for multithreaded (AFAIKS). This is probably not a perfect solution, but the least intrusive one ..

regards
Burkhard

I would add nodemgr as parameter to create, but with a default value of nil. If not NIL then just grab the default nodemanager.

That way, people with multithreading concerns can override, and it is perfectly backwards compatible.

There is no good system to do this kind of stuff automatic:
- I might have threads but
only read a xml config in the mainthread, no need for locks
- I might have a dozen xml readers somewhere, and they all get an own pool of nodes, inflating memory. _IF_ it is multithread.

Am Donnerstag, 7. August 2008 11:15 schrieb Burkhard Carstens: [...]

This would have been too easy :-)

IsMultiThread is false until the first thread is started, so we can't use that. However, we could use a global var in avl_tree interface like "var ThreadSafeAVLTree : boolean = false;" instead. This way, we don't have it threadsafe automatically, but if needed, the developer can set this to true before instantiating the first AVLTree. This is still more than we have now without breaking anything existing .. A big "Note: if you want to use it in multithreaded app, please set ThreadSafeAVLTree:=true; before creating the first instance" in the docs of AVLTree and XML would be helpfull of course.

regards
Burkhard

You mean "if nodemgr = nil" then grab the global one ? This wouldn't help much for the xml stuff or other things using avltree internally (if there are any), unless you introduce this additional parameter there, too.

That's true, but considering the fact that it's not threadsafe at all now .. even worse: consider a multithreaded app, that uses an avltree in one thread and a xmldocument in another thread ... this would give hard to find strange errors and the user (developer) doesn't even see a relation between avltree and xml, unless he digs into xml sources ..

However, see my other reply to my own post: using "IsMultiThread" won't work anyway so I already refrained from auomatic handling.

regards
Burkhard

Correct. But better do it correct directly. The kind of workarounds described here are fine for a single app, but not something you put in libs.

If you are so worried about that, give the XML units an own avl node mgr, that they always pass. But IMHO doing it right is important now.

Btw, this is also one of the reasons why I never do significant work in a constructor. This way, you always have to expand parameters in the constructor, facing incompabilities and inheritance problems.

If the constructor doesn't do stuff like loading the file, you can simply use a setter.

This will change soon. I've almost completed the improved parser which is very competitive with ansistring one (about 3 times faster than current implementation, twice faster than MSXML parser).

xmlconf is source-level compatible with xmlcfg, you can replace it in uses clause and the code should remain working (although slower). Later on, you can start replacing things like

s1 := cfg.readstring('foo/bar/value1');
s2 := cfg.readstring('foo/bar/value2');

with

cfg.OpenKey('foo/bar');
s1 := cfg.readstring('value1');
s2 := cfg.readstring('value2');
cfg.CloseKey;

In this simplest example, the code becomes more complicated. However, most real projects compose the paths from parts, and they no longer need to do that.

The above also means that the key caching implemented in xmlconf may be back-ported to xmlcfg without breaking the existing user code.

Sergei