From: Alexander Frink Date: Tue, 22 Feb 2000 19:53:27 +0000 (+0000) Subject: remember strategies least recently used and least frequently used, X-Git-Tag: release_0-5-3~7 X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=commitdiff_plain;h=660dc3380d44928709d5ac47d3ad6e98bb7c30c2 remember strategies least recently used and least frequently used, code moved to remember.h/cpp --- diff --git a/ginac/Makefile.am b/ginac/Makefile.am index e0cf87d5..0c67fd2d 100644 --- a/ginac/Makefile.am +++ b/ginac/Makefile.am @@ -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 diff --git a/ginac/Makefile.in b/ginac/Makefile.in index a5be0fed..04081088 100644 --- a/ginac/Makefile.in +++ b/ginac/Makefile.in @@ -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) diff --git a/ginac/function.pl b/ginac/function.pl index a680fc86..cb0fe80f 100755 --- a/ginac/function.pl +++ b/ginac/function.pl @@ -572,11 +572,16 @@ $implementation=< { -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 { -public: - remember_table() - { - } - remember_table(unsigned s, unsigned as, unsigned strat) - { - calc_size(s); - reserve(table_size); - for (unsigned i=0; i=size()) { - cerr << "entry=" << entry << ",size=" << size() << endl; - } - GINAC_ASSERT(entry & remember_tables(void) -{ - static vector * rt=new vector; - return *rt; -} - GINAC_IMPLEMENT_REGISTERED_CLASS(function, exprseq) ////////// @@ -1161,12 +1059,12 @@ vector & 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 index 00000000..b3307d3c --- /dev/null +++ b/ginac/remember.cpp @@ -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 + +#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=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()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()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 & remember_table::remember_tables(void) +{ + static vector * rt=new vector; + 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 index 00000000..07e8ec9d --- /dev/null +++ b/ginac/remember.h @@ -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 +#include + +#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 { +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 { +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_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