Which XQuery engine did you use to get these numbers, and can you publish the benchmark to allow it to be run from other XQuery engines?
It's worth remembering that people optimize XQuery engines to handle the most common usage scenarios, and the most common usage scenario for XQuery is to process XML. It may simply be that you are doing things that the vendor in question hasn't thought about much, because they consider other things more important. Michael Kay Saxonica On 5 Dec 2013, at 10:02, jean-marc Mercier <[email protected]> wrote: > Hello. > > To end this thread, I would like to give the results of two different XQUERY > implementations of a Red / Black tree for integer insertion. > > The first conclusion of this work seems that none of these implementations > are actually usable, due to poor performances. The best way to build a map, > or a stack, that can handle nodes or functions as keys, should be to > encapsulate the existing map modules provided by interpreters with a small > xquery code. Indeed, the map module I used is more than 1000 time faster for > inserting pairs of integers. > > A remark : I don't think possible to write a more efficient implementation > for Red Black tree insertion than John Snelson one. Mine is about 5 time > slower, because I introduced a lot of overload to be able to remove nodes, > and of course because I am not as XQUERY experimented as John. > > Another conclusion might be that it does not seem possible to write > extensively computing algorithms with XQUERY. Indeed, I was wondering why > these codes are showing so poor performances. Might it be due to the > interpreter optimization query process ? > > Left column (nb) is the number of insertion. removable.xq is the tree that I > implemented, rbtree is the original John Snelson one. > > > nb removable.xq rbtree.xq > 2 5.33 ms 0.75 ms > 4 10.12 ms 1.42 ms > 8 29.59 ms 4.11 ms > 16 60.74 ms 7.6 ms > 32 48.97 ms 6.18 ms > 64 51.5 ms 4.98 ms > 128 48.98 ms 10.49 ms > 256 92.06 ms 18.73 ms > 512 184.55 ms 35.92 ms > 1024 325.48 ms 69.97 ms > 2048 661.12 ms 136.05 ms > 4096 1315.19 ms 266.68 ms > 8192 2793.02 ms 573.12 ms > 16384 6053.26 ms 1265.82 ms > 32768 12938.48 ms 2620.19 ms > 65536 27746.55 ms 5655.38 ms > 131072 59775.33 ms 12058.8 ms > > > > 2013/12/3 jean-marc Mercier <[email protected]> > David, thanks, I feel less miserable :) > > The point is that I want a map (maps are standard in XQUERY) but that can > handle nodes or functions as keys, provided an external ordering function is > given. I also want a stack having the same properties. Such containers does > not exists, thus I decided to write them in pure xquery. My motivation was to > exercise myself, as well as testing whether xquery could fit my algorithmic > needs. I did it, starting with John Snelson work, that kindly point me out > its work over this topic. > > I thought that my code and John Snelson one had not the desired complexity > while profiling my code. I was just wrong. All this conversation took place > because I made bad measurements :( > > > > > > > 2013/12/3 David Lee <[email protected]> > Jean-marc, I completely understand your frustration with the lack of > "standard" data types like double linked lists, maps, stacks etc. > > I also had the same problem at first. However in general I have found that > looking for these types meant I was trying to solve the problem in a way > > which is not the best way in a functional language, and that there were other > ways of solving the same problem - often more elegantly. > > > > So I suggest you describe to the group, at a higher level, what kinds of > problems you are trying to solve where you feel these data types are > necessary. > > It may be that there are better ways of solving the problem without them. > > Or it may be that these types are really needed and things like johns rb tree > should be suggested as standard or atleast common libraries (such as in > functx). > > > > > > > > ---------------------------------------- > > David A. Lee > > [email protected] > > http://www.xmlsh.org > > > > > > _______________________________________________ > [email protected] > http://x-query.com/mailman/listinfo/talk
_______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
