remember strategies least recently used and least frequently used,
authorAlexander Frink <Alexander.Frink@uni-mainz.de>
Tue, 22 Feb 2000 19:53:27 +0000 (19:53 +0000)
committerAlexander Frink <Alexander.Frink@uni-mainz.de>
Tue, 22 Feb 2000 19:53:27 +0000 (19:53 +0000)
code moved to remember.h/cpp

ginac/Makefile.am
ginac/Makefile.in
ginac/function.pl
ginac/remember.cpp [new file with mode: 0644]
ginac/remember.h [new file with mode: 0644]

index e0cf87d53caec59e8d3575d2fb430882197c985b..0c67fd2de5d4d7a5a658d72d0381199696060f05 100644 (file)
@@ -8,7 +8,7 @@ libginac_la_SOURCES = add.cpp archive.cpp basic.cpp constant.cpp ex.cpp \
   symbol.cpp pseries.cpp utils.cpp ncmul.cpp clifford.cpp structure.cpp \
   color.cpp indexed.cpp idx.cpp isospin.cpp exprseq_suppl.cpp lst.cpp \
   lst_suppl.cpp simp_lor.cpp coloridx.cpp lorentzidx.cpp lortensor.cpp \
-  debugmsg.h utils.h 
+  remember.h remember.cpp debugmsg.h utils.h 
 libginac_la_LDFLAGS = -version-info $(LT_CURRENT):$(LT_REVISION):$(LT_AGE) \
   -release $(LT_RELEASE)
 ginacincludedir = $(includedir)/ginac
index a5be0fede6fd9c8ad80d16474dab6865aa2d5716..04081088d39d26e2f8d3e3b9a54acaaf7342d2b2 100644 (file)
@@ -103,7 +103,7 @@ VERSION = @VERSION@
 YACC = @YACC@
 
 lib_LTLIBRARIES = libginac.la
-libginac_la_SOURCES = add.cpp archive.cpp basic.cpp constant.cpp ex.cpp   expairseq.cpp exprseq.cpp fail.cpp function.cpp inifcns.cpp   inifcns_trans.cpp inifcns_zeta.cpp inifcns_gamma.cpp matrix.cpp mul.cpp   normal.cpp numeric.cpp operators.cpp power.cpp registrar.cpp relational.cpp   symbol.cpp pseries.cpp utils.cpp ncmul.cpp clifford.cpp structure.cpp   color.cpp indexed.cpp idx.cpp isospin.cpp exprseq_suppl.cpp lst.cpp   lst_suppl.cpp simp_lor.cpp coloridx.cpp lorentzidx.cpp lortensor.cpp   debugmsg.h utils.h 
+libginac_la_SOURCES = add.cpp archive.cpp basic.cpp constant.cpp ex.cpp   expairseq.cpp exprseq.cpp fail.cpp function.cpp inifcns.cpp   inifcns_trans.cpp inifcns_zeta.cpp inifcns_gamma.cpp matrix.cpp mul.cpp   normal.cpp numeric.cpp operators.cpp power.cpp registrar.cpp relational.cpp   symbol.cpp pseries.cpp utils.cpp ncmul.cpp clifford.cpp structure.cpp   color.cpp indexed.cpp idx.cpp isospin.cpp exprseq_suppl.cpp lst.cpp   lst_suppl.cpp simp_lor.cpp coloridx.cpp lorentzidx.cpp lortensor.cpp   remember.h remember.cpp debugmsg.h utils.h 
 
 libginac_la_LDFLAGS = -version-info $(LT_CURRENT):$(LT_REVISION):$(LT_AGE)   -release $(LT_RELEASE)
 
@@ -128,7 +128,7 @@ inifcns_zeta.lo inifcns_gamma.lo matrix.lo mul.lo normal.lo numeric.lo \
 operators.lo power.lo registrar.lo relational.lo symbol.lo pseries.lo \
 utils.lo ncmul.lo clifford.lo structure.lo color.lo indexed.lo idx.lo \
 isospin.lo exprseq_suppl.lo lst.lo lst_suppl.lo simp_lor.lo coloridx.lo \
-lorentzidx.lo lortensor.lo
+lorentzidx.lo lortensor.lo remember.lo
 CXXFLAGS = @CXXFLAGS@
 CXXCOMPILE = $(CXX) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS)
 LTCXXCOMPILE = $(LIBTOOL) --mode=compile $(CXX) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS)
@@ -156,8 +156,8 @@ DEP_FILES =  .deps/add.P .deps/archive.P .deps/basic.P .deps/clifford.P \
 .deps/isospin.P .deps/lorentzidx.P .deps/lortensor.P .deps/lst.P \
 .deps/lst_suppl.P .deps/matrix.P .deps/mul.P .deps/ncmul.P \
 .deps/normal.P .deps/numeric.P .deps/operators.P .deps/power.P \
