Comparison hash_set MSFT Google dense_hash_set

[GoogleCodeExporter]

What steps will reproduce the problem?
Hello, i'm trying to use your google dense hash set. My code work with
microsoft one and i changed it to use your. however, the time of execution
is 10 times slower. So i'm probably doing something wrong.

Here are my class :
For MSFT :
class myCompareFace : public stdext :: hash_compare<XFace>
{
public:
    size_t operator() (const XFace* key) const
    {
        return (size_t) key->getId();
    }
    bool operator() (const XFace* n1, const XFace* n2) const
    {
        static int v1[3],v2[3];

        int i;
        for(i=0;i<3;i++)
        {
            v1[i]=n1->getVertex(i)->getNum();
            v2[i]=n2->getVertex(i)->getNum();
        }

        std::sort(v1,v1+3);
        std::sort(v2,v2+3);
        for(i=0 ; i<3 ;i++)
        {::TTest++;
            if(v1[i] != v2[i])return true;
        }
        return false;

    }
};
FOR Google Dense_hash_set
struct MyClassHash 
{
    size_t operator()(const XFace* p) const 
    {
        return (size_t) p->getId();
    }
};

struct MyClassEqual {
    bool operator()(const XFace* n1, const XFace* n2) const 
    {
        static int v1[3],v2[3];

        int i;
        for(i=0;i<3;i++)
        {
            v1[i]=n1->getVertex(i)->getNum();
            v2[i]=n2->getVertex(i)->getNum();
        }

        std::sort(v1,v1+3);
        std::sort(v2,v2+3);
        for(i=0 ; i<3 ;i++)
        {
            ::TTest++;
            if(v1[i] != v2[i])return false;
        }
        return true;
    }
};

My Class XFace is a Triangular face with 3 vertex. The hash function is the
same for the two implementation. And the ==  or < for msf are the same.

The only differnce in the implementation are :
For google
google::dense_hash_set<XFace *,MyClassHash,MyClassEqual> myFaceHash; 
For MSFT:
stdext::hash_set<XFace *,myCompareFace> myFaceHash;

and then for google one ,I add a face that do not exist :
    XFace *a=new XFace(v,v,v,0);
    myFaceHash.set_empty_key(a);

And i get for exectution time:
MSFT 
FACES : 13711 EDGES : 1Vertex 1419 Nb Test : 630629
Topology built in 0.094seconds
GOOGLE :
FACES : 13711 EDGES : 1Vertex 1419 Nb Test : 9595492
Topology built in 1.203seconds

As you see the time is really bigger and moreover, i have 9595492 call to 
MyClassEqual and 630629 operator() with MSFT 

Am I doing something wrong with the set_empty_key?

Original issue reported on code.google.com by ory...@gmail.com on 27 Feb 2009 at 10:08

[GoogleCodeExporter]

Interesting.  dense_hash_set does a lot of comparisons against the empty-key, 
so if
those comparisons are slow, dense_hash_set will also be slow.  Since your set 
uses a
pointer for the key, it would be great if you could do set_empty_key(NULL), and 
then
have your comparison function do something really fast when one of the args is 
NULL.
 That should get performance back.

I'm closing this as a bug report.  If you'd like to discuss further, feel free 
to
mail to google-sparsehash@googlegroups.com

Original comment by csilv...@gmail.com on 27 Feb 2009 at 10:33

• Changed state: Invalid
• Added labels: Type-Defect, Priority-Medium