Generic compare function
in [C++]
|
From: Anders Dalvander on 15 Jan 2010 10:01 On Jan 14, 8:07 pm, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote: > Given the relatively low expenditure of intellectual energy required > to discover that (-, 0, +) is far more efficient than operator <, one > has to wonder for what reason was operator < chosen in the first > place. I would guess the rationale is rather simple: "less" is a much simpler concept than "compare". Even so, I would believe that using "compare" instead of "less" would be marginally better, and possible a premature optimization. For instance, imagine the difference in performance of std::map::find, if it would utilize "compare" instead of "less". Sure, if it would contain few elements the performance improvements would be relatively large, if it would contain many elements the relative performance improvements would be marginally. Using another data structure would probably be better anyway. Regards, Anders Dalvander -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Le Chaud Lapin on 16 Jan 2010 02:26 On Jan 15, 9:01 pm, Anders Dalvander <goo...(a)dalvander.com> wrote: > On Jan 14, 8:07 pm, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote: > > > Given the relatively low expenditure of intellectual energy required > > to discover that (-, 0, +) is far more efficient than operator <, one > > has to wonder for what reason was operator < chosen in the first > > place. > > I would guess the rationale is rather simple: "less" is a much simpler > concept than "compare". I do not see how "less" can be simpler than, say, strcmp(), an old from that obviously uses the "compare" method: int strcmp ( const char * str1, const char * str2 ); The actual code for strcmp() using "compare" is hardly more complex than would be that for "less". Onen simply returns the difference: int (str1[i]) - int(str2[i]). > Even so, I would believe that using "compare" instead of "less" would > be marginally better, and possible a premature optimization. On the contratry, "compare" can be nearly twice as fast as "less" in extreme cases. Imagine that the programmer has a set<> of 1,000,000 Foo's: set<Foo>; // 1,000,000 elements If the test of relative order of two Foo's is inherently long, such that its excution time dominates the execution time of the other operations, say, in in AVL/Red-Black implementations (mainly rotations), then the "compare" method will be 1.9x, 1.95x, 1.98x, etc. as fast as as the "less" method. What is notable is that, once the library designer has prescribed the "less" method, there is nothing that the library user could do to change this difference in performance. Not optimization of "less" will mitigate this inherent disparity. > For instance, imagine the difference in performance of std::map::find, > if it would utilize "compare" instead of "less". Sure, if it would > contain few elements the performance improvements would be relatively > large, if it would contain many elements the relative performance > improvements would be marginally. Using another data structure would > probably be better anyway. Well, I think it is the opposite. The more elements there are, the more one should prefer "compare", especially if the ordering test is inherently computationally expensive. -Le Chaud Lapin- -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Chris Morley on 16 Jan 2010 20:20 "Le Chaud Lapin" <jaibuduvin(a)gmail.com> wrote in message news:30ea50bf-18e2-4f45-a5d4- > On the contratry, "compare" can be nearly twice as fast as "less" in > extreme cases. Imagine that the programmer has a set<> of 1,000,000 > Foo's: This is a bold statement without supplying any argument as why. Why should it be twice the speed? Using < for tree operations doesn't require double the comparisons. Others have discussed relative speed of < vs compare so I won't so let's simply assume they are identical. > set<Foo>; // 1,000,000 elements > > If the test of relative order of two Foo's is inherently long, such > that its excution time dominates the execution time of the other > operations, say, in in AVL/Red-Black implementations (mainly > rotations), then the "compare" method will be 1.9x, 1.95x, 1.98x, etc. > as fast as as the "less" method. As someone who has actually implemented their own RB tree code (using indexes rather than pointers) I know that the number of comparisons (& branches) dominate performance (regardless of pred function complexity). Walking the tree and performing rotations are fast operations & you don't need many. With <, lower bound is trivial and requires one comparison per node till you hit the bottom of the tree. Checking each node for equality as well (did my return value == 0?) will double the branch statements per node traversed likely causing any node past 1/2 way down the tree to be slower (which is most of the nodes, it being a tree 'n all). Find is trivially written in terms of lower bound with one extra compare. iterator Find(const_reference Key, predT Pred) { iterator wherenode( LowerBound(Key,Pred) ); return (wherenode == end() || Pred( Key, *wherenode) ? end() : wherenode); } If you have a tree with the guarentee of no duplication of keys then you could optimise find to stop when it matches with compare but even then on average you don't have half the comparison operations. Most of the nodes are far from the head/root remember, it is a binary tree. Without this guarentee, you need to descend the entire tree anyway to look for duplicates so they are the same. Take a look at the STL library code to see how you actually do operations using < only. Tree source with gcc is hideously unreadable but the VS2008 xtree.h? (of the top of my head) is pretty clear. > Well, I think it is the opposite. The more elements there are, the > more one should prefer "compare", especially if the ordering test is > inherently computationally expensive. Don't forget that if you double the elements in a _balanced_ binary tree then you only increase the path height by 1 node. As most of the nodes are near the bottom of the tree by definition, even with hundreds of millions/billions of entries in the restricted no duplicates tree you save a few comparisons on average out of ~30. Do the arithmetic. If the key comparison is cheap however then you lose with compare vs < because the increased branches in your "optimised" find method. If you can make/demonstrate an STL replacement library with compare which performs 2x faster than implementations shipped with VS & GCC etc. then I'm sure many readers of this group would be very interested. Chris -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Adam Badura on 17 Jan 2010 02:11 > Perhaps this http://www.stepanovpapers.com/notes.pdf will provide an > explanation. This is over 200 pages. Are you expecting us to read it all and then reply whether it provided any explanation or not? Because this does not seem reasonable... I quickly browsed through parts about comparing but found nothing about this topic. And I do not have (sadly) that much time to read it all (now). Adam Badura -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Anders Dalvander on 17 Jan 2010 02:11
On Jan 16, 8:26 pm, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote: > > I would guess the rationale is rather simple: "less" is a much simpler > > concept than "compare". > > I do not see how "less" can be simpler than, say, strcmp(), an old > from that obviously uses the "compare" method: I'm not referring to the code, I'm referring to the model and concept. "less" models Strict Weak Ordering, a well known concept in programming as well as in other areas, see for instance http://en.wikipedia.org/wiki/Strict_weak_ordering or http://www.sgi.com/tech/stl/StrictWeakOrdering.html for description. SWO has four well defined properties: irreflexivity, asymmetry, transitivity and transitivity of equivalence. Which properties "compare" would have I don't know, I feel that it would have more complex properties than the ones for "less". This is what I meant with my statement that "less" is a much simpler concept than "compare". > Well, I think it is the opposite. The more elements there are, the > more one should prefer "compare", especially if the ordering test is > inherently computationally expensive. std::map::find is usually built on-top of std::map::lower_bound. To give a correct result std::map::find need one extra call to "less" than std::map::lower_bound. std::map::lower_bound, which only need to utilize "less", wouldn't gain anything from calling "compare" instead of "less", as "less" is the only thing needed and is only called once for every level in the map. Given a map of 1,000,000 elements, that map would have the height of 20. std::map::lower_bound would need to call "less" 20 times, and std::map::find would need to call "less" 21 times. For the same sized compmap, utilizing a "compare" function, compmap::lower_bound would need to call "less" 20 times, and compmap::find would need to call "less" 20 times. The complexity of compmap::find would on the other hand be greater as it cannot fully rely on compmap::lower_bound. std::map::find would call "less" at most 5% more times than compmap::find would call "compare", if the map would contain 1,000,000 elements. Regards, Anders Dalvander -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |