Hello. I just profiled your set collection at https://github.com/LeoWoerteler/xq-modules/
Results of the profile functions are attached below. The conclusion is that the overhead to pay by using your map, instead of "overloading" a vendor map solution based, as BaseX one, seems to be too heavy, at least for my purposes (the overhead to pay is around a factor 100). Please check these conclusions, but it seems that they are exactly the same than the map designed by John Snelson, and mine too (see the "map module for xquery?" thread at talk@x-query.com ). Note however that the performances of your tree are far better than John Snelson and mine, but still it is not enough.
- To reproduce the test : launch MapProfiler.xquery. This xquery files links to your map "ordered-map.xqm", also to the ones that I designed on top of BaseX map ("idmap.xqm","set.xqm"), as well as the standard BaseX map.
- The test consists simply in populating sets and maps of integers and nodes. Each test consists in inserting #nb=(2^i, i=10,..,20) of these objects and measuring time to build the map.
- Note : I added two functions to your ordered map module :ordered-map:insert-pair, ordered-map:insert-pairs, to have an handy Constructor from pairs. I have checked that these Ctors are not responsible for the overhead, but check it again.
Well, I am afraid that there might no be any XMas miracle: your tree seems to suffer from the very same problem than John Snelson and mine. I have no idea why we are facing these performance issues. Might it be due to XQUERY interpreter overhead, due to the query optimizer ?
The only thing that is sure is that as long as this problem will hold, nobody will be able to contribute seriously to XQUERY via external XQUERY modules using heavy algorithmic. And this is too bad, because XQUERY could be a really efficient language to that purposes.
If I misunderstood something, do not hesitate to comment.
Cheers,
Jean-Marc