-.deps/pseries.P .deps/registrar.P .deps/relational.P .deps/simp_lor.P \
-.deps/structure.P .deps/symbol.P .deps/utils.P
+.deps/pseries.P .deps/registrar.P .deps/relational.P .deps/remember.P \
+.deps/simp_lor.P .deps/structure.P .deps/symbol.P .deps/utils.P
 SOURCES = $(libginac_la_SOURCES)
 OBJECTS = $(libginac_la_OBJECTS)
 
index a680fc8685562b67630521aadb2dfa702eb2cc12..cb0fe80f1d74b5e012c4b5be9acc2b094b4948e7 100755 (executable)
@@ -572,11 +572,16 @@ $implementation=<<END_OF_IMPLEMENTATION;
 #include "inifcns.h"
 #include "utils.h"
 #include "debugmsg.h"
+#include "remember.h"
 
 #ifndef NO_NAMESPACE_GINAC
 namespace GiNaC {
 #endif // ndef NO_NAMESPACE_GINAC
 
+//////////
+// helper class function_options
+//////////
+
 function_options::function_options()
 {
     initialize();
@@ -668,113 +673,6 @@ void function_options::test_and_set_nparams(unsigned n)
     }
 }
 
-class remember_table_entry {
-public:
-    remember_table_entry(function const & f, ex const & r) :
-        hashvalue(f.gethash()), seq(f.seq), result(r)
-    {
-        last_access=0;
-        successful_hits=0;
-    }
-    bool is_equal(function const & f) const
-    {
-        GINAC_ASSERT(f.seq.size()==seq.size());
-        if (f.gethash()!=hashvalue) return false;
-        for (unsigned i=0; i<seq.size(); ++i) {
-            if (!seq[i].is_equal(f.seq[i])) return false;
-        }
-        last_access=access_counter++;
-        successful_hits++;
-        return true;
-    }
-    unsigned hashvalue;
-    exvector seq;
-    ex result;
-    mutable unsigned long last_access;
-    mutable unsigned successful_hits;
-
-    static unsigned access_counter;
-};    
-
-unsigned remember_table_entry::access_counter=0;
-
-class remember_table_list : public list<remember_table_entry> {
-public:
-    remember_table_list()
-    {
-        max_assoc_size=0;
-        delete_strategy=0;
-    }
-    remember_table_list(unsigned as, unsigned strat)
-    {
-        max_assoc_size=as;
-        delete_strategy=strat;
-    }
-    void add_entry(function const & f, ex const & result)
-    {
-        push_back(remember_table_entry(f,result));
-    }        
-    bool lookup_entry(function const & f, ex & result) const
-    {
-        for (const_iterator cit=begin(); cit!=end(); ++cit) {
-            if (cit->is_equal(f)) {
-                result=cit->result;
-                return true;
-            }
-        }
-        return false;
-    }
-protected:
-    unsigned max_assoc_size;
-    unsigned delete_strategy;
-};
-
-
-class remember_table : public vector<remember_table_list> {
-public:
-    remember_table()
-    {
-    }
-    remember_table(unsigned s, unsigned as, unsigned strat)
-    {
-        calc_size(s);
-        reserve(table_size);
-        for (unsigned i=0; i<table_size; ++i) {
-            push_back(remember_table_list(as,strat));
-        }
-    }
-    bool lookup_entry(function const & f, ex & result) const
-    {
-        unsigned entry=f.gethash() & (table_size-1);
-        if (entry>=size()) {
-            cerr << "entry=" << entry << ",size=" << size() << endl;
-        }
-        GINAC_ASSERT(entry<size());
-        return operator[](entry).lookup_entry(f,result);
-    }
-    void add_entry(function const & f, ex const & result)
-    {
-        unsigned entry=f.gethash() & (table_size-1);
-        GINAC_ASSERT(entry<size());
-        operator[](entry).add_entry(f,result);
-    }        
-    void calc_size(unsigned s)
-    {
-        // use some power of 2 next to s
-        table_size=1 << log2(s);
-    }
-protected:
-    unsigned table_size;
-};      
-
-// this is not declared as a static function in the class function
-// (like registered_function()) because of issues with cint
-static vector<remember_table> & remember_tables(void)
-{
-    static vector<remember_table> * rt=new vector<remember_table>;
-    return *rt;
-}
-
 GINAC_IMPLEMENT_REGISTERED_CLASS(function, exprseq)
 
 //////////
@@ -1161,12 +1059,12 @@ vector<function_options> & function::registered_functions(void)
 
 bool function::lookup_remember_table(ex & result) const
 {
-    return remember_tables()[serial].lookup_entry(*this,result);
+    return remember_table::remember_tables()[serial].lookup_entry(*this,result);
 }
 
 void function::store_remember_table(ex const & result) const
 {
-    remember_tables()[serial].add_entry(*this,result);
+    remember_table::remember_tables()[serial].add_entry(*this,result);
 }
 
 // public
