Hello,

I want to remove the avl_tree-related stuff from DOM unit. The reasons are:

1) It is targeted to optimize one particular type of documents, "configs", that require all node names within a single parent to be unique (strictly speaking, this isn't xml, it is more like ini-files or Windows registry).

For all other xml documents (which have repeating names) it simply doesn't work.

2) It is a severe performance and memory bottleneck. This maybe wasn't too noticeable in the past, but things had improved over time. Here are some numbers:

- Speed: here is the sample calltree of TDOMNode_WithChildren.InsertBefore (the main DOM tree building procedure):

650,963 * DOM_TDOMNODE_WITHCHILDREN_$__INSERTBEFORE$TDOMNODE$TDOMNODE$$TDOMNODE 25,890 > DOM_TDOMNODE_WITHCHILDREN_$__GETFIRSTCHILD$$TDOMNODE (2589x) 7,671,657 > DOM_TDOMNODE_WITHCHILDREN_$__ADDTOCHILDNODETREE$TDOMNODE (8471x) 76,239 > DOM_TDOMNODE_$__CHANGING (8471x)
8 > DOM_TDOMDOCUMENT_$__GETNODETYPE$$LONGINT (1x) 51,616 > DOM_TDOMELEMENT_$__GETNODETYPE$$LONGINT (6452x) 47,056 > DOM_TDOMTEXT_$__GETNODETYPE$$LONGINT (5882x) 36,856 > DOM_TDOMATTR_$__GETNODETYPE$$LONGINT (4607x)

As one may see, the avl_tree consumes more than 90% of total CPU time.

- Memory (numbers are for i386-linux):

TDOMAttr.InstanceSize = 56
TDOMElement.InstanceSize = 60
TDOMText.InstanceSize = 32

TAVLTree.InstanceSize = 20
TAVLTreeNode.InstanceSize = 24

Since each textnode has an associated TAVLTreeNode, and each Element/Attribute has both TAVLTreeNode and TAVLTree, the overall memory usage grows by about 75%.

3) It is known to have yet unresolved multithreading-related problems (Mantis 12984).

Given the above, I see no sense in further keeping this feature. However, the configs likely need some sort of optimization anyway. I see the following options:

1) Since all names in DOM document are now stored in a hashtable, it is easy to modify FindNode() so it compares pointers rather than strings.

2) The new xmlconf unit has the OpenKey/CloseKey methods which improve performance by limiting the search range to a specific element. Utilizing this feature, however, need modifications to the user code so it actually calls OpenKey/CloseKey (note that is works perfectly without the modifications, it's only the matter of performance).

3) It is possible to create even faster xmlconfig class, consisting of TXMLDocument + THashTable, offering O(1) access to any element. The problem is that it is somewhat mutually exclusive to the previous solution (OpenKey/CloseKey).

4) Finally, the xpath, being sufficiently mature, can supersede it all and provide a much more powerful solution.

Well... Thank you for reading this long message :-). I'd be happy to hear other's comment on it.

Regards,
Sergei

Since avl_tree was built to improve performance, this alone is reason enough to replace it with something more performant.

In the long run, I think XPath is the way to go, it's a standard, after all.

Michael.

In our previous episode, Sergei Gorelkin said:

I use the config stuff very heavily in my Delphi app at work (based on the lazarus one), and various little utils in FPC that communicate with it.

Currently the lazarus variant, but had planned to move to the FPC variant as soon as unicodestring would have been introduced.

I don't make that much use of the fact that it is avltree inside though, but I _really_ would like to keep the current interface, and not add additional requirements, since it is used fairly finely grained in my app, and making changes to how a node is retrieved is not an option. (opening/closing code is)

3) It is known to have yet unresolved multithreading-related problems (Mantis 12984).

(this is very minor afaik. The actual problem was fixed, and what is left is more the bugreporters wishlist to have one nodemgr over multiple threads, at the expense of making everything locked)

That should be enough. Performance is less of an item.

3) It is possible to create even faster xmlconfig class, consisting of TXMLDocument + THashTable, offering O(1) access to any element. The problem is that it is somewhat mutually exclusive to the previous solution (OpenKey/CloseKey).

I prefer that one.

4) Finally, the xpath, being sufficiently mature, can supersede it all and provide a much more powerful solution.

This is no help to me, i'm committed to the current interface

short summary:
- need the current interface very badly to be backwards compat, if I (and Lazarus) are ever migrating to a FCL one. Changes to the interface not really an option, then I'd stick to my ancient lazarus version forever.
- I'm talking about the lazarus version atm, afaik that one has been optimized in the past because the FCL version was slow.
- Don't like openkey/closekey much. On the other hand, my XML config loading/saving is not that much performance dependant, so if it remains working without openkey/closekey, and it is not too bad, it is fine. (I must be able to load/store a 10-40kb file in sub 50ms, but that should be doable).

2009/10/23 Sergei Gorelkin :

Hello, I want to remove the avl_tree-related stuff from DOM unit. The reasons are:

I am all for this removal .

(Sorry to disagree, I actually consider the issue major : by _default_, using different instances in different threads, each instance _exclusively_ used in one thread, is _not_ safe.)

Marco van de Voort wrote

short summary: - need the current interface very badly to be backwards compat, if I (and Lazarus) are ever migrating to a FCL one. Changes to the interface not really an option, then I'd stick to my ancient lazarus version forever.

The xmlconf has the same interface as xmlcfg, except string parameter types are WideString not AnsiString (this is handled transparently by the compiler), and OpenKey/CloseKey/ResetKey are added. So using xmlconf won't require any changes.

The Lazarus version of TXMLConfig, however, is not a TComponent descendant and has a different constructor, therefore replacing it with FCL version would require heavy patching - but that's a different and unrelated issue.

- I'm talking about the lazarus version atm, afaik that one has been optimized in the past because the FCL version was slow.

It's no longer that slow. I had put much effort in getting it as fast as possible. The current timings of reading the same 1 MByte XML file are (on a Core2Duo E7200, Windows - with non-refcounted WideStrings):

laz_xmlread: 60 ms,
xmlread + avl_tree: 80 ms,
xmlread w/o avl_tree: 40 ms, note that 2 times difference!.

Comparing the XMLConfig performance is a bit harder, because it depends on the structure of the configuration data - but at least the parsing time is always a part of loading the config data.

Since the numbers above are for 1 MByte file, it indeed should be doable.

Ok then, I think I should document this change at the User Changes Trunk wiki page and go ahead.

Regards,
Sergei

In our previous episode, Sergei Gorelkin said:

That is not a problem. The problem is that the getvalue/set behaviour must remain the same, and I must be able to select the encoding (or it should use the system default encoding). Those are the things I have many times. opening/closing only happens a handful times and is easily fixed.

You mean that you're using non-ascii characters a lot, and rely on the 'escaping' feature present in xmlcfg?

Sergei

Sergei Gorelkin wrote

I want to remove the avl_tree-related stuff from DOM unit. The reasons are:

If that's a CfV, I vote "yes".

Vinzent.