Commits

remusao committed 1ca5223

try to use judy for the hash map. Result are the same with unordered_map

Comments (0)

Files changed (7)

 
 set(CMAKE_CXX_FLAGS_DEBUG "-std=c++11 -pg -g")
 #set(CMAKE_CXX_FLAGS_DEBUG "-std=c++11 -Wall -W -Werror -pedantic -g")
-set(CMAKE_CXX_FLAGS "-std=c++11 -march=native -Ofast -findirect-inlining -funsafe-loop-optimizations -Wall -Wextra -pedantic")
+set(CMAKE_CXX_FLAGS "-std=c++11 -march=native -Ofast -findirect-inlining -funsafe-loop-optimizations -Wall -Wextra -fpermissive -lJudy -pedantic")
 
 #Defines subdirectory
 add_subdirectory(src/)

src/bddLib/bdd.cc

     {
         // init the memory manager
         Caching::g_mm = initMM<BddNode>(poolSize);
-        Caching::__node2id.max_load_factor(0.8);
+        //Caching::__node2id.max_load_factor(0.8);
 
         // true and false nodes are the first nodes
         // allocated with the memory manager. Their

src/bddLib/bdd.hh

             struct BddNode* root_; // Root of this BDD
     };
 
-    void initBdd(std::size_t nbVars, std::size_t poolSize = 134217728) noexcept;
+    void initBdd(std::size_t nbVars, std::size_t poolSize = 268435456) noexcept;
     void releaseBdd() noexcept;
 
     inline Bdd bdd_ithvar(std::size_t variable) noexcept

src/bddLib/bddNode.hh

     struct BddNode
     {
         // Attributes
-        unsigned var : 10;
-        std::size_t false_ptr : 27;
-        std::size_t true_ptr : 27;
+        unsigned var : 8;
+        std::size_t false_ptr : 28;
+        std::size_t true_ptr : 28;
     } __attribute__ ((packed));
 
 

src/bddLib/bddUtils.cc

 #include <queue>
+#include <Judy.h>
 #include "bddUtils.hh"
 #include "bdd.hh"
 #include "memoryManager.hh"
             };
             node = {id, getOffset(Caching::g_mm, false_ptr), getOffset(Caching::g_mm, true_ptr)};
 
+            BddNode** PValue;
 
             // Check if the newly created node isn't in the cache already
-            auto it = Caching::__node2id.find(hash);
+            JLG(PValue, Caching::__node2id[hash % HASHSIZE], hash);
+            // auto it = Caching::__node2id.find(hash);
 
-            if (it == Caching::__node2id.end())
+            if (!PValue)
             {
                 // Create a new node and add it to the hash table
-                BddNode* newNode = createNode(node);
-                Caching::__node2id[hash] = newNode;
-                res = newNode;
+                JLI(PValue, Caching::__node2id[hash % HASHSIZE], hash); 
+                res = createNode(node);
+                *PValue = res;
             }
             else
-                res = it->second;
+                res = (BddNode*)(*PValue);
         }
         else
             res = false_ptr;
     {
         BddNode*
         app(
-            std::unordered_map<std::size_t, BddNode*>& cache,
+            //std::unordered_map<std::size_t, BddNode*>& cache,
+            Pvoid_t cache[],
             const std::function<BddNode* (const BddNode*, const BddNode*)>& op,
             const BddNode* n1,
             const BddNode* n2) noexcept
                 std::size_t hash =
                      ((std::size_t)(getOffset(Caching::g_mm, n1)) << 32)
                     | (std::size_t)(getOffset(Caching::g_mm, n2));
-                auto it = cache.find(hash);
+                BddNode** PValue;
+                //auto it = cache.find(hash);
+                JLG(PValue, cache[hash % HASHSIZE], hash);
 
-                if (it != cache.end())
-                    res = it->second;
+                if (PValue)
+                    res = *PValue;
                 else if (getVarNode(n1) == getVarNode(n2))
                 {
                     res = makeNode(getVarNode(n1),
                             app(cache, op, getFalseNode(n1), getFalseNode(n2)),
                             app(cache, op, getTrueNode(n1), getTrueNode(n2)));
-                    cache[hash] = res;
+                    JLI(PValue, cache[hash % HASHSIZE], hash); 
+                    *PValue = res;
+                    //cache[hash] = res;
                 }
                 else if (getVarNode(n1) < getVarNode(n2))
                 {
                     res = makeNode(getVarNode(n1),
                             app(cache, op, getFalseNode(n1), n2),
                             app(cache, op, getTrueNode(n1), n2));
-                    cache[hash] = res;
+                    JLI(PValue, cache[hash % HASHSIZE], hash); 
+                    *PValue = res;
+                    //cache[hash] = res;
                 }
                 else
                 {
                     res = makeNode(getVarNode(n2),
                             app(cache, op, n1, getFalseNode(n2)),
                             app(cache, op, n1, getTrueNode(n2)));
-                    cache[hash] = res;
+                    JLI(PValue, cache[hash % HASHSIZE], hash); 
+                    *PValue = res;
+                    //cache[hash] = res;
                 }
             }
 
         const Bdd& bdd1,
         const Bdd& bdd2) noexcept
     {
-        std::unordered_map<std::size_t, BddNode*> cache;
+        //std::unordered_map<std::size_t, BddNode*> cache;
+        Pvoid_t cache[HASHSIZE] = { NULL };
         return Bdd(app(cache, op, bdd1.getRoot(), bdd2.getRoot()));
     }
 

src/bddLib/caching.cc

 namespace Bdd
 {
 //    std::unordered_map<std::size_t, struct BddNode*> Caching::__node2id;
-    UniqueHashMap Caching::__node2id(200000);
+//    UniqueHashMap Caching::__node2id(200000);
+    Pvoid_t Caching::__node2id[HASHSIZE] = { NULL };
     std::vector<std::size_t> Caching::__variables;
     struct BddNode* Caching::trueNode{nullptr};
     struct BddNode* Caching::falseNode{nullptr};

src/bddLib/caching.hh

 
 # include <unordered_map>
 # include <vector>
+# include <Judy.h>
 # include "memoryManager.hh"
 
+# define HASHSIZE (1 << 1)
 
 namespace Bdd
 {
     // Forward declaration
     struct BddNode;
 
-    typedef std::unordered_map<std::size_t, BddNode*> UniqueHashMap;
+    //typedef std::unordered_map<std::size_t, BddNode*> UniqueHashMap;
 
     // Global caching structures
     // Hashtable :
     {
         public:
 
-        static UniqueHashMap __node2id; // 2)
+      //  static UniqueHashMap __node2id; // 2)
+        
+        static Pvoid_t __node2id[HASHSIZE]; // Declare static hash table
 
         // Vector used to store the global order on variables
         static std::vector<std::size_t> __variables;