@@ -1188,11 +1086,12 @@ unsigned function::register_new(function_options const & opt)
     }
     registered_functions().push_back(opt);
     if (opt.use_remember) {
-        remember_tables().push_back(remember_table(opt.remember_size,
-                                                   opt.remember_assoc_size,
-                                                   opt.remember_strategy));
+        remember_table::remember_tables().
+            push_back(remember_table(opt.remember_size,
+                                     opt.remember_assoc_size,
+                                     opt.remember_strategy));
     } else {
-        remember_tables().push_back(remember_table());
+        remember_table::remember_tables().push_back(remember_table());
     }
     return registered_functions().size()-1;
 }
diff --git a/ginac/remember.cpp b/ginac/remember.cpp
new file mode 100644 (file)
index 0000000..b3307d3
--- /dev/null
@@ -0,0 +1,194 @@
+/** @file remember.cpp
+ *
+ *  Implementation of helper classes for using the remember option
+ *  in GiNaC functions */
+
+/*
+ *  GiNaC Copyright (C) 1999-2000 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <stdexcept>
+
+#include "function.h"
+#include "utils.h" // for log_2
+#include "remember.h"
+
+#ifndef NO_NAMESPACE_GINAC
+namespace GiNaC {
+#endif // ndef NO_NAMESPACE_GINAC
+
+//////////
+// class remember_table_entry
+//////////
+
+remember_table_entry::remember_table_entry(function const & f, ex const & r) :
+    hashvalue(f.gethash()), seq(f.seq), result(r)
+{
+    last_access=access_counter++;
+    successful_hits=0;
+}
+
+bool remember_table_entry::is_equal(function const & f) const
+{
+    GINAC_ASSERT(f.seq.size()==seq.size());
+    if (f.gethash()!=hashvalue) return false;
+    for (unsigned i=0; i<seq.size(); ++i) {
+        if (!seq[i].is_equal(f.seq[i])) return false;
+    }
+    last_access=access_counter++;
+    successful_hits++;
+    return true;
+}
+
+unsigned long remember_table_entry::access_counter=0;
+
+//////////
+// class remember_table_list
+//////////
+
+remember_table_list::remember_table_list(unsigned as, unsigned strat)
+{
+    max_assoc_size=as;
+    remember_strategy=strat;
+}
+
+
+void remember_table_list::add_entry(function const & f, ex const & result)
+{
+    if ((max_assoc_size!=0)&&
+        (remember_strategy!=remember_strategies::delete_never)&&
+        (size()>=max_assoc_size)) {
+        // table is full, we must delete an older entry
+        GINAC_ASSERT(size()>0); // there must be at least one entry
+        switch (remember_strategy) {
+        case remember_strategies::delete_cyclic:
+            // delete oldest entry (first in list)
+            erase(begin());
+            break;
+        case remember_strategies::delete_lru:
+            {
+                // delete least recently used entry
+                iterator it=begin();
+                iterator lowest_access_it=it;
+                unsigned long lowest_access=it->get_last_access();
+                ++it;
+                while (it!=end()) {
+                    if (it->get_last_access()<lowest_access) {
+                        lowest_access=it->get_last_access();
+                        lowest_access_it=it;
+                    }
+                    ++it;
+                }
+                erase(lowest_access_it);
+            }
+            break;
+        case remember_strategies::delete_lfu:
+            {
+                // delete least frequently used entry
+                iterator it=begin();
+                iterator lowest_hits_it=it;
+                unsigned lowest_hits=it->get_successful_hits();
+                ++it;
+                while (it!=end()) {
+                    if (it->get_successful_hits()<lowest_hits) {
+                        lowest_hits=it->get_successful_hits();
+                        lowest_hits_it=it;
+                    }
+                    ++it;
+                }
+                erase(lowest_hits_it);
+            }
+            break;
+        default:
+            throw(std::logic_error("remember_table_list::add_entry(): invalid remember_strategy"));
+        }
+        GINAC_ASSERT(size()==max_assoc_size-1);
+    }
+    push_back(remember_table_entry(f,result));
+}        
+
+bool remember_table_list::lookup_entry(function const & f, ex & result) const
+{
+    for (const_iterator cit=begin(); cit!=end(); ++cit) {
+        if (cit->is_equal(f)) {
+            result=cit->get_result();
+            return true;
+        }
+    }
+    return false;
+}
+
+//////////
+// class remember_table
+//////////
+
+remember_table::remember_table()
+{
+    table_size=0;
+    max_assoc_size=0;
+    remember_strategy=remember_strategies::delete_never;
+}
+
+remember_table::remember_table(unsigned s, unsigned as, unsigned strat) :
+    max_assoc_size(as), remember_strategy(strat)
+{
+    // we keep max_assoc_size and remember_strategy if we need to clear
+    // all entries
+
+    // use some power of 2 next to s
+    table_size=1 << log2(s);
+    init_table();
+}
+
+bool remember_table::lookup_entry(function const & f, ex & result) const
+{
+    unsigned entry=f.gethash() & (table_size-1);
+    GINAC_ASSERT(entry<size());
+    return operator[](entry).lookup_entry(f,result);
+}
+
+void remember_table::add_entry(function const & f, ex const & result)
+{
+    unsigned entry=f.gethash() & (table_size-1);
+    GINAC_ASSERT(entry<size());
+    operator[](entry).add_entry(f,result);
+}        
+
+void remember_table::clear_all_entries(void)
+{
+    clear();
+    init_table();
+}
+
+void remember_table::init_table(void)
+{
+    reserve(table_size);
+    for (unsigned i=0; i<table_size; ++i) {
+        push_back(remember_table_list(max_assoc_size,remember_strategy));
+    }
+}
+
+vector<remember_table> & remember_table::remember_tables(void)
+{
+    static vector<remember_table> * rt=new vector<remember_table>;
+    return *rt;
+}
+
+#ifndef NO_NAMESPACE_GINAC
+} // namespace GiNaC
+#endif // ndef NO_NAMESPACE_GINAC
diff --git a/ginac/remember.h b/ginac/remember.h
new file mode 100644 (file)
index 0000000..07e8ec9
--- /dev/null
@@ -0,0 +1,99 @@
+/** @file remember.h
+ *
+ *  Interface to helper classes for using the remember option
+ *  in GiNaC functions */
+
+/*
+ *  GiNaC Copyright (C) 1999-2000 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <vector>
+#include <list>
+
+#ifndef NO_NAMESPACE_GINAC
+namespace GiNaC {
+#endif // ndef NO_NAMESPACE_GINAC
+
+class function;
+class ex;
+    
+/** A single entry in the remember table of a function.
+    Needs to be a friend of class function to access 'seq'.
+    'last_access' and 'successful_hits' are updated at each successful
+    'is_equal'. */
+class remember_table_entry {
+public:
+    remember_table_entry(function const & f, ex const & r);
+    bool is_equal(function const & f) const;
+    ex get_result(void) const { return result; }
+    unsigned long get_last_access(void) const { return last_access; }
+    unsigned long get_successful_hits(void) const { return successful_hits; };
+
+protected:
+    unsigned hashvalue;
+    exvector seq;
+    ex result;
+    mutable unsigned long last_access;
+    mutable unsigned successful_hits;
+    static unsigned long access_counter;
+};    
+
+/** A list of entries in the remember table having some least
+    significant bits of the hashvalue in common. */
+class remember_table_list : public list<remember_table_entry> {
+public:
+    remember_table_list(unsigned as, unsigned strat);
+    void add_entry(function const & f, ex const & result);
+    bool lookup_entry(function const & f, ex & result) const;
+protected:
+    unsigned max_assoc_size;
+    unsigned remember_strategy;
+};
+
+/** The remember table is organized like an n-fold associative cache
+    in a microprocessor. The table has a width of 's' (which is rounded
+    to table_size, some power of 2 near 's', internally) and a depth of 'as'
+    (unless you choose that entries are never discarded). The place where
+    an entry is stored depends on the hashvalue of the parameters of the
+    function (this corresponds to the address of byte to be cached).
+    The 'log_2(table_size)' least significant bits of this hashvalue
+    give the slot in which the entry will be stored or looked up.
+    Each slot can take up to 'as' entries. If a slot is full, an older
+    entry is removed by one of the following strategies:
+    - oldest entry (the first one in the list)
+    - least recently used (the one with the lowest 'last_access')
+    - least frequently used (the one with the lowest 'successful_hits')
+    or all entries are kept which means that the table grows indefinitely. */
+class remember_table : public vector<remember_table_list> {
+public:
+    remember_table();
+    remember_table(unsigned s, unsigned as, unsigned strat);
+    bool lookup_entry(function const & f, ex & result) const;
+    void add_entry(function const & f, ex const & result);
+    void clear_all_entries(void);
+    void show_statistics(ostream & os, unsigned level) const;
+    static vector<remember_table> & remember_tables(void);
+protected:
+    void init_table(void);
+    unsigned table_size;
+    unsigned max_assoc_size;
+    unsigned remember_strategy;
+};      
+
+#ifndef NO_NAMESPACE_GINAC
+} // namespace GiNaC
+#endif // ndef NO_NAMESPACE_GINAC